Cryptography Reference
In-Depth Information
1.
Executing Construction 4.4.7
O
(log
n
) times in parallel, where
n
is the number of vertices
in the graph, results in a zero-knowledge proof system.
2.
Executing Construction 4.4.7 more than
O
(log
n
) times (say
O
((log
n
)
(log log
n
))
times) in parallel is not known to result in a zero-knowledge proof system. (Further-
more, it is unlikely that the resulting proof system can be shown to be zero-knowledge;
see Section 4.5.4.2.)
·
The gap between these conflicting statements seems less dramatic once one real-
izes that executing Construction 4.4.7
k
(
n
)
=
O
(log
n
) times in parallel results in a
zero-knowledge proof system of knowledge tightness approximately (3
/
2)
k
(
n
)
. (See
Exercise 19.)
4.5.
∗
Negative Results
In this section we review some negative results concerning zero-knowledge. These re-
sults indicate that some of the shortcomings of the results and constructions presented in
previous sections are unavoidable. Most importantly, Theorem 4.4.11 asserts the exis-
tence of (computational) zero-knowledge interactive proof systems for
NP
, assuming
that one-way functions exist. Three questions arise naturally:
1.
Unconditional results
: Can one prove the existence of (computational) zero-knowledge
proof systems for
without making any assumptions?
2.
Perfect zero-knowledge
: Can one present perfect zero-knowledge proof systems for
NP
NP
even under some reasonable assumptions?
3.
The role of randomness and interaction
: For example, can one present error-free zero-
knowledge proof systems for
NP
?
The answers to all these questions seem to be negative.
Another important question concerning zero-knowledge proofs is their preservation
under parallel composition. We shall show that,
in general
, zero-knowledge is not pre-
served under parallel composition (i.e., there exists a pair of zero-knowledge protocols
that when executed in parallel will leak knowledge, in a strong sense). Furthermore,
we shall consider some natural proof systems, obtained via parallel composition of
zero-knowledge proofs (e.g., the one of Construction 4.4.7), and indicate that it is
unlikely that the resulting composed proofs can be proved to be zero-knowledge.
Organization.
We start by reviewing some results regarding the essential roles of both
randomness and interaction in Theorem 4.4.11 (i.e., the existence of zero-knowledge
proofs for
). For these results we also present the relatively simple proof ideas (see
Section 4.5.1). Next, in Section 4.5.2, we claim that the existence of zero-knowledge
proofs for
NP
implies some form of average-case one-way hardness, and so the as-
sumption in Theorem 4.4.11 cannot be totally eliminated. In Section 4.5.3 we consider
perfect zero-knowledge proof systems, and in Section 4.5.4, the composition of zero-
knowledge protocols.
NP
