Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / lattice-based cryptography, basis reduction, learning with errors

Publication Info: Full version of paper in CT-RSA 2011

Date: received 21 Nov 2010, last revised 22 Nov 2010, withdrawn 23 Nov 2010

Contact author: cpeikert at cc gatech edu

Available format(s): (-- withdrawn --)

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

Version: 20101124:005704 (All versions of this report)

Short URL: ia.cr/2010/592

Discussion forum: Show discussion | Start new discussion