Homomorphic Encryption Tutorial Shai Halevi IBM CRYPTO 2011 Computing on Encrypted Data Wouldnt it be nice to be able to Encrypt my data before sending to the cloud While still allowing the cloud to search/sort/edit/ this data on my behalf Keeping the data in the cloud in encrypted form Without needing to ship it back and forth to be decrypted August 16, 2011 2 Computing on Encrypted Data

Wouldnt it be nice to be able to Encrypt my queries to the cloud While still allowing the cloud to process them Cloud returns encrypted answers that I can decrypt August 16, 2011 3 Computing on Encrypted Data $skj#[email protected] June 16, 2011 4 Computing on Encrypted Data

$kjh9*[email protected] &maXxjq02bflx m^00a2nm5,A4. pE.abxp3m58bsa (3saM%w,snanba nq~mD=3akm2,A Z,ltnhde83|3mz{n dewiunb4]gnbTa* kjew^bwJ^mdns0 June 16, 2011 5 Organization of the Tutorial Two parts with a 10-minute break in between First part quite high-level Lots of pictures/animations on the slides Covers the [Gentry 2009] blueprint

Second part more algebraic Lots of formulas on the slides Covers newer constructions [GH11,BV11,BGV11] (April 2011 and on) 02/08/2020 6 Some Notations An encryption scheme: (KeyGen, Enc, Dec) Plaintext-space = {0,1} (pk,sk) KeyGen($), cEncpk(b), bDecsk(c) Semantic security [GM84]: (pk, Encpk(0)) (pk, Encpk(1)) means indistinguishable by efficient algorithms

June 16, 2011 7 Homomorphic Encryption (FHE) H = {KeyGen, Enc, Dec, Eval} c* Evalpk(f, c) c* Homomorphic: Decsk(Evalpk( f, Encpk(x))) = f(x) c* may not look like a fresh ciphertext As long as it decrypts to f(x) Compact: Decrypting c* easier than computing f Otherwise we could use Evalpk (f, c)=(f, c) and Decsk(f, c) = f(Decsk(c)) |c*| independent of the complexity of f June 16, 2011

8 Privacy Homomorphisms [RAD78] Plaintext space P x1 x2 ci Enc(xi) * y Ciphertext space C c1

c2 # y Dec(d) d Some examples: Raw RSA: c xe mod N (x cd mod N) x1e x x2e = (x1 x x2) e mod N GM84: Enc(0)R QR, Enc(1)R QNR (in ZN*) Enc(b1) x Enc(b2) = Enc(b1b2) mod N June 16, 2011 9 More Privacy Homomorphisms Mult-mod-p [ElGamal84]

Add-mod-N [Pallier98] Quadratic-polys mod p [BGN06] Branching programs [IP07] A different type of solution for any circuit [Yao82,] Not compact, ciphertext grows with circuit complexity Also NC1 circuits [SYY00] June 16, 2011 10 (x,+)-Homomorphic Encryption It will be really nice to have Plaintext space Z2 (w/ ops +,x) Ciphertexts live in algebraic ring R (w/ ops +,x) Homomorphic for both + and x Enc(b1) + Enc(b2) in R = Enc(b1+ b2 mod 2) Enc(b1) x Enc(b2) in R = Enc(b1 x b2 mod 2)

Can compute any function on the encryptions Since every binary function is a polynomial Wont get exactly this, but its a good motivation June 16, 2011 11 The [Gentry 2009] Blueprint The [Gentry 2009] blueprint Evaluate any function in four easy steps Step 1: Encryption from linear ECCs Additive homomorphism Step 2: ECC lives inside a ring Error-Correcting Codes

(not Elliptic-Curve Cryptograp Also multiplicative homomorphism But only for a few operations (low-degree polys) Step 3: Bootstrapping Few ops (but not too few) any number of ops Step 4: Everything else Squashing and other fun activities June 16, 2011 13 Step 1: Encryption from Linear ECCs For random looking codes, hard to distinguish close/far from code

Many cryptosystems built on this hardness E.g., [McEliece78, AD97, GGH97, R03,] June 16, 2011 14 Step 1: Encryption from Linear ECCs KeyGen: choose a random Code Secret key: good representation of Code Allows correction of large errors Public key: bad representation of Code Can generate random code-words Hard to distinguish close/far from the code Enc(0): a word close to Code Enc(1): a random word Far from Code (with high probability)

June 16, 2011 15 Example: Integers mod p [vDGHV p N 2010] Code determined by a secret integer p Codewords: multiples of p Good representation: p itself Bad representation: ri << p N = pq, and also many xi = pqi + ri Enc(0): subset-sum(xis)+r mod N

r is new noise, chosen by encryptor Enc(1): random integer mod N June 16, 2011 16 A Different Input Encoding p Both Enc(0), Enc(1) close to the code Enc(0): distance to code is even Enc(1): distance to code is odd Security unaffected when p is odd N xi = pqi + ri

Plaintext encoded in the noise In our example of integers mod p: Enc(b) = 2(r+subset-sum(xis)) + b mod N = kp + 2(r+subset-sum(ris))+b Dec(c) = (c mod p) mod 2 June 16, 2011 much smaller than p/2 Additive Homomorphism c1+c2 = (codeword1+codeword2) + (2r1+b1)+(2r2+b2 ) codeword1+codeword2 Code (2r1+b1)+(2r2+b2 )=2(r1+r2)+b1+b2 is still small

If 2(r1+r2)+b1+b2 < min-dist/2, then dist(c1+c2, Code) = 2(r1+r2)+b1+b2 dist(c1+c2, Code) b1+b2 (mod 2) Additively-homomorphic while close to Code June 16, 2011 18 Step 2: Code Lives in a Ring What happens when multiplying in Ring: c1c2 = (codeword1+2r1+b1)(codeword2+2r2+b2) = codeword1X + Ycodeword2 + (2r1+b1)(2r2+b2) Code is an ideal If: codeword1X + Ycodeword2 Code

Product in Ring of (2r1+b1)(2r2+b2) < min-dist/2 Then small elements is small dist(c1c2, Code) = (2r1+b1)(2r2+b2) = b1b2 mod 2 June 16, 2011 19 Example: Integers mod p [vDGHV p N 2010] x = pq + r i

i Secret-key is p, public-key is N and the xis ci = Encpk(bi) = 2(r+subset-sum(xis)) + b mod N = kip + 2ri+bi i Decsk(ci) = (ci mod p) mod 2 c1+c2 mod N = (k1p+2r1+b1)+(k2p+2r2+b2) kqp = kp + 2(r1+r2) + (b1+b2) c1c2 mod N = (k1p+2r1+b1)(k2p+2r2+b2) kqp = kp + 2(2r1r2+r1b2+r2b1)+b1b2 Additive, multiplicative homomorphism 02/08/2020 As long as noise < p/2

20 Summary Up To Now We need a linear error-correcting code C With good and bad representations C lives inside an algebraic ring R C is an ideal in R Sum, product of small elements in R is still small Can find such codes in Euclidean space Often associated with lattices Then we get a somewhat homomorphic encryption, supporting low-degree polynomials Homomorphism while close to the code 02/08/2020 21

Instantiations [G 2009] Polynomial Rings Security based on hardness of Bounded-Distance Decoding in ideal lattices [vDGHV 2010] Integer Ring Security based on hardness of the approximate-GCD problem [GHV 2010] Matrix Rings (only partial solution) Only qudratic polynomials, security based on hardness of Learning with Errors (LWE) [BV 2011a] Polynomial Rings Security based on ring LWE June 16, 2011 22 Step 3: Bootstrapping So far, can evaluate low-degree polynomials x1

x2 P P(x1, x2 ,, xt) xt June 16, 2011 23 Step 3: Bootstrapping So far, can evaluate low-degree polynomials x1 x2 P

P(x1, x2 ,, xt) xt Can eval y=P(x1,x2,xn) when xis are fresh But y is an evaluated ciphertext Can still be decrypted But eval Q(y) will increase noise too much Somewhat Homomorphic encryption (SWHE) June 16, 2011 24 Step 3: Bootstrapping So far, can evaluate low-degree polynomials x1 x2

P P(x1, x2 ,, xt) xt Bootstrapping to handle higher degrees We have a noisy evaluated ciphertext y Want to get another y with less noise June 16, 2011 25 Step 3: Bootstrapping For ciphertext c, consider Dc(sk) = Decsk(c) Hope: Dc(*) is a low-degree polynomial in sk Include in the public key also Encpk(sk)

c y sk1 sk2 skn Requires circular security Dc c Dc(sk) = Decsk(c) = y Homomorphic computation applied only to the fresh encryption of sk

June 16, 2011 26 Step 3: Bootstrapping Similarly define Mc ,c (sk) = Decsk(c1)Decsk(c1) 1 y1 c1 sk1 sk2 skn 2

y2 c2 Mc ,c 1 2 c Mc ,c (sk) 1 2 = Decsk(c1) x Decsk(c2) = y1 x y2 Homomorphic computation applied only to the fresh encryption of sk June 16, 2011

27 Step 4: Everything Else Cryptosystems from [G09, vDGHV10, BG11a] cannot handle their own decryption Tricks to squash the decryption procedure, making it low-degree Nontrivial, requires putting more information about the secret key in the public key Requires yet another assumption, namely hardness of the Sparse-Subset-Sum Problem (SSSP) I will not talk about squashing here June 16, 2011 28 Performance of Blueprint

SWHE schemes may be reasonable But bootstrapping is inherently inefficient Homomorphic decryption for each multiplication Asymptotically, overhead of at least Best implementation so far is [GH 2011a] Implemented a variant of [Gentry 2009] Public key size ~ 2GB Bootstrapping takes 3-30 minutes Similar performance also in [CMNT 2011] Implemented the scheme from [vDGHV10] June 16, 2011 29 Beyond the Blueprint Chimeric HE [GH 2011b]

Bootstrapping without squashing Hybrid of SWHE and MHE schemes MHE = Multiplicative HE (e.g., Elgamal) + X X Express decryption as a restricted depth-3 SPS arithmetic circuit + + + Switch to MHE for the middle P level ++ + X ++ + All necessary MHE ciphertexts found in public key

Translate back to SWHE for the top S level SWHE evaluates MHE decryption, not own decryption No need for squashing, SSSP [Brakerski-Vaikuntanathan 2011b] FHE without squashing, security based on Learning-with-Errors (LWE), or ring-LWE Main innovation: multiplicative homomorphism without a ring structure A host of new techniques/tricks, can be used for further improvements 02/08/2020 32 Learning with Errors (LWE) [Regev 2005]

Hard to solve linear equations with noise Given: decide if b A Zqm R Zqnxm b is a random vector in Zqm, or b is close to the row-space of A (distance < bq) b = sA + e for random s Zqn and random short e Zqm Parameters: n (dim), qpoly(n) (modulus), b1/poly(n) (noise magnitude), m = poly(n) [Regev05, Peikert09]: As hard as some worst-case lattice problems in dim n (for certain range of params) 02/08/2020

33 The [BV11b] Construction Bit-by-bit encryption, plaintext is a bit b Think of it as symmetric encryption for now Secret-key s, ciphertext c, are vectors in Zqn Simplifying convention: s1 = 1, i.e., s = (1|t) Decryption is b=(~~ mod q) mod 2 (~~~~ mod q) is small, absolute value bq In other words: mod q maps to [-q/2, q/2] Ciphertexts are close to space orthogonal to s Plaintext encoded in parity of distance ~~

distance is the size of (~~ mod q) 02/08/2020 34 Homomorphism This is an instance of encryption from linear ECCs, additive homomorphism is for free As long as things remain close to the code But how to multiply? Ciphertexts are vectors, not ring elements Tensor product (??) M = uv, M = u v mod q ij i j t Can decrypt M(!), s(uv)s = ~~~~ (mod q) If no wraparound then ~~

(s(uv)st mod q) = (~~ mod q)(~~~~ mod q) So (s(uv)st mod q) mod 2 = Decs(u)Decs(v) 02/08/2020 35 Multiplying More than Once? s(uv)st is a bilinear form in s, so linear in ss Opening uv, ss into vectors, we get s(uv)st = Denote s*=vec(ss), c*=vec(uv), then: Decs*(c*) = (~~~~ mod q) mod 2 ~~~~ mod q is still quite small, (bq)2 << q We can repeat the process But dimension is squared, n n2 n4 n8 so can repeat only a constant number of times ~~

02/08/2020 36 Reducing the Dimension We have an extended ciphertext c* with respect to extended secret key s*=vec(ss) Want a low-dimension ciphertext c with respect to a standard secret key s Maybe s=s, maybe not Key idea: publish an encryption of s* under s to enable the translation Hopefully just a matrix M(s*s)Zqdim(s)x dim(s*), so that c = Mc*Zqdim(s) 02/08/2020 37

An Attempt that Almost Works b M= A = -tA+(2e+s*) mod q e is short R Zqdim(t) x dim(s*) Recall s=(1|t), so sM= tA+b = 2e+s* Let c = Mc*Zqdim(s), then mod q we have: ~~ sMc* <2e+s*,c*> ~~~~+2 If only c* was short, then 2 was small, so (<2e+s*,c*> mod q) = (~~~~ mod q)+2 Hence (~~~~ mod q) (~~~~ mod q) (mod 2) So Decs(c) = Decs* (c*) 02/08/2020 ~~

38 Can we Make c* Short? Want to represent the long vector c* by some short vector c, perhaps in higher dimension Example: c* =(76329, 31692, 43870) l2-norm ~ 90000 represented by c=(7,6,3,2,9, 3,1,6,9,2, 4,3,8,7,0) l2-norm only ~ 21 Later we will use binary rather than decimal Note that we have a linear relation: 02/08/2020 39

Can we Make c* Short? Denote c*=(), i.e., is the ith entry Let be binary representation of Let bj be the vector of jth bits bj=() so c*, and ~~ Let s**=PowersOf2q(s*)= (s*|2s*|4s*||2ls*) mod q, and c**=BitDecomp(c*) = (b0|b1 | b2 || bl ) Then ~~~~ ~~~~ (mod q) c** is short (in l2-norm), it is a 0-1 vector 02/08/2020 40 Dimension Reduction (Key-Switching) Publish the matrix M(s**s)Zqdim(s) x dim(s**) Given the expanded ciphertext c* Compute the doubly expanded c** Set c = Mc** mod q ~~

We know that ~~ ~~~~ (mod q) Also ~~~~ ~~~~+2 (mod q) (~~~~ mod q) is small and so is 2 hence (~~~~ mod q) = (~~~~+2 mod q) Last equality is over the integers Decs(c) = Decs* (c*) 02/08/2020 41 Security M(s*s)= -tA+2e+s* A ~~

Under LWE, cannot tell M(s*s) from random Even if you know s* (but not s) Assuming q is odd Pf: if (A, r)(A, tA+e) then (2A, 2r)(2A, 2tA+2e) For odd q: (2A, 2r) (A, r), (2A, 2tA+2e) (A, tA+2e) means that these distributions are identical We get (A, r) (A, tA+2e) It follows that (A, r)(A, r+s*)(A, tA+2e+s*) 02/08/2020 42 The [BV11b] Leveled SWHE

(Key-size linear in depth of circuits to evaluate) KeyGen: choose random s0,s1,,sd Zqn First entry in each si is 1 Public key has matrices M0=M(0s0) and Mi+1=M(si**si+1) for i=0,1,,d-1 Then s0M0 = 2e0, and siMi = 2ei+ Enc(b): rR{0,1}m, cM0r + [b,0,,0], output (c,0) Dec(c,i): Recover b( mod q) mod 2 02/08/2020 For level-0: = s0M0r+ b = 2+b e0,r are short so , hence no wraparound 43 The [BV11b] Leveled SWHE Ciphertexts in same level can be added directly To multiply two level-i ciphertexts (c1,i),(c2,i)

Compute the extended c*=vec(c1c2), the doubly extended c**, and set cMic** (c,i+1) is a level-(i+1) ciphertext Semantic-security follows because: Under LWE, the Mis are pseudo-random If they were random then ciphertexts would have no information about the encrypted plaintexts By leftover hash lemma 02/08/2020 44 From SWHE to FHE The noise in a ciphertext (c,i) is mod q Noise magnitude roughly doubles on addition, get squared on multiplication Can only evaluate log-depth circuits before the noise magnitude exceeds q

How to evaluate deeper circuits? Squash & bootstrap, Chimeric & bootstrap, or an altogether new technique 02/08/2020 45 Modulus Switching Converting c,s into c,s s.t. for some p < q (~~ mod p) (~~~~ mod q) (mod 2) [BV11b]: Use with to reduce decryption complexity, can bootstrap without squashing Modulus-switching & key-switching combined The resulting c can be decrypted, but cannot participate in any more homomorphic operations ~~

[BGV11] Use with to reduce the noise, can compute deeper circuits w/o bootstrapping Roughly just by scaling, cround(p/q c) Rounding appropriately 02/08/2020 46 Modulus Switching Main Lemma Let p mod q|< q/2 q/p 1 s must be 1 is the l1 norm of s short

Let c=rndc(p/q c), where rndc() rounds each entry up or down so that cc (mod 2) Then (i) (~~ mod p) (~~~~ mod q) (mod 2) and (ii)|~~~~ mod p||~~~~ mod q|+ 1 02/08/2020 47 Modulus Switching Main Lemma Proof: For some k, ~~~~ mod q = ~~~~ - kkq [] Actually in a smaller interval ~~~~ - kkq [ + 1, - 1 ] Multiplying by p/q we get ~~~~ - kp [+1, -1] Replacing c by c=rndc(c), adds error 1: ~~~~ - kp [, ], so ~~~~ - kp =~~~~ mod p ~~

This also proves Part (ii) 02/08/2020 48 Modulus Switching Main Lemma Proof: We know that ~~ mod q = ~~~~ - kq and ~~~~ mod p = ~~~~ - kp for the same k Since p,q are odd then kp kq (mod 2) Since cc (mod 2) then ~~~~ (mod 2) (~~~~ mod p) = ~~~~ - kp ~~~~ - kq (mod 2) = (~~~~ mod q) This proves part (i) 02/08/2020 ~~

49 Making s Small If s is random in Zqn then ||s||1 > q Luckily [ACPS 2009] proved that LWE is hard even when s is a random short vector chosen from the same distribution as the noise e So we use this distribution for the secret keys Alternatively, we could have used the trick with BitDecomp() and PowersOf2() 02/08/2020 50 Modulus Switching Example: q=127, p=29, c=(175,212), s=(2,3) ~~ mod q = 986 8 x 127 = 30 ~~

p/q c (39.9, 48.4) To get cc (mod 2) we round down both entries c=(39,48) ~~ mod p = 222 8 x 29 = 10 Indeed k=8 in both cases, 1030 (mod 2) The noise magnitude decreased from 30 to 10 But the relative magnitude increased, 02/08/2020 51 How Does Modulus-Switching Help? Start with large modulus q0, small noise q0 After 1st multiplication, noise grows to Switch the modulus to q1q0/, Noise similarly reduced to After next multiplication layer, noise again grows ~~

to , switch to q2q1/ to reduce it back to Keep switching moduli after each layer Setting qi+1qi/ Until last modulus is too small, qd/2 02/08/2020 52 How Does Modulus-Switching Help? Example: q0 Fresh ciphertexts Level-1, Level-1, degree=2 degree=2 Level-2, Level-2, degree=4

degree=4 Level-3, Level-3, degree=8 degree=8 Level-4, Level-4, degree=16 degree=16 02/08/2020 Using mod-switching Without mod-switching Noise Noise

Modulus Modulus decryption errors 53 Putting It All Together Use tensor-product for multiplication Then reduce the dimension with M(ss) First need to use PowersOf2/BitDecomp Then reduce the noise by switching modulus This works if the secret key s is short Repeat until modulus is too small

02/08/2020 54 The [BGV11] Leveled FHE d-level circuits, initial noise Also is another parameter Set odd moduli q0,,qd s.t. qi d-i+1 Key generation: Choose short secret siZq n , i=0,,d, first entry=1 i 2 Set si =vec(sisi)Zq , =PowersOf2q (si*)Zq ti *

n i i Public key has M0=M(0s0)Zq n x t and Mi=M(si)Zq n x t 0 i-1 i t0=3nlog(q0) and ti=n2log(qi) 0

i-1 The short error vector in Mi is eiZq t Then s0M0 = 2e0 mod q0 and siMi = 2ei+mod qi-1 i- 1 02/08/2020 i-1 55 The [G11] Leveled FHE Enc, Dec, and homomorphic addition are the same as in the leveled SWHE Level-i ciphertexts are modulo qi To multiply two level-i ciphertexts, c1,c2: 2

c*vec(c1c2) Zq n, ( mod qi) b1b2(mod 2) c**BitDecom(c*), ( mod qi) b1b2(mod 2) cMi+1c** mod qi ( mod qi) b1b2(mod 2) rndc(qi+1/qi c), (<> mod qi+1) b1b2(mod 2) i Noise in c is bounded by (2+stuff)/t 02/08/2020 56 What We Have So Far A leveled-FHE: Public-key size at least linear in circuit depth Can handle circuits of arbitrary polynomial depth

Security based on LWE For interesting circuits this is more that poly(n) Modulus gets smaller as we go up the circuit Lower levels somewhat more expensive 02/08/2020 57 Variants and Optimizations Use bootstrapping to recover large modulus Size of largest modulus depends on decryption circuit, not the circuits that we evaluate Can be made into pure FHE (non-leveled), need to assume circular security Base security on ring-LWE

LWE over a ring other than Zq (e.g., R=Zq[x]/f(x)) Can use smaller dimension (e.g., dim=2) Large plaintext space (not just Z2) Must tweak the modulus-switching technique 02/08/2020 58 Variants and Optimizations Batching: pack many bits into each ciphertext E.g., using the Chinese Remainders Theorem An operation (+,x) on ciphertext acts separately on each the packed bits Combining these optimizations, can reduce the overhead to Compare to for the original blueprint

02/08/2020 59 Current Status of HE constructions Many new ideas are at the table now Still figuring out what works and what doesnt Looking at recent history, we can expect more new ideas in the next few months/years Implementation efforts are underway Goal: get usable FHE At least for some applications My personal guess: almost at hand, perhaps only 2-3 years away Many open problems remain 02/08/2020

60