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

Shuai Han; Shengli Liu

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. ACISP 2017
Keywords: learning parity with noise key-dependent message security public-key encryption
Contact author(s): dalen17 @ sjtu edu cn
History: 2017-04-20: last of 2 revisions; 2017-04-11: received; See all versions
Short URL: https://ia.cr/2017/310
License: CC BY

BibTeX

@misc{cryptoeprint:2017/310,
      author = {Shuai Han and Shengli Liu},
      title = {{KDM}-Secure Public-Key Encryption from Constant-Noise {LPN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/310},
      year = {2017},
      url = {https://eprint.iacr.org/2017/310}
}