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

All the verification that Bob goes through in step (3) is to guarantee that no number appears twice in the sequence generated in step (4). Otherwise, if z_a =z_b, Alice knows that a ≤j <b.

The one drawback to this protocol is that Alice learns the result of the computation before Bob does. Nothing stops her from completing the protocol up to step (5) and then refusing to tell Bob the results in step (6). She could even lie to Bob in step (6).

Example of the Protocol

Assume they’re using RSA. Bob’s public key is 7 and his private key is 23; n =55. Alice’s secret value, i, is 4; Bob’s secret value, j, is 2. (Assume that only the values 1, 2, 3, and 4 are possible for i and j.)

(1)  Alice chooses x = 39, and c = E_B(39) = 19.

(2)  Alice computes c - i = 19 - 4 = 15. She sends 15 to Bob.

(3)  Bob computes the following 4 numbers:

y₁ = D_B(15 + 1) = 26

y₂ = D_B(15 + 2) = 18

y₃ = D_B(15 + 3) = 2

y₄ = D_B(15 + 4) = 39

He chooses p =31 and calculates:

z₁ = (26 mod 31) = 26

z₂ = (18 mod 31) = 18

z₃ = (2 mod 31) = 2

z₄ = (39 mod 31) = 8

He does all the verifications and confirms that the sequence is fine.

(4)  Bob sends Alice this sequence of numbers in this exact order:

26, 18, 2 + 1, 8 + 1, 31 = 26, 18, 3, 9, 31

(5)  Alice checks whether the 4th number in the sequence is congruent to x mod p. Since 9 ≠ 39 (mod 31), then i > j.

(6)  Alice tells Bob.

This protocol can be used to create far more complicated protocols. A group of people can conduct a secret auction over a computer network. They arrange themselves in a logical circle, and through individual pairwise comparisons, determine which is offering the highest price. In order to prevent people from changing their bids in mid-auction, some sort of bit-commitment protocol could also be used. If the auction is a Dutch auction, then the highest bidder gets the item for his highest price. If it is an English auction, then he gets the item for the second-highest price. (This can be determined by a second round of pairwise comparisons.) Similar ideas have applications in bargaining, negotiations, and arbitration.

23.15 Probabilistic Encryption

The notion of probabilistic encryption was invented by Shafi Goldwasser and Silvio Micali [624]. Although its theory makes it the most secure cryptosystem invented, its early implementation was impractical [625]. More recent implementations have changed that.

The point behind probabilistic encryption is to eliminate any information leaked with public-key cryptography. Because a cryptanalyst can always encrypt random messages with a public key, he can get some information. Assuming he has ciphertext C =E_K(M) and is trying to recover plaintext message M, he can pick a random message M' and encrypt it: C' =E_K(M'). If C'=C, then he guessed the correct plaintext. If it’s wrong, he just guesses again.

Also, no partial information is leaked about the original message. With public-key cryptography, sometimes a cryptanalyst can learn things about the bits: The XOR of bits 5, 17, and 39 is 1, and so on. With probabilistic encryption, even this type of information remains hidden.

Not a whole lot of information is to be gained here, but there are potential problems with allowing a cryptanalyst to encrypt random messages with your public key. Some information is being leaked to the cryptanalyst every time he encrypts a message. No one really knows how much.

Probabilistic encryption tries to eliminate that leakage. The goal is that no computation on the ciphertext, or on any other trial plaintexts, can give the cryptanalyst any information about the corresponding plaintext.

In probabilistic encryption, the encrypting algorithm is probabilistic rather than deterministic. In other words, a large number of ciphertexts will decrypt to a given plaintext, and the particular ciphertext used in any given encryption is randomly chosen.

C₁ = E_K(M), C₂ = E_K(M), C₃ = E_K(M),..., C_i = E_K(M)

M = D_K(C₁) = D_K(C₂) = D_K(C₃) =...= D_K(C_i)

With probabilistic encryption, a cryptanalyst can no longer encrypt random plaintexts looking for the correct ciphertext. To illustrate, assume the cryptanalyst has ciphertext Ci =E_K(M). Even if he guesses M correctly, when he encrypts E_K(M), the result will be a completely different C: C_j. He cannot compare C_i and C_j, and so cannot know that he has guessed the message correctly.

This is amazingly cool stuff. Even if a cryptanalyst has the public encryption key, the plaintext, and the ciphertext, he cannot prove that the ciphertext is the encryption of the plaintext without the private decryption key. Even if he tries exhaustive search, he can only prove that every conceivable plaintext is a possible plaintext.

Under this scheme, the ciphertext will always be larger than the plaintext. You can’t get around this; it’s a result of the fact that many ciphertexts decrypt to the same plaintexts. The first probabilistic encryption scheme [625] resulted in a ciphertext so much larger than the plaintext that it was unusable.

However, Manual Blum and Goldwasser have an efficient implementation of probabilistic encryption using the Blum Blum Shub (BBS) random-bit generator described in Section 17.9 [199].

The BBS generator is based on the theory of quadratic residues. In English, there are two primes, p and q, that are congruent to 3 modulo 4. That’s the private key. Their product, pq =n, is the public key. (Mind your ps and qs; the security of this scheme rests in the difficulty of factoring n.)

To encrypt a message, M, first choose some random x, relatively prime to n. Then compute

x₀ = x² mod n

Use x₀ as the seed of the BBS pseudo-random-bit generator and use the output of the generator as a stream cipher. XOR M, one bit at a time, with the output of the generator. The generator spits out bits b_i (the least-significant bit of x_i, where x_i =x_i-12 mod n), so

M = M₁ , M₂ , M₃ , ..., Mt

C = M₁ ⊕ b₁ , M₂ ⊕ b₂ , M₃ ⊕ b₃ , ..., Mt ⊕ bt

where t is the length of the plaintext

Append the last computed value, x_t, to the end of the message and you’re done.

The only way to decrypt this message is to recover x₀ and then set up the same BBS generator to XOR with the ciphertext. Because the BBS generator is secure to the left, the value x_t is of no use to the cryptanalyst. Only someone who knows p and q can decrypt the message.

In C, the algorithm to recover x₀ from x_t is:

int x0 (int p, int q, int n, int t, int xt)
{
     int a, b, u, v, w, z;
     /* we already know that gcd(p, q) == 1 */
     (void)extended_euclidian(p, q, &a, &b);
     u = modexp ((p+1)/4, t, p-1);
     v = modexp ((q+1)/4, t, q-1);
     w = modexp (xt%p, u, p);
     z = modexp (xt%q, v, q);
     return (b*q*w + a*p*z) % n;