全同态加密算法

1、Bar-Ilan UniversityDept. of Computer ScienceShaiShai HaleviHalevi IBM Research IBM ResearchBased Mostly on van-Based Mostly on van-DijkDijk, Gentry, , Gentry, HaleviHalevi, , VaikuntanathanVaikuntanathan, EC 2010, EC 20101 1Winter School on Secure Computation and EfficiencyBar-Ilan University, Israe

2、l 30/1/2011-1/2/2011Bar-Ilan UniversityDept. of Computer ScienceHomomorphicHomomorphic encryption encryption: Can evaluate some : Can evaluate some functions on encrypted datafunctions on encrypted data E.g., from Enc(x), Enc(y) compute Enc(x+y)Fully-Fully-homomorphichomomorphic encryption encryptio

3、n: Can evaluate : Can evaluate any function on encrypted dataany function on encrypted data E.g., from Enc(x), Enc(y) compute Enc(x3y-y7+xy)2 2Secure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University, Israel 20112011Bar-Ilan UniversityDept. of

4、 Computer ScienceSecure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University, Israel 20112011Evaluate low-degree Evaluate low-degree polynomials on polynomials on encrypted dataencrypted data3 3Part IPart IBar-Ilan UniversityDept. of Computer Sci

5、enceStoring an encrypted file F on a remote serverStoring an encrypted file F on a remote serverLater send keyword w to server, get answer, Later send keyword w to server, get answer, determine whether Fdetermine whether F contains wcontains w Trivially: server returns the entire encrypted file We w

6、ant: answer length independent of |F|Claim: to do this, sufficient to evaluate Claim: to do this, sufficient to evaluate low-degree polynomials on encrypted datalow-degree polynomials on encrypted data degree security parameter4 4Secure Computation and EfficiencySecure Computation and EfficiencyBar-

7、Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceFile is encrypted bit by bit, E(FFile is encrypted bit by bit, E(F1 1) E(F) E(Ft t) )Word has s bits wWord has s bits w1 1w w2 2w ws s For For i i=1,2,t-s+1, server computes the bit=1,2,t-s+1, serv

8、er computes the bitc ci i = = ci=1 if w=FiFi+1Fi+s-1 (w found in position i) else ci=0 Each ci is a degree-s polynomial in the Fis Trick from Smolansky93 to get degree-n polynomials,error-probability 2-nReturn n random subset-sumsReturn n random subset-sumsof the of the c ci iss (mod 2) to client (m

9、od 2) to client Still degree-n, another 2-n error5 52 mod )1 (11sjjijFwSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceWant an encryption scheme (Gen, Enc, Dec)Want an encrypt

10、ion scheme (Gen, Enc, Dec) Say, symmetric bit-by-bit encryption Semantically secure, E(0)E(1)Another procedure: Another procedure: C C* *= =EvalEval(f, C(f, C1 1,C,Ct t) ) f is a binary polynomial in t variables, degreen Represented as arithmetic circuit The Cis are ciphertextsFor any such f, and an

11、y For any such f, and any C Ci i=Enc(x=Enc(xi i) it holds that) it holds thatDec( Dec( EvalEval(f, C(f, C1 1,C,Ct t) ) = f(x) ) = f(x1 1,x xt t) ) Also |Eval(f,)| does not dependon the “size” of f (i.e., # of varsor # of monomials, circuit-size) Thats called “compactness”6 6Secure Computation and Ef

12、ficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceShared secret key: odd number Shared secret key: odd number p pTo encrypt a bit To encrypt a bit mm: : Choose at random small r, large q Output c = pq +

13、 2r + m Ciphertext is close to a multiple of p m = LSB of distance to nearest multiple of p To decrypt To decrypt c c: : Output m = (c mod p) mod 2= c p c/p mod 2= c c/p mod 2 = LSB(c) XOR LSB(c/p)7 7c/p is rounding of the rational c/p to nearest integerNoise much smaller than pThe “noise”Secure Com

14、putation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceBasically because:Basically because: If you add or multiply two near-multiples of p, you get another near multiple of pSecure Computation

15、 and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120118 8Bar-Ilan UniversityDept. of Computer Sciencec c1 1=q=q1 1p+2rp+2r1 1+m+m1 1, c, c2 2=q=q2 2p+2rp+2r2 2+m+m2 2c c1 1+c+c2 2 = (q = (q1 1+q+q2 2)p + 2(r)p + 2(r1 1+r+r2 2) + (m) + (m1 1+m+

16、m2 2) ) 2(r1+r2)+(m1+m2) still much smaller than pc1+c2 mod p = 2(r1+r2) + (m1+m2)c c1 1 x c x c2 2 = ( = (c c1 1q q2 2+q+q1 1c c2 2 q q1 1q q2 2p)p p)p + 2(2r + 2(2r1 1r r2 2+r+r1 1mm2 2+m+m1 1r r2 2) + m) + m1 1mm2 2 2(2r1r2+) still smaller than pc1xc2 mod p = 2(2r1r2+)+m1m2Distance to nearest mul

17、tiple of pSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120119 9Bar-Ilan UniversityDept. of Computer ScienceSecure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University,

18、 Israel 20112011c c1 1=q=q1 1p+2rp+2r1 1+m+m1 1, , c, , ct t=q=qt tp+2rp+2rt t+m+mt tLet f be a multivariate poly with integer Let f be a multivariate poly with integer coefficients (sequence of +s and coefficients (sequence of +s and xsxs) )Let c = Let c = EvalEval(f, c(f, c1 1, , c, , ct t) = f(c)

19、 = f(c1 1, , c, , ct t) ) f(c1, , ct) = f(m1+2r1, , mt+2rt) + qp = f(m1, , mt) + 2r + qp (c mod p) mod 2 = f(m1, , mt)Suppose this noise is much smaller than pThats what we want!1010Bar-Ilan UniversityDept. of Computer ScienceCan keep adding and multiplying until the Can keep adding and multiplying

20、until the “noise term” grows larger than p/2“noise term” grows larger than p/2 Noise doubles on addition, squares on multiplication Initial noise of size 2n Multiplying d ciphertexts noise of size 2dnWe choose r 2We choose r 2n n, p 2, p 2n n (and q 2(and q 2n n ) ) Can compute polynomials of degree

21、 n before the noise growstoo large25Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120111111Bar-Ilan UniversityDept. of Computer ScienceCiphertextCiphertext size grows with degree of f size grows with degree of f Also (slow

22、ly) with # of termsInstead, publish one “noiseless integer” N=Instead, publish one “noiseless integer” N=pqpq For symmetric encryption, include N with the secret key and with every ciphertext For technical reasons: q is odd, the qisare chosen from q rather than from 2n CiphertextCiphertext arithmeti

23、c mod N arithmetic mod NC Ciphertextiphertext-size remains -size remains always the same always the same1212Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120115Bar-Ilan UniversityDept. of Computer ScienceUsed to prove secu

24、rityRothblum11Rothblum11: Any : Any homomorphichomomorphic and and compact compact symmetric encryption (symmetric encryption (wrtwrt class class C C including including linear functions), can be turned into public keylinear functions), can be turned into public key Still homomorphic and compact wrt

25、 essentially the same class of functions CPublic key: Public key: t random bits m=(mt random bits m=(m1 1mmt t) and ) and their symmetric encryption their symmetric encryption c ci i= =EncEncsksk(m(mi i) ) t larger than size of evaluated ciphertextNewEncNewEncpkpk (b): (b): Choose random sChoose ran

26、dom ss.ts.t. . =b, use =b, use EvalEval to get to get c c* *= =EncEncsksk () Note that s c* is shrinking1313Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceThe approximate-GCD

27、 problem:The approximate-GCD problem: Input: integers w0, w1, wt, Chosen as w0=q0p, wi=qip + ri (p and q0 are odd) p$0,P, qi$0,Q, ri$0,R (with R P Q) Task: find pThmThm: If we can distinguish Enc(0)/Enc(1) for : If we can distinguish Enc(0)/Enc(1) for some p, then we can find that psome p, then we c

28、an find that p Roughly: the LSB of ri is a “hard core bit” If approx-GCD is hard then If approx-GCD is hard thenscheme is securescheme is secure(Later: Is approx-GCD hard?)(Later: Is approx-GCD hard?)Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israe

29、l University, Israel 201120111414Bar-Ilan UniversityDept. of Computer ScienceA.A. The approximate-GCD problem: The approximate-GCD problem: Input: w0=q0p, wi=qip+ri p$0,P, qi$0,Q, ri$0,R (with R P Q) Task: find pB.B. The cryptosystem The cryptosystem Input: : N=q0p, mj, cj=qjp+2rj+mj, c=qp+2r+m p$0,

30、P, qi$0,Q, ri$0,R (with R P RUse reliable distinguisher to learn qUse reliable distinguisher to learn q0 0 Using the binary GCD procedureFinally p = wFinally p = w0 0/q/q0 0Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120

31、111616Bar-Ilan UniversityDept. of Computer ScienceWe have We have w wi i= =q qi ip+rp+ri i, need x, need xi i=q=qi ip+p+2 2r ri i Then we can add the LSBs to get cj = xj + mjSet N=wSet N=w0 0, x, xi i=2w=2wi i mod N mod N Actually xi=2(wi+ri) mod N with ri random R by a super-polynomial factor 2qi m

32、od q0 is random in q0Secure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel 2011Bar-Ilan University, Israel 20111717Bar-Ilan UniversityDept. of Computer ScienceGiven Given anyany integer z= integer z=qp+rqp+r, with rR:, with rR:Set c = z+ m+2(r + subsetSumwi) m

33、od N For random rR, random bit mFor For everyevery z (with small noise), c is a nearly z (with small noise), c is a nearly random random ciphertextciphertext for for m+LSBm+LSB(r)(r) subsetSum(qis) mod q0 almost uniform in q0 subsetSum(ris)+r distributed almost identically to rFor every z=For every

34、z=qp+rqp+r, generate, generaterandom random ciphertextsciphertexts for bits for bitsrelated to LSB(r)related to LSB(r)Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120111818Bar-Ilan UniversityDept. of Computer ScienceGiven

35、 Given anyany integer z= integer z=qp+rqp+r, with rR:, with rR:Set c = z+ m+2(r + subsetSumwi) mod N For random rR, random bit mFor For everyevery z (with small noise), c is a nearly z (with small noise), c is a nearly random random ciphertextciphertext for for m+LSBm+LSB(r)(r) A guess for c mod p m

36、od 2 vote for r mod 2Choose many random Choose many random cscs, take majority, take majorityNoticeable advantage for random cs Reliably computing r mod 2 for every z with small noiseSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Isr

37、ael 201120111919Bar-Ilan UniversityDept. of Computer Sciencez = (2s)p + r z/2=sp+r/2 floor(z/2) = sp+floor(r/2)From From anyany z= z=qp+rqp+r (rR) can get r mod 2 (rR) can get r mod 2 Note: z = q+r mod 2 (since p is odd) So (q mod 2) = (r mod 2) (z mod 2)Given zGiven z1 1, , z z2 2, both near multip

38、les of p, both near multiples of p Get bi := qi mod 2, if z1|p|p|2 2 In our case |p|n2, |qi|n5 |p|2Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120112626Bar-Ilan UniversityDept. of Computer ScienceConsider the rows of thi

39、s matrix B:Consider the rows of this matrix B: They span dim-(t+1) lattice(q(q0 0,q,q1 1,q,qt t) ) B is shortB is short 1st entry: q0R 1): q0(qip+ri)-qi(q0p)=q0ri Less than QR in absolute value Total size less than QRt vs. size QP (or more) for basis vectorsHopefully we can find it with Hopefully we

40、 can find it with a lattice-reduction algorithm a lattice-reduction algorithm (LLL or variants)(LLL or variants)R w1 w2 wt -w0 -w0 -w0B=Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120112727Bar-Ilan UniversityDept. of Com

41、puter ScienceIs (qIs (q0 0,q,q1 1,q,qt t) ) B the shortest in the lattice?B the shortest in the lattice? Is it shorter than tdet(B)1/t+1 ? det(B) is small-ish (due to R in the corner) Need (QP)tR)1/t+1 QR t+1 (log Q + log P log R) / (log P log R) log Q/log Plog Q = log Q = w w(log(log2 2P) P) need t

42、= need t=w w(log P)(log P)Quality of LLL & co. degrades with tQuality of LLL & co. degrades with t Find vectors of size 2etshortest t=w(log P) 2etQR det(B)1/t+1 Contemporary lattice reduction not strong enoughMinkowski boundR w1 w2wt -w0 -w0 -w0Secure Computation and EfficiencySecure Computa

43、tion and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120112828Bar-Ilan UniversityDept. of Computer SciencetlogQ/logPsize (log scale)the solution weare seeking auxiliary solutions(Minkowski)converges to logQ+logPWhat LLL can findmin(blueblue,purplepurple)+etblue lineremains ab

44、ovepurple linelog QSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120112929Bar-Ilan UniversityDept. of Computer ScienceA Simple Scheme that supports computing A Simple Scheme that supports computing low-degree polynomials o

45、n encrypted datalow-degree polynomials on encrypted data Any fixed polynomial degree can be done To get degree-d, ciphertext size must be w(nd2)Already can be used in applicationsAlready can be used in applications E.g., the keyword-match exampleNext we turn it into aNext we turn it into afully-full

46、y-homomorphichomomorphic scheme scheme3030Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011Bar-Ilan UniversityDept. of Computer ScienceSecure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University

47、, Israel Bar-Ilan University, Israel 20112011Part IIPart II3131Bar-Ilan UniversityDept. of Computer ScienceSo far, can evaluate low-degree polynomialsSo far, can evaluate low-degree polynomialsf(x1, x2 , xt)fx2xtx1Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan Uni

48、versity, Israel University, Israel 201120113232Bar-Ilan UniversityDept. of Computer ScienceSo far, can evaluate low-degree polynomialsSo far, can evaluate low-degree polynomialsCan Can evaleval y= =f(x1,x2,xn) when when xis are “fresh”s are “fresh”But But y is “evaluated is “evaluated ciphertextciph

49、ertext” ” Can still be decrypted But eval Q(y) has too much noisefSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011x2xtx1f(x1, x2 , xt)3333Bar-Ilan UniversityDept. of Computer ScienceSo far, can evaluate low-degree polyn

50、omialsSo far, can evaluate low-degree polynomialsBootstrapping to handle higher degrees:Bootstrapping to handle higher degrees:For a For a ciphertextciphertext c, consider , consider Dc(sk) = DecDecsk( (c) ) Hope: Dc(*) has a low degree in sk Then so are Ac1,c2(sk) = Decsk(c1) + Decsk(c2)and Mc1,c2(

51、sk) = Decsk(c1) x Decsk(c2)fSecure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 20112011f(x1, x2 , xt)3434x2xtx1Bar-Ilan UniversityDept. of Computer ScienceMc1,c2sk1sk2sknInclude in the public key also Include in the public key als

52、o EncEncpk( (sk) )HomomorphicHomomorphic computation computation applied only to the “fresh” applied only to the “fresh” encryption of encryption of sksk1sk2sknx1x2c1c2Mc1,c2(sk)= Decsk(c1) x Decsk(c2) = x1 x x2cRequires “circular security”Secure Computation and EfficiencySecure Computation and Effi

53、ciencyBar-Bar-IlanIlan University, Israel University, Israel 201120113535Bar-Ilan UniversityDept. of Computer ScienceFix a scheme (Gen, Enc, Dec, Fix a scheme (Gen, Enc, Dec, EvalEval) ) For a classFor a class F F of functions , denoteof functions , denoteC CF F = Eval(f, c1,ct) : f F, ci Enc(0/1) E

54、ncrypt some t bits and evaluate on them some fFScheme Scheme bootstrappablebootstrappable if exists if exists F F for which: for which: Eval “works” for F f F, ci Enc(xi), Dec( Eval(f,c1,ct) ) = f(x1,xt) Decryption + add/mult in F c1,c2CF , Ac1,c2(sk), Mc1,c2(sk) FThmThm: Circular secure : Circular

55、secure & & BoostrappableBoostrappable HomomorphicHomomorphic for any for any funcfunc. .3636Secure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University, Israel 20112011Bar-Ilan UniversityDept. of Computer Sciencec/p, rounded to nearest in

56、tegerDecDecp p(c) = LSB(c) (c) = LSB(c) LSB(c/p) LSB(c/p) We have |c|n5, |p|n2Navely computing c/p takes degree nNavely computing c/p takes degree n5 5Our scheme only supports degree Our scheme only supports degree n nNeed to “squash the decryption circuit” Need to “squash the decryption circuit” in

57、 order to get a in order to get a bootstrappablebootstrappable scheme scheme Similar techniques to Gentry 09Secure Computation and EfficiencySecure Computation and EfficiencyBar-Bar-IlanIlan University, Israel University, Israel 201120113737Bar-Ilan UniversityDept. of Computer ScienceAdd to public k

58、ey another “hint” about Add to public key another “hint” about sksk Hint should not break secrecy of encryptionWith hint, With hint, ciphertextciphertext can be publically can be publicallypost-processed, leaving less work for Decpost-processed, leaving less work for DecIdea is used in server-aided

59、cryptography.Idea is used in server-aided cryptography.Old decryption algorithmmcskDecSecure Computation and EfficiencySecure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University, Israel 201120113838Bar-Ilan UniversityDept. of Computer ScienceSecure Computation and EfficiencySec

60、ure Computation and EfficiencyBar-Ilan University, Israel Bar-Ilan University, Israel 20112011Old decryption algorithmmcskDeccf(sk, r)PublicPost-Processingsk*mDec*c*Processed ciphertextNew approachThe hint about sk in public keyHint in pub key lets anyone post-process the ciphertext, leaving less work for Dec*3939