### Better Key Sizes (and Attacks) for LWE-Based Encryption

Richard Lindner and Chris Peikert

##### Abstract

We analyze the concrete security and associated key sizes for theoretically sound lattice-based encryption schemes based on the learning with errors'' (LWE) problem. Our main contributions are (1)~a new, detailed model and experimental analysis of how basis-reduction and post-reduction attacks perform on the specific family of random lattices arising from the use of LWE, and (2)~concrete parameters and security estimates for an LWE-based cryptosystem that is more compact and efficient than the more well-known schemes from the literature. For security levels exceeding that of a $128$-bit symmetric cipher, our new key sizes are at least $10$ times smaller than prior recommendations.

Note: Bug found in concrete bit security estimates; revision available shortly.

Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of paper in CT-RSA 2011
Keywords
lattice-based cryptographybasis reductionlearning with errors
Contact author(s)
cpeikert @ cc gatech edu
History
2010-11-24: withdrawn