Lecture 22 Homomorphic Encryption 4

《Lecture 22 Homomorphic Encryption 4》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Lecture22

2、HomomorphicEncryption4:Constructionoffullyhomomorphicencryption.BoazBarakApril21,2010Reviewofmildlyhomomorphicscheme(Recallthatbxedenotestheintegerclosesttox,breakingties,say,downwards.)AssumptionWe'llmakethefollowinglearningdivisorwithnoise"assumptio

3、n:LDNAssump-tion:letParandomnbitprime,Rarandomn4bitprime,andletN=PR.Adistin-guisherthatisgivenNandX1;:::;Xpoly(n)cannotdistinguishbetweencase(I)Xi'sarechosenindependentlyatrandomfrom[N],and(II)Xi=PQi+2Ei(modN)whereQiischosenindependentlyatrandomfrom[R]andEiischo

4、senindependentlyatrandomfrom[2n0:1;+2n0:1].Note:FollowingSushant'ssuggestion,IchangedtheLDNassumptionsothatNisanexactmultipleofP.Thismakesreducingciphertextsizemucheasier,sincenowreducingmoduloNdoesn'tintroduceanyadditionalnoise(canyouseewhy?).Ialsochangedthepa

5、rametersabit(setNtohaven5bitsratherthan100n),sincethereareinfactsomeattacksifNisnotbigenough.Thismakesnodierenceinanythingwediscussedlasttime.Addingthe(modN)incase(II)doesnotmakeanydierenceaswith1negl(n)probabilityXiwillbeanumberbetween1andN

6、it'sjustabitclean

7、erthisway.Revisionoflastlecture'sscheme:Belowisaslightvariantoftheprivatekeymildlyhomomor-phicschemeweshowedonMonday.AsImentionedinclassandyou'llshowinanexercise,afullyhomomorphicprivatekeyencryptionimpliesafullyhomomorphicpublickeyencryption,sooncewegetafullyho

8、momorphicencryptionwe'llbene.KeyWechoosePtobearandomnbitprime,andRtobearandomn4bitprime,N=PQ.WekeepPsecret,andcanpublishNasapublicparameter.(OnecanalsothinkofNasbeingconcatenatedtoeveryencryption.)EncryptionEncE(b)denotesencryptionofbwithkeyPandnoiseparameterE.

9、It'sdenedPasfollows:chooseQR[N=P]andEpR[E;+E],andoutputX=QP+2E+b(modN).WesettheparameterEtobe2n.DecryptionTodecryptX,outputXbX=PeP(mod2).11Thisisaclosevarianttothedecryptionalgorithmofoutputting(X+2bP=4c(modP))(mod2)IshowedlasttimesinceXbX=PePisthesameasXbX

10、=P+0:5cP,whichinourcase(whereX=Pisveryclosetoaninteger)equalsX+2bP=4c(modP)uptoanevennumber.1pSecurityandcorrectnessofschemeThechoice2nfortheparameterEmakestheschemeb