Cryptography Reference
In-Depth Information
8.8 Homomorphic Encryption
There are many public-key encryption schemes that we have not discussed so far and
here we will discuss some which are of special interest and, in particular, some of
the more interesting public-key
homomorphic encryption schemes
. We have already
mentioned these schemes but now we are going to discuss them in more detail
because their design has been gaining momentum in recent years with the goal of
allowing computation on encrypted data without having to decrypt it, in such a way
that the resulting data correspond to a similar computation on the plaintexts. The
rough idea to achieve this is, therefore, assuming that
(
pk
,
sk
)
is a public key/private
key pair, and
c
1
,
c
2
...
c
t
are ciphertexts such that
c
i
=
Enc
(
pk
,
m
i
)
(for
i
=
1
,...
t
and plaintexts
m
1
,
m
2
,...
m
t
), to be able to compute a certain function
f
of the
ciphertexts
c
1
,...,
c
t
to obtain a new ciphertext
f
(
c
1
,
c
2
,...,
c
t
)
such that
f
(
Dec
(
sk
,
f
(
c
1
,...,
c
t
))
=
m
1
,
m
2
,...,
m
t
),
where
f
is a known function acting on
t
-tuples of plaintexts. This gives a more
general concept of homomorphic encryption scheme, with the simplest examples
being those schemes, such as plain RSA (because of the multiplicative property)
and Elgamal (as we saw in Exercise 8.26), in which both the plaintext and the
ciphertext spaces have a group structure and the decryption algorithm preserves
the group operation and hence defines a group homomorphism. In these cases, the
roles of
f
and
f
are played by the group operations so that, if we denote these
operations multiplicatively and if
m
1
,
m
2
are messages such that
Enc
(
,
m
1
)
=
pk
c
1
and
Enc
(
pk
,
m
2
)
=
c
2
, it holds that
c
1
·
c
2
is a valid encryption of
m
1
·
m
2
and
hence
Dec
m
2
. Thus one can multiply two ciphertexts (with the
group operation in the ciphertext space) to obtain a new ciphertext that is a valid
encryption of the product of the corresponding plaintexts (with the operation defined
in the plaintext space). Next we briefly discuss another interesting homomorphic
scheme.
(
sk
,
c
1
·
c
2
)
=
m
1
·
8.8.1 The Goldwasser-Micali Encryption Scheme
When studying plain Rabin encryption, we mentioned the
quadratic residuosity
problem (QR problem
, for short), which is the problem of deciding, for a com-
posite positive integer
n
and
x
∈ Z
n
, whether
x
is a quadratic residue modulo
n
or,
more specifically, of distinguishing quadratic residues modulo
n
from quadratic non-
residues modulo
n
whose Jacobi symbol is equal to 1.
8
This problem was the basis
8
Recall from the definition of Legendre symbol and from Proposition 2.14 that if
n
=
pq
is the
∈ Z
n
is a quadratic residue modulo
n
if and
product of two distinct odd primes, then an element
x
only if
p
1and
q
1 which, in particular, implies that
n
=
=
=
1.