Paper 2023/947

Concrete Security from Worst-Case to Average-Case Lattice Reductions

Joel Gärtner, Royal Institute of Technology

A famous reduction by Regev shows that random instances of the Learning With Errors (LWE) problem are asymptotically at least as hard as a worst-case lattice problem. As such, by assuming that standard lattice problems are hard to solve, the asymptotic security of cryptosystems based on the LWE problem is guaranteed. However, it has not been clear to which extent, if any, this reduction provides support for the security of present concrete parametrizations. In this work we therefore use Regev's reduction to parametrize a cryptosystem, providing a reference as to what parameters are required to actually claim security from this reduction. This requires us to account for the concrete performance of this reduction, allowing the first parametrization of a cryptosystem that is provably secure based only on a conservative hardness estimate for a standard lattice problem. Even though we attempt to optimize the reduction, our system still requires significantly larger parameters than typical LWE-based cryptosystems, highlighting the significant gap between parameters that are used in practice and those for which worst-case reductions actually are applicable.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. AfricaCrypt 2023
Post-quantum cryptographyLattice-based cryptographyLearning With ErrorsProvable securityPublic Key Cryptography
Contact author(s)
jgartner @ kth se
2023-06-19: approved
2023-06-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joel Gärtner},
      title = {Concrete Security from Worst-Case to Average-Case Lattice Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/947},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.