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

The fact that a simulator can forge transcripts has a very important consequence. Anything that Vic (or anyone else) can compute from the transcript could also be computed from a forged transcript. Hence, participating in the proof system does not increase Vic’s ability to perform any computation; and in particular, it does not enable Vic himself to “prove” that G₁ and G₂ are isomorphic. Moreover, Vic cannot subsequently convince someone else that G₁ and G₂ are isomorphic by showing them the transcript T, since there is no way to distinguish a legitimate transcript from one that has been forged.

We still have to make precise the idea that a forged transcript “looks like” a real one. We give a rigorous definition in terms of probability distributions.

Figure 13.6 Forging algorithm for transcripts for Graph Isomorphism

DEFINITION 13.1 Suppose that we have a polynomial-time interactive proof system for a decision problem II, and a polynomial-time simulator S. Denote the set of all possible transcripts that could be produced as a result of Peggy and Vic carrying out the interactive proof with a yes-instance x by , and denote the the set of all possible forged transcripts that could be produced by S by . For any transcript , let denote the probability that T is the transcript produced from 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 . (In other words, the set of real transcripts is identical to the set of forged transcripts, and the two probability distributions are identical.) Then we define the interactive proof system to be perfect zero-knowledge for Vic.

Of course we can define zero-knowledge however we like. But it is important that the definition captures our intuitive concept of what “zero-knowledge” should mean. We are saying that an interactive proof system is zero-knowlege for Vic if there exists a simulator that produces transcripts with an identical probability distribution to those produced when Vic actually takes part in the protocol. (This is a related but stronger concept than that of indistinguishable probability distributions that we studied in Chapter 12.) We have observed that a transcript contains all the information gained by Vic by taking part in the protocol. So it should seem reasonable to say that whatever Vic might be able to do after taking part in the protocol he could equally well do by just using the simulator to generate a forged transcript. We are perhaps not defining “knowledge” by this approach; but whatever “knowledge” might be, Vic doesn’t gain any!

We will now prove that the interactive proof system for Graph Isomorphism is perfect zero-knowledge for Vic.

THEOREM 13.1

The interactive proof system for Graph Isomorphism is perfect zero-knowledge for Vic.

PROOF Suppose that G₁ and G₂ are isomorphic graphs on n vertices. A transcript T (real or forged) contains n triples of the form (H, i, p), where i = 1 or 2, ρ is a permutation of {1, …, n}, and H is the image of G_i under the permutation ρ. Call such a triple a valid triple and denote by the set of all valid triples. We begin by computing , the number of valid triples. Evidently since each choice of i and p determines a unique graph H.

In any given round, say j, of the forging algorithm, it is clear that each valid triple (H, i, p) occurs with equal probability 1/(2 × n!). What is the probability that the valid triple (H, i, p) is the jth triple on a real transcript? In the interactive proof system, Peggy first chooses a random permutation π and then computes H to be the image of G₁ under π. The permutation ρ is defined to be π if i = 1, and it is defined to be the composition of the two permutations π and ρ if i = 2.

We are assuming that the value of i is chosen at random by Vic. If i = 1, then all n! permutations ρ are equiprobable, since ρ = π in this case and π was chosen to be a random permutation. On the other hand, if i = 2, then p = π ρ, where π is random and σ is fixed. In this case as well, every possible permutation ρ is equally probable. Now, since the two cases i = 1 and 2 are equally probable, and each permutation ρ is equally probable (independent of the value of i), and since i and p together determine H, it follows that all triples in are equally likely.

Since a transcript consists of the concatenation of n independent random triples, it follows that

for every possible transcript T.

The proof of Theorem 13.1 assumes that Vic follows the protocol when he takes part in the interactive proof system. The situation is much more subtle if Vic does not follow the protocol. Is it true that an interactive proof remains zero-knowledge even if Vic deviates from the protocol?

In the case of Graph Isomorphism, the only way that Vic can deviate from the protocol is to choose his challenges i in a non-random way. Intuitively, it seems that this does not provide Vic with any “knowledge.” However, transcripts produced by the simulator will not “look like” transcripts produced by Vic if he deviates from the protocol. For example, suppose Vic chooses i = 1 in every round of the proof. Then a transcript of the interactive proof will have i_j = 1 for 1 ≤ j ≤ n; whereas a transcript produced by the simulator will have i_j = 1 for 1 ≤ j ≤ n only with probability 2^-n.

The way around this difficulty is to show that, no matter how a “cheating” Vic deviates from the protocol, there exists a polynomial-time simulator that will produce forged transcripts that “look like” the transcripts produced by Peggy and (the cheating) Vic during the interactive proof. As before, the phrase “looks like” is formalized by saying that two probability distributions are identical.

Here is a more formal definition.

Table of Contents