Subexponential key recovery proved for major lattice families
The mathematical proofs establish subexponential key recovery for problem families tied to all seven NIST third-round lattice candidates.
Edited by Boris Djordjevic · Paperfoot
In a preprint, researchers proved classical subexponential algorithms—methods that scale faster than polynomial time but slower than purely exponential growth—for secret recovery in growing parameter families linked to all seven NIST third-round lattice candidates. These candidate schemes include Kyber and Dilithium, alongside FrodoKEM, SABER, NTRU LPRime, Falcon, and NTRU-HPS/HRSS. For the first five families, under polynomial moduli and polylogarithmic coefficient scales, the algorithm recovers the short secret component in expected subexponential time and memory. For schemes based on quotient relations such as Falcon and cyclic NTRU, the authors developed an affine slice search guided by estimated Gaussian masses. That search recovers equivalent signing keys or key cores with high probability within subexponential bounds.
Why it matters
Through mathematical proofs, the work shows that classical algorithms can recover secrets in subexponential time for problem families associated with all seven third-round NIST lattice candidates. This defines theoretical limits on how problem hardness scales as parameters grow.
Caveats
The authors state that their results do not establish a reduction in the concrete security of the currently specified parameter sets. The proofs apply to growing parameter families under specific modulus conditions, and the work is a preprint.
In this paper
secret recovery in NIST third-round lattice families
- Methods
- shifted sampler of Aggarwal, Dadush, and Stephens-DavidowitzBucketAndCombine
What it shows
- For quotient relations, the slice search recovers an equivalent Falcon signing key with high probability in subexponential time and space.
The algorithm then recovers an equivalent signing key with high probability in time and space 2^(O(n/lnln n)).
Abstract
- The subexponential results do not establish a reduction in the concrete security of the currently specified parameter sets.
Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.
Abstract
- For strongly conditionally similar lists, the empirical average of any bounded function concentrates around its Gaussian mean.
If (\mathbf{X}_{1},\ldots,\mathbf{X}_{N}) is strongly conditionally \gamma -similar to D, where 0≤\gamma≤ 1, then for every function H with values in [-1,1] and every u>0,
Lemma 3.1.
- Cyclic pairing of a strongly conditionally similar input list produces an output list with doubled variance and bounded similarity growth.
If \gamma≥ 0, 0<\varepsilon≤ 1/2, t≥\sqrt{2}\eta_{\varepsilon}(L), and the input list is strongly conditionally \gamma -similar to D_{L^{\prime},t}, then the output list is strongly conditionally (4\gamma+3\varepsilon) -similar to D_{L,\sqrt{2}t}.
Lemma 3.2 (Correctness and distribution of cyclic pairing).
Quoted word for word from the full text on arXiv.
The paper
Provable Subexponential Algorithms for NIST Third-Round Lattice Families
arXiv, Oct 8, 2026, Open access, CC BY, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.11254
arXiv:2610.11254v1 in cs.CR
Cite as BibTeX
@misc{gao2026provable,
title = {Provable Subexponential Algorithms for NIST Third-Round Lattice Families},
author = {Gao, Yiming and Han, Xuyuan and Hu, Honggang},
year = {2026},
eprint = {2610.11254},
archivePrefix = {arXiv},
primaryClass = {cs.CR},
doi = {10.48550/arxiv.2610.11254},
url = {https://arxiv.org/abs/2610.11254}
}