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.
Contents
- Scheme definition
- Key generation
- Message encryption
- Message decryption
- Security and efficiency
- References
The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value
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.
Scheme definition
Note that the following description is a draft, and may contain errors!
Blum-Goldwasser 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
To allow for decryption, the modulus used in Blum-Goldwasser encryption should be a Blum integer. This value is generated in the same manner as an RSA modulus, except that the prime factors
- Alice generates two large prime numbers
p and q such that p ≠ q , randomly and independently of each other, wherep ≡ q ≡ 3 mod4 . - Alice computes
N = p q .
The public key is
- Alice keeps the private key secret.
- Alice gives
N to Bob.
Message encryption
Suppose Bob wishes to send a message m to Alice:
- Bob first encodes
m as a string ofL bits( m 0 , … , m L − 1 ) . - Bob selects a random element
r , where1 < r < N , and computesx 0 = r 2 m o d N . - Bob uses the BBS pseudo-random number generator to generate
L random bitsb → = ( b 0 , … , b L − 1 ) (the keystream), as follows:- For
i = 0 toL : - Set
b i x i - Increment
i . - Compute
x i = ( x i − 1 ) 2 m o d N .
- For
- Bob computes the ciphertext bits using the bits from the BBS as a stream cipher keystream, XORing the plaintext bits with the keystream:
- For
i = 0 toL − 1 : -
c → = m → ⊕ b →
- For
- Bob sends a message to Alice -- the enciphered bits and the final
x L ( c 0 , … , c L − 1 ) , x L
(The value
To improve performance, the BBS generator can securely output up to
Message decryption
Alice receives
- Using the prime factorization
( p , q ) , Alice computesr p = y ( ( p + 1 ) / 4 ) L m o d p andr q = y ( ( q + 1 ) / 4 ) L m o d q . - Compute the initial seed
x 0 = ( q ( q − 1 m o d p ) r p + p ( p − 1 m o d q ) r q ) m o d N - From
x 0 b → - Compute the plaintext by XORing the keystream with the ciphertext:
m → = c → ⊕ b →
Alice recovers the plaintext
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
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.