Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree

• SVP asks for a shortest nonzero lattice vector, while CVP asks for a lattice vector closest to a given target.Source: §1 · p. 3
• Exact and sufficiently accurate SVP and CVP are difficult despite efficient coarse approximation algorithms, making their complexity a central benchmark and a foundation of lattice-based cryptography.Source: §1 · p. 3
• Randomized classical algorithms solve SVP on arbitrary lattices with success probability at least 2/3 in worst-case time and space 2^{n/2+o(n)}.Source: §1 · p. 3
• The same complexity applies to CVP when the target satisfies dist(y, L) ≤ αλ_1(L) for α < 1.039... = 1/(2√t_0), with t_0 = 0.23147....Source: §1 · p. 3

Gradient signal

• A shortest vector’s q-ary periodic-Gaussian gradient points approximately toward the vector, up to sign, with exponentially small relative error.For the appropriate width, the shortest-vector term dominates the primal gradient, while the remaining terms have norm at most 2^-Ω(n)||v||.Source: §1.1 · pp. 4–5

Coset aggregation

• Coset gradients aggregate q-ary points over intermediate-lattice cosets so the shortest-vector contribution remains detectable without evaluating all q^n candidate points.The target point is one of q^n possibilities, and the coset size is selected so its gradient term remains detectable in the aggregate.Source: §1.1 · p. 5

Meet-in-the-middle

• Phase-weighted coset sums convert a condition on one Gaussian sample into a prescribed condition on the difference of two independent samples.The construction uses matching pairs whose transformed difference satisfies the desired subspace component, with randomization by a uniform U ∈ GL_n(F_q).Source: §1.1 · p. 6

Difference tree

• A binary difference tree generalizes the two-sample construction, and its expansion contains a term proportional to the shortest vector while the remaining terms are small with high probability.In the four-sample case, three difference constraints are imposed; for p = 2^m−1 samples, components of the encoded shortest vector are handled implicitly except for the final indexed component.Source: §1.1 · pp. 6–8

Efficient estimation

• The tree evaluates sums over N^p sample tuples without enumeration, using level-wise matching and a fast Fourier transform to compute all final θ values simultaneously.The estimator is built from p discrete-Gaussian lists, recursively combines pairs satisfying difference constraints, and applies one fast Fourier transform over H_m.Source: §1.1 · p. 8

Complexity and limitations

• Balancing list size and coset parameters yields 2^{n/2+o(n)} time and space, while further improvement is constrained by Gaussian-sampling cost and the shrinking desired signal.The same exponent arises from balancing coset size against estimation error and from the requirement N ≥ 2^{n/2} for the known sampler; increasing p eventually makes the desired term too small to detect.Source: §1.1 · p. 9

Technical overview

• The gradient-tree proof rewrites node averages and differences into weighted squared norms, then uses affine coset constraints and injectivity to bound contributions recursively by discrete-Gaussian masses.This controls all terms other than the desired term G(w_v)f(w_v)^{p−1}.Source: §1.1 · p. 10

The CVP extension

• For CVP, the shifted periodic Gaussian gradient satisfies −G_y(w_v) pointing toward the closest-vector error e = v − y, enabling the same coset gradient-tree construction.The estimate approximates the desired gradient term up to a phase factor, with error about Q^{-1/2} = 2^{-n/4} up to small factors.Source: §1.1 · p. 10
• For α < 1/(2√t_0), where t_0 = 0.23147…, the procedure runs in time and space 2^{n/2+o(n)} and guarantees dist(y, L) ≤ 1.039…λ_1(L).The guarantee follows from the lattice-packing bound; technically, sufficiently small error is handled directly by the BDD algorithm.Source: §1.1 · p. 10

2 Preliminaries

• The paper defines standard sets, finite-field notation, norms, distances, indicators, asymptotic conventions, and exact-arithmetic assumptions for the dimension parameter n.Polynomial factors in n and input bit length are suppressed, and polynomial precision is sufficient throughout.Source: §2 · p. 11

2.1 Lattice and discrete Gaussian

• A full-rank lattice L=BZ^n has first minimum λ_1(L), dual lattice L*=B^-T Z^n, and lattice-point constant β=20.4014... from and [47, Lemma 3].The paper notes improved bounds in but does not use them.Source: §2.1 · p. 11
• Discrete-Gaussian preliminaries establish maximal mass for centered cosets, efficient sampling slightly above the smoothing parameter, and the definition of SVP.For full-rank L and κ = Ω(n), Theorem 2.2 gives a classical algorithm outputting every requested 1 ≤ M ≤ 2^{n/2} lattice vectors in time 2^{n/2+polylog(κ)+o(n)}.Source: §2.1 · p. 11

2.2 Useful lemmas

• A useful norm lemma shows that if x approximates nonzero y within relative error ε<1, then x is nonzero and its norm is correspondingly bounded below.The proof applies the triangle inequality to obtain ∥x∥≥(1−ε)∥y∥>0.Source: §2.2 · p. 12

Parameters

• The analysis fixes t0 = 0.23147..., chooses t0 < t < 1/4, and uses d satisfying λ ≤ d ≤ (1 + 1/n)λ.The algorithm guesses d from a polynomial-size list and analyzes correctness using a qualifying guess.Source: §3 · p. 12

Periodic Gaussian

• The section defines the periodic Gaussian and derives primal and dual representations for its gradient using Poisson summation.These representations underpin the later gradient estimates.Source: §3 · pp. 12–13

q-ary Cosets

• For an odd prime q, lattice dual vectors are represented by residues in L*/qL* ≅ F_q^n, enabling q-ary coset notation and Gaussian definitions.The construction associates v ∈ L with w = B^-1v mod q and defines the corresponding q-ary periodic Gaussian and gradient.Source: §3 · p. 13

Gradient Direction

• For a shortest vector v, the gradient of the periodic Gaussian at v/q has direction close to v under λ ≤ d ≤ (1 + 1/n)λ and t0 < t < 1/4.Lemma 3.4 applies when q is an odd prime and w = B^-1v mod q.Source: §3 · p. 13

4 The SVP algorithm

• Theorem 4.1 gives a randomized classical algorithm solving SVP with probability at least 2/3 in worst-case time and space 2^n/2+o(n).Source: §4 · p. 14

4.1 The first estimation target

• The first estimation target guarantees that a normalized real or imaginary part of the estimator lies within 2^-Ω(n) of ±v/λ for a shortest vector v.The lemma assumes λ_1(L) ≤ d ≤ (1 + 1/n)λ and t_0 < t < 1/4.Source: §4.1 · p. 14

4.2 The coordinate decomposition and the estimator

• Coordinate decomposition defines an ideal quantity A_δ over a search space of size 2^n/2+o(n), and with high probability one value encodes the shortest-vector direction.The estimator uses independent discrete-Gaussian samples, random U ∈ GL_n(F_q), and affine coset offsets δ; all values bA_δ(θ) can be computed in time and space 2^n/2+o(n).Source: §4.2 · pp. 17, 19, 20

4.3 The algorithm

• The algorithm uses p log p = o(n) and parameters Q,N = 2^n/2+o(n), taking a lattice basis as input and outputting a shortest nonzero vector with probability at least 2/3.Source: §4.3 · pp. 20–21

Algorithm 2: The SVP algorithm

• Algorithm 2 begins with LLL reduction, then repeats preprocessing and discrete-Gaussian sampling for each d ∈ D.The samples use s^2 = 4nt ln 2/(πd^2), with pN samples for each r ∈ [0,p).Source: Algorithm 2: The SVP algorithm · p. 21
• Algorithm 2 samples discrete Gaussians, chooses random U and δ, queries BDD on real and imaginary coset-gradient components, and returns the shortest returned nonzero vector.It uses d with λ ≤ d ≤ (1+1/n)λ; samples are generated with 2^o(n) calls and are inverse-exponentially close to independent discrete Gaussian samples.Source: Algorithm 2: The SVP algorithm · p. 21
• 2^(n/2+o(n)) time and space with success probability at least 2/3 are achieved by repeating Algorithm 2 a constant number of times.For the target coset, a queried BDD target lies within 2λ/n of a shortest vector except with probability o(1), so successful preprocessing returns that vector; the minimum-norm selection then outputs a shortest vector.Source: Algorithm 2: The SVP algorithm · p. 21

4.4 Proofs of the lemmas

• The proof organizes intermediate subspaces, lattices, cosets, and Gaussian widths so recursive quantities depend only on cosets and satisfy an averaging recurrence.The quantities are even and periodic, and the recurrence sums over lower-level cosets contained in a fixed higher-level coset.Source: §4.4 · pp. 21, 23, 24
• The expansion of V_j is uniquely reindexed by the tuple (u_{r,b})_{r,b} without multiplicity, and its first-term bound is a product of discrete Gaussian masses.The expansion for T_j is bounded by that for V_j with an additional factor (2πs2/q)2 ∥u0,0∥2 in each summand.Source: §4.4 · pp. 25, 28
• The remaining transformed tuples are classified by their first nonzero difference, reducing their contributions to Gaussian mass on intermediate lattices excluding zero.The all-zero tuple vanishes, while nonzero cases are bounded by summing over at most 2^o(n) distinguished variables and absorbing subexponential factors.Source: §4.4 · p. 29
• The nonprincipal-mass analysis recursively controls B_j and E_j through V_j = V_{j−1}^2 + Δ_j and T_j = T_{j−1}V_{j−1} + Γ_j.Induction starts from B_0 = E_0 = 0, and subexponential factors are absorbed into the o(n) terms.Source: §4.4 · pp. 30–31
• Lemma 4.14 gives simultaneous high-probability bounds across all recursive levels when λ1(L) ≤ d ≤ (1 + 1/n)λ1(L).The guarantee fails with probability o(1) over U.Source: §4.4 · p. 30
• Lemma 4.15 shows that the relevant expectation is zero when index-overlap sets are empty and is bounded otherwise, uniformly over θ and index pairs.The proof uses independence for disjoint sample collections and induction for overlapping terms, with failure probability 2^-Ω(n).Source: §4.4 · pp. 31, 36
• Average-difference variables form a bijective expansion in which each variable lies in a specified coset of an intermediate lattice, enabling sequential Gaussian-mass bounds.After fixing lower-level differences, higher-level differences lie in cosets of K_h−1, while a_j,0 lies in a coset of K_j+1.Source: §4.4 · p. 33
• Character orthogonality removes all terms with α ≠ α′ after averaging over δ, leaving only matching indices.The proof then fixes a surviving α and analyzes the contributions indexed by r.Source: §4.4 · p. 36
• Independence of the relevant samples permits factorization of the corresponding expectations, while shared samples combine the two character terms.These cases provide the expectation identities used in the lemma bounds.Source: §4.4 · p. 36
• The absolute value of Eq. (71) is bounded by (s^2λ/q)2^Q|I|−1 2^o(n), and comparing Eqs. (71) and (72) completes the desired bound.Using s^2λ^2 = Θ(n) and q = n^O(1), the proof absorbs the factor of two into 2^o(n).Source: §4.4 · p. 36

5 CVP with a distance guarantee

• For every fixed α < 1.03925…, exact CVP under dist(y,L) ≤ αλ_1(L) is solvable with probability at least 2/3 in time and space 2^{n/2+o(n)}.This is the section’s main theorem and applies to every lattice and target satisfying the stated promise.Source: §5 · p. 37

5.1 The first estimation target

• The first estimation target recovers the closest-vector error direction, or reduces directly to BDD when its norm is below n^{-1/3}λ.When ∥e∥ ≥ n^{-1/3}λ, one of the normalized real or imaginary estimator components is within 2^{-Ω(n)} of ±e/∥e∥, enabling a nearby lattice query.Source: §5.1 · pp. 38–39

5.2 The coordinate decomposition and the estimator

• The coordinate decomposition constructs an estimator whose values for all θ can be approximated in time and space 2^{n/2+o(n)} with exponentially small additive error.The estimator is supported by recursive q-ary differences, a uniform high-probability approximation over y and θ, and batch computation of all estimator vectors.Source: §5.2 · p. 41

5.3 The algorithm

• The algorithm uses LLL-selected distance scales, random translations, BDD preprocessing, Gaussian samples, and estimator directions to generate candidate closest vectors under the promised distance bound.For each estimator direction, it queries both signs and all discretized step lengths, discards invalid outputs, and returns the collected vector nearest to y.Source: §5.3 · p. 42, Algorithm 4: CVP with a distance… · p. 42

Algorithm 4: CVP with a distance guarantee

• The correctness proof shows that one queried point lies within the BDD radius, so successful preprocessing returns the closest vector after undoing the random translation.The short-error case is solved directly at the translated target; otherwise the estimator supplies a direction, sign, and step whose query recovers the same closest vector.Source: Algorithm 4: CVP with a distance… · pp. 42–43
• 2^{n/2+o(n)} time and space, with success probability at least 2/3 after constant repetitions, follows for Algorithm 4 despite its shifted-query and parameter-search overhead.Each repetition uses 2^{n/2+o(n)} time and space; shifted queries contribute only Q^{2o(n)} BDD queries, while n^2 + 1 choices of d and constant repetitions add a polynomial factor.Source: Algorithm 4: CVP with a distance… · p. 43

5.4 Random target CVP in a random lattice

• With probability 1 − exp(−Ω(n^{2/3})) over a Haar-random lattice, Algorithm 4 solves a uniformly random CVP target with probability at least 1/2 for sufficiently large n.The target is sampled uniformly modulo the lattice, and the guarantee is over the target and the algorithm’s internal randomness.Source: §5.4 · p. 43

5.5 Proofs of the CVP lemmas

• For the Rj- and Hj+1-sums, tuple indexing introduces no multiplicity, specified varying values lie in single cosets of L or Kj+1, and estimates hold simultaneously for every y.Source: §5.5 · p. 47
• The remaining CVP analysis bounds first- and second-moment quantities across the q-ary levels, including the shifted signal estimate and the generalized second-moment recurrence.Lemma 5.15 controls nonprincipal coset contributions, while Lemma 5.16 extends the recursive bounds to omitted-index sets.Source: §5.5 · pp. 48–50
• The recursive bounds for T_j,I,y and V_j,I,y follow by case analysis on the left and right index subsets, with accumulated factors absorbed into 2^o(n).The first inequality is invoked at most 2j ≤ p times, while the second is invoked at most once.Source: §5.5 · p. 50
• Lemma 5.17 bounds the relevant expectation by separating disjoint and overlapping index sets and using character orthogonality to eliminate mismatched phase terms.For nonempty overlap, only equal auxiliary indices remain; shared samples cancel their characters and target phases, reducing the expression to norm factors controlled by the preceding lemmas.Source: §5.5 · pp. 50–51
• The proof of Lemma 5.6 expands the estimator’s squared norm, counts ordered pairs by their overlap set, and applies Lemma 5.17’s bound.For each nonempty I ⊆ [0, p), at most N 2^(p−|I|) ordered pairs have overlap set I; using N = Q^p4 yields the stated bound uniformly in y and θ.Source: §5.5 · p. 51