![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Consider what happens during round j of the interactive proof. The probability that V*s challenge i′j = 1 is some real number p1 and the probability that his challenge i′j = 2 is 1 - p1, where p1 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 p1, 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 p1/n! if i = 1, and (1 - p1)/n! if i = 2. Next, lets 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 ij = 1 and V*s challenge is 1 is p1/2; and the probability that ij = 2 and V*s challenge is 2 is (1 - p1)/2. In each of these situations, (H, ij, ρ) 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 ij = 1. As mentioned above, the probability that V*s challenge is 1 is p1. The probability that a triple (H, 1, ρ) is written as the jth triple on the transcript during the Hence, the probability that (H, 1, ρ) is the jth triple on the transcript is The case ij = 2 is analyzed in a similar fashion: the probability that (H, 2, ρ) is written as the jth triple on the transcript is (1 - p1)/n! Hence, the two probability distributions on the partial transcripts at the end of round j are identical. By induction, the two probability distribution 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 Gi where i = 1 or 2 is chosen at random). Further, provided that Vic constructs each challenge graph by taking an isomorphic copy of either G1 or G2, 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 G1 or G2, but Vic does not know which Gi 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 didnt previously know, and (possibly) couldnt 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.
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 Vics challenge, Peggy either gives Vic a square root of y or a square root of xy.
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 log2 n rounds is only 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |