You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Book;
Report;
Electronic Conference Proceeding
Title:
Commitments and efficient zero knowledge proofs from learning parity with noise ; LNCS
Contributor:
Jain, Abhishek
[Author];
Krenn, Stephan
[Author];
Pietrzak, Krzysztof Z
[Author];
Tentes, Aris
[Author];
Wang, Xiaoyun
[Author];
Sako, Kazue
[Author]
Published:
Springer, 2012
Published in:Jain A, Krenn S, Pietrzak KZ, Tentes A. Commitments and efficient zero knowledge proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer; 2012:663-680. doi: 10.1007/978-3-642-34961-4_40
Language:
English
DOI:
https://doi.org/10.1007/978-3-642-34961-4_40
Origination:
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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.