2012 | OriginalPaper | Buchkapitel
On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations
verfasst von : Ronald Cramer, Ivan Damgård, Valerio Pastro
Erschienen in: Information Theoretic Security
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 present a protocol that allows to prove in zero-knowledge that committed values
x
i
,
y
i
,
z
i
,
i
= 1,…,
l
satisfy
x
i
y
i
=
z
i
, where the values are taken from a finite field. For error probability 2
−
u
the size of the proof is linear in
u
and only logarithmic in
l
. Therefore, for any fixed error probability, the amortized complexity vanishes as we increase
l
. In particular, when the committed values are from a field of small constant size, we improve complexity of previous solutions by a factor of
l
. Assuming preprocessing, we can make the commitments (and hence the protocol itself) be information theoretically secure. Using this type of commitments we obtain, in the preprocessing model, a perfect zero-knowledge interactive proof for circuit satisfiability of circuit
C
where the proof has size
O
(|
C
|). We then generalize our basic scheme to a protocol that verifies
l
instances of an algebraic circuit
D
over
K
with
v
inputs, in the following sense: given committed values
x
i
,
j
and
z
i
, with
i
= 1,…,
l
and
j
= 1,…,
v
, the prover shows that
D
(
x
i
,1
,…,
x
i
,
v
) =
z
i
for
i
= 1,…,
l
. The interesting property is that the amortized complexity of verifying one circuit only depends on the multiplicative depth of the circuit and not the size. So for circuits with small multiplicative depth, the amortized cost can be asymptotically smaller than the number of multiplications in
D
. Finally we look at commitments to integers, and we show how to implement information theoretically secure homomorphic commitments to integer values, based on preprocessing. After preprocessing, they require only a constant number of multiplications per commitment. We also show a variant of our basic protocol, which can verify
l
integer multiplications with low amortized complexity. This protocol also works for standard computationally secure commitments and in this case we improve on security: whereas previous solutions with similar efficiency require the strong RSA assumption, we only need the assumption required by the commitment scheme itself, namely factoring.