IACR News item: 18 September 2025
Léo Ducas, Johanna Loyer
ePrint Report
Most concrete analyses of lattice reduction focus on the BKZ algorithm or its variants relying on Shortest Vector Problem (SVP) oracles. However, a variant by Li and Nguyen (Cambridge U. Press 2014) exploits more powerful oracles, namely for the Densest rank-$k$ Sublattice Problem ($DSP_k$) for $k \geq 2$.
We first observe that, for random lattices, $DSP_2$ --and possibly even $DSP_3$-- seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive.
We therefore proceed to a heuristic and average-case analysis of the slope of $DSP_k$-BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggests a prediction for the volume of the densest rank-$k$ sublattice of a random lattice.
Under this heuristic, the slope for $k=2$ or $3$ appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the "Dimensions for Free'' of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic.
Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems.
We first observe that, for random lattices, $DSP_2$ --and possibly even $DSP_3$-- seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive.
We therefore proceed to a heuristic and average-case analysis of the slope of $DSP_k$-BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggests a prediction for the volume of the densest rank-$k$ sublattice of a random lattice.
Under this heuristic, the slope for $k=2$ or $3$ appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the "Dimensions for Free'' of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic.
Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems.
Additional news items may be found on the IACR news page.