Cryptography Reference
In-Depth Information
polynomial-time strategy
B
∗
and every polynomial
p
,thereexistsa
probabilistic polynomial-time algorithm
C
∗
such that the following two
probability ensembles are computationally indistinguishable:
}
x∈S,z∈{
0
,
1
}
p
(
|x|
)
de
= the output of
B
∗
when
having auxiliary-input
z
and interacting with
A
on common
input
x ∈ S
;and
(
A, B
∗
(
z
))(
x
)
(1)
{
de
= the output of
C
∗
on inputs
x
C
∗
(
x, z
)
(2)
{
}
x∈S,z∈{
0
,
1
}
p
(
|x|
)
∈
p
(
|x|
)
.
S
and
z
∈{
0
,
1
}
Almost all known zero-knowledge proofs are in fact auxiliary-input
zero-knowledge. As hinted above,
auxiliary-input zero-knowledge is pre-
served under sequential composition
(76). A simulator for the multiple-
session protocol can be constructed by iteratively invoking the single-
session simulator that refers to the residual strategy of the adversarial
verifier in the given session (while feeding this simulator with the tran-
script of previous sessions). Indeed, the residual single-session verifier
gets the transcript of the previous sessions as part of its auxiliary input
(i.e.,
z
in Definition 4.1). (For details, see (65, Sec. 4.3.4).)
4.3
Zero-knowledge proofs for all NP-assertions and their
applications
A question avoided so far is whether zero-knowledge proofs exist at
all. Clearly, every set in
) has a “trivial” zero-
knowledge proof (in which the verifier determines membership by
itself); however, what we seek is zero-knowledge proofs for statements
that the verifier cannot decide by itself.
Assuming the existence of “commitment schemes” (see below),
which in turn exist if one-way functions exist (101; 85),
there exist
(auxiliary-input)
zero-knowledge proofs of membership in any NP-set
(i.e., sets having eciently verifiable static proofs of membership).
These zero-knowledge proofs, first constructed by Goldreich, Micali and
Wigderson (75) (and depicted in Figure 4.2), have the following impor-
tant property: the prescribed prover strategy is ecient, provided it is
P
(or rather in
BPP
