Metraipolis › archive › dc_7db958ff9f76

Provable Subexponential Algorithms for NIST Third-Round Lattice Families — arXiv:2610.11254

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.11254
License (as archived)
CC0-1.0
Archived
2026-10-09T06:20:27.539Z
SHA-256 of the archived text
5956059d0f5294f53465929bab260f6d16dc07e2b0d38115cf5f2e1cb283e993
Stable URL of this page
https://metraipolis.com/documento/dc_7db958ff9f76

How to cite

Provable Subexponential Algorithms for NIST Third-Round Lattice Families — arXiv:2610.11254 — arXiv (en), https://arxiv.org/abs/2610.11254 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7db958ff9f76 (Metraipolis archive dc_7db958ff9f76, sha256 5956059d0f5294f53465929bab260f6d16dc07e2b0d38115cf5f2e1cb283e993)
BibTeX
@misc{dc7db958ff9f76,
  title = {Provable Subexponential Algorithms for NIST Third-Round Lattice Families — arXiv:2610.11254},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.11254},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7db958ff9f76; sha256 5956059d0f5294f53465929bab260f6d16dc07e2b0d38115cf5f2e1cb283e993},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11254. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2610.11254 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:50:00.814Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).