Blum–Goldwasser cryptosystem

The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream.

The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value $N = pq$ where $p, q$ are large primes. BG has multiple advantages over earlier probabilistic encryption schemes such as the Goldwasser–Micali cryptosystem. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e.g., hardness of the quadratic residuosity problem or the RSA problem). Secondly, BG is efficient in terms of storage, inducing a constant-size ciphertext expansion regardless of message length. BG is also relatively efficient in terms of computation, and fares well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below).

Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.

Operation

The Blum–Goldwasser cryptosystem consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

=Key generation=

The public and private keys are generated as follows:

Choose two large distinct prime numbers $p$ and $q$ such that $p \equiv 3 \bmod{4}$ and $q \equiv 3 \bmod{4}$ .
Compute $n = pq$ .{{IETF RFC|4086}} section "6.2.2. The Blum Blum Shub Sequence Generator"

Then $n$ is the public key and the pair $(p,q)$ is the private key.

=Encryption=

A message $M$ is encrypted with the public key $n$ as follows:

Compute the block size in bits, $h = \lfloor log_2(log_2(n)) \rfloor$ .
Convert $M$ to a sequence of $t$ blocks $m_1, m_2, \dots, m_t$ , where each block is $h$ bits in length.
Select a random integer $r < n$ .
Compute $x_0 = r^2 \bmod{n}$ .
For $i$ from 1 to $t$
Compute $x_i = x_{i-1}^2 \bmod{n}$ .
Compute $p_i =$ the least significant $h$ bits of $x_i$ .
Compute $c_i = m_i \oplus p_i$ .
Finally, compute $x_{t+1} = x_t^2 \bmod{n}$ .

The encryption of the message $M$ is then all the $c_i$ values plus the final $x_{t+1}$ value: $(c_1, c_2, \dots, c_t, x_{t+1})$ .

=Decryption=

An encrypted message $(c_1, c_2, \dots, c_t, x)$ can be decrypted with the private key $(p,q)$ as follows:

Compute $d_p = ((p+1)/4)^{t+1} \bmod{(p-1)}$ .
Compute $d_q = ((q+1)/4)^{t+1} \bmod{(q-1)}$ .
Compute $u_p = x^{d_p} \bmod{p}$ .
Compute $u_q = x^{d_q} \bmod{q}$ .
Using the Extended Euclidean Algorithm, compute $r_p$ and $r_q$ such that $r_p p + r_q q = 1$ .
Compute $x_0 = u_q r_p p + u_p r_q q \bmod{n}$ . This will be the same value which was used in encryption (see proof below). $x_0$ can then used to compute the same sequence of $x_i$ values as were used in encryption to decrypt the message, as follows.
For $i$ from 1 to $t$
Compute $x_i = x_{i-1}^2 \bmod{n}$ .
Compute $p_i =$ the least significant $h$ bits of $x_i$ .
Compute $m_i = c_i \oplus p_i$ .
Finally, reassemble the values $(m_1, m_2, \dots, m_t)$ into the message $M$ .

Example

Let $p = 19$ and $q = 7$ . Then $n = 133$ and $h = \lfloor log_2(log_2(133)) \rfloor = 3$ .

To encrypt the six-bit message $101001_2$ , we break it into two 3-bit blocks $m_1 = 101_2, m_2 = 001_2$ , so $t = 2$ . We select a random $r = 36$ and compute $x_0 = 36^2 \bmod 133 = 99$ . Now we compute the $c_i$ values as follows:

: $\begin{align}
x_1 &= 99^{2} \bmod 133 = 92 = 1011100_2 ; \quad p_1 = 100_2 ; \quad c_1 = 101_2 \oplus 100_2 = 001_2 \\
x_2 &= 92^{2} \bmod 133 = 85 = 1010101_2 ; \quad p_2 = 101_2 ; \quad c_2 = 001_2 \oplus 101_2 = 100_2 \\
x_3 &= 85^{2} \bmod 133 = 43
\end{align}$

So the encryption is $(c_1 = 001_2, c_2 = 100_2, x_3 = 43)$ .

To decrypt, we compute

: $\begin{align}
d_p &= 5^3 \bmod 18 = 17 \\
d_q &= 2^3 \bmod 6 = 2 \\
u_p &= 43^{17} \bmod 19 = 4 \\
u_q &= 43^{2} \bmod 7 = 1 \\
(r_p, r_q) &= (3, -8) \text{ since } 3 \cdot 19 + (-8) \cdot 7 = 1 \\
x_0 &= 1 \cdot 3 \cdot 19 + 4 \cdot (-8) \cdot 7 \bmod 133 = 99 \\
\end{align}$

It can be seen that $x_0$ has the same value as in the encryption algorithm. Decryption therefore proceeds the same as encryption:

: $\begin{align}
x_1 &= 99^{2} \bmod 133 = 92 = 1011100_2 ; \quad p_1 = 100_2 ; \quad m_1 = 001_2 \oplus 100_2 = 101_2 \\
x_2 &= 92^{2} \bmod 133 = 85 = 1010101_2 ; \quad p_2 = 101_2 ; \quad m_2 = 100_2 \oplus 101_2 = 001_2
\end{align}$

Proof of correctness

We must show that the value $x_0$ computed in step 6 of the decryption algorithm is equal to the value computed in step 4 of the encryption algorithm.

In the encryption algorithm, by construction $x_0$ is a quadratic residue modulo $n$ . It is therefore also a quadratic residue modulo $p$ , as are all the other $x_i$ values obtained from it by squaring. Therefore, by Euler's criterion, $x_i^{(p-1)/2} \equiv 1 \mod{p}$ . Then

: $x_{t+1}^{(p+1)/4} \equiv (x_t^2)^{(p+1)/4)} \equiv x_t^{(p+1)/2} \equiv x_t(x_t^{(p-1)/2}) \equiv x_t \mod{p}$

Similarly,

: $x_t^{(p+1)/4} \equiv x_{t-1} \mod{p}$

Raising the first equation to the power $(p+1)/4$ we get

: $x_{t+1}^{((p+1)/4)^2} \equiv x_t^{(p+1)/4} \equiv x_{t-1} \mod{p}$

Repeating this $t$ times, we have

: $x_{t+1}^{(p+1)/4)^{t+1}} \equiv x_0 \mod{p}$

: $x_{t+1}^{d_p} \equiv u_p \equiv x_0 \mod{p}$

And by a similar argument we can show that $x_{t+1}^{d_q} \equiv u_q \equiv x_0 \mod{q}$ .

Finally, since $r_p p + r_q q = 1$ , we can multiply by $x_0$ and get

: $x_0 r_p p + x_0 r_q q = x_0$

from which $u_q r_p p + u_p r_q q \equiv x_0$ , modulo both $p$ and $q$ , and therefore $u_q r_p p + u_p r_q q \equiv x_0 \mod{n}$ .

Security and efficiency

The Blum–Goldwasser scheme is semantically-secure based on the hardness of predicting the keystream bits given only the final BBS state $y$ and the public key $N$ . However, ciphertexts of the form ${\vec c}, y$ are vulnerable to an adaptive chosen ciphertext attack in which the adversary requests the decryption $m^{\prime}$ of a chosen ciphertext ${\vec a}, y$ . The decryption $m$ of the original ciphertext can be computed as ${\vec a} \oplus m^{\prime} \oplus {\vec c}$ .

Depending on plaintext size, BG may be more or less computationally expensive than RSA. Because most RSA deployments use a fixed encryption exponent optimized to minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. However, as the RSA decryption exponent is randomly distributed, modular exponentiation may require a comparable number of squarings/multiplications to BG decryption for a ciphertext of the same length. BG has the advantage of scaling more efficiently to longer ciphertexts, where RSA requires multiple separate encryptions. In these cases, BG may be significantly more efficient.

References

M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information", Proceedings of Advances in Cryptology – CRYPTO '84, pp. 289–299, Springer Verlag, 1985.
Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. {{ISBN|0-8493-8523-7}}

External links

[http://www.cacr.math.uwaterloo.ca/hac/ Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8]

Category:Public-key encryption schemes