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

Consider what happens during round j of the interactive proof. The probability that V*’s challenge i′_j = 1 is some real number p₁ and the probability that his challenge i′_j = 2 is 1 - p₁, where p₁ depends on the state of the algorithm V* at the beginning of round j. We noted earlier that in the interactive proof, all possible graphs H are chosen by Peggy with equal probability. As well, any permutation ρ occurs with equal probability, independent of the value of p₁, since all permutations are equally likely for either possible challenge i′_j. Hence, the probability that the jth triple on the transcript is (H, i, ρ) is p₁/n! if i = 1, and (1 - p₁)/n! if i = 2.

Next, let’s do a similar analysis for the simulation. In any given iteration of the repeat loop, S* will choose any graph H with probability 1/n!. The probability that i_j = 1 and V*’s challenge is 1 is p₁/2; and the probability that i_j = 2 and V*’s challenge is 2 is (1 - p₁)/2. In each of these situations, (H, i_j, ρ) is written as the jth triple on the transcript. With probability 1/2, nothing is written on the tape during any given iteration of the repeat loop.

Let us first consider the case i_j = 1. As mentioned above, the probability that V*’s challenge is 1 is p₁. The probability that a triple (H, 1, ρ) is written as the jth triple on the transcript during the iteration of the repeat loop is

Hence, the probability that (H, 1, ρ) is the jth triple on the transcript is

The case i_j = 2 is analyzed in a similar fashion: the probability that (H, 2, ρ) is written as the jth triple on the transcript is (1 - p₁)/n!

Hence, the two probability distributions on the partial transcripts at the end of round j are identical. By induction, the two probability distribution and are identical, and the proof is complete.

It is interesting also to look at the interactive proof system for Graph Non-isomorphism. It is not too difficult to prove that this proof is perfect zero-knowledge if Vic follows the protocol (i.e., if Vic chooses each challenge graph to be a random isomorphic copy of G_i where i = 1 or 2 is chosen at random). Further, provided that Vic constructs each challenge graph by taking an isomorphic copy of either G₁ or G₂, the protocol remains zero-knowledge even if Vic chooses his challenges in a non-random fashion. However, suppose that our ubiquitous troublemaker, Oscar, gives a graph H to Vic which is isomorphic to one of G₁ or G₂, but Vic does not know which G_i is isomorphic to H. If Vic uses this H as one of his challenge graphs in the interactive proof system, then Peggy will give Vic an isomorphism he didn’t previously know, and (possibly) couldn’t figure out for himself. In this situation, the proof system is (intuitively) not zero-knowledge, and it does not seem likely that a transcript could be forged by a simulator.

Figure 13.8 A perfect zero-knowledge interactive proof system for Quadratic Residues

It is possible to alter the proof of Graph Non-isomorphism so it is perfect zero-knowledge, but we will not go into the details.

We now present some other examples of perfect zero-knowledge proofs. A perfect zero-knowledge proof for Quadratic Residues (modulo n = pq, where p and q are prime) is given in Figure 13.8. Peggy is proving that x is a quadratic residue. In each round, she generates a random quadratic residue y and sends it to Vic. Then, depending on Vic’s challenge, Peggy either gives Vic a square root of y or a square root of xy.

Figure 13.9 Subgroup Membership

It is clear that the protocol is complete. To prove soundness, observe that if x is not a quadratic residue, then Peggy can answer only one of the two possible challenges since, in this case, y is a quadratic residue if and only if xy is not a quadratic residue. So Peggy will be caught in any given round of the protocol with probability 1/2, and her probability of deceiving Vic in all log₂ n rounds is only . (The reason for having log₂ n rounds is that the size of the problem instance is proportional to the number of bits in the binary representation of n, which is log₂ n. Hence, the deception probability for Peggy is exponentially small as a function of the size of the problem instance, as in the zero-knowledge proof for Graph Isomorphism.)

Perfect zero-knowledge for Vic can be shown in a similar manner as was done for Graph Isomorphism. Vic can generate a triple (y, i, z) by first choosing i and z, and then defining

Triples generated in this fashion have exactly the same probability distribution as those generated during the protocol, assuming Vic chooses his challenges at random. Perfect zero-knowledge (for an arbitrary V*) is proved by following the same strategy as for Graph Isomorphism. It requires building a simulator S* that guesses V*’s challenges and keeps only the triples where the guesses are correct.

We now present one more example of a perfect zero-knowledge proof, this one for a decision problem related to the Discrete Logarithm problem. The problem, which we call Subgroup Membership, is defined in Figure 13.9. Of course, the integer k (if it exists) is just the discrete logarithm of β.

We present a perfect zero-knowledge proof for Subgroup Membership in Figure 13.10. The analysis of this protocol is similar to the others that we have looked at; the details are left to the reader.

Figure 13.10 A perfect zero-knowledge interactive proof system for Subgroup Membership

Table of Contents