6.889: New Developments in Cryptography February 8, 2011Fully Homomorphic EncryptionInstructor: Boaz Barak Scribe: Alessandro ChiesaAchieving fully-homomorphic encryption, under any kind of reasonab l e computational assump-tions (and under any reasonable definition of “reasonable”) was a holy grail of c ry p t ograp hy for over30 years. In 2009, Craig Gentry [Gen09a, Gen09b, Gen10] proposed the first fully-homomorphicencryption scheme that is secure under a r eason ab le assumption. Craig Gentry and Shai Halevihave already implemented the scheme, and are working on optimizations [GH10].In the next two lecture s, we will describe a somewhat si mp l i fie d variant of Gentry’s construction,obtained by Martin van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan [vDGHV10](with a slight simplification suggested by Sushant Sachdeva, which was also i n de pendently observedby Ivan Damg˚ard).1 DefinitionsTwo sequences of distributions X = {Xn∈ ∆({0, 1}poly(n))}n∈Nand Y = {Yn∈ ∆({0, 1}poly(n))}n∈Nare statistically indistinguishable if, for every function family {fn: {0, 1}poly(n)→{0, 1}}n∈Nandfor all sufficiently large n ∈ N, � E[f (Xn)] − E[f(Yn)] � < 2−n1/1000,where�·� denotes the �1norm.The definition of strongly fully-h omom orp h ic encrypt i on is as follows:Definition 1. We say that a quadruple (Gen , Enc, Dec, Eval) of probabilistic polynomial-time al-gorithms is a strongly fully-homomorphic (public-key) encryption scheme (FHE for short) if:1. (Gen, Enc, Dec) is a semantically-secure (public-key) encryption scheme1and,2. For every polynomially-bound ed function t: N → N, every polynomial-size t-input circuitfamily {Cn}n∈N,every3. For every sequence of key pairs {(pkn, skn) ∈ Gen(1n)}n∈N, every polynomially-boundedfunction t: N → N, every polynomial-size t-input circuit family {Cn}n∈N,everysequenceof input bits {(b1,n,b2,n,...,bt(n),n):bi,n∈{0, 1}}n∈N, every sequence of valid ciphertexts{(c1,n,c2,n,...,ct(n),n):ci,n∈ Encpkn(bi,n)}n∈N,wehave:2�c∗← Evalpkn(Cn,c1,n,...,ct(n),n):c∗�n∈N≈s�c∗← Encpkn(Cn(c1,n,...,ct(n),n)) : c∗�n∈N.The s econ d (very strong) condition implies, in partic u lar, the following weaker one: for all suf -ficiently large n ∈ N, for every b1,...,bt(n)∈{0, 1}, the following two distributions are statisticallyindistinguishable:�(pk, sk) ← Gen(1n); c1← Encpk(b1); ... ; ct(n)← Encpk(bt(n));c∗← Evalpk(Cn,c1,...,ct(n)):(pk,c1,...,ct(n),c∗)�n∈N1That is, the two sequences of distributions given by {(pk, sk) ← Gen(1n); c ← Encpk(0) : (pk,b)}n∈Nand{(pk, sk) ← Gen(1n); c ← Encpk(1) : (pk,b)}n∈Nare comput a ti o n a ll y indistingui sh a b le , i.e., any circuit of polynomialsize will succeed in distinguishing them with bias less than one ove r any polynomial; for the purposes of this class,we can replace “any poly n o mi al” with some fixed super-polynomia l function such as 2−n0.001.2We require statistical indistinguishability, because we want the two distributions to be close even for a distin-guisher that knows the secret key sk. That will ensure that they decrypt to the same value!2-1and�(pk, sk) ← Gen(1n); c1← Encpk(b1); ... ; ct(n)← Encpk(bt(n));c∗← Encpk(Cn(c1,...,ct(n))) : (pk,c1,...,ct(n),c∗)�n∈N.This latter condition allows for Eval to fail on “bad” public keys or “bad” ciphertexts.Recall that, in the definition of weakly fully-homomorphic encryption, the second condition i srelaxed to an even weaker condition that only requires Eval to output ciph er t ex t s not much longerthan the input ciphertexts.Our fi rs t observation is that it suffices to construct an evaluation algorithm Eval only for XORand AND (or, equ i val ently, for add it i on and multiplication modulo 2) , because {XOR, AND} is auniversal gate set and thus we can perform the evaluation of a circuit C gate by gate. (Thoughone still has to argue that, since the size of the circuit is much smaller than the statistical distance,performing an evaluation for each gate in t he circuit will not increase the statistical distance by toomuch.) Hence, we will work with the following equivalent formulation of strongly fully-homomorphicencryption:Definition 2. We say that a quadrup l e (Gen, Enc, Dec , Add, Mult) of probabil is t ic polynomial-timealgorithms is a strongly fully-homomorphic (public-key) encryption scheme (FHE for short) if:1. (Gen, Enc, Dec) is a semantically-secure (public-key) encryption scheme and,2. For every two bits b and b�in {0, 1}:(a) for every three seque nc es {(pkn, skn) ∈ Gen(1n)}n∈N, {cn∈ Encpkn(b)}, and {c�n∈Encpkn(b�)},�c∗← Addpkn(cn,c�n):c∗�n∈N≈s�c∗← Encpkn(b ⊕ b�):c∗�n∈N.(b) for every three sequ en ce s {(pkn, skn) ∈ Gen(1n)}n∈N, {cn∈ Encpkn(b)}, and {c�n∈Encpkn(b�)},�c∗← Multpkn(cn,c�n):c∗�n∈N≈s�c∗← Encpkn(b ⊕ b�):c∗�n∈N.Similarly to Definition 1, the second condition implies, in particular, that�(pk, sk) ← Gen(1n); c ← Encpk(b); c�← Encpk(b�); c∗← Addpk(c, c�):(pk,c,c�,c∗)�n∈N≈s�(pk, sk) ← Gen(1n); c ← Encpk(b); c�← Encpk(b�); c∗← Encpk(b ⊕ b�):(pk,c,c�,c∗)�n∈N.and�(pk, sk) ← Gen(1n); c ← Encpk(b); c�← Encpk(b�); c∗← Multpk(c, c�):(pk,c,c�,c∗)�n∈N≈s�(pk, sk) ← Gen(1n); c ← Encpk(b); c�← Encpk(b�); c∗← Encpk(b ∧ b�):(pk,c,c�,c∗)�n∈N.However, for s i mp li c ity, we will use the stronger definition, as it is easier to work with (and we cananyways achieve it). Thus, henceforth we will focus on constructing a scheme satisfying Definition 2.2-2Private-key FHE. The definitions for private-key strongly fu ll y -h omom orp hi c encryption schemesare analogous, except that the algorithms Eval, Add, and Mult do not get the secret key as input.(Else, the “computing on ciphertex t” task would be tr i v ial : Eval could simply decrypt, evaluatethe circuit on the plaintexts, and then re-encrypt.)Also, one can easily transform a privat e -key FHE into a public-key FHE, by letting the publickey be encryptions of zero and one. (In fact, this is an even easier transformation t han the one ofRothblum [Rot10] that we discussed in the last lecture, and can be approached as an easier variantof the homework exercise.)2 Construction of a “noisy” homomorphic encryption schemeOur first st e p is to construct a primitive, wh ich is