You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: |
    In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as algorithms, namely $\approx
      \beta^{\frac{n}{2\beta}}\operatorname{covol}({\Lambda})^{\frac{1}{n}}$ for a random lattice ${\Lambda}$ of rank $n$. Compared to the so-called Kannan’s embedding technique, our algorithm allows using precomputations and can be used for efficient batch  instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a *proven* reduction from approximating the closest vector with a factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector Problem () in dimension $\beta$.
address: |
    ${}^\divideontimes$ NTT Corporation, Tokyō, Japan\
    ${}^\star$ Rennes University, Rennes, France 
author:
- 'Thomas Espitau${}^\divideontimes$'
- 'Paul Kirchner${}^\star$'
subtitle: '*Time-approximation tradeoff for approx-CVP*'
title: 'The nearest-colattice algorithm'
---

Introduction {#sec:introduction}
============

Lattices, CVP, SVP {#lattices-cvp-svp .unnumbered}
------------------

In a general setting, a real *lattice* ${\Lambda}$ is a finitely generated free ${\mathbf{Z}}$-module, endowed with a positive-definite quadratic form on its ambient space ${\Lambda}\otimes_{\mathbf{Z}}{\mathbf{R}}$, or equivalently is a discrete subgroup of a Euclidean space.

A fundamental lattice problem is the *Closest Vector Problem*, or  for short. The goal of this problem is to find a lattice point that is closest to a given point in its ambient space. This problem is provably difficult to solve, being actually a -hard problem. It is known to be harder than the *Shortest Vector Problem* () [@goldreich1999approximating], which asks for the shortest non-zero lattice point. is, in turn, the cornerstone of lattice reduction algorithms (see for instance [@Schnorr87; @C:HanPujSte11; @EC:MicWal16]). These algorithms are at the heart of lattice-based cryptography [@regev2009lattices], and are invaluable in plenty of computational problems, including Diophantine approximation, algebraic number theory or optimization (see [@nguyen2010lll] for a survey on the applications of the algorithm).

On CVP-solving algorithms {#on-cvp-solving-algorithms .unnumbered}
-------------------------

There are three families of algorithms solving :

Enumeration algorithms

:   consisting in recursively explore all vectors in a set containing a closest vector. Kannan’s algorithm takes time $n^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(n{\aftergroup\egroup\originalright})}}$ and polynomial space [@kannan1987minkowski]. This estimate was later refined to $n^{\frac{n}{2}+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(n{\aftergroup\egroup\originalright})}}$ by Hanrot and Stehlé [@C:HanSte07].

Voronoi cell computation

:   Micciancio and Voulgaris’ Voronoi cell algorithm solves  in time $(4+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^n$ but uses a space of $(2+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^n$ [@SODA:MicVou10].

Sieving algorithms

:   where vectors are combined in order to get closer and closer to the target vector. Heuristic variants take time as low as $(4/3+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\frac{n}{2}}$ [@SODA:BDGL16], but proven variants of classical sieves [@ajtai2002sampling; @blomer2009sampling; @eisenbrand2011covering] could only solve with approximation factor $1+\epsilon$ at a cost in the exponent. In 2015, a $(2+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^n$ sieve for *exact* was finally proven by Aggarwal, Dadush and Stephen-Davidowitz [@FOCS:AggDadSte15] thanks to the properties of discrete Gaussians.

Many algorithms for solving its relaxed variant, , have been proposed. However, they come with caveats. For example, Dadush, Regev and Stephens-Davidowitz [@dadush2014closest] give algorithms for this problem, but only with exponential time precomputations. Babai [@Babai86 Theorem 3.1] showed that one can reach an $2^{\frac{n}{2}}$-approximation factor for in polynomial time. To the authors’ knowledge, this has never been improved (while keeping the polynomial-time requirement), though the approximation factor for has been significantly reduced [@Schnorr87; @C:HanPujSte11; @EC:MicWal16].

We aim at solving the relaxed version of for relatively large approximation factors, and study the tradeoff between the quality of the approximation of the solution found and the time required to actually find it. In particular, we exhibit a hierarchy of polynomial-time algorithms solving , ranging from Babai’s nearest plane algorithm to an actual  oracle.

Contributions and summary of the techniques {#contributions-and-summary-of-the-techniques .unnumbered}
-------------------------------------------

In \[sec:nearest\_coplane\] we introduce our so-called [[****]{}]{} algorithm. Inspired by Babai’s algorithm, it shows that in practice, we can achieve the performance of Kannan’s embedding but with a basis which is *independent* of the target vector. Denote by $T(\beta)$ (resp. $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)$) the time required to solve $\sqrt{\beta}$-Hermite- (resp. exactly solve ) in rank $\beta$). Quantitatively, we show that:

Let $\beta>0$ be a positive integer and $B$ be a basis of a lattice ${\Lambda}$ of rank $n>2\beta$. After precomputations using a time bounded by $T(\beta)(n+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}$, given a target $t\in{\Lambda}_{\mathbf{R}}$ and under a heuristic on the covering radius of random lattice, the algorithm [[****]{}]{} finds a vector $x\in {\Lambda}$ such that $$\|x-t\| \leq \Theta(\beta)^{\frac{n}{2\beta}}\operatorname{covol}({\Lambda})^{\frac{1}{n}}$$ in time $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)(n+\log \|t\|+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}$.

Furthermore, the structure of the algorithms allow time-memory tradeoff and batch oracle to be used.

We believe that this algorithm has been in the folklore for some time, and it is somehow hinted in `ModFalcon`’s security analysis [@modfalcon Subsection 4.2], but without analysis of the heuristics introduced.

Our second contribution is an algorithm, which gives a time-quality tradeoff similar to the one given by the <span style="font-variant:small-caps;">bkz</span> algorithm [@Schnorr87; @C:HanSte07], or variants of it [@STOC:GamNgu08; @aggarwal2019slide]. Note however that the approximation factor is significantly higher than the corresponding theorems for . Written as a reduction, we prove that, for a $\gamma$- oracle [$\mathcal{O}$]{}:

Let ${\Lambda}$ be a lattice of rank $n$. Then one can solve the $(n^\frac32\gamma^3)$-closest vector problem in ${\Lambda}$, using $2n^2$ calls to the oracle [$\mathcal{O}$]{} during precomputation, and polynomial-time computations.

Babai’s algorithm requires that the Gram-Schmidt norms do not decrease by too much in the reduced basis. While this is true for a reduced basis [@LLL82], we do not know a way to guarantee this in the general case. To overcome this difficulty, the proof technique goes as follows: first we show that it is possible to find a vector within distance $\frac{\sqrt{n}\gamma}{2}\lambda_n({\Lambda})$ of the target vector, with the help of a highly-reduced basis. This is not enough, as the target can be very closed compared to $\lambda_n({\Lambda})$. We treat this peculiar case by finding a short vector in the dual lattice and then directly compute the inner product of the close vectors with our short dual vector. In the other case, Banaszczyk’s transference theorem [@banaszczyk1993new] guarantees that $\lambda_n({\Lambda})$ is comparable to the distance to the lattice, so that we can use our first algorithm directly.

Based on a result due to Kannan (see for instance [@dubey2011approximating]) that $\sqrt{n}\gamma^2$ reduces to $\gamma$-. Combined with the reduction from $\gamma^2$- to $\gamma$- of [@lovasz1986algorithmic], we get a polynomial time reduction from $\sqrt{n}\gamma^4$- to $\gamma$-. Hence, our result is better when $n^{\frac32}\gamma^3$ is smaller than $\sqrt{n} \gamma^4$, i.e., when $n < \gamma$.

Algebraic and computational background {#sec:background}
======================================

In this preliminary section, we recall the notions of geometry of numbers used throughout this paper, the computational problems related to ${\mbox{\textsc{svp}}}$ and ${\mbox{\textsc{cvp}\xspace}}$, and a brief presentation of some lattice reduction algorithms solving these problems.

Notations and conventions {#notations-and-conventions .unnumbered}
-------------------------

### General notations {#general-notations .unnumbered}

The bold capitals ${\mathbf{Z}}$, ${\mathbf{Q}}$ and ${\mathbf{R}}$ refer as usual to the ring of integers and respectively the field of rational and real numbers. Given a real number $x$, the integral roundings *floor*, *ceil* and *round to the nearest integer* are denoted respectively by $\lfloor x\rfloor, \lceil x\rceil, \lfloor x
\rceil$. All logarithms are taken in base $2$, unless explicitly stated otherwise.

### Computational setting {#computational-setting .unnumbered}

The generic complexity model used in this work is the random-access machine (RAM) model and the computational cost is measured in operations.

Euclidean lattices and their geometric invariants {#sec:euclidean_spaces}
-------------------------------------------------

### Lattices {#sec:definitions}

A (real) *lattice* ${\Lambda}$ is a finitely generated free ${\mathbf{Z}}$-module, endowed with a Euclidean norm $\|.\|$ on the real vector space ${\Lambda}_{\mathbf{R}}= {\Lambda}\otimes_{\mathbf{Z}}{\mathbf{R}}$.

We may omit to write down the norm to refer to a lattice ${\Lambda}$ when any ambiguity is removed by the context. By definition of a finitely-generated free module, there exists a finite family $(v_1,
\ldots, v_n) \in {\Lambda}^n$ such that ${\Lambda}= \bigoplus_{i=1}^n v_i {\mathbf{Z}}$, called a *basis* of ${\Lambda}$. Every basis has the same number of elements $\operatorname{rk}({\Lambda})$, called the rank of the lattice.

### Sublattices, quotient lattice {#sec:sublattices_quotients}

Let $({\Lambda}, \|\cdot\|)$ be a lattice, and let ${\Lambda}'$ be a submodule of ${\Lambda}$. Then the restriction of $\|\cdot\|$ to ${\Lambda}'$ endows ${\Lambda}$ with a lattice structure. The pair $({\Lambda}', \|\cdot\|)$ is called a *sublattice* of ${\Lambda}$. In the following of this paper, we restrict ourselves to so-called *pure sublattices*, that is such that the quotient $\faktor{{\Lambda}}{{\Lambda}'}$ is torsion-free. In this case, the quotient can be endowed with a canonical lattice structure by defining: $$\|v+{\Lambda}'\|_{{\Lambda}/{\Lambda}'} = \inf_{v'\in{\Lambda}'_{\mathbf{R}}} \|v-v'\|_{\Lambda}.$$ This lattice is isometric to the projection of ${\Lambda}$ orthogonally to the subspace of ${\Lambda}_{\mathbf{R}}$ spanned by ${\Lambda}'$.

### On effective lifting.

Given a coset $v+{\Lambda}'$ of the quotient $\faktor{{\Lambda}}{{\Lambda}'}$, we might need to find a representative of this class in ${\Lambda}$. While any element could be theoretically taken, from an algorithmic point of view, we shall take an element of norm somewhat small, so that its coefficients remain polynomial in the input representation of the lattice. An effective solution to do so consists in using for instance the *Babai’s rounding* or *Babai’s nearest plane* algorithms. For completeness purpose we recast here the pseudo-code of such a [[****]{}]{} function using the nearest-plane procedure.

Compute the Gram-Schmidt orthogonalization $(v_1^*, \ldots, v_k^*)$ of $B$ $s \gets -t$ $t+s$

### Orthogonality and algebraic duality {#sec:algebraic_nuality}

The *dual* lattice ${{{\Lambda}}^{\vee}}$ of a lattice ${\Lambda}$ is defined as the module $\textrm{Hom}({\Lambda},{\mathbf{Z}})$ of integral linear forms, endowed with the derived norm defined by $$\|\varphi\| = \inf_{v\in{\Lambda}_{\mathbf{R}}\setminus\{0\}}
\frac{|\varphi(v)|}{\|v\|_{\Lambda}}$$ for $\varphi\in{{{\Lambda}}^{\vee}}$. By Riesz’s representation theorem, it is isometric to: $$\{ x\in{\Lambda}_{\mathbf{R}}~|~ {\langle {{x}},{{v}} \rangle}\in{\mathbf{Z}},
\forall v\in{\Lambda}\}$$ endowed with the dual of $\|\cdot\|_{\Lambda}$.

Let ${\Lambda}'\subset{\Lambda}$ be a sublattice. Define its *orthogonal* in ${\Lambda}$ to be the sublattice $${{\Lambda}'_{\bot}} = \{x \in {{{\Lambda}}^{\vee}} : {\langle {{x}},{{{\Lambda}'}} \rangle} = 0\}$$ of ${{{\Lambda}}^{\vee}}$. It is isometric to ${{{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}}{{\Lambda}'}{\aftergroup\egroup\originalright})}^{\vee}}$, and by biduality ${{{{\Lambda}'}^{\vee}}_{\bot}}$ shall be identified with $\faktor{{\Lambda}}{{\Lambda}'}$.

### Filtrations {#sec:filtrations}

A filtration (or flag) of a lattice ${\Lambda}$ is an increasing sequence of submodules of ${\Lambda}$, i.e. each submodule is a proper submodule of the next: $\{0\}={\Lambda}_{0}\subset {\Lambda}_{1}\subset {\Lambda}_{2}\subset \cdots \subset
{\Lambda}_{k}={\Lambda}.$ If we write the $\operatorname{rk}({\Lambda}_i) = d_i$, then we have: $ 0=d_{0}<d_{1}<d_{2}<\cdots <d_{k}=\operatorname{rk}({\Lambda}),$ A filtration is called *complete* if $d_i = i$ for all i.

### Successive minima, covering radius and transference {#sec:minima}

[R]{}[0.3]{}

(0,-1.2) – (0,3.8); (-1.1,0) – (3.8,0); (0,0) – (1,1); (0,0) – (-1,1); (0.6,1) node [$u$]{}; (-0.6,1) node [$v$]{}; (2,2) circle \[radius=1\]; (3,1) circle \[radius=1\]; (1,3) circle \[radius=1\]; (3,3) circle \[radius=1\]; (2,2) circle \[radius=1\]; (3,1) circle \[radius=1\]; (1,3) circle \[radius=1\]; (3,3) circle \[radius=1\]; (3,1) – (4,1); (3.55,1.2) node [$\mu({\Lambda})$]{}; (-1,3) circle \[radius=0.1\]; (1,-1) circle \[radius=0.1\]; (-1,-1) circle \[radius=0.1\]; (-1,1) circle \[radius=0.1\]; (3,-1) circle \[radius=0.1\]; (0,0) circle \[radius=0.1\]; (0,2) circle \[radius=0.1\]; (1,1) circle \[radius=0.1\]; (1,3) circle \[radius=0.1\]; (3,1) circle \[radius=0.1\]; (2,0) circle \[radius=0.1\]; (2,2) circle \[radius=0.1\]; (3,3) circle \[radius=0.1\];

Let ${\Lambda}$ be a lattice of rank $n$. By discreteness in ${\Lambda}_{\mathbf{R}}$, there exists a vector of minimal norm in ${\Lambda}$. This parameter is called the *first minimum* of the lattice and is denoted by $\lambda_1({\Lambda})$. An equivalent way to define this invariant is to see it as the smallest positive real $r$ such that the lattice points inside a ball of radius $r$ span a space of dimension 1. This definition leads to the following generalization, known as successive minima.

Let ${\Lambda}$ be a lattice of rank $n$. For $1\leq i\leq n$, define the $i$-th minimum of ${\Lambda}$ as $$\hspace{-12em}\lambda_i({\Lambda}) = \inf \{r\in{\mathbf{R}}|
  \dim({\mathrm{span}}({\Lambda}\cap B(0, r))) \geq i\}.$$

The covering radius a lattice ${\Lambda}$ or rank $n$ is defined as $$\mu({\Lambda}) = \max_{x\in {\Lambda}_{\mathbf{R}}} {\mathrm{dist}}(x,{\Lambda}).$$

It means that for any vector of the ambient space $x\in {\Lambda}_{\mathbf{R}}$ there exists a lattice point $v \in {\Lambda}$ at distance smaller than $\mu({\Lambda})$.

We now recall Banaszczyk’s transference theorem, relating the extremal minima of a lattice and its dual:

\[thm:transference\] For any lattice $\Lambda$ of dimension $n$, we have $$\hspace{-12em} 1\leq
  2\lambda_1({{\Lambda}^{\vee}})\mu(\Lambda)\leq n,$$ implying, $$\hspace{-12em}1\leq \lambda_1({{\Lambda}^{\vee}})\lambda_n(\Lambda)\leq n.$$

Computational problems in geometry of numbers
---------------------------------------------

### The shortest vector problem {#sec:shortest_vector_problem}

In this section, we introduce formally the  problem and its variants and discuss their computational hardness.

Let $\gamma = \gamma(n) \geq 1$. The $\gamma$-Shortest Vector Problem ($\gamma$-) is defined as follows.

Input

:   A basis $(v_1, \ldots, v_n)$ of a lattice ${\Lambda}$ and a target vector $t \in{\Lambda}_{\mathbf{R}}$.

Output

:   A lattice vector $v\in{\Lambda}\setminus\{0\}$ satisfying $\|v\|\leq \gamma \lambda_1({\Lambda})$.

In the case where $\gamma=1$, the corresponding problem is simply called .

 is -hard under randomized reductions for every constant approximation factor.

A variant of the problem consists of finding vectors within Hermite-like inequalities.

Let $\gamma = \gamma(n) \geq 1$. The $\gamma$-Hermite Shortest Vector Problem ($\gamma$-) is defined as follows.

Input

:   A basis $(v_1, \ldots, v_n)$ of a lattice ${\Lambda}$.

Output

:   A lattice vector $v\in{\Lambda}\setminus\{0\}$ satisfying $\|v\|\leq \gamma \operatorname{covol}({\Lambda})^{\frac1n}$.

There exists a simple polynomial-time dimension-preserving reduction between these two problems, as stated by Lovász in [@lovasz1986algorithmic 1.2.20]:

\[thm:lovasz\_reduction\] One can solve $\gamma^2$- using $2n$ calls to a $\gamma$- oracle and polynomial time.

This can be slightly improved in case the oracle is built from a oracle in lower dimension [@aggarwal2019slide].

### An oracle for $\gamma$-

We note $T(\beta)$ a function such that we can solve ${\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(\sqrt{\beta}{\aftergroup\egroup\originalright})}$- in time at most $T(\beta)$ times the input size. We have the following bounds on $T$, depending on if we are looking at an algorithm which is:

Deterministic

:   $T(\beta)=(4+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\beta/2}$, proven by Micciancio and Voulgaris in[@SODA:MicVou10];

Randomized

:   $T(\beta)=(4/3+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\beta/2}$ , introduced by Wei, Liu and Wang in [@RSA:WeiLiuWan15];

Heuristic

:   $T(\beta) = (3/2+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\beta/2}$ in [@SODA:BDGL16] by Becker, Ducas, Gama, Laarhoven.

There also exists variants for quantum computers [@laarhoven2015finding], and time-memory tradeoffs, such as [@PKC:HerKirLaa18]. By providing a back-and-forth strategy coupled with enumeration in the dual lattice, the *self dual block Korkine-Zolotarev* () algorithm provides an algorithm better than the famous <span style="font-variant:small-caps;">bkz</span> algorithm.

\[thm:BKZ\] There exists an algorithm ouputting a vector $v$ of a lattice ${\Lambda}$ satisfying: $$\|v\| \leq \beta^{\frac{n-1}{2(\beta-1)}} \cdot
  \operatorname{covol}({\Lambda})^{\frac{1}{n}}.$$ Such a bound can be achieved in time $(n+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}T(\beta)$, where $B$ is the integer input basis representing ${\Lambda}$.

The bound we get is a direct consequence of [@EC:MicWal16 Theorem 1]. We only replaced the *Hermite constant* $\gamma_\beta$ by an upper bound in ${\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(\beta{\aftergroup\egroup\originalright})}$.

A stronger variant of this estimate is heuristically true, at least for “random” lattices, as it is suggested by the Gaussian Heuristic in [@EC:MicWal16 Corollary 2]. Under this assumption, one can bound not only the length of the first vector but also the gap between the covolumes of the filtration induced by the outputted basis.

\[thm:HBKZ\] There exists an algorithm ouputting a complete filtration of a lattice ${\Lambda}$ satisfying: $$\operatorname{covol}(\faktor{\Lambda_i}{\Lambda_{i-1}}) \approx
  \Theta(\beta)^{\frac{n+1-2i}{2(\beta-1)}} \operatorname{covol}({\Lambda})^{\frac{1}{n}}$$ Such a bound can be achieved in time $(n+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}T(\beta)$, where $B$ is the integer-valued input basis. Further, we have: $$\Theta(\sqrt{\beta})
    \operatorname{covol}^\frac1\beta{{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{\Lambda_n}{\Lambda_{n-\beta}}{\aftergroup\egroup\originalright})}
\approx \operatorname{covol}{{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{\Lambda_{n-\beta+1}}{\Lambda_{n-\beta}}{\aftergroup\egroup\originalright})}.$$

The closest vector problem {#sec:closest_vector_problem}
--------------------------

In this section we introduce formally the  problem and its variants and discuss their computational hardness.

Let $\gamma = \gamma(n) \geq 1$. The $\gamma$-Closest Vector Problem ($\gamma$-) is defined as follows.

Input

:   A basis $(v_1, \ldots, v_n)$ of a lattice ${\Lambda}$ and a target vector $t \in{\Lambda}\otimes{\mathbf{R}}$.

Output

:   A lattice vector $v\in{\Lambda}$ satisfying $\|x-t\|\leq \gamma \min_{v\in{\Lambda}} \|v-t\|$.

In the case where $\gamma=1$, the corresponding problem is called .

$n^{\frac{c}{\log \log n}}$- is -hard for any $c>0$.

We let $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)$ be such that we can solve in dimension $\beta$ in running time bounded by $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)$ times the size of the input. Hanrot and Stehlé proved $\beta^{\beta/2+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(\beta{\aftergroup\egroup\originalright})}}$ with polynomial memory [@C:HanSte07]. Sieves can provably reach $(2+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\beta}$ with exponential memory [@FOCS:AggDadSte15]. More importantly for this paper, heuristic sieves can reach $(4/3+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})^{\beta/2}$ for solving an entire batch of $2^{0.058\beta}$ instances [@sieve20].

The nearest colattice algorithm {#sec:nearest_coplane}
===============================

We aim at solving the $\gamma-$ by recursively exploiting the datum of a filtration $${\Lambda}_0 \subset {\Lambda}_1 \subset \cdots \subset
{\Lambda}_k = {\Lambda}$$ *via* recursive approximations. The central object used during this reduction is the *nearest colattice* relative to a target vector.

In this section, and the next one, we assume that the size of the bases is always small, essentially as small as the input basis. This is classic, and can be easily proven.

Nearest colattice to a vector
-----------------------------

\[def:nearest\_colattice\] Let $0\rightarrow
  {\Lambda}'\rightarrow{\Lambda}\rightarrow\faktor{{\Lambda}}{{\Lambda}'}\rightarrow 0$ be a short exact sequence of lattices, and set $t\in {\Lambda}_{\mathbf{R}}$ a target vector. A nearest ${\Lambda}'$-colattice to $t$ is a coset $\bar{v} = v+{\Lambda}'\in
  \faktor{{\Lambda}}{{\Lambda}'}$ which is the closest to the projection of $t$ in $\faktor{{\Lambda}_{\mathbf{R}}}{{\Lambda}'_{\mathbf{R}}}$, i.e. such that: $$\bar{v} = \operatorname*{argmin}_{v\in{\Lambda}}
    \|(t-v)+{\Lambda}'\|_{{{\Lambda}_{\mathbf{R}}}/{{\Lambda}'_{\mathbf{R}}}}$$

This definition makes sense thanks to the discreteness of the quotient lattice $\faktor{{\Lambda}}{{\Lambda}'}$ in the real vector space $\faktor{{\Lambda}_{\mathbf{R}}}{{\Lambda}'_{\mathbf{R}}}$.

To illustrate this definition, we give two examples in dimension 3, of rank 1 and 2 nearest colattices. Set ${\Lambda}$ a rank 3 lattice, and fix ${\Lambda}_1$ and ${\Lambda}_2$ two pure sublattices of respective rank 1 and 2. Denote by $\pi_i$ the canonical projection onto the quotient $\faktor{{\Lambda}}{{\Lambda}_i}$, which is of dimension $3-i$ for $i\in\{1,2\}$. The ${\Lambda}_i$-closest colattice to $t$, denoted by $v_i+{\Lambda}_i$ is such that $\pi_i(v_i)$ is a closest vector to $\pi_i(t)$ in the corresponding quotient lattice. Figures (<span style="font-variant:small-caps;">a</span>) and (<span style="font-variant:small-caps;">b</span>) respectively depict these situations.

A computational insight on \[def:nearest\_colattice\] is to view a nearest colattice as a solution to an instance of exact- in the quotient lattice $\faktor{{\Lambda}}{{\Lambda}'}$.

Taking the same notations as in \[def:nearest\_colattice\], let us project $t$ orthogonally onto the affine space $v+{\Lambda}'_{\mathbf{R}}$, and take $w$ a closest vector to this projection. The vector $w$ is then relatively close to $t$. Let us quantify its defect of closeness towards an actual closest vector to $t$:

\[prop:defect\_target\] With the same notations as above: $$\|t-w\|^2 \leq \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}}{{\Lambda}'}{\aftergroup\egroup\originalright})^2 +
  \mu{\mathopen{}\mathclose\bgroup\originalleft}({\Lambda}'{\aftergroup\egroup\originalright})^2$$

Clear by Pythagoras’ theorem.

By definition of the covering radius, we then have:

\[cor:subadditivity\] short exact sequence of lattices. Then we have: $$\mu({\Lambda})^2 \leq \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}}{{\Lambda}'}{\aftergroup\egroup\originalright})^2 +
  \mu{\mathopen{}\mathclose\bgroup\originalleft}({\Lambda}'{\aftergroup\egroup\originalright})^2$$

This inequality is tight, as being an equality when there exists a sublattice ${\Lambda}''$ such that ${\Lambda}'\oplus {\Lambda}'' = {\Lambda}$ and ${\Lambda}'' \subseteq {{\Lambda}'_{\bot}}$.

Recursion along a filtration
----------------------------

Let us now consider a filtration $${\Lambda}_0 \subset {\Lambda}_1 \subset \cdots
  \subset {\Lambda}_k = {\Lambda}$$ and a target vector $t\in{\Lambda}_{\mathbf{R}}$. Repeatedly applying \[cor:subadditivity\] along the subfiltrations $0\subset {\Lambda}_i \subset {\Lambda}_{i+1}$, yields a sequence of inequalities $\mu({\Lambda}_{i+1})^2-\mu{\mathopen{}\mathclose\bgroup\originalleft}({\Lambda}_i{\aftergroup\egroup\originalright})^2 \leq
  \mu{\mathopen{}\mathclose\bgroup\originalleft}({{\Lambda}_{i+1}}/{{\Lambda}_{i}}{\aftergroup\egroup\originalright})^2$. The telescoping sum now gives the relation: $$\mu({\Lambda})^2 \leq \sum_{i=1}^k
    \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})^2.$$ This formula has a very natural algorithmic interpretation as a recursive oracle for approx-:

1.  Starting from the target vector $t$, we solve the instance corresponding to $\pi(t)$ in the quotient $\faktor{{\Lambda}_k}{{\Lambda}_{k-1}}$ with $\pi$ the canonical projection onto this quotient to find $v+{\Lambda}_{k-1}$ the nearest ${\Lambda}_{k-1}$-colattice to $t$.

2.  We then project $t$ orthogonally onto $v+({{\Lambda}_{k-1}}\otimes_{\mathbf{Z}}{\mathbf{R}})$. Call $t'$ this vector.

3.  A recursive call to the algorithm on the instance $(t'-v,
          {\Lambda}_0\subset \cdots \subset {\Lambda}_{k-1}))$ yields a vector $w \in {\Lambda}_2$.

4.  Return $w+v$.

Its translation in pseudo-code is given in an iterative manner in the algorithm [[****]{}]{}.

$s \gets -t$ $t+s$

\[prop:sum\_covering\] Let $B$ be a basis of a lattice ${\Lambda}$ of rank $n$. Given a target $t\in{\Lambda}_{\mathbf{R}}$, the algorithm [[****]{}]{} finds a vector $x\in {\Lambda}$ such that $$\|x-t\|^2 \leq \sum_{i=1}^k \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})^2$$ in time $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)(n+\log \|t\|+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}$, where $\beta$ is the largest gap of rank in the filtration: $\beta = \max_i
  (\operatorname{rk}({\Lambda}_{i+1})-\operatorname{rk}({\Lambda}_{i}))$.

The bound on the quality of the approximation is a direct consequence of the discussion conducted before. The running time bound derives from the definition of $T_{\mathrm{CVP}}$ and on the fact that the [[****]{}]{} operations can be conducted in polynomial time.

\[rem:babai\] In the specific case where the filtration is complete, that is to say that $\operatorname{rk}({\Lambda}_i)=i$ for each $1\leq i \leq n$, the [[****]{}]{} algorithm coincides with the so-called *Babai’s nearest plane* algorithm. In particular, it recovers a vector at distance $$\sqrt{\sum_{i=1}^{n}
  \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright})^2} =\frac12\sqrt{\sum_{i=1}^{n}
  \operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright})^2},$$ by using that for each index $i$, we have $\mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright}) =
    \frac12 \operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright})$ as these quotients are one-dimensional.

The bound given in \[prop:sum\_covering\] is not easily instantiable as it requires to have access to the covering radius of the successive quotients of the filtration. However, under a mild heuristic on random lattices, we now exhibit a bound which only depends on the parameter $\beta$ and the covolume of ${\Lambda}$.

On the covering radius of a random lattice
------------------------------------------

In this section we prove that the covering radius of a random lattice behaves essentially in $\sqrt{\operatorname{rk}(\Lambda)}$.

In 1945, Siegel [@Siegel] proved that the projection of the Haar measure of ${\mathrm{SL}}_n({\mathbf{R}})$ over the quotient ${\mathrm{SL}}_n({\mathbf{R}})/{\mathrm{SL}}_n({\mathbf{Z}})$ is of finite mass, yielding a natural probability distribution $\nu_n$ over the moduli space $\mathcal{L}_n$ of unit-volume lattices. By construction this distribution is translation-invariant, that is, for any measurable set $\mathcal{S} \subseteq \mathcal{L}_n$ and all $U \in {\mathrm{SL}}_n({\mathbf{Z}})$, we have $\nu_n(\mathcal{S}) = \nu_n(\mathcal{S}U)$. A *random lattice* is then defined as a unit-covolume lattice in ${\mathbf{R}}^n$ drawn under the probability distribution $\nu_n$.

We first recall an estimate due to Rogers [@rogers1955mean], giving the expectation[^1] of the number of lattice points in a fixed set.

\[thm:rogers\] Let $n\leq 4$ be an integer and $\rho$ be the characteristic function of a Borel set $C$ of ${\mathbf{R}}^n$ whose volume is $V$, centered at 0. Then: $$\begin{aligned}
      0  \le  \int_{\mathcal{L}_n} \rho({\Lambda}\setminus \{0\})  d\nu_n({\Lambda})
      &-
      2
      e^{-V/2} \sum_{r=0}^{\infty} \frac{r}{r!} (V/2)^r \\
      &
      \le {\mathopen{}\mathclose\bgroup\originalleft}(V+1{\aftergroup\egroup\originalright})
      {\mathopen{}\mathclose\bgroup\originalleft}(
        6 {\mathopen{}\mathclose\bgroup\originalleft}(\sqrt{\frac{3}{4}}{\aftergroup\egroup\originalright})^n + 105\cdot 2^{-n}
      {\aftergroup\egroup\originalright}).
    \end{aligned}$$

This allows to prove that the first minimum of a random lattice is greater than a multiple of $\sqrt{n}$.

\[lem:estimate\_lambda1\] Let $\Lambda$ be a random lattice of rank $n$. Then, with probability $1-2^{-\Omega(n)}$, $\lambda_1(\Lambda)>c\sqrt{n}$ for a universal constant $c>0$.

Consider the ball $C$ of volume $0.99^n$. It has a radius lower bounded by $c\sqrt{n}$. By \[thm:rogers\], the expectation of the number of lattice points in $C$ is at most $$128{\mathopen{}\mathclose\bgroup\originalleft}(\frac34{\aftergroup\egroup\originalright})^{\frac{n}{2}}(V+1)+ V \in (1+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})V.$$ This estimate thus bounds the probability that there exists a non-zero lattice vector in $C$ by $1-2^{-\Omega(n)}$, using Markov’s inequality.

Using the transference theorem, we then derive the following estimate on the covering radius of a random lattice:

Let $\Lambda$ be a random lattice of rank $n$. Then, with probability $1-2^{-\Omega(n)}$, $\mu(\Lambda)<d\sqrt{n}$ for a universal constant $d$.

First remark that the dual lattice ${{\Lambda}^{\vee}}$ follows the same distribution. Hence, using the estimate of \[lem:estimate\_lambda1\], we know that with probability $1-2^{-\Omega(n)}$, $\lambda_1({{\Lambda}^{\vee}})>c\sqrt{n}$. Banaszczyk’s transference theorem indicates that in this case, $$\mu(\Lambda)\leq
  \frac{n}{\lambda_1({{\Lambda}^{\vee}})} \leq \frac{\sqrt{n}}{c},$$ concluding the proof.

This justifies the following heuristic:

\[heur:lambda1\_heur\] In algorithm [[****]{}]{}, for any index $i$, we have $\mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})\leq c
  \lambda_1{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})$ for some universal constant $c$.

The Gaussian heuristic suggests that “almost all” targets $t$ are at distance $(1+{\mathrm{o}{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})})\lambda_1(\Lambda)$, so that for practical purpose in the analysis we can take $c=1$ in \[heur:lambda1\_heur\].

Quality of the algorithm on random lattices
-------------------------------------------

\[thm:quality\_complexity\_average\] Let $\beta>0$ be a positive integer and $B$ be a basis of a lattice ${\Lambda}$ of rank $n>2\beta$. After precomputations using a time bounded by $T(\beta)(n+\log \|B\|)^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(1{\aftergroup\egroup\originalright})}}$, given a target $t\in{\Lambda}_{\mathbf{R}}$ and under \[heur:lambda1\_heur\], the algorithm [[****]{}]{} finds a vector $x\in {\Lambda}$ such that $$\|x-t\| \leq
  \Theta(\beta)^{\frac{n}{2\beta}}\operatorname{covol}({\Lambda})^{\frac{1}{n}}$$ in time $T_{{\mbox{\textsc{cvp}\xspace}}}(\beta)\textrm{Poly}(n,\log \|t\|,\log \|B\|)$.

We start by reducing the basis $B$ of ${\Lambda}$ using the algorithm, and collect the vectors in blocks of size $\beta$, giving a filtration: $$\{0\} = {\Lambda}_0 \subset {\Lambda}_1 \subset \cdots \subset {\Lambda}_k = {\Lambda},$$ for $k = {\mathopen{}\mathclose\bgroup\originalleft}\lceil\frac{n}{\beta}{\aftergroup\egroup\originalright}\rceil$ and $\operatorname{rk}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright}) = \beta$ for each index $i$ except the penultimate one, of rank $n-\beta{\mathopen{}\mathclose\bgroup\originalleft}\lfloor\frac{n}{\beta}{\aftergroup\egroup\originalright}\rfloor$. We define $l_i$ as $\operatorname{rk}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})$. By \[thm:HBKZ\] and finite induction in each block using the multiplicativity of the covolume over short exact sequences, we have for $i<k-1$ $$\begin{aligned}
      \operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright})^{\frac{1}{l_i}}& \approx
\operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}({\Lambda}{\aftergroup\egroup\originalright})^\frac1n
      {\mathopen{}\mathclose\bgroup\originalleft}(\prod_{j=i\beta}^{i\beta+l_i-1}
      \Theta(\beta)^{\frac{n+1-2j}{2(\beta-1)}}{\aftergroup\egroup\originalright})^{\frac{1}{l_i}}
       \\
                                                    &=
                                                    \Theta(\beta)^{\frac{
                                                        n + 2 - 2i\beta-l_i
                                                    }{2(\beta-1)}}
                                                    \operatorname{covol}({\Lambda})^\frac{1}{n}.
    \end{aligned}$$ We also have $$\Theta(\sqrt{\beta})\operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{k}}{{\Lambda}_{k-1}}{\aftergroup\egroup\originalright})^{1/\beta}\approx
  \Theta(\beta)^{\frac{n+1-2(n-\beta)}{2(\beta-1)}}\operatorname{covol}^{\frac1n} {\Lambda}$$ so that the previous approximation is also true for $i=k-1$. Using \[heur:lambda1\_heur\] and Minkowski’s first theorem, we can estimate the covering radius of this quotient as: $$\mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_{i+1}}{{\Lambda}_i}{\aftergroup\egroup\originalright}) \leq \Theta(\sqrt{l_i})
  \Theta(\beta)^{\frac{n+2-2i\beta-l_i}{2(\beta-1)}}\operatorname{covol}^\frac1n{{\Lambda}}.$$ Using \[prop:sum\_covering\], now asserts that [[****]{}]{} returns a vector at distance from $t$ bounded by: $$\operatorname{covol}({\Lambda})^\frac1n\sum_{i=0}^k \Theta(\sqrt{l_i})
\Theta(\beta)^{\frac{n+2-2i\beta-l_i}{2(\beta-1)}}=
  \Theta(\beta)^{\frac{n}{2\beta-2}}\operatorname{covol}({\Lambda})^\frac1n$$ where the last equality stems from the condition $n\geq 2\beta$, so that only the first term is significant.

Note that in the algorithm, all lattices depend only on ${\Lambda}$, not on the targets. Therefore, it is possible to use algorithms after precomputations. These algorithms are significantly faster; we refer to  [@sieve20] for heuristic ones and to [@dadush2014closest; @stephens2019time] for proven approximation algorithms.

Proven algorithm with precomputation
====================================

In all of this section, let us fix an oracle [$\mathcal{O}$]{}, solving the $\gamma$-. We solve with preprocessing from the oracle $\mathcal{O}$.

\[thm:main\_result\] Let ${\Lambda}$ be a lattice of rank $n$. Then one can solve the $(n^\frac32\gamma^3)$-closest vector problem in ${\Lambda}$, using $2n^2$ calls to the oracle [$\mathcal{O}$]{} during precomputation, and polynomial time computations.

The first step of this reduction consists in proving that we can find a lattice point at a distance roughly $\lambda_n(\Lambda)$.

\[thm:absolu\] Let ${\Lambda}$ be a lattice of rank $n$ and $t\in{\Lambda}\otimes{\mathbf{R}}$ a target vector, then one can find a lattice vector $c\in{\Lambda}$ satisfying $$\|c-t\|\leq\frac{\sqrt{n}\gamma}{2}\lambda_n(\Lambda),$$ using $n$ calls to the oracle [$\mathcal{O}$]{} during precomputation, and polynomial time computations.

We aim at constructing a complete filtration $$\{0\} \subset {\Lambda}_1 \subset
  \cdots \subset {\Lambda}_n = {\Lambda}$$ of the input lattice ${\Lambda}$ such that for any index $1\leq i\leq n-1$, we have: $$\operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright}) \leq \gamma
\lambda_n({\Lambda}).$$ We proceed inductively:

-   By a call to the oracle [$\mathcal{O}$]{} on the lattice ${\Lambda}$, we find a vector $b_1$. Set ${\Lambda}_1 = b_1{\mathbf{Z}}$ the corresponding sublattice.

-   Suppose that the filtration is constructed up to index $i$. Then we call the oracle [$\mathcal{O}$]{} on the quotient sublattice $\faktor{{\Lambda}}{{\Lambda}_i}$ (or equivalently on the projection of ${\Lambda}$ orthogonally to ${\Lambda}_i$), and lift the returned vector using the [[****]{}]{} function in $v \in {\Lambda}$. Eventually we set ${\Lambda}_{i+1} = {\Lambda}_i\oplus v{\mathbf{Z}}$.

At each index, we have by construction $\lambda_{n-i+1}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}}{\Lambda_{i}}{\aftergroup\egroup\originalright})\leq
  \lambda_n(\Lambda)$. As such, $\operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}}{\Lambda_{i}}{\aftergroup\egroup\originalright})\leq
  \lambda_n(\Lambda)^{n-i+1}$, and, eventually, we have for each index $i$: $$\operatorname{covol}{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright})\leq
  \gamma\cdot\lambda_n(\Lambda).$$

As stated in \[rem:babai\], Babai’s algorithm on the point $t$ returns a lattice vector $c\in{\Lambda}$ such that: $$\|c-t\|\leq \sqrt{\sum_{i=1}^{n}
    \mu{\mathopen{}\mathclose\bgroup\originalleft}(\faktor{{\Lambda}_i}{{\Lambda}_{i-1}}{\aftergroup\egroup\originalright})^2}\leq
    \frac{\sqrt{n}\gamma\lambda_n(\Lambda)}{2}.$$

For a random lattice, we expect $\lambda_n(\Lambda)\approx
  \sqrt{n}\operatorname{covol}(\Lambda)^{\frac1n}$, so that the distance between the decoded vector and the target is only a factor $\gamma$ times larger than the guaranteed output of the oracle.

We can now complete the reduction:\
*Proof of \[thm:main\_result\].* Let ${\Lambda}$ be a rank $n$ lattice. Without loss of generality, we might assume that the norm $\|.\|$ of ${\Lambda}$ coincides with its dual norm, so that the dual ${{{\Lambda}}^{\vee}}$ can be isometrically embedded in ${\Lambda}_{\mathbf{R}}$. We first find a non-zero vector in the dual lattice: $c\in {{\Lambda}^{\vee}}$, where $\|c\|\leq \gamma^2
  \lambda_1({{\Lambda}^{\vee}})$ using Lovász’s reduction stated in \[thm:lovasz\_reduction\] on the oracle [$\mathcal{O}$]{}. Define $v\in{\Lambda}$ and $e\in{\Lambda}\otimes{\mathbf{R}}$ to satisfy $t=v+e$ with $\|e\|$ minimal. We now have two cases, depending on how large is the error term $e$:

Case $\|c\|\|e\|\geq 1/2$ (large case)

:   Then, by pluging Banaszczyk’s transference inequality to the bound on $\|c\|$ we get: $$\|e\|\geq \frac{1}{2\gamma^2\lambda_1({{\Lambda}^{\vee}})}\geq
          \frac{\lambda_n(\Lambda)}{2n\gamma^2}.$$ Thus, we can use \[thm:absolu\] to solve with approximation factor equal to: $$\frac{\sqrt{n}
            \gamma}{2}{\mathopen{}\mathclose\bgroup\originalleft}({\frac{1}{2n\gamma^2}}{\aftergroup\egroup\originalright})^{-1}=n^{\frac32}\gamma^3.$$

Case $\|c\|\|e\|<1/2$ (small case)

:   

Overall, we get the following corollary by using the Micciancio-Voulgaris algorithm for the oracle [$\mathcal{O}$]{}:

We can solve $\beta^{{\mathrm O{\mathopen{}\mathclose\bgroup\originalleft}(\frac{n}{\beta}{\aftergroup\egroup\originalright})}}$- deterministically in time bounded by $2^\beta$ times the size of the input.

Using exactly the scheme proof scheme, we can refine the approximation factor to a $n^{3/2}\gamma_S \gamma$ by using a separate $\gamma_S$-SVP oracle instead of using $\gamma$- as a $\gamma^2$- oracle.

Cryptographic perspectives {#sec:applications}
==========================

In cryptography, the <span style="font-variant:small-caps;">Bounded Distance Decoding</span> (<span style="font-variant:small-caps;">bdd</span>) problem[^2] has a lot of importance, as it directly relates to the celebrated *Learning With Error* problem (<span style="font-variant:small-caps;">lwe</span>) [@regev2009lattices]. This latter problem can be reduced to , however our theoretical reduction with has a loss which is too large to be competitive.

In the so-called GPV framework [@STOC:GenPeiVai08], instantiated in the `DLP` cryptosystem [@AC:DucLyuPre14] and its follow-ups `Falcon` [@fouque2018falcon], `ModFalcon` [@modfalcon], a valid signature is a point close to a target, which is the hash of the message. Hence, forging a signature boils down to finding a close vector to a random target. Our first (heuristic) result implies that, once a reduced basis has been found, forging a message is relatively easy. Previous methods such as in [@fouque2018falcon] used Kannan’s embedding [@kannan1987minkowski] so that the cost given only applies for one forgery, whereas a batch forgery is possible for roughly the same cost.

The same remark applies for practically solving the <span style="font-variant:small-caps;">bdd</span> problem, and indeed the <span style="font-variant:small-caps;">lwe</span> problem. Once a highly reduced basis is found, it is enough to compute a on the tail of the basis, and finish with Babai’s algorithm. More precisely, by using the same notations an exploiting the proof of \[thm:quality\_complexity\_average\], a sufficient condition for decoding will be: $$\|\pi(e)\| \leq \theta(\beta)^{\frac{2\beta-n}{2\beta}}\operatorname{covol}({\Lambda})^\frac1n,$$ where, $\pi$ is the orthogonal projection onto $\faktor{{\Lambda}}{{\Lambda}_k}$ and $\beta$ is the rank of this latter lattice.

This trick seems to have been in the folklore for some time, and is the reason given by `NewHope` [@USENIX:ADPS16] designers for selecting a random “$a$”, which corresponds to a random lattice (where the authors of [@USENIX:ADPS16] claim that Babai’s algorithm is enough, but it seems to be practically true in general for an extremely well reduced basis, i.e. with more precomputations performed).

Acknowledgments {#acknowledgments .unnumbered}
===============

This work was done while the authors were visiting the Simons Institute for the theory of computing in February 2020. They also thanks the anonymous reviewers for their insightful comments on this work.

[10]{}

D. Aggarwal, D. Dadush, and N. [Stephens-Davidowitz]{}. Solving the closest vector problem in [$2^n$]{} time - the discrete [Gaussian]{} strikes again! In [*56th FOCS*]{}. [IEEE]{} Computer Society Press. 2015.

D. Aggarwal, J. Li, P. Q. Nguyen, and N. Stephens-Davidowitz. Slide reduction, revisited—filling the gaps in [SVP]{} approximation. , 2019.

M. Ajtai, R. Kumar, and D. Sivakumar. Sampling short lattice vectors and the closest lattice vector problem. In [*Proceedings 17th IEEE Annual Conference on Computational Complexity*]{}. IEEE, 2002.

E. Alkim, L. Ducas, T. P[ö]{}ppelmann, and P. Schwabe. Post-quantum key exchange - [A]{} new hope. In [*USENIX Security 2016.*]{}

L. Babai. . , 6(1), 1986.

W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. , 296(1), 1993.

A. Becker, L. Ducas, N. Gama, and T. Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In [*27th SODA*]{}. [ACM-SIAM]{}, 2016.

J. Bl[ö]{}mer and S. Naewe. Sampling methods for shortest vectors, closest vectors and successive minima. , 410(18) 2009.

C. Chuengsatiansup, T. Prest, D. Stehl[é]{}, A. Wallet, and K. Xagawa. Modfalcon: compact signatures based on module [NTRU]{} lattices. , 2019.

D. Dadush, O. Regev, and N. Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In [*2014 IEEE 29th Conference on Computational Complexity (CCC)*]{}, IEEE, 2014.

I. Dinur, G. Kindler, and S. Safra. Approximating-[CVP]{} to within almost-polynomial factors is np-hard. In [*Proceedings 39th Annual Symposium on Foundations of Computer Science*]{}. IEEE, 1998.

C. Dubey, and T .Holenstein. Approximating the closest vector problem using an approximate shortest vector oracle Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 2011

L. Ducas, T. Laarhoven, and W. P. van Woerden. The randomized slicer for [CVPP]{}: sharper, faster, smaller, batchier. Cryptology ePrint, Report 2020/120.

L. Ducas, V. Lyubashevsky, and T. Prest. Efficient identity-based encryption over [NTRU]{} lattices. In [*ASIACRYPT 2014*]{}. Springer 2014.

F. Eisenbrand, N. H[ä]{}hnle, and M. Niemeier. Covering cubes and the closest vector problem. In [*the 27th symposium on Computational geometry*]{}, 2011.

P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang. Falcon: Fast-fourier lattice-based compact signatures over [NTRU]{}. , 2018.

N. Gama and P. Q. Nguyen. Finding short lattice vectors within [Mordell]{}’s inequality. In [*40th ACM STOC*]{}. [ACM]{} Press, 2008.

C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In [*40th ACM STOC*]{}. [ACM]{} Press, 2008.

O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. , 71(2) 1999.

G. Hanrot, X. Pujol, and D. Stehl[é]{}. Analyzing blockwise lattice algorithms using dynamical systems. In [*CRYPTO 2011*]{}. Springer, 2011.

G. Hanrot and D. Stehl[é]{}. Improved analysis of kannan’s shortest lattice vector algorithm. In [*CRYPTO 2007*]{}. Springer, 2007.

I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In [*39th ACM STOC*]{}. [ACM]{} Press, 2007.

G. Herold, E. Kirshanova, and T. Laarhoven. Speed-ups and time-memory trade-offs for tuple lattice sieving. In [*PKC 2018*]{}. Springer, 2018.

R. Kannan. Minkowski’s convex body theorem and integer programming. , 12(3) 1987.

T. Laarhoven, M. Mosca, and J. Van De Pol. Finding shortest lattice vectors faster using quantum search. , 77(2-3) 2015.

A. K. Lenstra, H. W. J. Lenstra, and L. Lov[á]{}sz. . , 261 1982.

L. Lov[á]{}sz. SIAM, 1986.

D. Micciancio and P. Voulgaris. Faster exponential time algorithms for the shortest vector problem. In [*21st SODA*]{}. [ACM-SIAM]{}, 2010.

D. Micciancio and M. Walter. Practical, predictable lattice basis reduction. In [*EUROCRYPT 2016*]{}. Springer, 2016.

P. Q. Nguyen and B. Vall[é]{}e. . Springer, 2010.

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. , 56(6) 2009.

C. A. Rogers et al. Mean values over the space of lattices. , 94 1955.

C. Schnorr. . , 53 1987.

C. L. Siegel. . , 46(2) 1945.

N. Stephens-Davidowitz. A time-distance trade-off for [GDD]{} with preprocessing—instantiating the [DLW]{} heuristic. , 2019.

W. Wei, M. Liu, and X. Wang. Finding shortest lattice vectors in the presence of gaps. In [*CT-RSA 2015*]{}. Springer, 2015.

[^1]: The result proved by Rogers is actually more general and bounds all the moment of the enumerator of lattice points. For the purpose of this work, only the first moment is actually required.

[^2]: This problem being defined as finding the closest lattice vector of a target, provided it is within a fraction of $\lambda_1(\Lambda)$.