---
res:
bibo_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 Σ-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.\r\n\r\nTo 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Abhishek
foaf_name: Jain, Abhishek
foaf_surname: Jain
- foaf_Person:
foaf_givenName: Stephan
foaf_name: Krenn, Stephan
foaf_surname: Krenn
foaf_workInfoHomepage: http://www.librecat.org/personId=329FCCF0-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Aris
foaf_name: Tentes, Aris
foaf_surname: Tentes
bibo_doi: 10.1007/978-3-642-34961-4_40
bibo_volume: 7658
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Commitments and efficient zero knowledge proofs from learning parity
with noise@
...