International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 03 September 2012

Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, Aris Tentes
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.