Cryptology ePrint Archive: Report 2010/613

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

Richard Lindner and Chris Peikert

Abstract: We analyze the concrete security and key sizes of theoretically sound lattice-based encryption schemes based on the ``learning with errors'' (LWE) problem. Our main contributions are: (1)~a new lattice attack on LWE that combines basis reduction with an enumeration algorithm admitting a time/success tradeoff, which performs better than the simple distinguishing attack considered in prior analyses; (2)~concrete parameters and security estimates for an LWE-based cryptosystem that is more compact and efficient than the well-known schemes from the literature. Our new key sizes are up to $10$ times smaller than prior examples, while providing even stronger concrete security levels.

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 30 Nov 2010

Contact author: cpeikert at cc gatech edu

Available formats: PDF | BibTeX Citation

Note: Contains corrected final security estimates from (withdrawn) eprint report 2010/592.

Version: 20101130:200934 (All versions of this report)

Discussion forum: Show discussion | Start new discussion