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 practically oriented study of the cryptosystem suggested by Alekhnovich 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. Our conclusion is that LPN-based public-key cryptography indeed seems practical although additional work is required to determine a more exact comparison to existing public key schemes.

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

Date: received 11 Dec 2012, last revised 6 Mar 2013

Contact author: sp590 at cam ac uk

Available formats: PDF | BibTeX Citation

Note: The section on parameter choices in this version of the paper assumes that the work of Levieil and Fouque (SVN 2006) is state of the art for practical attacks on LPN. After very recent work by Bernstein and Lange (report 2012/355), this is no longer the case. Our paper now mentions this recent work and the next version will take it into account in the choices of parameters.

Version: 20130307:035905 (All versions of this report)

Discussion forum: Show discussion | Start new discussion