Cryptology ePrint Archive: Report 2017/310

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

Shuai Han and Shengli Liu

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.

Category / Keywords: public-key cryptography / learning parity with noise, key-dependent message security, public-key encryption

Original Publication (with minor differences): ACISP 2017

Date: received 8 Apr 2017, last revised 19 Apr 2017

Contact author: dalen17 at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20170420:051332 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]