Cryptography Reference
In-Depth Information
decrypt messages because knowledge of the factorization of
n
makes it easy to decide
whether an element of
Z
n
is a quadratic residue or not: the receiver just computes
the Lagrange symbol of the ciphertext with respect to the primes
p
and
q
. If both
are equal to
+
1 then the plaintext is a bit '0' by Proposition 2.14 and if both are
equal to
−
1 then the plaintext is '1' (the mixed case in which one of the Lagrange
symbols is
1 cannot happen because, by construction, the Jacobi
symbol—and hence the product of the two Lagrange symbols—is equal to
+
1 and the other is
−
1).
This setup seems OK except for one thing: given only
n
there is no known efficient
way, in general, to randomly chose an element in
+
1
n
. This problem can be solved
by adding something else to the public key, namely, a randomly chosen element
x
QN
1
n
, which can easily be obtained by the key generation algorithm with the
help of the factorization of
n
, as it suffices to ensure that the Legendre symbol with
respect to both prime factors
p
and
q
is
←
QN
1
n
−
1. Once this element
x
←
QN
is added
to
n
to form the public key, it is easy to choose random elements in both
QR
n
and
Z
n
and squares it; in
the second, one chooses a random quadratic residue as before and then multiplies it
by
x
. The resulting element is a quadratic non-residue modulo
p
and also modulo
q
and its Jacobi symbol with respect to
n
is 1, so it is indeed an element of
1
QN
n
. In the first case one just chooses a random element of
1
n
.
Bearing in mind these remarks, the Goldwasser-Micali encryption scheme may
be described as follows:
QN
Definition 8.19
The
Goldwasser-Micali
public-key encryption scheme is defined
by the following algorithms:
Gen
: On input 1
k
, run the modulus generation algorithm to obtain
•
(
n
,
p
,
q
)
such
n
.
that
n
=
pq
, where
p
and
q
are random primes of length
k
, and choose
x
←
QN
The public key is
pk
=
(
n
,
x
)
and the private key is
sk
=
(
p
,
q
)
.
•
Enc
: On input a public key
pk
=
(
n
,
x
)
and a message
m
∈{
0
,
1
}
, choose a
x
m
r
2
∈ Z
n
.
random element
r
← Z
n
and output the ciphertext
c
=
(
·
)
mod
n
∈ Z
n
, compute
p
•
Dec
: On input a private key
sk
=
(
p
,
q
)
and a ciphertext
c
and
q
. If both values are 1 then output
m
=
0, otherwise (i.e., if both values are
−
1) output
m
=
1.
Exercise 8.35
Prove the correctness of the Goldwasser-Micali encryption scheme
by showing that, for each public key/private key pair and each
m
∈{
0
,
1
}
,
Dec
(
sk
,
Enc
(
pk
,
m
))
=
m
.
Exercise 8.36
Prove that if the QR problem is hard relative to the modulus genera-
tion algorithm, then the Goldwasser-Micali encryption scheme is CPA secure.
Exercise 8.37
Write, along the lines of the preceding ones, a Maple implementation
of the Goldwasser-Micali encryption scheme and use it to encrypt/decrypt (very)
short messages (see remark below about message expansion).
Remark 8.8
An important drawback that makes the Goldwasser-Micali encryption
scheme unsuitable for practical use is its inefficiency, since encryption requires either
