Cryptology ePrint Archive: Report 2012/699

Is Public-Key Encryption Based on LPN Practical?

Ivan Damg{\aa}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.

Category / Keywords: implementation / LPN, public key encryption, implementation

Date: received 11 Dec 2012, last revised 19 Aug 2013

Contact author: sunoo at mit edu

Available format(s): PDF | BibTeX Citation

Note: This version takes into account the recent attacks on LPN that invalidated the conclusions of the previous version.

Version: 20130820:005829 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]