Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise
verfasst von : Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, Aris Tentes
Erschienen in: Advances in Cryptology – ASIACRYPT 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 ℓ, our 3 round protocol has communication complexity
${\mathcal O}(t|C|\ell\log(\ell))$
and computational complexity of
${\mathcal O}(t|C|\ell)$
bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.