Paper 2015/013

Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification

Nico Döttling

Abstract

Cryptographic schemes based on the Learning Parity with Noise (LPN) problem have several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

Note: This is the full version of the paper with the same name that will be published in the proceedings of the 18th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2015).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2015
Keywords
Low Noise LPNKey Dependent Message SecurityLPN Hardness Reduction
Contact author(s)
nico doettling @ gmail com
History
2015-01-12: revised
2015-01-12: received
See all versions
Short URL
https://ia.cr/2015/013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/013,
      author = {Nico Döttling},
      title = {Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification},
      howpublished = {Cryptology ePrint Archive, Paper 2015/013},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/013}},
      url = {https://eprint.iacr.org/2015/013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.