Subexponential time algorithms improve solving lattice-based cryptography problems
Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples
Cryptography and Security
Summary
Lattice-based cryptography problems like Learning With Errors (LWE) are important for secure communication. The authors show improvements to an existing algorithm that solves these problems faster and using fewer samples than before, under certain parameter settings. Their approach is simpler and more direct than previous complex analyses. This can help better understand the efficiency and security of cryptographic systems based on LWE.
What this means in practice
- •For cryptography engineers: Estimate the security and runtime for lattice-based cryptographic schemes with small-error LWE instances more precisely.
- •For security protocol developers: Design cryptographic protocols that account for improved algorithms solving LWE in subexponential time with fewer samples.
A theory result. No direct application yet.
Authors
Haoxing Lin, Prashant Nalini Vasudevan
Abstract
We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{κ+o(1)}$, for any fixed $κ>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = Ω(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+ω(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.