You are looking at a specific version 20130820:005829 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.