essentially “encryptions of zero.” The list has length polynomial in l. To encrypt a bit m, the ciphertext c is (
essentially) m plus a random subset sum of the ciphertexts in the
public key. If these ciphertexts have very small noise, the
resulting ciphertext will also have small noise, and decryption will work properly: (c mod p) mod 2 will equal m, as
3. 3. how homomorphic is it?
What is the set of permitted functions that our homomorphic encryption scheme e can handle?
To answer this question, we need to analyze how the
noise grows as we add and multiply ciphertexts. Encrypte
outputs a fresh ciphertext with a small noise, at most N bits.
As we Adde, Sube, or Multe ciphertexts, the output ciphertext
becomes more noisy. Multiplication tends to increase the
noise faster than addition or subtraction. In particular, for
ciphertexts c1 and c2 with k1- and k2-bit noises, the ciphertext
c ¬ c1 • c2 has (roughly) (k1 + k2)-bit noise.
What happens when we perform many Adde, Sube, and
Multe operations, as prescribed by the circuit representing
a function f Similar to what we saw above with multiplication, we have
f †(c1, ..., ct) = f †(m¢ 1, ..., m¢t) + pq¢
for some integer q¢, where m¢t is the noise associated to ci.
If |f †(m¢ 1, ..., m¢t)|< p/2, then ( f †(c1, …, ct) mod p) equals
f †(m¢ 1, ..., m¢t). And if we reduce this result modulo 2, we
obtain the correct result: f (m1, …, mt).
In short, the functions that e can handle are those for
which | f † (a1, …, at)| is always less than p/2 if all of the ai are
at most N bits.
e is already quite powerful. As an example, it can handle an elementary symmetric polynomial of degree d in t
variables, as long as 2Nd • ( t d) < p/2, which is true (roughly)
when d < P/(N • log t). For our suggested parameters, this
degree can be quite large: l/(log t) = W(l/log l). That e can
evaluate polynomials of such high degree makes it “
homomorphic enough” for many applications. For example, it
works well when f is a highly parallelizable function—e.g.,
a basic keyword search—in which case f has fairly low
3. 4. Semantic security and approximate GCDs
Euclid showed that, given two integers x1 and x2, it is easy to
compute their greatest common divisor (gcd). But suppose
that x1 = s1 + p • q1 and x2 = s2 + p • q2 are near-multiples of p,
with s1 and s2 much smaller than p. When p is only an approximate gcd, is it still possible to compute p efficiently—i.e., in
time polynomial in the bit-lengths of x1 and x2 Not in general, as far as we know.
In fact, if we sample si, p and qi with l, l2, and l5 bits (
similar to our scheme e), then the approximate gcd problem seems
to remain hard even if we are given arbitrarily many samples
xi = si + p • qi, rather than just two. For these parameters,
known attacks—including those using continued fractions
and simultaneous diophantine approximation—take time
essentially exponential in l.
Moreover, we can reduce the approximate gcd problem
to the security of our somewhat homomorphic encryption
scheme. That is, we can prove that an attacker cannot efficiently break the semantic security of our encryption scheme
unless the approximate gcd problem is easy.
4. BootStRAPPABLe enCRYPtIon
4. 1. Alice’s eureka moment
One night, Alice dreams of immense riches, caverns piled
high with silver, gold, and diamonds. Then, a giant dragon
devours the riches and begins to eat its own tail! She awakes
with a feeling of peace. As she tries to make sense of her
dream, she realizes that she has the solution to her problem. She knows how to use her defective boxes to securely
delegate the assembly of even the most intricate pieces!
Like before, she gives a worker a glovebox, box #1, containing the raw materials. But she also gives him several additional gloveboxes, where box #2 contains (locked inside) the
key to box #1, box #3 contains the key to box #2, and so on.
To assemble an intricate design, the worker manipulates the
materials in box #1 until the gloves stiffen. Then, he places
box #1 inside box #2, where the latter box already contains a
the key to box #1. Using the gloves for box #2, he opens box
#1 with the key, extracts the partially assembled trinket, and
continues the assembly within box #2 until its gloves stiffen.
He then places box #2 inside box #3, and so on. When the
worker finally finishes his assembly inside box n, he hands
the box to Alice.
Of course, Alice observes, this trick does not work unless
the worker can open box i within box #(i + 1), and still
have time to make a little bit of progress on the assembly,
all before the gloves of box #(i + 1) stiffen. But as long as the
unlocking operation (plus a little bit of assembly work) takes
less than a minute, and as long as she has enough defective
gloveboxes, then it is possible to assemble any piece, no
matter how complicated!
4. 2. A dream deciphered
In the analogy, the defective gloveboxes represent our somewhat homomorphic encryption scheme, which can perform
Add, Sub, and Mult operations on ciphertexts for a little
while—it can handle functions in a limited set Fe—until the
noise becomes too large. What we would like to do is use this
somewhat homomorphic scheme to construct a fully homomorphic one.
As before, box #1 with the precious materials inside
represents the ciphertexts that encrypt the initial data. Box
#(i + 1) with the key for box i inside represents an encrypted
secret decryption key—i.e., ski encrypted under pki+ 1.
In the analogy, Alice discovers that there is only one thing
that her workers really need to be able to do in less than
1min with the gloves, aside from performing a very small
operation on the piece: unlock box i within box #(i + 1) and
extract the piece. It will turn out that there is only one function that our scheme e really needs to be able to handle, with
a tiny bit of room left over to perform one more Add, sub,
or Mult: the decryption function (which is like unlocking the