A Refined Analysis of the Cost for Solving LWE via uSVP

摘要: The learning with errors (LWE) problem (STOC’05) introduced by Regev is one of the fundamental problems in lattice-based cryptography. One standard strategy to solve LWE reduce it a unique SVP (\(\mathrm {\textsc {u}SVP}\)) via Kannan’s embedding and then apply lattice reduction \(\mathrm {u}SVP}\) problem. There are two methods for estimating cost solving this strategy: first method considers largeness gap (Gama-Nguyen, Eurocrypt’08) second (Alkim et al., USENIX’16) shortness projection shortest vector Gram-Schmidt vectors. These estimates have been investigated Albrecht al. (Asiacrypt’16) who present sound analysis show that experiments fit more consistently estimate. They also observe some cases even behaves better than estimate perhaps due intersection projected In work, we revisit work Alkim We report further providing comparisons suggest leads accurate prediction practice. empirical evidence confirming assumptions used Furthermore, examine gaps derived from embedded explain why preferable use \(\mu = 1\) lattice. This shows there coherent relation between {u}SVP}\). Finally, has conjectured will not happen large parameters. indeed case: no as \(\beta \rightarrow \infty \).