International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Estimating the Security of Lattice-based Cryptosystems

Authors:
Markus Rückert
Michael Schneider
Download:
URL: http://eprint.iacr.org/2010/137
Search ePrint
Search Google
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 classic schemes. With our work, we close this gap by providing a handy 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 \url{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 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.
BibTeX
@misc{eprint-2010-23038,
  title={Estimating the Security of Lattice-based Cryptosystems},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Lattice-based cryptography, post-quantum cryptography, Lenstra Heuristic},
  url={http://eprint.iacr.org/2010/137},
  note={ rueckert@cdc.informatik.tu-darmstadt.de 14848 received 12 Mar 2010, last revised 27 Aug 2010},
  author={Markus Rückert and Michael Schneider},
  year=2010
}