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 ($\text{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 $\mathrm{\Sigma }$-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages ${\text{vm}}_0,\dots ,{\text{vm}}_u$, are such that ${\text{vm}}_0=C({\text{vm}}_1,\dots ,{\text{vm}}_u)$ 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.