Paper 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.
Note: Contains corrected final security estimates from (withdrawn) eprint report 2010/592.
Metadata
- Available format(s)
-
PDF
- 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-30: received
- Short URL
- https://ia.cr/2010/613
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2010/613,
author = {Richard Lindner and Chris Peikert},
title = {Better Key Sizes (and Attacks) for LWE-Based Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2010/613},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/613}},
url = {https://eprint.iacr.org/2010/613}
}
