Cryptography: Theory and Practice:Zero-knowledge Proofs

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

Previous Table of Contents Next


Chapter 13
Zero-knowledge Proofs

13.1 Interactive Proof Systems

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:

1.  receive a message from the other party
2.  perform a private computation
3.  send a message to the other party.

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 Vic’s 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

completeness
If x is a yes-instance of the decision problem II, then Vic will always accept Peggy’s proof.
soundness
If x is a no-instance of II, then the probability that Vic accepts the proof is very small.

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  Peggy’s non-isomorphic graphs and Vic’s 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 Vic’s computations are all polynomial-time. We cannot say anything about Peggy’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net