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.
Category / Keywords: public-key cryptography / Lattice-based cryptography, post-quantum cryptography, Lenstra Heuristic Date: received 12 Mar 2010, last revised 6 Oct 2010 Contact author: rueckert at cdc informatik tu-darmstadt de Available formats: PDF | BibTeX Citation Note: Mainly editorial changes and clarifications in response to comments received. Version: 20101006:091355 (All versions of this report) Discussion forum: Show discussion | Start new discussion