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

13.5 Zero-knowledge Arguments

Let us recap the basic properties of the computational zero-knowledge proof for Graph 3-colorability presented in the last section. No assumptions are needed to prove completeness and soundness of the protocol. A computational assumption is needed to prove zero-knowledge, namely that the underlying bit commitment scheme is secure. Observe that if Peggy and Vic take part in the protocol, then Vic may later try to break the bit commitment scheme that was used in the protocol (for example, if the scheme based on quadratic residuosity were used, then Vic would try to factor the modulus). If at any future time Vic can break the bit commitment scheme, then he can decrypt the blobs used by Peggy in the protocol and extract the 3-coloring.

This analysis depends on the properties of the blobs that were used in the protocol. Although the binding property of the blobs is unconditional, the concealing property relies on a computational assumption.

An interesting variation is to use blobs in which the concealing property is unconditional but the binding property requires a computational assumption. This leads to a protocol that is known as a zero-knowledge argument rather than a zero-knowledge proof. The reader will recall that we have assumed up until now that Peggy is all-powerful; in a zero-knowledge argument we will assume that Peggy’s computations are required to be polynomial-time. (In fact, this assumption creates no difficulties, for we have already observed that Peggy’s computations are polynomial-time provided she knows one 3-coloring of G.)

Let us begin by describing a couple of bit commitment schemes of this type and then examine the ramifications of using them in the protocol for Graph 3-coloring.

The first scheme is (again) based on the Quadratic Residues problem. Suppose n = pq, where p and q are prime, and let m ∈ QR(n) (note that in the previous scheme m was a pseudo-square). In this scheme neither the factorization of n nor the square root of m should be known to Peggy. So either Vic should construct these values or they should be obtained from a (trusted) third party.

Let and Y = QR(n), and define

As before, Peggy encrypts a value b by choosing a random x and computing the blob y = f(b, x). In this scheme all the blobs are quadratic residues. Further, any y ∈ QR(n) is both an encryption of 0 and an encryption of 1. For suppose y = x² mod n and m = k² mod n. Then

This means that the concealing property is achieved unconditionally. On the other hand, what happens to the binding property? Peggy can open any given blob both as a 0 and as a 1 if and only if she can compute k, a square root of m. So, in order for the scheme to be (computationally) binding, we need to make the assumption that it is infeasible for Peggy to compute a square root of m. (If Peggy were all-powerful, then she could, of course, do this. This is one reason why we are now assuming that Peggy is computationally bounded.)

As a second bit commitment scheme of this type, we give an example of a scheme based on the Discrete Logarithm problem. Let p be a prime such that the discrete log problem in is infeasible, let α be a primitive element of and let . The value of β should be chosen by Vic, or by a trusted third party, rather than by Peggy. This scheme will have , and f is defined by

It is not hard to see that this scheme is unconditionally concealing, and it is binding if and only if it is infeasible for Peggy to compute the discrete logarithm log_α β.

Now, suppose we use one of these two bit commitment schemes in the protocol for Graph 3-colorability. It is easy to see that the protocol remains complete. But now the soundness condition depends on a computational assumption: the protocol is sound if and only if the bit commitment scheme is binding. What happens to the zero-knowledge aspect of the protocol? Because the bit commitment scheme is unconditionally concealing, the protocol is now perfect zero-knowledge rather than just computational zero-knowledge. Thus we have a perfect zero-knowledge argument.

**Table 13.1** Comparison of Properties of Proofs and Arguments
property	zero-knowledge proof	zero-knowledge argument


completeness	unconditional	unconditional
soundness	unconditional	computational
zero-knowledge	computational	perfect
binding blobs	unconditional	computational
concealing blobs	computational	unconditional

Whether one prefers an argument to a proof depends on the application, and whether one wants to make a computational assumption regarding Peggy or Vic. A comparison of the properties of proofs and arguments is summarized in Table 13.1. In the column “zero-knowledge proof,” the computational assumptions pertain to Peggy’s computing power; in the column “zero-knowledge argument,” the computational assumptions refer to Vic’s computing power.

13.6 Notes and References

Most of the material in this chapter is based on Brassard, Chaum, and Crépeau [BCC88] and on Goldreich, Micali, and Wigderson [GMW91]. The bit commitment schemes we present, and a thorough discussion of the differences between proofs and arguments, can be found in [BCC88] (however, note that the term “argument” was first used in [BC90]). Zero-knowledge proofs for Graph Isomorphism, Graph Non-isomorphism and Graph 3-colorability can be found in [GMW91]. Another relevant paper is Goldwasser, Micali, and Rackoff [GMR89], in which interactive proof systems are first defined formally. The zero-knowledge proof for Quadratic Residues is from this paper.

The idea of coin-flipping by telephone is due to Blum [BL82].

A very informal and entertaining illustration of the concept of zero-knowledge is presented by Quisquater and Guillou [QG90]. Also, see Johnson [JO88] for a more mathematical survey of interactive proof systems.

Figure 13.14 An interactive proof system for Quadratic Non-residues

Table of Contents