Is Public-Key Encryption Based on LPN Practical?
LPN samples are computationally very simple to generate, but the problem nevertheless seems to be very hard. The two main types of non-trivial attack on LPN are exhaustive search over possible error vectors, and the Blum-Kalai-Wasserman (BKW) algorithm. The authors conduct a practically oriented study of the cryptosystem suggested by Alekhnovich based on the Learning Parity with Noise (LPN) problem. They consider several improvements to the scheme, inspired by similar existing variants of Regev's LWEbased cryptosystem. Their 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.