Source-linked AI summary
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot, Damien Stehlé
TL;DR
Lattice-based cryptosystems rely on the difficulty of shortest- and closest-vector problems, while Kannan’s algorithms remained analytically outdated despite their role in cryptanalytic reduction methods. This paper improves their complexity analyses and reports substantially lower bounds for both SVP and CVP.
Problem
Kannan’s shortest- and closest-vector algorithms underpin lattice-based cryptosystems’ security analysis and Schnorr’s block algorithms, but their complexity estimates had not improved for more than twenty years.
Method
The paper analyzes Kannan’s enumeration algorithms using properties of HKZ-reduced bases, induction over interval decompositions, and lattice-point estimates within convex bodies.
Results
The analysis lowers Kannan’s SVP complexity bound and reduces the CVP bound from d^d+o(d) to d^(d/2)+o(d).
Takeaways & Limitations
The SVP improvement yields better worst-case efficiency/quality trade-offs in Schnorr’s block-based algorithms and may help explain tractability in moderate dimensions.
Takeaways & Limitations
The hidden constants in the o(d) terms may be large for practical dimensions and were not optimized.
Abstract
from arXiv · showhide
The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.
1 Introduction
Lattice cryptosystems rely on hard shortest- and closest-vector problems, making precise complexity estimates for Kannan’s algorithms important for meaningful key sizes. The paper improves these analyses and connects the SVP improvement to Schnorr’s block algorithms.
- Motivation: Cryptosystems including NTRU, GGH, and Ajtai-Dwork rely on the difficulty of shortest- or closest-vector problems in high-dimensional lattices.The paper motivates precise complexity estimates because generic attacks solve SVP and influence meaningful key-size selection.
- Consequences: The SVP improvement directly yields better worst-case efficiency/quality trade-offs in Schnorr’s block-based algorithms.Kannan’s enumeration is a time-consuming component of those algorithms, and basis preprocessing affects its efficiency.
- Prior algorithms: Kannan’s deterministic SVP algorithm uses exhaustive enumeration after substantial basis preprocessing, while Fincke–Pohst enumerates within an ellipsoid.Kannan’s analysis instead uses a hyper-parallelepiped, whereas Fincke–Pohst uses a contained hyper-ellipsoid.
- Main result: The paper lowers Helfrich’s complexity bound for Kannan’s SVP algorithm to d^(2e+o(d)) ≈ d^(0.184·d)+o(d).The improved analysis is based on counting lattice points through ellipsoids rather than the less efficient containing parallelepiped.
- Main result: The same analysis lowers Kannan’s CVP complexity bound from d^(d+o(d)) to d^(d/2+o(d)).The paper presents this as a sibling result adapting the SVP analysis to closest-vector solving.
- Limitations: The hidden o(d) constants may be large at practical dimensions because the analysis did not optimize them.Heuristic volume estimates would produce much smaller hidden constants, but the paper does not develop those estimates fully.
2 Background on Lattice Reduction
This section introduces lattices, their volume and minimum, SVP and CVP, and the reduction notions used to analyze lattice bases. It contrasts inexpensive LLL reduction with stronger, more expensive HKZ reduction.
- Lattice geometry: The Gram–Schmidt orthogonalisation constructs an orthogonal family from the ordered basis vectors.Its vectors and coefficients depend on the order of the basis, and are rational for integer input vectors.
- Lattice invariants: The lattice volume det(L) is the product of the norms of Gram–Schmidt vectors and does not depend on the chosen lattice basis.Geometrically, it is the volume of the parallelepiped spanned by a basis.
- SVP and CVP: The minimum λ(L) is the radius of the smallest origin-centred closed ball containing a non-zero lattice vector, and SVP asks for a vector attaining it.CVP instead asks for a lattice vector closest to a given target in the real span of the lattice.
- Basis reduction: HKZ reduction combines size reduction, a shortest first basis vector, and recursively HKZ-reduced orthogonal projections.Minkowski’s theorem supplies the stated geometric properties used later in the analysis.
- Basis reduction: LLL reduction is cheaper than HKZ reduction but produces a basis of substantially lower quality.An LLL-reduced basis can nevertheless be computed deterministically in polynomial time and provides exponential approximations to SVP and CVP.
3 Kannan’s SVP Algorithm
Kannan’s SVP algorithm combines short-lattice-point enumeration with substantial basis preprocessing to compute an HKZ-reduced basis. Its complexity analysis bounds enumeration and recursive reduction costs, yielding an improved deterministic running-time bound.
- Algorithm structure: Kannan’s algorithm computes an HKZ-reduced basis using repeated short lattice points enumeration.The enumeration procedure finds lattice vectors within a prescribed squared-norm bound, while the overall algorithm recursively reduces projected bases.
- Basis preprocessing: Kannan preprocesses the basis toward quasi-HKZ reduction before enumeration, including projection and recursive HKZ reduction.A quasi-HKZ-reduced basis is size-reduced, satisfies a Gram–Schmidt norm condition, and becomes HKZ-reduced after projection orthogonally to b1.
- Short lattice points enumeration: The enumeration algorithm outputs all lattice vectors of squared norm at most A from an integral lattice basis.It operates by testing integer coefficient combinations against bounds derived from orthogonalized basis vectors.
- Improved bound: The paper improves the overall deterministic bound to P(log B, n) · d^(2e)+o(d) for computing an HKZ-reduced basis.The improved enumeration bound applies when the input basis is quasi-HKZ-reduced and A = ||b1||^2.
4 Complexity of the Enumeration Procedure
The enumeration procedure’s complexity is reduced to counting integer points in hyper-ellipsoids, then bounded using geometric properties of HKZ-reduced bases. The resulting analysis improves Kannan’s bounds and supports better worst-case trade-offs for block reduction.
- Enumeration complexity: The enumeration procedure’s complexity is, up to polynomial factors, bounded by its number of loop iterations.This connects the algorithmic cost to counting admissible truncated integer coordinates.
- Enumeration complexity: Each truncated coordinate is tested through neighboring integer choices, so valid points generate only a controlled number of non-valid candidates.The procedure considers adjacent coordinate extensions around valid truncated coordinates.
- Geometric reformulation: The analysis converts lattice-point enumeration into counting integer points inside hyper-ellipsoids associated with projected basis vectors.The ellipsoidal formulation underlies the subsequent geometric estimates.
- Geometric reformulation: The proof uses HKZ-reduced bases, interval decompositions, density estimates, induction, and Minkowski’s theorem to control the relevant products.Complicated index sets are split into blocks of consecutive large and small vectors, with decreasing densities maintained during recombination.
- Improved bound: For large index sets, the new bound is significantly better than combining separate interval estimates, including the worst case near [d(1 − 1/e), d].The paper explicitly contrasts the resulting lower bound with the weaker bound obtained from repeated applications of earlier relations.
5 CVP and Other Related Problems
The paper adapts its enumeration analysis to CVP and related lattice-vector enumeration tasks, and derives consequences for Schnorr’s block-based reduction strategy. These adaptations improve deterministic complexity and worst-case reduction bounds.
- CVP: The adapted Kannan CVP algorithm HKZ-reduces the basis and enumerates lattice vectors near the target vector.Babai’s nearest hyperplane algorithm supplies a distance bound used to choose the enumeration radius.
- CVP: d^d/2+o(d) is the deterministic complexity bound for finding all closest lattice vectors, improving the previous d^d+o(d) bound.The bound includes a polynomial factor in log B and n.
- Related problems: The analysis also applies to enumerating all lattice vectors below a prescribed length, including applications to lattice theta series.This is presented as a related consequence of the CVP-oriented adaptation.
- Schnorr reduction: The improved SVP analysis yields a significant worst-case bound improvement for Schnorr’s block-based strategy to compute relatively short vectors.The bounds quantify the shortest-vector quality reachable at a specified computational effort.
- Schnorr reduction: The multiplicative exponent constant in the block-reduction bounds is divided by e ≈ 2.7.The table entries describe upper bounds reachable for computational effort 2^t as t grows.
Proof of Lemma 2
This proof establishes the lemma by induction on k, using bounds on the Hermite constant and monotonicity properties of the resulting logarithmic expression.
- Induction: The proof proceeds by induction on k, beginning with the base case k = 1.The base case follows from the bound γ_d ≤ (d + 4)/4.
- Induction: The induction step defines G_d(k) and proves the corresponding bound for k + 1.The argument assumes the result for k in J1, d − 2K and establishes it for the next index.
- Induction: The remaining inequalities follow from monotonicity in d and the fact that the final term is negative at d = 3.These properties complete the induction step.
Proof of Lemma 3
The proof develops the geometric estimates needed for the enumeration analysis through convexity, Minkowski’s theorem, and induction. It handles interval and fractional-index cases with case-specific inequalities.
- Core estimates: Convexity of x log x supplies the central inequality used in the lemma’s estimates.The proof applies this convexity to weighted positive quantities.
- Core estimates: The induction derives the required basis-product inequalities by applying Minkowski’s bound to lower-dimensional HKZ-reduced bases.The argument rewrites the induction hypothesis and combines it with the relevant equation.
- Case analysis: The technical proof concludes by bounding the relevant expressions after rewriting them through repeated applications of the preceding equations.The appendix contains the detailed algebraic case analysis.