Paper 2012/699
Is Public-Key Encryption Based on LPN Practical?
Ivan Damgård and Sunoo Park
Abstract
We conduct a study of the cryptosystem suggested by Alekh\-novich based on the Learning Parity with Noise (LPN) problem. We consider several improvements to the scheme, inspired by similar existing variants of Regev's LWE-based cryptosystem, and compute which parameters one would need for various security levels, given the currently best known attacks. Our conclusion is that LPN-based public-key cryptography is in several respects not competitive with existing schemes, as both public key, ciphertext and encryption time become very large already for 80-bit security. There are ways to overcome some of these problems, but we do not know how to make both public key and ciphertext be small at the same time. On the other hand, decryption time seems to be competitive with existing schemes that use exponentiation to decrypt, if more than 128-bit security is desired. Thus LPN based public key encryption only seems attractive if one has a very specialized application where the time spent on decryption can be considered the only bottleneck.
Note: This version takes into account the recent attacks on LPN that invalidated the conclusions of the previous version.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- LPNpublic key encryptionimplementation
- Contact author(s)
- sunoo @ mit edu
- History
- 2014-04-21: last of 11 revisions
- 2012-12-14: received
- See all versions
- Short URL
- https://ia.cr/2012/699
- License
-
CC BY