Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Very informally, a zero-knowledge proof system allows one person to convince another person of some fact without revealing any information about the proof. We first discuss the idea of an interactive proof system. In an interactive proof system, there are two participants, Peggy and Vic. Peggy is the prover and Vic is the verifier. Peggy knows some fact, and she wishes to prove to Vic that she does.
It is necessary to describe the kinds of computations that Peggy and Vic will be allowed to perform, and also to describe the interaction that takes place. It is convenient to think of both Peggy and Vic as being probabilistic algorithms. Peggy and Vic will each perform private computations, and each of them has a private random number generator. They will communicate to each other through a communication channel. Initially, Peggy and Vic both possess an input x. The object of the interactive proof is for Peggy to convince Vic that x has some specified property. More precisely, x will be a yes-instance of a specified decision problem II.
The interactive proof, which is a challenge-and-response protocol, consists of a specified number of rounds. During each round, Peggy and Vic alternately do the following:
A typical round of the protocol will consist of a challenge by Vic, and a response by Peggy. At the end of the proof, Vic either accepts or rejects, depending on whether or not Peggy successfully replies to all of Vics challenges. We define the protocol to be an interactive proof system for the decision problem II if the following two properties are satisfied whenever Vic follows the protocol:
Figure 13.1 Graph Isomorphism
We will restrict our attention to interactive proof systems in which the computations performed by Vic can be done in polynomial time. On the other hand, we do not place any bound on the computation time required by Peggy (informally, Peggy is all-powerful).
We begin by presenting an interactive proof system for the problem of Graph Non-isomorphism. The Graph Isomorphism problem is described in Figure 13.1. This is an interesting problem since no polynomial-time algorithm to solve it is known, but it is not known to be NP-complete.
We will present an interactive proof system which will allow Peggy to prove to Vic that two specified graphs are not isomorphic. For simplicity, let us suppose that G1 and G2 each have vertex set {1, , n}. The interactive proof system for Graph Non-isomorphism is presented in Figure 13.2.
We present a toy example.
Example 13.1
Suppose G1 = (V, E1) and G2 = (V, E2), where V = {1, 2, 3, 4}, E1 = {12, 14, 23, 34} and E2 = {12, 13, 14, 34}.
Suppose in some round of the protocol that Vic gives Peggy the graph H = (V, E3), where E3 = {13, 14, 23, 24} (see Figure 13.3). The graph H is isomorphic to G1 (one isomorphism from H to G1 is the permutation (1 3 4 2)). So Peggy answers 1.
It is easy to see that this proof system satisfies the completeness and soundness properties. If G1 is not isomorphic to G2, then j will equal i in every round, and Vic will accept with probability 1. Hence, the protocol is complete.
Figure 13.2 An interactive proof system for Graph Non-isomorphism
Figure 13.3 Peggys non-isomorphic graphs and Vics challenge
On the other hand, suppose that G1 is isomorphic to G2. Then any challenge graph H submitted by Vic is isomorphic to both G1 and G2. Peggy has no way of determining if Vic constructed H as an isomorphic copy of G1 or of G2, so she can do no better than make a guess j = 1 or 2 for her response. The only way that Vic will accept is if Peggy is able to guess all n choices of i made by Vic. Her probability of doing this is 2-n. Hence, the protocol is sound.
Notice that Vics computations are all polynomial-time. We cannot say anything about Peggys computation time since the Graph Isomorphism problem is not known to be solvable in polynomial time. However, recall that we assumed that Peggy has infinite computing power, so this is allowed under the rules of the game.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC