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.