Cryptography: Theory and Practice:Zero-knowledge Proofs | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

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 . Suppose that, for every such V*, there exists an expected polynomial-time probabilistic algorithm S* = S*(V*) (the simulator) which will produce a forged transcript. Denote the set of possible forged transcripts by . For any transcript , let denote the probability that T is the transcript produced by V* taking part in the interactive proof. Similarly, for , let denote the probability that T is the (forged) transcript produced by S*. Suppose that , and for any , suppose that . Then the interactive proof system is said to be perfect zero-knowledge (without qualification).

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 i_j that V* will make in each round j. That is, S* generates a random valid triple of the form (H_j, i_j, ρ_j), and then executes the algorithm V* to see what its challenge is for round j. If the guess i_j is the same as the challenge i′_j (as produced by V*), then the triple (H_j, i_j, ρ_j) is appended to the forged transcript. If not, then this triple is discarded, S* guesses a new challenge i_j, 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 i_j = i′_j. However, we can show that the average running time of the simulator is polynomial, and that the two probability distributions and are identical.

Figure 13.7 Forging algorithm for V* for transcripts for Graph Isomorphism

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 i_j 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 and are identical. In Theorem 13.1, where Vic was honest, we were able to compute the two probability distributions and see that they were identical. We also used the fact that triples (H, i, ρ) generated in different rounds of the proof are independent. However, in the current setting, we have no way of explicitly computing the two probability distributions. Further, triples generated in different rounds of the proof need not be independent. For example, the challenge that V* presents in round j may depend in some very complicated way on challenges from previous rounds and on the way Peggy replied to those challenges.

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 and on the set of partial transcripts that could occur at the end of round j. Notice that and . Hence, if we can show that the two distributions and are identical for all j, then we will be done.

The case j = 0 corresponds to the beginning of the algorithm; at this point the transcript contains only the two graphs G₁ and G₂. 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 and on are identical, for some j ≥ 1. We now prove that the two probability distributions and on are identical.

Table of Contents