Optimization of Fully Homomorphic Encryption

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

1、OptimizationofFullyHomomorphicEncryptionJean-SebastienCoron1,DavidNaccache2,andMehdiTibouchi1;21UniversiteduLuxembourg6,rueRichardCoudenhove-Kalergil-1359Luxembourg,Luxembourgjean-sebastien.coron@uni.lu2EcolenormalesuperieureDepartementd'informatique,G

2、roupedecryptographie45,rued'Ulm,f-75230ParisCedex05,Francefdavid.naccache,mehdi.tibouchig@ens.frAbstract.Wedescribeacompressiontechniquethatreducesthepublic-keysizeofthevanDijketal.6:55fullyhomomorphicschemeovertheintegersfromO~()toO~().Ourvariantremainss

3、emanticallysecure,butintherandomoraclemodel.Weobtainanimplementationofthefullschemewithapublic-keysizeof4:6MBinsteadof802MBusingthesameparametersandwiththesameeciencyasin[3].AsimilarcompressiontechniqueisalsoapplicabletoBrakerskiandVaikuntanathan'sfullyhom

4、omorphicscheme.WealsoshowhowtoadaptthenewframeworkfromBrakerski,GentryandVaikuntanathanforleveledfullyhomomorphicencryptiontothevanDijketal.schemeovertheintegers.1IntroductionFullyHomomorphicEncryption.Anencryptionschemeissaidtobefullyhomomorphicwhenitispos

5、sibletoperformimplicitadditionandmultiplicationofplaintextwhilemanipulatingonlyciphertexts.TherstconstructionofafullyhomomorphicschemewasdescribedbyGentryin[5].Gentryrstdescribedasomewhathomomorphic"schemethatsupportsalimitednumberofadditionsandmultiplic

6、ationsonciphertexts.Thisisbecausetheciphertextnoiseincreaseswitheverymultiplicationandmustremainupper-bounded;thereforeonlyapolynomialofsmalldegreecanbeappliedonciphertexts.ThesecondstepinGentry'sframeworkconsistsinsquashing"thedecryptionproceduresothatitc

7、anbeexpressedasalowdegreepolynomialinthebitsoftheciphertextandthesecretkey.ThenGentry'skeyideaconsistsinevaluatingthisdecryptionpolynomialnotonthebitsoftheciphertextandthesecret-key(whichwouldgivetheplaintext),buthomomorphicallyontheencryptionofthosebits,wh

8、ichgivesanotherciphertextforthesameplaintext.Ifthedegreeofthedecryptionpolynomialissmallenough,thenoiseofthenewciphertextcanbeactuallysmallerthanintheoriginalciphertext,andthereforethisnewciphertextcan