Paper 2012/513

Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise

Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes

Abstract

We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (\LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages \vm0,,\vmu, are such that \vm0=C(\vm1,,\vmu) for any circuit C. To get soundness which is exponentially small in a security parameter , and when the zero-knowledge property relies on the LPN problem with secrets of length , our round protocol has communication complexity and computational complexity of bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. extended abstract appears in ASIACRYPT 2012
Keywords
commitment schemesLearning Parity with NoiseZero-Knowledge Proofs of Knowledge
Contact author(s)
stephan krenn @ ist ac at
History
2012-09-25: revised
2012-09-03: received
See all versions
Short URL
https://ia.cr/2012/513
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/513,
      author = {Abhishek Jain and Stephan Krenn and Krzysztof Pietrzak and Aris Tentes},
      title = {Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/513},
      year = {2012},
      url = {https://eprint.iacr.org/2012/513}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.