Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Unfortunately, a pair of dishonest parties can cheat. Alice and Carol, working together, can easily find out what secret Bob is getting: If they know the FBI of C_b and Bob’s encryption algorithm, they can find b such that C_b has the right FBI. And Bob and Carol, working together, can easily get all the secrets from Alice.

If you assume honest parties,there’s an easier protocol [389].

(1)  Alice encrypts all of the secrets with RSA and sends them to Bob: C_i = S_i^e mod n

(2)  Bob chooses his secret C_b, picks a random r, and sends C', to Alice.

C' = C_br^e mod n

(3)  Alice sends Bob P'.

P' = C'^d mod n

(4)  Bob calculates S_b.

S_b = P'r^-1 mod n

If the parties may be dishonest, Bob can prove in zero-knowledge that he knows some r such that C'=C_br^e mod n and keep b secret until Alice gives him P' in step (3) [246].

23.10 Fair and Failsafe Cryptosystems

Fair Diffie-Hellman

Fair cryptosystems are a way to do key escrowing in software (see Section 4.14). This example is from Silvio Micali [1084,1085]. It is patented [1086,1087].

In the basic Diffie-Hellman scheme, a group of users share a prime, p, and a generator, g. Alice’s private key is s, and her public key is t =g^s mod p.

Here’s how to make Diffie-Hellman fair (this example uses five trustees).

(1)  Alice chooses five integers, s₁ , s₂, s₃, s₄, and s₅, each less than p - 1. Alice’s private key is

s = (s₁ + s₂ + s₃ + s₄ + s₅) mod p - 1

and her public key is

t = g^s mod p

Alice also computes

t_i = g^si mod p, for i = 1 to 5

Alice’s public shares are t_i, and her private shares are s_i.

(2)  Alice sends a private piece and corresponding public piece to each trustee. For example, she sends s₁ and t₁ to trustee 1. She sends t to the KDC.

(3)  Each trustee verifies that

t_i = g^si mod p

If it does, the trustee signs t_i and sends it to the KDC. The trustee stores s_i in a secure place.

(4)  After receiving all five public pieces, the KDC verifies that

t = (t₁ * t₂ * t₃ * t₄ * t₅) mod p

If it does, the KDC approves the public key.

At this point, the KDC knows that the trustees each have a valid piece, and that they can reconstruct the private key if required. However, neither the KDC nor any four of the trustees working together can reconstruct Alice’s private key.

Micali’s papers [1084,1085] also contain a procedure for making RSA fair and for combining a threshold scheme with the fair cryptosystem, so that m out of n trustees can reconstruct the private key.

Failsafe Diffie-Hellman

Like the previous protocol, a group of users share a prime, p, and a generator, g. Alice’s private key is s, and her public key is t =g^s mod p.

(1)  The KDC chooses a random number, B, between 0 and p - 2, and commits to B using a bit-commitment protocol (see Section 4.9).

(2)  Alice chooses a random number, A, between 0 and p - 2. She sends g^A mod p to the KDC.

(3)  The user “shares” A with each trustee using a verifiable secret-sharing scheme (see Section 3.7).

(4)  The KDC reveals B to Alice.

(5)  Alice verifies the commitment from step (1). Then she sets her public key as

t = (g^A)g^B mod p

She sets her private key as

s = (A + B) mod (p - 1)

The trustees can reconstruct A. Since the KDC knows B, this is enough to reconstruct s. And Alice cannot make use of any subliminal channels to send unauthorized information. This protocol, discussed in [946,833] is being patented.

23.11 Zero-Knowledge Proofs of Knowledge

Zero-Knowledge Proof of a Discrete Logarithm

Peggy wants to prove to Victor that she knows an x that satisfies

A^x ≡ B (mod p)

where p is a prime, and x is a random number relatively prime to p - 1. The numbers A, B, and p are public, and x is secret. Here’s how Peggy can prove she knows x without revealing it (see Section 5.1) [338,337].

(1)  Peggy generates t random numbers, r₁ , r₂ , ..., r_t, where all r_i are less than p - 1.1

(2)  Peggy computes h_i = A^ri mod p, for all values of i, and sends them to Victor.

(3)  Peggy and Victor engage in a coin-flipping protocol to generate t bits: b₁, b₂ , ..., b_t.

(4)  For all t bits, Peggy does one of the following:

a)  If b_i = 0, she sends Victor r_i

b)  If b_i = 1, she sends Victor s_i = (r_i - r_j) mod (p - 1), where j is the lowest value for which b_j = 1

(5)  For all t bits, Victor confirms one of the following:

a)  If b_i = 0, that A^ri ≡ h_i (mod p)

b)  If b_i = 1, that A^si ≡ h_ih_j^-1 (mod p)

(6)  Peggy sends Victor Z, where

Z = (x - r_j) mod (p - 1)

(7)  Victor confirms that A^Z ≡ Bh_j^-1 (mod p)

Peggy’s probability of successfully cheating is 2^-t.

Zero-Knowledge Proof of the Ability to Break RSA

Alice knows Carol’s private key. Maybe she has broken RSA; maybe she has broken into Carol’s house and stolen the key. Alice wants to convince Bob that she knows Carol’s key. However, she doesn’t want to tell Bob the key or even decrypt one of Carol’s messages for Bob. Here’s a zero-knowledge protocol by which Alice convinces Bob that she knows Carol’s private key [888].