Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Here is how the system works. To encrypt a plaintext x, choose a randomizer and compute y = eK(x,r). Any such value y = eK(x,r) can be decrypted to x. Property 2 is stating that the probability distribution of all encryptions of x cannot be distinguished from the probability distribution of all encryptions of x′ if x′ ≠ x. Informally, an encryption of x looks like an encryption of x′. The security parameter ε should be small: in practice we would want to have for some small c > 0.
We now present the Goldwasser-Micali Probabilistic Public-key Cryptosystem in Figure 12.9. This system encrypts one bit at a time. A 0 bit is encrypted to a random quadratic residue modulo n; a 1 bit is encrypted to a random pseudo-square modulo n. When Bob recieves an element he can use his knowledge of the factorization of n to determine whether y ∈ QR(n) or whether . He does this by computing
then
Figure 12.9 Goldwasser-Micali Probabilistic Public-key Cryptosystem
A more efficient probabilistic public-key cryptosystem was given by Blum and Goldwasser. The Blum-Goldwasser Probabilistic Public-key Cryptosystem is presented in Figure 12.10. The basic idea is as follows. A random seed s0 generates a sequence of psuedorandom bits using the BBS Generator. The zis are used as a keystream, i.e., the are exclusive-ored with the plaintext bits to form the ciphertext. As well, the element mod n is transmitted as part of the ciphertext.
When Bob receives the ciphertext, he can compute s0 from , then reconstruct the keystream, and finally exclusive-or the keystream with the ciphertext bits to obtain the plaintext. We should explain how Bob derives s0 from . Recall that each si-1 is the principal square root of si. Now, n = pq with p ≡ q ≡ 3 mod 4, so the square roots of any quadratic residue x modulo p are ±x(p+1)/4. Using properties of Jacobi symbols, we have that
It follows that x(p+1)/4 is the principal square root of x modulo p. Similarly, x(q+1)/4 is the principal square root of x modulo q. Then, using the Chinese remainder theorem, we can find the principal square root of x modulo n.
Figure 12.10 Blum-Goldwasser Probabilistic Public-key Cryptosystem
More generally, will be the principal root of x modulo p and will be the principal root of x modulo q. Since has order p - 1, we can reduce the exponent modulo p - 1 in the computation mod p. In a similar fashion, we can reduce the exponent modulo q - 1. In Figure 12.10, having obtained the principal roots of modulo p and modulo q (steps 1-4 of the decryption process), the Chinese remainder theorem is used to compute the principal root of modulo n.
Here is an example to illustrate.
Example 12.6
Suppose n = 192649, as in Example 12.4. Suppose further that Alice chooses r = 20749 and wants to encrypt the 20-bit plaintext string
She will first compute the keystream
exactly as in Example 12.4, and then exclusive-or it with the plaintext, to obtain the ciphertext
which she transmits to Bob. She also computes
and sends it to Bob.
Of course Bob knows the factorization n = 383 × 503, so (p + 1)/4 = 96 and (q + 1)/4 = 126. He begins by computing
and
Next, he calculates
and
Now Bob proceeds to solve the system of congruences
to obtain Alices seed r = 20749. Then he constructs Alices keystream from r. Finally, he exclusive-ors the keystream with the ciphertext to get the plaintext.
A lengthy treatment of PRBGs can be found in the book by Kranakis [KR86]. See also the survey paper by Lagarias [LA90].
The Shrinking Generator is due to Coppersmith, Krawczyk, and Mansour [CKM94]; another practical method of constructing PBRGs using LFSRs has been given by Gunther [GU88]. For methods of breaking the Linear Congruential Generator, see Boyar [BO89].
The basic theory of secure PRBGs is due to Yao [YA82], who proved the universality of the next bit test. Further basic results can be found in Blum and Micali [BM84]. The BBS Generator is described in [BBS86]. The security of the Quadratic Residues problem is studied by Goldwasser and Micali [GM84], on which we based much of Section 12.3.1. We have, however, used the approach of Brassard and Bratley [BB88A, Section 8.6] to reduce the error probability of an unbiased Monte Carlo algorithm.
Properties of the RSA Generator are studied in Alexi, Chor, Goldreich, and Schnorr [ACGS88]. PRBGs based on the Discrete Logarithm problem are treated in Blum and Micali [BM84], Long and Wigderson [LW88], and Håstad, Schrift, and Shamir [HSS93]. A sufficient condition for the secure extraction of multiple bits per iteration of a PRBG was proved by Vazirani and Vazirani [VV84].
Figure 12.11 Discrete Logarithm Generator
The idea of probabilistic encryption is due to Goldwasser and Micali [GM84]; the Blum-Goldwasser Cryptosystem is presented in [BG85].
Previous | Table of Contents | Next |
Copyright © CRC Press LLC