Paper 2010/592

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.

Metadata
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
2010-11-23: received
See all versions
Short URL
https://ia.cr/2010/592
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.