The Blum–Goldwasser (BG) cryptosystem is an
asymmetric key encryption algorithm
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
proposed by
Manuel Blum
Manuel Blum (born 26 April 1938) is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and ...
and
Shafi Goldwasser
en, Shafrira Goldwasser
, name = Shafi Goldwasser
, image = Shafi Goldwasser.JPG
, caption = Shafi Goldwasser in 2010
, birth_place = New York City, New York, U.S.
, birth_date =
, death_dat ...
in 1984. Blum–Goldwasser is a
probabilistic
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, ...
,
semantically secure cryptosystem with a constant-size
ciphertext expansion. The encryption algorithm implements an XOR-based
stream cipher
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
using the
Blum-Blum-Shub (BBS) pseudo-random number generator to generate the
keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext).
The "characters" in the keystream can be bits, bytes, numbers or actual char ...
. Decryption is accomplished by manipulating the final state of the BBS generator using the
private key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
, 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
where
are large
primes
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. BG has multiple advantages over earlier probabilistic encryption schemes such as the
Goldwasser–Micali cryptosystem
The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably se ...
. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e.g., hardness of the
quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
or the
RSA problem
In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a ''message'' to an ''exponent'', modulo a composite number ''N'' whose factors are not known. Thus ...
). 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
and
such that
and
.
# Compute
.
[ section "6.2.2. The Blum Blum Shub Sequence Generator"]
Then
is the public key and the pair
is the private key.
Encryption
A message
is encrypted with the public key
as follows:
# Compute the block size in bits,
.
# Convert
to a sequence of
blocks
, where each block is
bits in length.
# Select a random integer
.
# Compute
.
# For
from 1 to
## Compute
.
## Compute
the least significant
bits of
.
## Compute
.
# Finally, compute
.
The encryption of the message
is then all the
values plus the final
value:
.
Decryption
An encrypted message
can be decrypted with the private key
as follows:
# Compute
.
# Compute
.
# Compute
.
# Compute
.
# Using the
Extended Euclidean Algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ...
, compute
and
such that
.
# Compute
. This will be the same value which was used in encryption (see proof below).
can then used to compute the same sequence of
values as were used in encryption to decrypt the message, as follows.
# For
from 1 to
## Compute
.
## Compute
the least significant
bits of
.
## Compute
.
# Finally, reassemble the values
into the message
.
Example
Let
and
. Then
and
.
To encrypt the six-bit message
, we break it into two 3-bit blocks
, so
. We select a random
and compute
. Now we compute the
values as follows:
:
So the encryption is
.
To decrypt, we compute
:
It can be seen that
has the same value as in the encryption algorithm. Decryption therefore proceeds the same as encryption:
:
Proof of correctness
We must show that the value
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
is a quadratic residue modulo
. It is therefore also a quadratic residue modulo
, as are all the other
values obtained from it by squaring. Therefore, by
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \tex ...
,
. Then
:
Similarly,
:
Raising the first equation to the power
we get
:
Repeating this
times, we have
:
:
And by a similar argument we can show that
.
Finally, since
, we can multiply by
and get
:
from which
, modulo both
and
, and therefore
.
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
and the public key
. However, ciphertexts of the form
are vulnerable to an
adaptive chosen ciphertext attack
An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
in which the adversary requests the decryption
of a chosen ciphertext
. The decryption
of the original ciphertext can be computed as
.
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.
External links
Menezes, Oorschot, Vanstone, Scott: ''Handbook of Applied Cryptography'' (free PDF downloads), see Chapter 8
{{DEFAULTSORT:Blum-Goldwasser cryptosystem
Public-key encryption schemes