Cryptology ePrint Archive: Report 2012/513

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

Abhishek Jain and Stephan Krenn and 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.

Category / Keywords: cryptographic protocols / commitment schemes, Learning Parity with Noise, Zero-Knowledge Proofs of Knowledge

Publication Info: extended abstract appears in ASIACRYPT 2012

Date: received 3 Sep 2012, last revised 25 Sep 2012

Contact author: stephan krenn at ist ac at

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20120925:091138 (All versions of this report)

Discussion forum: Show discussion | Start new discussion