Somewhat Practical Fully Homomorphic

Encryption ?

Junfeng Fan and Frederik Vercauteren

Katholieke Universiteit Leuven, COSIC & IBBT

Kasteelpark Arenberg 10
B-3001 Leuven-Heverlee, Belgium
[email protected]

Abstract. In this paper we port Brakerski’s fully homomorphic scheme based

on the Learning With Errors (LWE) problem to the ring-LWE setting. We in-
troduce two optimised versions of relinearisation that not only result in a
smaller relinearisation key, but also faster computations. We provide a de-
tailed, but simple analysis of the various homomorphic operations, such as
multiplication, relinearisation and bootstrapping, and derive tight worst case
bounds on the noise caused by these operations. The analysis of the bootstrap-
ping step is greatly simplified by using a modulus switching trick. Finally, we
derive concrete parameters for which the scheme provides a given level of
security and becomes fully homomorphic.

1 Introduction

Fully homomorphic encryption (FHE) allows evaluation of arbitrary functions on

encrypted data, and as such has a myriad of potential applications such as private
cloud computing. Gentry [7, 8] was the first to show that FHE is theoretically possible.
His construction consisted of three parts: first, construct an encryption scheme that is
somewhat homomorphic, i.e. that can evaluate functions of limited complexity (think
low degree), secondly, simplify the decryption function of this scheme as much as
possible (so called squashing), thirdly, evaluate this simplified decryption function
homomorphically to obtain ciphertexts with a fixed inherent noise size (so called
bootstrapping).
The first variants [21, 18, 20, 4, 5] of Gentry’s scheme all followed the same struc-
ture and as such had to make additional security assumptions to enable the squashing
step. More recent schemes [9, 4, 3, 2] avoid squashing all together and can bootstrap by
evaluating the real decryption circuit. Another advantage of the more recent schemes
is that their security is based on the Learning with Errors (LWE) problem [17] or its
ring variant RLWE [15], the hardness of which can be related to classical problems
on (ideal) lattices.
?
This work was supported in part by the Research Council K.U.Leuven: GOA TENSE
(GOA/11/007), by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian
Science Policy) and by the European Commission through the ICT programme under
contract ICT-2007-216676 ECRYPT II.
 All existing schemes have the common trait that they add a small “noise” compo-
nent during encryption. Computing homomorphically on ciphertexts will cause these
noises to grow up to the point when they become so large that decryption fails.
The bootstrapping approach by Gentry can then be used to lower the noise in a
ciphertext to a fixed level determined by the complexity of the decryption circuit. Es-
pecially the noise growth caused by homomorphic multiplication has been the major
obstacle to designing efficient schemes. In the first generation of schemes, the noises
themselves multiplied upon each homomorphic multiplication leading to a doubly ex-
ponential growth in the depth of the circuit, i.e. evaluating a depth n circuit on clean
n
ciphertexts (with noise E) resulted in a noise E 2 . A first major improvement was
proposed in [3] leading to a noise level of only E n for a depth n circuit. The most
recent scheme [2] further improves on this in that the noise for each multiplication
level grows with a constant factor independent of the noise present in the ciphertext,
i.e. the noise for a depth n circuit is E · c(λ)n where c(λ) is a constant that depends
on the security parameter.
As to whether any of these proposals is really practical, the answer is simply
“no”. There have been several attempts [18, 10, 19, 16, 11] at implementing most of
the schemes mentioned, but none of them comes even close to being practical. The
most recent paper [11] manages to execute one AES encryption homomorphically
in eight days using a massive amount (tens of GBs) of RAM memory. Of course,
compared to the very first proposals, there has been a major advance in efficiency.
The main contribution of this paper is its simplicity due to our down to earth
approach, whereby any excess mathematical machinery (beautiful it may be) has
been left out. Other contributions of this paper are as follows: we port the scheme
by Brakerski [2] from the LWE setting to the RLWE setting, which in itself is rather
trivial. We provide a detailed, but simple analysis of the various homomorphic op-
erations, such as multiplication, relinearisation and bootstrapping, and derive tight
worst case bounds on the noise caused by these operations. Using a simple modu-
lus switching trick we simplify the analysis of the bootstrapping step. Combining
this with a practical security analysis of the scheme following [14], we finally obtain
concrete parameters for a fully homomorphic scheme with a given security level.
Although this paper is not about optimising the various subroutines, we do provide
two versions of relinearisation that are more efficient than the approach taken in [2].
Whenever applicable, we will mention existing optimisations that remain valid for
the proposed scheme. In a follow up paper we will consider the real practicality of
this scheme by implementing it both in software and hardware, which will show that
the title is indeed justified.
The remainder of the paper is organised as follows: Section 2 briefly recalls nota-
tion and some background on probability. Section 3 reviews a very elegant encryption
scheme based on RLWE, which will be used as the basis for the somewhat homomor-
phic scheme described in Section 4. Section 5 analyses the bootstrapping step and
determines the minimal depth at which the somewhat homomorphic scheme can be
made fully homomorphic. Section 6 uses the analysis of Lindner and Peikert [14] to
derive parameters for a fully homomorphic scheme with a given security level. Finally,
Section 7 concludes the paper and highlights work in progress.

2
2 Preliminaries
2.1 Basic Notation
The basic object we will work with is the polynomial ring R = Z[x]/(f (x)) where
f (x) ∈ Z[x] is a monic irreducible polynomial of degree d. In practice one would
typically restrict to using a cyclotomic polynomial Φm (x), i.e. the minimal polynomial
of the primitive m-th roots of unity. The most popular choice for expository purposes
is to take f (x) = xd + 1 with d = 2n .
Elements of the ring R will be denoted in lowercase bold, e.g.Pa ∈ R. The co-
d−1 i
efficients of an element a ∈ R will be denoted by ai , i.e. a = i=0 ai · x . The
infinity norm ||a|| is defined as maxi |ai | and the expansion factor of R is defined as
δR = max{||a · b||/(||a|| · ||b||) : a, b ∈ R}.
Let q > 1 be an integer, then by Zq we denote the set of integers (−q/2, q/2]. Note
that we really simply consider Zq to be a set, and as such should not be confused
with the ring Z/qZ. Similarly, we denote with Rq the set of polynomials in R with
coefficients in Zq . For a ∈ Z we denote by [a]q the unique integer in Zq with [a]q =
a mod q. In very few places we will need reduction in the interval [0, q), which will be
denoted as rq (a) (remainder modulo q).
Similarly, when a ∈ R, we denote by [a]q the element in R obtained by applying
[·]q to all its coefficients. For x ∈ R, we use bxe to denote rounding to the nearest
integer and bxc , dxe to indicate rounding up or down. Given an integer n, we denote
by size(n) its bit size, i.e. size(n) = dlog2 (n + 0.5)e. With n[i] we denote the i-th bit
(counting from 0) in the bit-expansion of |n|.
Note that all arithmetic takes place in R itself and in many cases even (tem-
porarily) in Q[x]/(f (x)). When implementing the scheme presented in this paper one
therefore has to take care precisely when the result of a computation can be reduced
modulo some integer q.

2.2 Probability
Given a probability distribution D, we use x ← D to denote that x is sampled from
D. For a set S, x ← S denotes that x is sampled uniformly from S. A distribution χ
over the integers is called B-bounded if it is supported on [−B, B].
The discrete Gaussian distribution DZ,σ over the integers is the probability dis-
tribution that assigns a probability proportional to exp(−π|x|2 /σ 2 ) to each x ∈ Z.
We note that DZ,σ is statistically indistinguishable from a B-bounded distribution
for large enough B, e.g. in practice one could take B = 10 · σ.
The discrete Gaussian distribution DZ,σ is then used to define a distribution χ
on R. The distribution χ is in general not as simple as just sampling the coefficients
according to DZ,σ . However, for the polynomial f (x) = xd + 1 with d a power of 2, we
d
can indeed define χ as DZ,σ . For more general cyclotomic polynomials, sampling from
2
χ is only slightly more involved. Recall that for the √ normal distribution N (0, σ ),
we have that Probx←N (0,σ ) [|x| > k · σ] = erf(k/ 2). As such define the function
2
√
β() := min{β | erf(β/ 2) < }, then with probability 1 −  the samples are bounded
by β · σ. For instance, if we set  = 2−64 , then it suffices to take β() > 9.2.

3
3 RLWE-based Encryption
In this section we recall a very simple and elegant encryption scheme based on the
RLWE problem introduced by Lyubashevsky, Peikert and Regev [15].

3.1 RLWE Problem

The RLWE problem is simply a ring based version of the LWE problem [17] and is
formulated as follows.
Definition 1 (Decision-RLWE). For security parameter λ, let f (x) be a cyclo-
tomic polynomial Φm (x) with deg(f ) = ϕ(m) depending on λ and set R = Z[x]/(f (x)).
Let q = q(λ) ≥ 2 be an integer. For a random element s ∈ Rq and a distribution
(q)
χ = χ(λ) over R, denote with As,χ the distribution obtained by choosing a uniformly
random element a ← Rq and a noise term e ← χ and outputting (a, [a · s + e]q ). The
(q)
Decision-RLWEd,q,χ problem is to distinguish between the distribution As,χ and the
uniform distribution U (Rq2 ).
The RLWE problem can be reduced (using a quantum algorithm) to the shortest
vector problem over ideal lattices [15]. Furthermore, one can restrict s to be sampled
from χ instead of taken uniformly in Rq without any security implications [1, 15].
Finally, we note that the hardness of the problem is independent of the precise shape
of q [13] and as such q does not has to be prime and can be taken simply as a power
of 2.

3.2 Encryption Scheme

The above decision problem immediately leads to the following encryption scheme as
described in the extended version of [15]. The plaintext space is taken as Rt for some
integer t > 1. Let ∆ = bq/tc and denote with rt (q) = q mod t then we clearly have
q = ∆ · t + rt (q). We remark that q nor t have to prime, nor that t and q are coprime.
The encryption scheme LPR.ES is then defined as follows:
– LPR.ES.SecretKeyGen(1λ ): sample s ← χ and output sk = s
– LPR.ES.PublicKeyGen(sk): set s = sk, sample a ← Rq , e ← χ and output

pk = ([−(a · s + e)]q , a) .

– LPR.ES.Encrypt(pk, m): to encrypt a message m ∈ Rt , let p0 = pk[0], p1 = pk[1],

sample u, e1 , e2 ← χ and return
 
ct = [p0 · u + e1 + ∆ · m]q , [p1 · u + e2 ]q

– LPR.ES.Decrypt(sk, ct): set s = sk, c0 = ct[0], c1 = ct[1] and compute

t · [c0 + c1 · s]q
 

q t

4
The above scheme can be shown to be semantically secure assuming the hardness of
RLWE given 3 samples [15].
To show that decryption is correct for properly encrypted ciphertexts, we prove
the following lemma.
Lemma 1. Using the notation of the above encryption scheme LPR.ES and assuming
that ||χ|| < B, we have that

[c0 + c1 · s]q = ∆ · m + v (1)

with ||v|| ≤ 2 · δR · B 2 + B. This implies that for 2 · δR · B 2 + B < ∆/2, decryption

works correctly.
Proof: Simply writing out the definition modulo q gives:

c0 + c1 · s = p0 · u + e1 + ∆ · m + p1 · u · s + e2 · s mod q
= ∆ · m + e · u + e1 + e2 · s mod q .

Since ∆ · m + e · u + e1 + e2 · s is already in Rq for small enough error terms, we con-

clude that v = e · u + e1 + e2 · s. Since e, e1 , e2 , u, s ← χ, we recover the given bound
||v|| ≤ 2 · δR · B 2 + B. Write c0 + c1 · s = ∆ · m + v + q · r, then if we divide by q and
multiply by t, we obtain m + (t/q) · (v −  · m) + t · r, where  = q/t − ∆ = rt (q)/t < 1.
For the rounding to be correct, we need (t/q) · ||v −  · m|| < 1/2 and since m ∈ Rt ,
the given bound follows. 

The term v is called the noise contained in the ciphertext and if not clear from
the context which ciphertext ct it belongs to, it will be denoted as v(ct). Looking
at the exact expression of the noise term, we see that taking u and s as small as
possible will make the noise smaller. This remark leads to the following optimisation
and corresponding assumption.
Optimisation/Assumption 1: Instead of sampling s, u ← χ, we will sample s, u
from R2 , i.e. the norm ||s|| = ||u|| = 1. We note that the noise terms e1 , e2 remain
sampled from χ. The bound in Lemma 1 is then replaced by B · (2 · δR + 1). The
security implications of this optimisation seem to be minor, at least when we make
the assumption that the results for the LWE setting carry over to the RLWE setting.
In [12], the authors show that for the standard LWE one can take the secret s from
any distribution, as long as the distribution has sufficient entropy. Assuming that the
LWE analysis also holds for the RLWE
setting, we can even use a secret with a given
low Hamming weight h, as long as hd is large enough.

4 Somewhat Homomorphic Encryption

In this section we will derive a simple somewhat homomorphic encryption scheme
FV.SH based on RLWE by using LPR.ES as a basis. In fact, FV.SH is mostly a simple
port to the RLWE stetting of the fully homomorphic scheme by Brakerski [2] based
on standard LWE.

5
 The scheme consists of an augmented version of the scheme LPR.ES introduced in
the previous section. The generation of the secret key, public key and the encryp-
tion/decryption procedures will remain exactly the same bar the fact that we use the
optimisation u, s ← R2 . The main addition to LPR.ES is a so called relinearisation key
rlk that will be used to compute a homomorphic multiplication.
The main invariant of the scheme LPR.ES is given by Equation (1), namely when
we interpret the elements of a ciphertext ct as the coefficients of a polynomial ct(x)
and evaluate this polynomial in s we obtain
[ct(s)]q = ∆ · m + v ,
from which we can easily recover the message m. Using this interpretation it is quite
easy to derive homomorphic addition FV.SH.Add and multiplication FV.SH.Mul.

Addition Let cti for i = 1, 2 be two ciphertexts, with [cti (s)]q = ∆ · mi + vi , then
it is easy to see that
[ct1 (s) + ct2 (s)]q = ∆ · [m1 + m2 ]t + v1 + v2 −  · t · r ,
where  = q/t−∆ = rt (q)/t < 1 and m1 +m2 = [m1 + m2 ]t +t·r. Note that ||r|| ≤ 1,
which implies that the noise in the sum has grown additively by a maximum of t. As
such, we can then simply define
FV.SH.Add(ct1 , ct2 ) := ([ct1 [0] + ct2 [0]]q , [ct1 [1] + ct2 [1]]q ) .

Multiplication Homomorphic multiplication consists of two steps: the first step is

quite easy, and basically consists of multiplying the polynomials ct1 (x) and ct2 (x)
together and scaling by t/q. The problem however is that we end up with a ciphertext
consisting of 3 ring elements instead of 2. The second step resolves this issue and is
called “relinearisation”.

Basic Multiplication First write the evaluation of cti (x) in s as an equality in R

as follows
cti (s) = ∆ · mi + vi + q · ri .
An easy computation shows that ||ri || < δR ·||s||. If we then multiply these expressions
together we obtain:
(ct1 · ct2 )(s) = ∆2 · m1 · m2 + ∆ · (m1 · v2 + m2 · v1 ) + q · (v1 · r2 + v2 · r1 )
(2)
+ v1 · v2 + q · ∆ · (m1 · r2 + m2 · r1 ) + q 2 · r1 · r2 .
The above expression shows that we need to scale with a factor of 1/∆ to be able to
recover a ciphertext that encrypts [m1 · m2 ]t . However, since ∆ does not necessarily
divide q, we would get a large noise caused by the rounding error of the last term.
As such, we will scale by t/q which solves this rounding issue. Let ct1 (x) · ct2 (x) =
c0 + c1 · x + c2 · x2 , then we will use the approximation
t
· (ct1 · ct2 )(s) = bt · c0 /qe + bt · c1 /qe · s + bt · c2 /qe · s2 + ra , (3)
q

6
which introduces an approximation error ra of size < (δR · ||s|| + 1)2 /2.
If we write m1 · m2 = [m1 · m2 ]t + t · rm , then ||rm || < (t · δR )/4. Similarly, if
we write v1 · v2 = [v1 · v2 ]∆ + ∆ · rv , then ||rv || < (E 2 · δR )/∆ where E is a bound
on the original noise terms, i.e. ||vi || < E. By multiplying equation (2) by t/q and
grouping terms together we obtain the somewhat complicated looking equality, where
we mainly used that t · ∆ = q − rt (q):
t · (ct1 · ct2 )(s)
= ∆ · [m1 · m2 ]t + (m1 · v2 + m2 · v1 ) + t · (v1 · r2 + v2 · r1 )
q
+ rv + (q − rt (q)) · (rm + m1 · r2 + m2 · r1 ) + q · t · r1 · r2
t rt (q)
+ · [v1 · v2 ]∆ − · (∆ · m1 · m2 + (m1 · v2 + m2 · v1 ) + rv ) .
q q
The basic idea of writing the expression like this is to make clear which terms will
disappear after reduction modulo q and which terms are affected by rounding. Note
that in the above expression all terms are integral bar the terms rr on the last line.
The rounding therefore affects the last line only, and ||rr || is easily seen to be smaller
than δR · (t + 1/2)2 + 1/2. Reducing modulo q and substituting equation (3) then
leads to
bt · c0 /qe + bt · c1 /qe · s + bt · c2 /qe · s2 q = ∆ · [m1 · m2 ]t + (m1 · v2 + m2 · v1 )
 

+ t · (v1 · r2 + v2 · r1 ) + rv − rt (q) · (rm + m1 · r2 + m2 · r1 ) + brr − ra e .

It is easy to bound the size of the new noise term in the right hand side which finally
proves the following lemma.
Lemma 2. Let cti for i = 1, 2 be two ciphertexts, with [cti (s)]q = ∆ · mi + vi and
||vi || < E < ∆/2, and let ct1 (x) · ct2 (x) = c0 + c1 · x + c2 · x2 , then
bt · c0 /qe + bt · c1 /qe · s + bt · c2 /qe · s2 q = ∆ · [m1 m2 ]t + v3 ,
 

with ||v3 || < 2 · δR · t · E · (δR · ||s|| + 1) + 2 · t2 · δR

2
· (||s|| + 1)2 .
This lemma shows that the noise does not grow quadratically upon multiplication,
2
but is only multiplied roughly by the factor 2 · t · δR · ||s||. As such we see that not
only t, but especially the norm of the secret s has a significant influence on the noise
growth. By using optimisation 1 again we have ||s|| = 1 and thus significantly limit
the growth of the noise during multiplication.

Relinearisation Using Lemma 2 we already have a ciphertext that encrypts the

multiplication of both plaintexts. However, a remaining problem is that the number
of elements in the ciphertext has gone up. To rectify this phenomenon we need a
procedure called relinearisation that takes a degree 2 ciphertext and reduces it again
to a degree 1 ciphertext. It is precisely this step that will require the introduction of
a relinearisation key rlk. Let ct = [c0 , c1 , c2 ] denote a degree 2 ciphertext, then we
need to find ct0 = [c00 , c01 ] such that
c0 + c1 · s + c2 · s2 q = [c00 + c01 · s + r]q ,
 

7
where ||r|| is small. Since s2 is not known, a first idea would be to provide a masked
version of s2 as follows (compare with LPR.ES.PublicKeyGen):
 sample a0 ← Rq , e0 ←
χ and output rlk := ( −(a0 · s + e0 ) + s2 q , a0 ). Note that rlk[0]+rlk[1]·s = s2 +e0 .
The problem however is that since c2 is a random element in Rq , the noise e0 will
be magnified too much resulting in a bad approximation of c2 · s2 and thus causing
a huge error r.

Relinearisation: Version 1 A first possible solution is to slice c2 into parts of small

norm by choosing a base T (note that T is totally independent of t) and to write c2
Pl (i)
in base T , i.e. c2 = i=0 T i · c2 mod q, with ` = blogT (q)c and the coefficients of
(i)
c2 are in RT . The relinearisation key rlk then consists of the masked versions of
T i · s2 for i = 0, . . . , `:

rlk = [( −(ai · s + ei ) + T i · s2 q , ai ) : i ∈ [0..`]] .

 

Assumption 2: Note that the relinearisation key rlk contains masked versions of
T i · s2 , which are neither real samples of the RLWE distribution, nor real encryptions
of T i · s2 . This fact introduces an extra assumption on our scheme, namely that the
scheme is still secure when the adversary has access to rlk. This property is a form
of weak circular security.
If we now define
" `
# " `
#
(i) (i)
X X
0 0
c0 = c0 + rlk[i][0] · c2 and c1 = c1 + rlk[i][1] · c2 , (4)
i=0 q i=0 q

then we can compute

`
(i)
X
c00 + c01 · s = c0 + c1 · s + c2 s2 − c2 · ei mod q .
i=0

P` (i)
By applying [·]q to both sides we finally see that we can take r = i=0 c2 · ei . The
above derivation also shows that T has the following effects:

– the size of the evaluation key is given by ` + 1 ' logT (q), so the greater T is, the
smaller rlk,
– the number of multiplications in the relinearisation is 2 · ` ' 2 · logT (q), where
one is multiplying an element from RT with an element from Rq ,
– the noise introduced by relinearisation is bounded by (l + 1) · B · T · δR /2, so
greater T causes more noise.

Note that the noise introduced by relinearisation is totally independent of the noise
inherent in the ciphertext being relinearised. Furthermore, we only need to relinearise
after a multiplication (which causes the underlying error to grow as well), so we should
choose T at least as large such that the relinearisation error is of similar size as the
error contained in a ciphertext after one multiplication. This gives us a minimal value

8
of T that we should consider using. However, when the error has grown large after
several multiplications, we can relinearise with respect to T 2 instead of T . Note that
all the information required to do this is already contained in the evaluation key rlk.
We call this approach dynamic relinearisation.
The above strategy minimizes the relinearisation error, but another strategy is to
minimize the relinearisation
√  time and space. As such we want to take T very large,
for instance T = q , since then we only have two slices to take care off. For such
large T , the size of the noise after the first relinearisation typically will make a huge
jump, but all following relinearisations will not cause the noise to increase.

Relinearisation: Version 2 The second possible solution is akin towards some

form of “modulus switching” and works as follows. Recall that the problem of simply
masking s2 is that the error term e0 gets multiplied with c2 and thus results in a huge
error term r. Assume therefore that we do not simply give out the masked version of
s2 , but a masked version that can accommodate this extra error. For instance, instead
of working modulo q, we could consider giving out a masked version modulo p · q for
some integer p. Since we want to obtain an approximation of c2 · s2 modulo q, we will
have to scale by p. As such, we have to give out rlk := ([−(a · s + e) + p · s2 ]p·q , a),
with a ∈ Rp·q and e ← χ0 . Here one has to take care to choose the variance of χ0 such
that the resulting system is secure. Simply taking χ = χ0 will result in a considerable
loss of security. As shown in Section 6, if we write p · q = q k for
√
some√real k√ > 0 and
0 1− k
assume that ||χ|| < B, then we require that ||χ || = Bk > α · q k− k · B k , where
α is a constant, e.g. α ' 3.758.
To obtain a ciphertext corresponding to c2 · s2 , we can then simply compute

    !
c2 · rlk[0] c2 · rlk[1]
(c2,0 , c2,1 ) = , .
p q p q

An easy computation then shows that c2,0 + c2,1 · s = c2 · s2 + r with

q · Bk · δ R
||r|| < + (δR · ||s|| + 1)/2 .
p

The above formula can be used to easily compute the p that results in a given re-
linearisation error. For instance, if we want to minimize the relinearisation error and
thus demand it to be smaller than the error after one multiplication, we have to
√
choose p ≥ q 3 in case B is small and not dependent on q. For huge B, e.g. B ' q
the situation is worse, since then we require p ≥ q 8 to obtain minimal error. Note
however that again we can apply dynamic relinearisation depending on the noise al-
ready present in the ciphertext that needs to be relinearised. Furthermore, if we take
p = bn for some base b, then it is easy to transform rlk valid for p · q into an rlk
valid for p0 · q for p0 | p by rescaling by p0 /p.

9
Definition of FV.SH This finally brings us to the definition of the scheme FV.SH.
Using the notation introduced for the scheme LPR.ES, we have:

– FV.SH.SecretKeyGen(1λ ): sample s ← R2 and output sk = s

– FV.SH.PublicKeyGen(sk) = LPR.ES.PublicKeyGen(sk)
– FV.SH.EvaluateKeyGen:
• Version 1: parameters (sk, T ): for i = 0, . . . , ` = blogT (q)c, sample ai ←
Rq , ei ← χ and return
h  i
−(ai · s + ei ) + T i · s2 q , ai : i ∈ [0..`] .

rlk =

• Version 2: parameters (sk, p): sample a ← Rp·q , e ← χ0 and return

rlk = [−(a · s + e) + p · s2 ]p·q , a .

– FV.SH.Encrypt(pk, m): to encrypt a message m ∈ Rt , let p0 = pk[0], p1 = pk[1],

sample u ← R2 , e1 , e2 ← χ and return
 
ct = [p0 · u + e1 + ∆ · m]q , [p1 · u + e2 ]q

– FV.SH.Decrypt(sk, ct) = LPR.ES.Decrypt

– FV.SH.Add(ct1 , ct2 ): return ([ct1 [0] + ct2 [0]]q , [ct1 [1] + ct2 [1]]q )
– FV.SH.Mul(ct1 , ct2 , rlk): compute
 
t · (ct1 [0] · ct2 [0])
c0 =
q q
 
t · (ct1 [0] · ct2 [1] + ct1 [1] · ct2 [0])
c1 =
q q
 
t · (ct1 [1] · ct2 [1])
c2 =
q q

P` (i)
• FV.SH.Relin Version 1: write c2 in base T , i.e. write c2 = i=0 c2 T i with
(i)
c2 ∈ RT and set
" `
# " `
#
(i) (i)
X X
0 0
c0 = c0 + rlk[i][0] · c2 and c1 = c1 + rlk[i][1] · c2 .
i=0 q i=0 q

Return (c00 , c01 ).

• FV.SH.Relin Version 2: compute
    !
c2 · rlk[0] c2 · rlk[1]
(c2,0 , c2,1 ) = , ,
p q p q

and return ([c0 + c2,0 ]q , [c1 + c2,1 ]q ).

10
Combining Lemma 2 with the analysis of the relinearisation step, we have proved the
following lemma.

Lemma 3. Let cti for i = 1, 2 be two ciphertexts, with [cti (s)]q = ∆ · mi + vi , and
||vi || < E < ∆/2. Set ctadd = FV.SH.Add(ct1 , ct2 ) and ctmul = FV.SH.Mul(ct1 , ct2 , rlk)
then

[ctadd (s)]q = ∆ · [m1 + m2 ]t + vadd ,

[ctmul (s)]q = ∆ · [m1 · m2 ]t + vmul ,

with ||vadd || < 2 · E + t and ||vmul || < E · t · δR · (δR + 1.25) + ERelin where Version 1:
ERelin = (l + 1) · B · T · δR /2 and
√
Version
√
2:√ ERelin = (q · Bk · δR )/p + (δR · ||s|| + 1)/2,
with p = q k−1 and Bk > α1− k · q k− k · B k .
To see what the maximum depth (note that we are really talking about depth, and
not about the degree of the corresponding Boolean function) is that we can evaluate,
recall that the noise of a fresh ciphertext assuming s, u ∈ R2 is roughly given by
2 · δR · B. Since we choose T or p such that the noise introduced by relinearisation is
smaller than the noise from a multiplication, we will ignore the second term ERelin .
Note that this implicitly introduces an assumption on the maximum size of B. The
2L+1
noise after L levels of multiplications is roughly of size ' 2 · B · δR · tL . Since we
can only decrypt when this noise is smaller than ∆/2, this bring us to the following
theorem.

Theorem 1. Using the notation of the scheme FV.SH and assuming that ||χ|| < B,
FV.SH can correctly evaluate circuits of multiplicative depth L with
L
4 · δR · (δR + 1.25)L+1 · tL−1 < bq/Bc .

A very important remark here is to note that B does not appear on the left hand
side, since the noise introduced by multiplication does not involve B. This shows
that even for large values of B we are still able to perform a reasonable number of
multiplications, which is different from the existing RLWE-based schemes.

5 Fully Homomorphic Encryption

To turn the somewhat homomorphic encryption scheme FV.SH into a fully homomor-
phic encryption scheme, we require a method to lower the noise before we hit the
maximum noise level. Gentry’s idea of bootstrapping [7] is really simple, namely run
the decryption of FV.SH in the encrypted domain, i.e. homomorphically. The result of
this operation will be an encryption of the same message, but with noise of a fixed
size. If the decryption circuit can be evaluated in depth D, then the noise after boot-
strapping equals the noise one would obtain by evaluating a depth D circuit, which is
clearly independent of the starting noise present in the ciphertext. Therefore, if FV.SH
can handle circuits of depth D + 1, we can still handle one multiplication after boot-
strapping and thus obtain a fully homomorphic scheme. In practice it might be better

11
to “over-design” the homomorphic capability of the scheme, i.e. choose parameters
such that the maximum depth L is strictly greater than D + 1.
Since we need to run FV.SH.Decrypt homomorphically, we require the decryption
circuit to be as simple as possible. In the early days of FHE schemes [8, 21, 18, 4, 5]
this was typically handled by squashing the decryption circuit by writing the secret
key s as the solution to a sparse subset sum problem, which introduced a new secu-
rity assumption. In our case however, we can simply handle the real FV.SH.Decrypt
without the need for squashing.
Recall that given a ciphertext ct, we have ct[0]+ct[1]·s = ∆·m+v+q·r, for some
error term v with ||v|| < ∆/2. In a first step we will compute ct[0] + ct[1] · s mod q,
which can then be transformed easily in the centered reduction [ct[0] + ct[1] · s]q .
The crucial observation is that if we do not allow the norm of v to grow to its
maximum size, but only up to ||v|| < ∆/µ for some µ > 2, we can optimize the
decryption by ignoring most of ct[0] and ct[1]. Indeed, if we replace ct[0] and ct[1]
by c0 = ct[0] + e0 and c1 = ct[1] + e1 with ||ei || < ∆/ν (for instance by setting all
lower order bits to zero), then we have

c0 + c1 · s = ∆ · m + v + e0 + e1 · s + q · r .

The noise term in this truncated ciphertext therefore has gone up from ||v|| to ||v +
e0 + e1 · s||. To bound the size of the new noise we require two functions: define
abs(a(x)) for a(x) ∈ Z[x] as the polynomial obtained by taking the absolute value of
its coefficients, and define the function H(f ) by
( d−1
)
X
i+j
H(f ) = max || abs(x mod f (x))|| | j = 0, . . . , d − 1 . (5)
i=0

For polynomials of the form f = xd + 1, we have that H(f ) = 1. If we now let h

denote the Hamming weight of s, then we conclude that the new noise is bounded
by ∆/µ + (H(f ) · h + 1) · ∆/ν. As such the truncated ciphertext will still decrypt
as long as 2 · µ · (H(f ) · h + 1) < ν · (µ − 2). By taking µ = 2v + 4 we can take
ν = (2 + 22−v ) · (H(f ) · h + 1). This shows that we can simply work with the top
part of ct[0] mod q and ct[1] mod q of size SR = size(dν · te) bits. Note that since we
first compute the result modulo q, all these coefficients will be positive and we do not
have to mess about with a sign bit.
Each coefficient of the result c0 + c1 · s can thus be computed (recall that s is
binary) as a sum of d + 1 integers each of which has SR bits. We can represent this
situation by a (d + 1) × SR matrix M of the bits of each of these integers (least
significant bit in first column, little endian notation). Note that roughly half of the
bits in the matrix will be zero, and by moving all zeros down, we in fact will be
working with a matrix of roughly half the size. To simplify the exposition, we present
the analysis for two cases: firstly, the optimised case with q = 2n and t | q, which
is very easy to analyse and provides optimal results, and secondly, the general case.
Unlike previous papers where the general case was handled directly, we use a modulus
switching trick to (almost) reduce it to the optimal case.

12
5.1 Optimised case: q = 2n and t | q
The reason why this case is easier to handle is due to the fact that the decryption
function simplifies considerably: indeed since q = 2n and t | q, we can write ∆ = 2k .
It is easy to see that
   
t c0 + c1 · s
· [c0 + c1 · s]q = ,
q t ∆ t

by using the expression c0 + c1 · s = ∆ · m + e + q · r. As such we do not require

centered reduction, and the division by ∆ boils down to a simple shift. Furthermore,
since t also is a power of 2, the final centered reduction is a simple function of the bits
obtained modulo t. To be precise we summarize how the decryption of one coefficient
of the message (say the constant coefficient) will be performed:
– Given ciphertext ct consider the top SR bits of ct modulo q, i.e. set d0 =
(ct[0] mod q)  (n − SR ) and d1 = (ct[1] mod q)  (n − SR ), where  de-
notes right shift
– Consider the d + 1 integers modulo 2SR obtained from the constant coefficients
of d0 (x) and sj · xj · d1 (x) mod f (x) for j = 0, . . . , d − 1 and put the bits of each
of these constants in the (d + 1) × SR matrix M
– Add d + 1 integers together modulo 2SR resulting in an integer 0 ≤ w < 2SR
– Define the rounding bit wb = w[k − n + SR − 1] and finally output m0 =
[w  (k − n + SR ) + wb ]t
The main computation in decryption therefore is simply computing a sum of (d + 1)
integers modulo 2SR by computing the sum of the rows of the matrix M . For this
we use a standard two stage process: we first repeatedly use a carry-save adder that
takes as input 3 rows of M and reduces them to two rows with the same sum. More
in detail: denote by ai , bi , ci for i = 1, . . . , SR the bits in the three rows A, B, C, then
the carry save adder returns two rows containing in the i-th position

ai ⊕ bi ⊕ ci and ai−1 bi−1 ⊕ bi−1 ci−1 ⊕ ai−1 ci−1

where a−1 , b−1 , c−1 , aSR +1 , bSR +1 , cSR +1 are zero by definition. Note that since we are
computing the sum only modulo 2SR we can ignore any carry propagation beyond the
SR -th bit. The crucial point to remark here is that when we perform this computation
in the encrypted domain, the noise of the first row has not increased much, since it
does not involve any multiplications. In the next iteration, we should take care to
maximally combine rows with similar noise level. The reason for this is that the noise
of a product of two ciphertexts is a constant factor larger than the maximum of the
noises. As such, we need to try to multiply ciphertexts in a balanced way by combining
them according to their noise sizes. We can repeat the carry-save adder until we are
left with two rows. In the second stage, we use a simple schoolbook addition to finally
recover the full sum represented by SR bits. It is easy to see that the degree of the
k-th bit (counting from 0) as a Boolean expression in the bits bi,j is given by 2k ,
so we need a depth SR − 1 circuit to add these numbers together modulo 2SR . The
rounding bit then simply is the k − n + SR − 1-th bit (starting to count at 0 for LSB)

13
and the result modulo t is obtained by adding this bit to the n − k last bits. Note
that this step does not increase the required depth since we are working modulo t.
Furthermore, note that knowing the result modulo t is equivalent with knowing the
centered reduction result, so we can skip the last step. By this we mean that if we
would encrypt m + t where m ∈ Zt , then decryption would still result in m.
The reason why we have written decryption really as a binary circuit is that this
allows us to evaluate the circuit homomorphically, i.e. in the encrypted domain. Note
that this requires giving out the encryption of the bits of the secret s, so we introduce
the following procedure:
– FV.FH.BootKeyGen(s, pk): return

bsk = [FV.FH.Encrypt(si , pk) : i ∈ [0..d − 1]] .

Note that in practice one would not encrypt all bits separately, but use SIMD tech-
niques to encrypt several bits simultaneously thereby significantly lowering the mem-
ory usage of the bootstrapping key bsk.
The analysis of the required multiplicative depth can be summarized in the fol-
lowing theorem.
Theorem 2. The somewhat homomorphic encryption scheme FV.SH for q = 2n , t | q
and using a binary secret s of Hamming weight h, can be turned into a fully ho-
momorphic encryption scheme FV.FH by using a bootstrapping procedure if FV.SH can
evaluate circuits of depth L ≥ size(dν · te) where ν = γ · (H(f ) · h + 1) with 2 < γ < 3
and H(f ) as defined in Equation (5).
The above theorem thus shows that for t = 2, h = 63 and f (x) = xd + 1, we only
require L = 9 if we use µ = 210 . Also note that the required L to obtain FV.FH does
not depend on the choice of q nor χ, but only on t, the Hamming weight h of the
secret key and the properties of the polynomial f .

5.2 General case

Although the general case can be handled directly, i.e. by analysing FV.SH.Decrypt
as is, we will use a little trick that simplifies the analysis immensely. Recall that a
valid ciphertext ct satisfies ct[0] + ct[1] · s = ∆ · m + v + q · r, with ||v|| < ∆/2 and
||r|| < δR · ||s||. If we assume that the noise v is not maximal size, we can simply
switch from modulus q to 2n where n = blog2 (q)c by a simple scaling over 2n /q.
Indeed, if we define ci = b2n · ct[i]/qe for i = 0, 1, then one can easily verify that
 n
2
c0 + c1 · s = · m + e + 2n · r ,
t

with ||e|| < ||v|| + t + (1 + δR · ||s||). As long as ||e|| < b2n /tc /2, we obtain a valid
ciphertext with respect to the modulus 2n instead of q.
The decryption now almost becomes as simple as in the optimised case, by consid-
ering (c0 , c1 ) as the ciphertext to decrypt. The first step is exactly the same as before:
we work with the top bits only via d0 and d1 and thus obtain an approximation to

14
(c0 + c1 · s) mod 2n by 2` · (d0 + d1 · s) mod 2n with ` = n − SR using a circuit of
depth SR − 1. Let w be the constant coefficient of (d0 + d1 · s) mod 2SR , then the
constant term of the message is given by

t · [2` · w]2n
 
.
2n t

Since t no longer necessary divides 2n however, we really need to work with the
centered reduction instead of just modulo 2n , but this is rather easy. If w > 2SR −1 ,
we need to replace it by w − 2SR so if we define wc = w[SR − 1] · w[SR − 2] mod 2,
then the centered reduction is given by the combination of

wr := (1 ⊕ wc ) · w + wc · (2SR − w) mod 2SR

and a sign bit equal to wc (a 1 indicates negative number). Note that (2SR −w) is very
easy to compute by negating all bits of w and adding 1. Since these operations add
two levels, the centered reduction wr can be obtained with a circuit of depth SR + 1.
To compute t · wr we require an extra HW (t) − 1 levels, where HW (t) denotes the
Hamming weight of t. Dividing by 2n is for free and the rounding is taken care of as
in the optimal case, i.e. by simply adding the first bit after the binary point, which
requires at most one level of depth extra. As before, we can again ignore the final
centered reduction modulo t. This finally proves the more general theorem.
Theorem 3. The somewhat homomorphic encryption scheme FV.SH with binary se-
cret s of Hamming weight h, can be turned into a fully homomorphic encryption
scheme FV.FH by using a bootstrapping procedure if FV.SH can evaluate circuits of
depth L ≥ size(dν · te) + HW (t) + 2 where HW (t) denotes Hamming weight of t and
ν = γ · (H(f ) · h + 1) with 2 < γ < 3 and H(f ) as defined in Equation (5).

6 Choosing Parameters

In this section we explain how to choose parameters that guarantee a given level
of security, and allow a depth L circuit to be evaluated. Combining this with the
minimal L to obtain FHE, we thus derive parameters that allow FHE.

6.1 Practical Hardness of RLWE

To assess the hardness of the RLWE-problem, we will follow the analysis of Lindner
and Peikert [14] for the standard LWE problem. We therefore implicitly assume that
the analysis of Lindner and Peikert also holds for the RLWE-problem.
As before, let q denote the modulus, d the degree of the polynomial ring R and
let σ 2 denote the variance of the probability distribution χ. Gamma and Nguyen [6]
defined the Hermite factor δ m of a basis B of an m-dimensional lattice Λ as ||b1 || =
δ m · det(Λ)1/m , with b1 the shortest vector in B. Lindner and Peikert [14] call δ the
root-Hermite factor. Furthermore, Gamma and Nguyen showed that the run time of
reduction required to achieve a given δ (in large enough dimension) mainly depends

15
on δ, and not on the dimension or determinant. Lindner and Peikert [14] show that
the time in seconds to compute a basis with root-Hermite factor δ is roughly given
by
log2 (time) = 1.8/ log2 (δ) − 110 .
If we assume a security level of λ bits, i.e. we set time = 2λ , then the minimal δ we
can achieve according to the above estimate is log2 (δ) = 1.8/(λ + 110). For instance,
when we set λ = 128, we obtain that δ ' 1.0052.
In order for the distinguishing attack described inp [14] to succeed with advantage ε
we need to find vectors of length α · (q/σ), with α = ln(1/ε)/π, so for an advantage
of ε = 2−64 , we have α ' 3.758. For a fixed root-Hermite factor δ, Lindner and
Peikert [14] show that using the optimal √ attack strategy, the length of the shortest
2 d log2 (q) log2 (δ)
vector one can compute is given by 2 . This leads to the condition
q √
α · < 22 d log2 (q) log2 (δ) . (6)
σ
Note that the above equation shows that for fixed q and growing σ, we can take a
lower degree d, providing more flexibility than previous works where σ was always
chosen to be very small. Furthermore, this equation also shows that for fixed d and
a fixed security level, we can transform one valid parameter pair (q,√σ) into√another √
valid pair (q k , σk ) for any real k > 1 as long as we choose σk > α1− k · q k− k · σ k .
Note that it is precisely this bound that was used in FV.SH.Relin, Version 2.

6.2 Parameters for FHE

To generate parameters for an FHE scheme at a given security level λ, we first com-
pute log2 (δ) = 1.8/(λ + 110). Equation 6 then allows us to either choose the degree d
first and compute a valid (q, σ)-pair; or to choose (q, σ) first and derive d from this.
Recall that the distribution χ can be considered B-bounded when we set B = β() · σ
for some tiny . According to Theorem 1, the maximum multiplicative depth Lmax
that FV.SH can handle satisfies
q
Lmax
4 · β() · δR · (δR + 1.25)Lmax +1 · tLmax −1 < . (7)
σ
Recall that the above inequality assumes that the noise introduced by relinearisation
is smaller than the noise after the first multiplication. For both versions of relineari-
sation, this noise depends on B, so this implicit assumption bounds the maximum
allowable B.
From Theorem 3 we can easily derive the minimum Lmin (given t and a Hamming
weight h) to obtain FHE, and this Lmin is independent of (q, σ). In fact, if we use a
parametrised family for f (x), e.g. f (x) = xd + 1, for which H(f ) is constant, then
Lmin is even independent of d. Of course we need to choose h large enough such that
χ has sufficient entropy, but this is a minor restriction. Substituting this Lmin in
Equation (7), multiplying by α and combining with Equation (6) then finally gives:
√
Lmin
4 · α · β() · δR · (δR + 1.25)Lmin +1 · tLmin −1 < 22 d log2 (q) log2 (δ) .

16
Note that the left hand side does not depend on q and only δR depends on f and
thus d. The above formula thus allows us to either choose d first and then compute
a valid (q, σ)-pair or vice-versa. To provide a simple example, consider the family
fd (x) = xd + 1, then δR = d, H(fd ) = 1 and for t = 2, h = 63 we have Lmin = 9.
For  = 2−64 we have β() ' 9.2 and α ' 3.8 and for 128-bit security level we have
log2 (δ) = 0.0076. If we choose q = 2n and d = 2k , then substituting all these values
then finally leads to √
15.13 + 19 · k < 0.174 · n · 2k/2 .
So if we choose k = 10, then we require n > 1358 to guarantee FHE capabilities.

7 Conclusions and Future Work

In this paper we ported Brakerski’s FHE scheme from the LWE to the RLWE setting
and provided a detailed analysis of all subroutines involved such as multiplication,
relinearisation and bootstrapping. This analysis results in tight worst case bounds
on the noise caused by homomorphic operations, which can be used to derive very
concrete parameters for which the scheme can be made fully homomorphic. We in-
troduced two optimised versions of relinearisation that result both in a smaller re-
linearisation key and faster computations than existing solutions. Furthermore, we
simplified the analysis of the bootstrapping step by a modulus switching trick.
The results in this paper provide a sound theoretical basis for practical imple-
mentations. We note however that the derived bounds are worst case bounds and
not average case bounds that can be easily derived from the central limit theorem.
In a follow up paper we will consider very practical aspects of this scheme, including
the average case bounds and we will report on an implementation in the Magma
computer algebra system and on a highly optimised dedicated polynomial multiplier
hardware implementation.
Two further major optimisations are possible and are work in progress, namely the
bootstrapping step can be highly improved by using a much better SIMD approach
than the current state-of-the-art; and the actual homomorphic system itself should
be replaced by our “t-adic approach to FHE”, which keeps the size of the ciphertext
minimal w.r.t. the size of the noise it contains.

Acknowledgments
The authors would like to thank Damien Stehlé, Ron Steinfeld, Oded Regev and Chris
Peikert for sharing their deep insights about lattice and (R)LWE related matters
(amongst many other topics).

References
1. Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic
Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Ad-
vances in Cryptology - CRYPTO 2009, volume 5677 of Lecture Notes in Computer Sci-
ence, pages 595–618. Springer, 2009.

17
 2. Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Clas-
sical GapSVP. IACR Cryptology ePrint Archive, 2012:78, 2012.
3. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic
encryption without bootstrapping. In Innovations in Theoretical Computer Science
2012, pages 309–325. ACM, 2012.
4. Zvika Brakerski and Vinod Vaikuntanathan. Fully Homomorphic Encryption from Ring-
LWE and Security for Key Dependent Messages. In Advances in Cryptology - CRYPTO
2011, volume 6841 of Lecture Notes in Computer Science, pages 505–524. Springer, 2011.
5. Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. Fully
Homomorphic Encryption over the Integers with Shorter Public Keys. In Advances in
Cryptology - CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages
487–504. Springer, 2011.
6. Nicolas Gama and Phong Q. Nguyen. Predicting Lattice Reduction. In Advances in
Cryptology - EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science,
pages 31–51. Springer, 2008.
7. Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University,
2009. crypto.stanford.edu/craig.
8. Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC 2009, pages
169–178. ACM, 2009.
9. Craig Gentry and Shai Halevi. Fully Homomorphic Encryption without Squashing Using
Depth-3 Arithmetic Circuits. In FOCS 2011, pages 107–109. IEEE, 2011.
10. Craig Gentry and Shai Halevi. Implementing Gentry’s Fully-Homomorphic Encryption
Scheme. In Advances in Cryptology - EUROCRYPT 2011, volume 6632 of Lecture Notes
in Computer Science, pages 129–148. Springer, 2011.
11. Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic Evaluation of the AES
Circuit. IACR Cryptology ePrint Archive, 2012:99, 2012.
12. Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Ro-
bustness of the Learning with Errors Assumption. In ICS 2010, pages 230–240. Tsinghua
University Press, 2010.
13. Adeline Langlois and Damien Stehlé. Hardness of decision (R)LWE for any modulus.
IACR Cryptology ePrint Archive, 2012:91, 2012.
14. Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based
Encryption. In Topics in Cryptology - CT-RSA 2011, volume 6558 of Lecture Notes in
Computer Science, pages 319–339. Springer, 2011.
15. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning
with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, volume 6110
of Lecture Notes in Computer Science, pages 1–23. Springer, 2010. Full version of the
paper available upon request from authors.
16. Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. Can homomorphic en-
cryption be practical? In CCSW 2011, pages 113–124. ACM, 2011.
17. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography.
In STOC 2005, pages 84–93. ACM, 2005.
18. Nigel P. Smart and Frederik Vercauteren. Fully Homomorphic Encryption with Rela-
tively Small Key and Ciphertext Sizes. In PKC 2010, volume 6056 of Lecture Notes in
Computer Science, pages 420–443. Springer, 2010.
19. Nigel P. Smart and Frederik Vercauteren. Fully Homomorphic SIMD Operations. IACR
Cryptology ePrint Archive, 2011:133, 2011.
20. Damien Stehlé and Ron Steinfeld. Faster Fully Homomorphic Encryption. In Advances
in Cryptology - ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science,
pages 377–394. Springer, 2010.

18
21. Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully Homo-
morphic Encryption over the Integers. In Advances in Cryptology - EUROCRYPT 2010,
volume 6110 of Lecture Notes in Computer Science, pages 24–43. Springer, 2010.

19