Fully Homomorphic EncryptionBoaz BarakFebruary 9, 2011Achieving fully homomorphic encryption, under any kind of reasonab l e computati onal assump-tions (and under any reasonable definition of ”reasonable”..), was a holy grail of cryptographyfor many years until finally achieved by Craig Gentry in 2009. In these lectur es we’ll describe asomewhat simplified variant of Gentry’s constructi on obtained by van Dijk, Gentry, Halevi andVaikuntanathan (w it h another slight simplification suggested by Sushant Sachdeva, and was alsoindependently observed by Ivan Damgard).1 DefinitionsWe r ecal l the definition of fully homomorphic encryption:Definition 1. We say that a quad ru p le of p.p.t algorithms (Gen, Enc, Dec, Eval)isastrongly fullyhomomorphic encryption scheme (FHE for short) if (Gen, Enc, Dec) is semantically secure and inaddition for every t = poly(n) an d polynomial s i z e circuit C taking t bits as input, every b1,...,bt∈{0, 1} and c1,...,ctoutput by Encpk(b1),...,Encpk(bt), the distributions Evalpk(C, c1,...,ct) andEncpk(C(b1,...,bt) are statistically indistinguishable.It’s a relatively straightforwar d exercise to show that it is enough to have an evaluation algorithmfor AND and XOR, or equi valently multiplication and addition modulo 2. That is, t h e following isan equivalent alternative definition of FHE:Definition 2. We say that a quadru p le of p.p.t algorithms (Gen, Enc, Dec, Add, Mult)isastronglyfully homomorphic encryption scheme (FHE for short) if (Gen, Enc, Dec) is semantically secur e andin addition for every b, b�∈{0, 1} and c, c�output by Encpk(b) and Encpk(b�)respectively:• The distribut ion s Mu l tpk(c, c�) and Encpk(b ∧ b�) are statistically indistinguishable.• The distribut ion s Addpk(c, c�) and Encpk(b ⊕ b�) are statistically indistinguishable.For this class, we define two distributions X, Y over {0, 1}nare statistically indistinguishab le iffor every function f : {0, 1}n→{0, 1}, �E[f (X)] − E[f (Y )]� < 2−n1/1000.Recall that an encryption scheme is semantically secure if the two distri b ut i on s ( pk, Encpk(0))and (pk, Encpk(1)) are computationally indistinguishable (e.g., any circuit of polynomial size willsucceed in distinguishing them with b i as less than one over any polynomial; if you want, you canreplace “any polynomial” with some fixed super-polynomial function such 2−n1/1000).The de fini t ion s for private key encryption are analogous, but now Eval, Add, Mult don’t get th ekey as input. As mentioned in cl ass (and is in fact an easier variant of the homework exercise), onecan easily transform a private key FHE into a public key FHE, letting the public key be encryptionsof zero and one.From n ow on, we’ll focus on construct i n g a scheme satis fy i n g Defi ni t i on 2.12 Construction of a “noisy homomorphic” encryption scheme.Our first step will be to construct a weaker notion than FHE that we’ll call a “noisy homomorphicencryption scheme”. This will also be an encryption scheme with the Add and Mult algorithms,but will sati sf y a relaxed notion of homom orp hi s m. It will be easier to first c ons t ru ct the scheme,and then define prec is el y the notion of homomorphism it satisfies. We remark that our notion ofnoisy homomorphism will im pl y weak homomorphism (i.e., compact encryption) with respe ct tosome subclass of circuits (specifically arithmetic circu i ts modulo 2 with depth up to n/100 wheren is our security parameter).2.1 LDN AssumptionThe encryption scheme will be based on the following computational problem. Let N = PQ beequal to the product of two large primes, and suppose that you are given various random productsR1P (mod N),...,RtP (mod N)wheretheRi’s are chosen randomly in [Q].In this cas e, recovering P is easily done by computing the gcd of, say, R1P and R2P sincewith good probability P will be t he only common factor between them. But the gcs algori t hm isextremely s en si t i ve to noise, and so it is not clear how to adapt this to the case when you are givenR1P + E1(mod N),...,RtP + Et(mod N), where the Ei’s are noise factors that are chosen insome interval [−E, + − E] for a parameter E � N . This motivates us to making the followingassumption:Learning divisor with noise (LDN) assumption. Let P a random n bit prime, Q a randomn4bit prime, and let N = PQ and E ≥ 2n0.1. Then, for every t = poly(n) there is no polynomi altime algorithm that on input N and X1,...,Xt∈ ZNcan distinguish between case (I) the Xi’s arechosen ind ependently at random from ZN, and (II) Xi= PRi+2Ei(mod N)whereRiis chosenindependently at random from ZQand Eiis chosen independently at random from [−E, +E].Some notes are in order:1. We use small letters such as n, t for values that are polynomial in the security par ame t er(which we often denote by n), and capital letters such as N,P, Q,R for large numbers thathave poly(n) digits ( an d he nc e are e xponential in n).2. We denote by ZNthe set {0,...,N − 1} and by Z∗Nthe set {X ∈ ZN: gcd(X,N)=1}.IfN is prime then Z∗N= {1,...,N − 1}. When speak i ng about a random X, it usually won’tmatter if we take it from ZNor Z∗Nsince |Z ∗N|/|ZN|�|ZN|.3. The assumption can be seen to be monotone in E. That is, increasing E only makes the prob-lem of distinguishing between the two cases harder. (The intuition i s that the distinguishercan always add more noise to the inputs on its own.)4. We made the noise even (i.e. 2Eiinstead of 2Ei) for convenience, but the two choices areequivalent - exercise!. See footnote for hint15. Obviously the LDN assumption is stronger than t he assumption that factoring N is hard.There is a variant of the LDN assumption that is still useful for FHE but is not known toimply that factoring is hard.1Hint: Given a number of the form RP + E if you multiply it by two you get 2RP +2E but since Q is odd, if R is uniform over ZQthen2R is uniform over ZQas well.22.2 The noisy homomorphic encrypti on schemeWe now describe the noisy homomorphi c encryption scheme (Gen, Enc, Dec, Add, Mult). It willbe a private ke y scheme (since it will be easy to convert it eventually to public key). We willassume however that it has public parameters— which are values that are generated by the keygeneration algorithm Gen and made public and can be used by all algorithms. Formally, such publicparameters are never needed since we can always append them to the encryption, bu t it makes forcleaner notation to