Source-linked AI summary
Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree
Minki Hhan
TL;DR
Exact SVP and sufficiently accurate CVP remain difficult despite faster approximation methods. The paper uses a q-ary coset-gradient approach with combinatorial aggregation to obtain randomized algorithms running in time and space 2^(n/2)+o(n), including a CVP guarantee below 1.039λ1(L).
Problem
Exact and sufficiently accurate SVP and CVP remain computationally difficult, despite polynomial-time algorithms for useful coarse approximations.
Method
The algorithm uses gradients of the periodic Gaussian at q-ary points, aggregates them over affine cosets, and computes the relevant coset gradient through a combinatorial tree.
Results
The randomized algorithms achieve success probability at least 2/3 and worst-case time and space 2^(n/2)+o(n) for arbitrary-lattice SVP and the stated CVP setting.
Takeaways & Limitations
The approach gives exact SVP at this complexity and solves CVP with dist(y, L) ≤ 1.039...λ1(L) while retaining the same asymptotic bound.
Takeaways & Limitations
The paper states that going below 2^(n/2)+o(n) appears difficult for this optimization and that the tree algorithm may not improve the midpoint Hessian.
Abstract
from arXiv · showhide
This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact that, for a shortest vector $v$, the gradient (rather than Hessian) of the periodic Gaussian function at $v/q$ is nearly proportional to $v$ (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner's generalized birthday algorithm, yielding the $2^{n/2+o(n)}$ time and space complexity. A variant of the algorithm solves the exact closest vector problem on every input $(y,\mathcal L)$ with a distance guarantee $\operatorname{dist}(y,\mathcal L)\le 1.039λ_1(\mathcal L)$ within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space $2^{n/2+o(n)}$.
1 Introduction
The paper develops improved randomized algorithms for exact lattice problems, addressing the gap between efficient coarse approximation and the difficulty of exact or tight solutions. Its main result achieves worst-case time and space 2^(n/2)+o(n) for arbitrary-lattice SVP and a guaranteed-distance version of CVP.
- Problem setting: SVP asks for a shortest nonzero lattice vector, while CVP asks for the lattice vector closest to a target.These problems are central to geometry of numbers, computational complexity, and lattice-based cryptography.
- Motivation: Exact and sufficiently accurate SVP and CVP remain difficult despite polynomial-time algorithms that provide useful exponential approximations.This discrepancy motivates continued efforts to reduce the complexity of exact lattice algorithms.
- Motivation: Recent worst-case SVP algorithms reached 2^0.5596n+o(n), 2^0.6039n+o(n), and 2^0.7314n+o(n) time, breaking the 2^n barrier.The supplied passage reports these bounds as recent improvements in the complexity of SVP.
- Main result: The paper presents improved randomized algorithms for exact lattice problems.This statement introduces the paper’s main contribution before the theorem’s guarantees.
- Main result: With success probability at least 2/3, the algorithms solve arbitrary-lattice SVP in worst-case time and space 2^(n/2)+o(n).The same asymptotic bound also applies to the stated CVP setting.
- Main result: The CVP algorithm applies to targets satisfying dist(y, L) ≤ αλ1(L) for α < 1.039..., while retaining time and space 2^(n/2)+o(n).The theorem states this guarantee for the distance from the target to the lattice.
1.1 Technical overview
The algorithm uses a q-ary periodic-Gaussian gradient whose shortest-vector contribution reveals the vector’s direction, then computes the relevant coset gradients through a difference tree without enumerating all candidate tuples.
- Gradient signal: For a shortest vector v, the periodic-Gaussian gradient at v/q is nearly proportional to v, up to sign, while its error is exponentially smaller.The analysis bounds the error by ∥e∥≤2^-Ω(n)∥v∥.
- Coset aggregation: Evaluating gradients at all q^n possible q-ary points is too expensive, so the algorithm aggregates them over affine cosets of intermediate lattices.The desired shortest-vector term remains detectable in the coset sum when its q-ary representation lies in the selected coset.
- Difference representation: Multiplying the gradient by an even phase factor converts a coset condition on one sample into a prescribed condition on the difference of two discrete-Gaussian samples.Phase weighting also permits the difference to lie in an arbitrary prescribed coset.
- Difference tree: The q-ary difference tree recursively matches pairs by subspace components, replaces each pair by its difference, and passes the result to the next level.A four-sample example imposes three successive difference conditions before exposing the component indexed by θ.
- Signal extraction: At the selected θ*= (U^-T w_v)_{H_m}, the tree expansion contains a term approximately pointing toward v, while the other components are handled implicitly by internal sums.The desired term has unit-modulus phase factor, and the algorithm evaluates the required sum without enumerating all N^p tuples.
- CVP extension: For closest-vector instances, the same construction achieves time and space 2^{n/2+o(n)} under the distance guarantee dist(y,L)≤1.039…λ_1(L).The analysis requires t>0.23147… and α<1/(2√t_0).
2 Preliminaries
This section establishes lattice notation, Gaussian distributions and smoothing tools, the core lattice problems, and the preprocessing BDD primitive used later.
- Lattice notation: An n-dimensional full-rank lattice is generated by integer combinations of a nonsingular basis matrix's columns.The first minimum λ1(L) is the length of a shortest nonzero lattice vector.
- Lattice notation: The dual lattice consists of vectors having integer inner products with every primal-lattice vector, and has basis B−T.
- Gaussian tools: Discrete and periodic Gaussians provide the distributional and analytic tools for lattice calculations.Poisson summation implies that a centered coset has maximal Gaussian mass among shifted cosets.
- Lattice problems: SVP finds a shortest nonzero lattice vector, while CVP finds the lattice vector closest to a target.Both are presented as central problems in geometry of numbers, complexity, and lattice-based cryptography.
- Lattice problems: A near-shortest target distance promise makes the closest lattice vector unique for α-BDD.The promise is dist(y,L) < αλ1(L), with 0 < α < 1/2.
- BDD primitive: The preprocessing BDD algorithm runs in worst-case time and space 2^{n/2+o(n)} and then solves promised instances deterministically in time 2^{o(n)}.It succeeds with constant probability and produces advice of size 2^{o(n)}.
3 Preparation
This section develops q-ary periodic-Gaussian gradients and shows that evaluating them at a shortest vector's q-ary point reveals its direction under suitable parameter conditions.
- Parameter selection: The algorithm guesses d from a polynomial-size list and analyzes correctness using a guess within a factor 1 + 1/n of λ1(L).Other guesses do not affect time complexity or correctness.
- Analytic bounds: The preparation relies on periodic-Gaussian definitions and auxiliary bounds uniform over lattices and suitable width parameters.
- q-ary representations: The q-ary periodic Gaussian and its gradient admit primal and dual representations, with residue classes represented in L*/qL* ≅ F_q^n.The gradient is odd and the periodic Gaussian is even.
- Gradient preparation: For an odd prime q, the periodic-Gaussian gradient at v/q has direction close to a shortest vector v.The statement assumes λ1(L) ≤ d ≤ (1 + 1/n)λ1(L) and t0 < t < 1/4.
- Gradient analysis: The gradient's alignment with v follows by bounding contributions from other lattice vectors using shortest-vector geometry and Gaussian-mass estimates.The proof combines inequalities for x + v, Gaussian monotonicity, smoothing bounds, and the gradient representation.
4 The SVP algorithm
The SVP algorithm combines a q-ary Gaussian-gradient estimator with coordinate decomposition and efficient estimation, recovering a shortest-vector direction and then the vector itself. It succeeds with probability at least 2/3 in worst-case time and space 2^n/2+o(n).
- Theorem 4.1 gives a randomized classical SVP algorithm with success probability at least 2/3 and worst-case time and space 2^n/2+o(n).
- The algorithm chooses p = Θ(n/log^3 n), q = (2 + o(1))√p, and m = log_2 p + 1.The prime-size relation follows from the prime number theorem.
- 4.2 The coordinate decomposition and the estimator: The coordinate decomposition represents the target using independent discrete-Gaussian samples, recursive differences, affine cosets, and character-orthogonality identities.The decomposition uses Y_0,r = U[B^T X_r mod q] and recursively defined differences Y_j,a.
- 4.2 The coordinate decomposition and the estimator: A search space of size Q = 2^n/2+o(n) contains an A_δ(θ) whose direction approximates a shortest vector, while Lemmas 4.3–4.5 control its principal and nonprincipal contributions.The relevant θ is θ* = (U^-T w)_H_m, and the approximation holds except with probability o(1) over the stated randomness.
- 4.3 The algorithm: The algorithm queries a preprocessing BDD structure with a target within 2λ/n of v, then returns the shortest among the nonzero vectors found.The DGS calls, estimator, BDD queries, repetitions, and parameter choices together retain the 2^n/2+o(n) worst-case bound.
5 CVP with a distance guarantee
The paper extends its approach to CVP targets within a 1.03925λ_1(L) distance guarantee, using shifted periodic-Gaussian estimates and a q-ary difference-tree computation. The resulting randomized algorithm runs in time and space 2^{n/2+o(n)}, with an additional random-target guarantee for Haar–Siegel lattices.
- The CVP guarantee: 1.03925λ_1(L) is the supported CVP distance threshold for the randomized algorithm, which succeeds with probability at least 2/3.The theorem applies for every fixed α < 1.03925 and promises dist(y,L) ≤ αλ_1(L).
- Shifted Gaussian analysis: The CVP analysis shifts the periodic Gaussian and its gradient around the closest lattice vector v, with error e = v − y.The shifted functions are analyzed using the residue w = B^-1v mod q and the closest-vector condition.
- Reduction to BDD: When the target error is at least n^-1/3λ, the estimated real or imaginary gradient direction yields a short list of shifted BDD queries containing v; smaller errors already satisfy the n^-1/3-BDD promise.A suitable direction approximates ±e/∥e∥, and one of O(n^1/3) shifts comes within n^-1/3λ of v.
- Estimator computation: The estimator approximates all required vectors simultaneously with exponentially small failure probability, and the batch computation costs 2^{n/2+o(n)} time and space.Lemma 5.8 gives the batch bound; Lemma 5.6 provides uniformity over targets and query points.
- Overall complexity: The full algorithm retains 2^{n/2+o(n)} time and space because shifted queries and parameter choices add only subexponential or polynomial overhead.Each repetition succeeds with constant probability, and a constant number of repetitions raises success probability to at least 2/3.
- Random-instance guarantee: For a Haar–Siegel random lattice, the algorithm solves a uniformly random CVP target with probability at least 1/2 for almost every lattice.The exceptional lattice probability is exp(-Ω(n^{2/3})).