eprint.iacr.orgpaper

Provable Subexponential Algorithms for NIST Third-Round Lattice Families

An IACR ePrint paper by Yiming Gao, Xuyuan Han, and Honggang Hu presenting provable classical subexponential algorithms (running in roughly 2^((1/2+o(1))n/ln ln n) time/space) for recovering short secrets in growing parameter families tied to all seven NIST third-round lattice candidates: Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, Dilithium/ML-DSA, Falcon, and cyclic NTRU-HPS/HRSS. The approach extends the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and a low-error decision-LWE algorithm, using an exact squared-Euclidean-norm gap to binary-search each secret coordinate, and an "affine slice search" over the public lattice for NTRU/Falcon-type quotient relations. The authors explicitly note the subexponential complexity applies to growing/weakened parameter regimes and does not reduce the concrete security of the currently specified NIST parameter sets.