Cryptography Reference
In-Depth Information
be. More importantly, we introduce and discuss a more refined measure of the “actual
security” of a zero-knowledge proof, called knowledge tightness.
In order to establish common ground for comparing zero-knowledge proofs, we have
to specify a desired measure of error probability for these proofs. An instructive choice,
used in the sequel, is to consider the complexity of zero-knowledge proofs with error
probability 2
−
k
, where
k
is a parameter that may depend on the length of the common
input. Another issue to bear in mind when comparing zero-knowledge proofs concerns
the assumptions under which they are valid. Throughout this entire subsection we stick
to the assumption used thus far (i.e., the existence of one-way functions).
4.4.4.1. Standard Efficiency Measures
Natural and standard efficiency measures to be considered are as follows:
•
The
communication complexity of the proof
. The most important communication mea-
sure is the
round complexity
(i.e., the number of message exchanges). The total number
of bits exchanged in the interaction is also an important consideration.
•
The
computational complexity of the proof
(specifically, the number of elementary steps
taken by each of the parties).
Communication complexity seems more important than computational complexity as
long as the trade-off between them is “reasonable.”
To demonstrate these measures, we consider the zero-knowledge proof for
G
3
C
pre-
sented in Construction 4.4.7. Recall that this proof system has a very moderate accep-
tance gap, specifically 1
E
). Thus, Construction
4.4.7 has to be applied sequentially
k
·|
E
|
times in order to result in a zero-knowledge
proof with error probability
e
−
k
, where
e
≈
2
.
718 is the natural-logarithm base. Hence,
the round complexity of the resulting zero-knowledge proof is
O
(
k
·|
E
|
), the bit com-
plexity is
O
(
k
·|
E
|·|
V
|
/
|
E
|
, on common input graph
G
=
(
V
,
2
), and the computational complexity is
O
(
k
·|
E
|·
poly(
|
V
|
)),
where the polynomial poly(
·
) depends on the commitment scheme in use.
Much more efficient zero-knowledge proof systems can be custom-made for spe-
cific languages in
NP
. Furthermore, even if one adopts the approach of reducing the
construction of zero-knowledge proof systems for
NP
languages to the construction
NP
of a zero-knowledge proof system for a single
-complete language, efficiency
improvements can be achieved. For example, using Exercise 20, one can present
zero-knowledge proofs for the Hamiltonian-cycle problem (again with error 2
−
k
) having
round complexity
O
(
k
), bit complexity
O
(
k
·|
V
|
2
+
ε
), and computational complexity
O
(
k
0 is a constant depending on the desired security of the
commitment scheme (in Construction 4.4.7 and in Exercise 20 we chose
·|
V
|
2
+
O
(
ε
)
), where
ε>
1). Note
that complexities depending on the instance size are affected by reductions among
problems, and hence a fair comparison is obtained by considering the complexities for
the generic problem (i.e., Bounded Halting).
The round complexity of a protocol is a very important efficiency consideration, and
it is desirable to reduce it as much as possible. In particular, it is desirable to have zero-
knowledge proofs with constant numbers of rounds and negligible error probability.
This goal is pursued in Section 4.9.
ε
=
