![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
DEFINITION 13.2 Suppose that we have a polynomial-time interactive proof system for a given decision problem II. Let V* be any polynomial-time probabilistic algorithm that (a possibly cheating) verifier uses to generate his challenges. (That is, V* represents either an honest or cheating verifier.) Denote the set of all possible transcripts that could be produced as a result of Peggy and V* carrying out the interactive proof with a yes-instance x of II by In the special case where V* is the same as Vic (i.e., when Vic is honest), the above definition is exactly the same as what we defined as perfect zero-knowledge for Vic. In order to prove that a proof system is perfect zero-knowledge, we need a generic transformation which will construct a simulator S* from any V*. We proceed to do this for the proof system for Graph Isomorphism. The simulator will play the part of Peggy, using V* as a restartable subroutine. Informally, S* tries to guess the challenge ij that V* will make in each round j. That is, S* generates a random valid triple of the form (Hj, ij, ρj), and then executes the algorithm V* to see what its challenge is for round j. If the guess ij is the same as the challenge i′j (as produced by V*), then the triple (Hj, ij, ρj) is appended to the forged transcript. If not, then this triple is discarded, S* guesses a new challenge ij, and the algorithm V* is restarted after resetting its state to the way it was at the beginning of the current round. By the term state we mean the values of all variables used by the algorithm. We now give a more detailed description of the simulation algorithm S*. At any given time during the execution of the program V*, the current state of V* will be denoted by state(V*). A pseudo-code description of the simulation algorithm is given in Figure 13.7. It is possible that the simulator will run forever, if it never happens that ij = i′j. However, we can show that the average running time of the simulator is polynomial, and that the two probability distributions
THEOREM 13.2 The interactive proof system for Graph Isomorphism is perfect zero-knowledge. PROOF First, we observe that, regardless of how V* generates its challenges, the probability that the guess ij of S* is the same as the challenge i′j is 1/2. Hence, on average, S* will generate two triples for every triple that it concatenates to the forged transcript. Hence, the average running time is polynomial in n. The more difficult task is to show that the two probability distributions The way to handle these difficulties is to look at the probability distributions on the possible partial transcripts during the course of the simulation or interactive proof, and proceed by induction on the number of rounds. For 0 ≤ j ≤ n, we define probability distributions The case j = 0 corresponds to the beginning of the algorithm; at this point the transcript contains only the two graphs G1 and G2. Hence, the probability distributions are identical when j = 0. We use this for the start of the induction. We make an inductive hypothesis that the two probability distributions
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |