Cryptography Reference
In-Depth Information
we combine the following two observations (which also rely on the efficient
implementation of
P
):
1.
The distributions of the common reference string
are indeed very different in the
two cases (i.e., real execution versus simulator's output). Yet, by the pseudoran-
domness of
G
, this difference is computationally indistinguishable. Thus, the ver-
ifier's view in real execution is computationally indistinguishable from its view
in the case in which the common reference string is selected exactly as in the
simulation (but the prover acts as in Construction 4.10.12).
2.
The zero-knowledge property of
P
implies that
P
is witness-indistinguishable (as
defined in Section 4.6). Thus, one cannot distinguish the case in which
P
uses a
witness for
x
L
(as in Construction 4.10.12) from the case in which
P
uses as
witness a seed for the pseudorandom sequence
p
(as done by the simulator). The
same holds when repeating the proving process polynomially many times.
∈
In other words, the zero-knowledge claim is proved by using a hybrid argument,
where the (single) intermediate hybrid corresponds to executing the prover strat-
egy (as is) on a pseudorandom reference string as produced by the simulator
(rather than on a truly random reference string). These two observations establish
that this intermediate hybrid is computationally indistinguishable from both of
the extreme hybrids (which are the ensembles we wish to relate).
Using Theorem 4.10.10 and Proposition 4.10.13, we obtain the following:
Theorem 4.10.14:
Assuming the existence of families of trapdoor permutations,
27
each language in
NP
has an
unboundedly
zero-knowledge non-interactive proof
system. Furthermore, the prover can be implemented by a probabilistic polynomial-
time machine that gets an
NP
-witness as auxiliary input.
4.10.3.2. Adaptive Zero-Knowledge
As mentioned in Section 4.10.1, the definitions used thus far are non-adaptive. This
refers to both the soundness and the zero-knowledge conditions. (The same applies
also to the completeness condition; but because all commonly used schemes have
perfect completeness,
28
this issue is of little interest). In the adaptive analogies, the
common input is adversarially selected after the common reference string is fixed. The
formulation of adaptive soundness is straightforward, and we call the reader's attention
to the formulation of adaptive zero-knowledge.
Definition
4.10.15
(Non-Interactive
Zero-Knowledge
Proofs,
Adaptive
Version):
Let
(
P
V
)
be a non-interactive proof system for a language L
(
i.e., as
in Definition 4.10.1).
,
27
See footnote 25.
28
That is, for every
x
∈
L
, it actually holds that
Pr
[
V
(
x
,
R
,
P
(
x
,
R
))
=
1]
=
1.
