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 public-key cryptosystems based on variants of the Learning Parity with Noise (LPN) problem. The main LPN variant in consideration was introduced by Alekhnovich (FOCS 2003), and we describe several improvements to the originally proposed scheme, inspired by similar existing variants of Regev's LWE-based cryptosystem. To achieve further efficiency, we propose the first public-key cryptosystem based on (a variant of) the ring-LPN problem, which is a more recently introduced LPN variant that makes for substantial improvement in terms of both time and space. For both cases, we compute the parameters required for various security levels in practice, given the best currently known attacks.

Our conclusion is that the basic LPN-based scheme is in several respects not competitive with existing practical schemes, as the public key, ciphertexts and encryption time become very large already for 80-bit security. On the other hand, the ring-LPN based scheme is far better in all these respects. Although the public key and ciphertexts are still larger than for, say, RSA at comparable security levels, they are not prohibitively large; moreover, for decryption, the scheme outperforms RSA for security levels of 112 bits or more. Thus LPN-based public-key cryptography seems to be somewhat more promising for practical use than has been generally assumed so far.

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

Date: received 11 Dec 2012, last revised 26 Jan 2014

Contact author: sunoo at csail 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: 20140126:205953 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]