Cryptography Reference
In-Depth Information
Proposition 4.3.9: The language G I has a perfect zero-knowledge interactive
proof system. Furthermore, the programs specified in Construction 4.3.8 satisfy
the following:
1. If G 1 and G 2 are isomorphic (i.e., ( G 1 ,
G 2 )
G I ), then the verifier always accepts
(when interacting with P GI ).
2. If G 1 and G 2 are not isomorphic (i.e., ( G 1 ,
G I ), then no matter with which
machine the verifier interacts, it will reject the input with probability at least 2 .
3. The prover (i.e., P GI ) is perfect zero-knowledge. Namely, for every probabilistic
polynomial-time interactive machine V , there exists a probabilistic polynomial-
time algorithm M outputting
G 2 )
def
=
1
with probability at most
2 , so that for every x
( G 1 ,
G 2 )
G I , the following two random variables are identically distributed :
view P GI
V ( x ) (i.e., the view of V after interacting with P GI , on common input x )
m ( x ) (i.e., the output of machine M , on input x , conditioned on not being
).
A zero-knowledge interactive proof system for GI with error probability 2 k (only
in the soundness condition) can be derived by executing the foregoing protocol,
sequentially , k times. We stress that in each repetition of the protocol, both the (pre-
scribed) prover and verifier must use “fresh” coin tosses that are independent of the coin
tosses used in prior repetitions of the protocol. For further discussion, see Section 4.3.4.
We remark that k parallel executions will also decrease the error in the soundness condi-
tion to 2 k , but the resulting interactive proof is not known to be zero-knowledge in the
case in which k grows faster than logarithmic in the input length. In fact, we believe that
such an interactive proof is not zero-knowledge. For further discussion, see Section 4.5.
We stress that it is not known whether or not GI
. Hence, Proposition 4.3.9
asserts the existence of a perfect zero-knowledge proof for a language not known to be
in
BPP
BPP
.
Proof: We first show that these programs indeed constitute a (general) interactive
proof system for GI . Clearly, if the input graphs G 1 and G 2 are isomorphic, then
the graph G constructed in Step P1 will be isomorphic to both of them. Hence,
if each party follows its prescribed program, then the verifier will always accept
(i.e., output 1). Part 1 follows. On the other hand, if G 1 and G 2 are not isomorphic,
then no graph can be isomorphic to both G 1 and G 2 . It follows that no matter how
the (possibly cheating) prover constructs G , there exists σ ∈{ 1 , 2 } such that G
and G σ are not isomorphic. Hence, if the verifier follows its program, then it will
reject (i.e., output 0) with probability at least
1
2 . Part 2 follows.
It remains to show that P GI is indeed perfect zero-knowledge on GI . This is
indeed the difficult part of the entire proof. It is easy to simulate the output of the
verifier specified in Construction 4.3.8 (since its output is identically 1 for inputs
in the language GI ). Also, it is not hard to simulate the output of a verifier that
follows the program specified in Construction 4.3.8, except that at termination
it will output the entire transcript of its interaction with P GI (see Exercise 12).
The difficult part is to simulate the output of an efficient verifier that deviates
arbitrarily from the specified program.
Search WWH ::




Custom Search