Paper 2010/137

Estimating the Security of Lattice-based Cryptosystems

Markus Rückert and Michael Schneider

Abstract

Encryption and signature schemes based on worst-case lattice problems are promising candidates for the post-quantum era, where classic number-theoretic assumptions are rendered false. Although there have been many important results and breakthroughs in lattice cryptography, the questions of how to systematically evaluate their security in practice and how to choose secure parameters are still open. This is mainly due to the fact that most security proofs are essentially asymptotic statements. In addition, the hardness of the underlying complexity assumption is controlled by several interdependent parameters rather than just a simple bit length as in many classic schemes. With our work, we close this gap by providing a framework that (1) distills a hardness estimate out of a given parameter set and (2) relates the complexity of practical lattice-based attacks to symmetric "bit security" for the first time. Our approach takes various security levels, or attacker types, into account. Moreover, we use it to predict long-term security in a similar fashion as the results that are collected on www.keylength.com. In contrast to the experiments by Gama and Nguyen (Eurocrypt 2008), our estimates are based on precisely the family of lattices that is relevant in modern lattice-based cryptography. Our framework can be applied in two ways: Firstly, to assess the hardness of the (few) proposed parameter sets so far and secondly, to propose secure parameters in the first place. Our methodology is applicable to essentially all lattice-based schemes that are based on the learning with errors problem (LWE) or the small integer solution problem (SIS) and it allows us to compare efficiency and security across different schemes and even across different types of cryptographic primitives.

Note: Mainly editorial changes and clarifications in response to comments received.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Lattice-based cryptographypost-quantum cryptographyLenstra Heuristic
Contact author(s)
rueckert @ cdc informatik tu-darmstadt de
History
2010-10-06: last of 4 revisions
2010-03-12: received
See all versions
Short URL
https://ia.cr/2010/137
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/137,
      author = {Markus Rückert and Michael Schneider},
      title = {Estimating the Security of Lattice-based Cryptosystems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/137},
      year = {2010},
      url = {https://eprint.iacr.org/2010/137}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.