Cryptography Reference
In-Depth Information
8.9.1 Fully Homomorphic Encryption
The examples of homomorphic encryption schemes we have mentioned are schemes
that are homomorphic with respect to an operation involving plaintexts and another
one involving ciphertexts. But an interesting question is to extend this property to
more complex algebraic structures that involve two operations, namely to rings. The
idea is to obtain an encryption scheme that preserves both operations, i.e., such that
encryption behaves as a ring homomorphism (sometimes these schemes are called
algebraic homomorphic encryption schemes
). This idea was formulated in a some-
what different language already in 1978 when Rivest, Adleman and Dertouzos asked
in [163] for a
fully homomorphic encryption scheme
, namely an encryption scheme
endowed with an efficient algorithm
Eval
which, for any valid public key
pk
,anycir-
cuit
C
, and any ciphertexts
c
i
=
Enc
(
pk
,
m
i
)
, outputs
c
←
Eval
(
pk
,
C
,
c
1
,...,
c
t
)
,
where
c
is a valid encryption of
C
under the key
pk
. Without going into
details, we will just mention that this way one would be able to perform arbitrary
computations on encrypted data with the only restriction that they were efficiently
expressed as a circuit.
An important point to take into account in the quest for fully homomorphic encryp-
tion is that, as we have seen in all our examples, a homomorphic encryption scheme
cannot be CCA secure (in the IND-CCA2 sense) because it is clearly malleable and
an adversary, after being given the challenge ciphertext, can operate it with another
ciphertext it chooses and obtain a decryption of the new ciphertext from the oracle,
from which the decryption of the challenge ciphertext can be deduced because of
the known relation between the plaintexts. Thus homomorphic encryption is a two-
edged sword: it cannot reach the highest security level but its additional properties
make it useful in cases where CPA security is sufficient. This is, if anything, even
more so in the case of a fully homomorphic scheme, so the challenge was to find a
scheme that was, at the same time, fully homomorphic and CPA secure under some
reasonable hardness condition.
The problem was finally solved by Gentry in 2009, and we refer to [84] for a
full account and for interesting potential applications of such a scheme such as, for
example, searching encrypted databases or running programs on a cluster of remote
computers while the programs and the data are kept encrypted. Gentry's scheme
is based on
lattices
, namely, subsets of
(
m
1
,...,
m
t
)
n
obtained as linear combinations with
integer coefficients of a set of linearly independent vectors of
R
n
(called a basis
of the lattice) and, more specifically, on
ideal lattices
, which are lattices that can be
represented as ideals of a ring (i.e., as additive subgroups closed under multiplication
by elements of the ring). The ring considered for this purpose is the quotient ring of
Z[
R
modulo the ideal generated by a monic irreducible polynomial
f
of degree
n
(defined similarly to the rings
x
]
). The
elements of this ring may be identified with integer coefficient polynomials of degree
at most
n
Z
p
[
x
Z[
x
]
now replacing
Z
p
[
x
]
−
1 and both the ring and its nonzero ideals are additively isomorphic to
n
and define, in particular, lattices. Gentry's scheme is CPA secure under a lattice
problem and, while not yet efficient enough for practical use, it has opened a line
Z
