Cryptography Reference
In-Depth Information
one or two modular multiplications to encrypt a single bit and decryption at least one
Legendre symbol computation per bit. Another inconvenience is the large message
expansion it produces. In contrast with the efficient schemes we have seen, which
expand messages by a small constant factor no larger than 4, the expansion factor
of Goldwasser-Micali is log
2
n
as each bit is encrypted as an element of
Z
n
. Since
a necessary condition for the hardness of the QR problem for the modulus
n
is the
hardness of factoring
n
, in order to attain practical security the modulus should have
at least 2000 bits producing a totally impractical expansion factor of at least 2000.
To prove the homomorphic property of Goldwasser-Micali, we observe that, as it
is easy to see using the multiplicative property of the Legendre symbol, the following
holds:
=
Proposition 8.8
Let n
pq, where p, q are distinct odd primes, and denote by
⊆ Z
n
. Then the following
X
·
Y the subset
{
xy
|
x
∈
X, y
∈
Y
}
for subsets X , Y
conditions hold:
(i)
QR
n
·
QR
n
⊆
QR
n
,
1
1
(ii)
QR
n
·
QN
n
⊆
QN
n
,
1
1
(iii)
n
⊆
QR
n
.
Exercise 8.38
Prove Proposition 8.8.
QN
n
·
QN
As a consequence of Proposition 8.8 it is straightforward to see that the
Goldwasser-Micali encryption scheme is homomorphic because if
c
1
,
c
2
∈ Z
n
are
two ciphertexts, then the decryption of their product is the sum of the corresponding
plaintexts
m
1
,
m
2
∈ Z
2
. Thus the decryption function is a group homomorphism
but we cannot say the same about encryption because it is probabilistic and hence it
does not define a map from the plaintext space
{
0
,
1
}
—which can be identified with
Z
n
the (additive) group
J
n
). But we can also obtain a homomorphism
from the encryption algorithm as in the following exercise:
Z
2
—to
(or to
Exercise 8.39
Z
n
and
(i) Prove that
J
n
is a subgroup of
QR
n
, in turn, is a subgroup of
J
n
.
=
(
,
)
(ii) If
pk
n
x
is a Goldwasser-Micali public key, consider the quotient
J
n
/QR
n
and show that the map
Z
2
→
J
n
/QR
n
defined by
m
→
group
Enc
(
pk
,
m
)QR
n
is a group homomomorphism (actually an isomorphism).
Exercise 8.40
Show, using the homomorphic property, that the Goldwasser-Micali
encryption scheme is not CCA secure.
8.8.2 The Paillier Encryption Scheme
In order to provide an appreciation for the advantages of homomorphic encryption
schemes, let us consider a situation in which they can be particularly useful. Suppose
that wewant to implement an electronic voting system that guarantees confidentiality,
