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.3 Bit Commitments

The zero-knowledge proof system for Graph Isomorphism is interesting, but it would be more useful to have zero-knowledge proof systems for problems that are known to be NP-complete. There is theoretical evidence that perfect zero-knowledge proofs do not exist for NP-complete problems. However, we can describe proof systems that attain a slightly weaker form of zero-knowledge called computational zero-knowledge. The actual proof systems are described in the next section; in this section we describe the technique of bit commitment that is an essential tool used in the proof system.

Suppose Peggy writes a message on a piece of paper, and then places the message in a safe for which she knows the combination. Peggy then gives the safe to Vic. Even though Vic doesn’t know what the message is until the safe is opened, we would agree that Peggy is committed to her message because she cannot change it. Further, Vic cannot learn what the message is (assuming he doesn’t know the combination of the safe) unless Peggy opens the safe for him. (Recall that we used a similar analogy in Chapter 4 to describe the idea of a public-key cryptosystem, but in that case, it was the recipient of the message, Vic, who could open the safe.)

Suppose the message is a bit b = 0 or 1, and Peggy encrypts b in some way. The encrypted form of b is sometimes called a blob and the encryption method is called a bit commitment scheme. In general, a bit commitment scheme will be a function f : {0, 1} × X → Y, where X and Y are finite sets. An encryption of b is any value f(b, x), x ∈ X. We can informally define two properties that a bit commitment scheme should satisfy:

concealing: For a bit b = 0 or 1, Vic cannot determine the value of b from the blob f(b, x).
binding: Peggy can later “open” the blob, by revealing the value of x used to encrypt b, to convince Vic that b was the value encrypted. Peggy should not be able to open a blob as both a 0 and a 1.

If Peggy wants to commit any bitstring, she simply commits every bit independently.

One way to perform bit commitment is to use the Goldwasser-Micali Probabilistic Cryptosystem described in Section 12.4. Recall that in this system, n = pq, where p and q are primes, and . The integers n and m are public; the factorization n = pq is known only to Peggy. In our bit commitment scheme, we have and

Peggy encrypts a value b by choosing a random x and computing y = f(b, x); the value y comprises the blob.

Later, when Peggy wants to open y, she reveals the values b and x. Then Vic can verify that

Let us think about the concealing and binding properties. A blob is an encryption of 0 or of 1, and reveals no information about the plaintext value x provided that the Quadratic Residues problem is infeasible (we discussed this at length in Chapter 12). Hence, the scheme is concealing.

Is the scheme binding? Let us suppose not; then

for some . But then

which is a contradiction since .

We will be using bit commitment schemes to construct zero-knowledge proofs. However, they have another nice application, to the problem of coin-flipping by telephone. Suppose Alice and Bob want to make some decision based on a random coin flip, but they are not in the same place. This means that it is impossible for one of them to flip a real coin and have the other verify it. A bit commitment scheme provides a way out of this dilemma. One of them, say Alice, chooses a random bit b, and computes a blob, y. She gives y to Bob. Now Bob guesses the value of b, and then Alice opens the blob to reveal b. The concealing property means that it is infeasible for Bob to compute b given y, and the binding property means that Alice can’t “change her mind” after Bob reveals his guess.

We now give another example of a bit commitment scheme, this time based on the Discrete Logarithm problem. Recall from Section 5.1.2 that if p = 3 (mod 4) is a prime such that the Discrete Logarithm problem in is infeasible, then the second least significant bit of a discrete logarithm is secure. Actually, it has been proved for primes p ≡ 3 (mod 4) that any Monte Carlo algorithm for the Second Bit problem having error probability 1/2 = ∈ with ∈ > 0 can be used to solve the Discrete Log problem in . This much stronger result is the basis for the bit commitment scheme.

This bit commitment scheme will have X = {1, …, p - 1} and . The second least significant bit of an integer x, denoted by SLB(x), is defined as follows:

The bit commitment scheme f is defined by

In other words, a bit b is encrypted by choosing a random element having second last bit b, and raising α to that power modulo p. (Note that SLB(p - x) ≠ SLB (x) since p ≡ 3 (mod 4).)

The scheme is binding, and by the remarks made above, it is concealing provided that the Discrete Logarithm problem in is infeasible.

Table of Contents