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 $\Sigma$-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages $\vm_0,\ldots,\vm_u$, are such that $\vm_0=C(\vm_1,\ldots,\vm_u)$ for any circuit $C$. To get soundness which is exponentially small in a security parameter $t$, and when the zero-knowledge property relies on the LPN problem with secrets of length $\ell$, our $3$ round protocol has communication complexity $\bigO(t|C|\ell\log(\ell))$ and computational complexity of $\bigO(t|C|\ell)$ 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},
      note = {\url{https://eprint.iacr.org/2012/513}},
      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.