Paper 2017/310 Original: eprint.iacr.org/2017/310 ↗

KDM-Secure Public-Key Encryption from Constant-Noise LPN

Abstract

The Learning Parity with Noise (LPN) problem has found many applications in cryptography due to its conjectured post-quantum hardness and simple algebraic structure. Over the years, constructions of different public-key primitives were proposed from LPN, but most of them are based on the LPN assumption with _low noise_ rate rather than _constant noise_ rate. A recent breakthrough was made by Yu and Zhang (Crypto'16), who constructed the first Public-Key Encryption (PKE) from constant-noise LPN. However, the problem of designing a PKE with _Key-Dependent Message_ (KDM) security from constant-noise LPN is still open. In this paper, we present the first PKE with KDM-security assuming certain sub-exponential hardness of constant-noise LPN, where the number of users is predefined. The technical tool is two types of _multi-fold LPN on squared-log entropy_, one having _independent secrets_ and the other _independent sample subspaces_. We establish the hardness of the multi-fold LPN variants on constant-noise LPN. Two squared-logarithmic entropy sources for multi-fold LPN are carefully chosen, so that our PKE is able to achieve correctness and KDM-security simultaneously.