10.1007/978-3-642-34961-4_40
Jain, Abhishek
Abhishek
Jain
Krenn, Stephan
Stephan
Krenn
Pietrzak, Krzysztof Z
Krzysztof Z
Pietrzak
Tentes, Aris
Aris
Tentes
Commitments and efficient zero knowledge proofs from learning parity with noise
LNCS
Springer
2012
2018-12-11T12:00:38Z
2019-08-02T12:37:59Z
conference
https://research-explorer.app.ist.ac.at/record/2974
https://research-explorer.app.ist.ac.at/record/2974.json
482570 bytes
application/pdf
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 m_0,...,m_u, are such that m_0=C(m_1,...,m_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 l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.