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 noisekey-dependent message securitypublic-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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/310}},
      url = {https://eprint.iacr.org/2017/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.