Random lattice bases allow smaller enumeration trees than hkz limits
Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices
Cryptography and Security
Summary
Finding the shortest vector in a lattice is a key problem in cryptography and geometry, often solved by enumerating candidate vectors in a search tree. The authors studied how big these search trees are on random high-dimensional lattices, depending on the chosen lattice bases. They showed that the best known lattice bases (called HKZ bases) do not give the smallest trees on average, and they found new ways to build bases with significantly smaller search trees. This improves understanding of the problem's complexity and helps build faster algorithms for lattice problems with preprocessing.
What this means in practice
- •For cryptography engineers: Optimize algorithms for shortest vector and closest vector problems using improved lattice bases that reduce search tree sizes on random lattices.
- •For security software developers: Develop faster lattice-based cryptanalysis tools exploiting tighter bounds on enumeration complexity with new basis constructions.
A theory result. No direct application yet.
Authors
Thijs Laarhoven
Abstract
To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \leq 1/(4\sqrt{e}) \approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.