资源描述：
《Fully Homomorphic Encryption over the Integers》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、FullyHomomorphicEncryptionovertheIntegersMartenvanDijkCraigGentryShaiHaleviVinodVaikuntanathanMITIBMResearchIBMResearchIBMResearchJune8,2010AbstractWedescribeaverysimple“somewhathomomorphic”encryptionschemeusingonlyelemen-tarymodulararithmetic,anduseGentry’stechniquestoconvertitintoafullyh
2、omomorphicscheme.ComparedtoGentry’sconstruction,oursomewhathomomorphicschememerelyusesadditionandmultiplicationovertheintegersratherthanworkingwithideallatticesoverapolynomialring.Themainappealofourapproachistheconceptualsimplicity.Wereducethesecurityofoursomewhathomomorphicschemetofindinga
3、napproximateintegergcd–i.e.,givenalistofintegersthatarenear-multiplesofahiddeninteger,outputthathiddeninteger.Weinvestigatethehardnessofthistask,buildingonearlierworkofHowgrave-Graham.1IntroductionWhatisthesimplestencryptionschemeforwhichonecanhopetoachievesecurity?TheCaesarcipherissimple,
4、butnotsecure.Webelievethatconventionalpublic-keyencryptionschemeswithmodularexponentiationsaresecure,butmodularexponentiationisnotaverysimpleoperation.Ifweweretoforgetourcurrentschemesandstartfromscratch,perhapssomethinglikethefollowingschemewouldbeagoodcandidateforasimplesymmetricencrypti
5、onscheme:KeyGen:Thekeyisanoddinteger,chosenfromsomeintervalp∈[2η−1,2η).Encrypt(p,m):Toencryptabitm∈{0,1},settheciphertextasanintegerwhoseresiduemodphasthesameparityastheplaintext.Namely,setc=pq+2r+m,wheretheintegersq,rarechosenatrandominsomeotherprescribedintervals,suchthat2rissmallerthanp
6、/2inabsolutevalue.Decrypt(p,c):Output(cmodp)mod2.Whenthenoiserissufficientlysmallerthanthesecretkeyp,thissimpleencryptionschemeturnsouttobe“somewhathomomorphic”inthesenseof[6]–namely,itcanbeusedtoevaluatelow-degreepolynomialsoverencrypteddata.Moreover,withajudiciouschoiceofparameters(say√3r≈
7、2ηandq≈2η),thissimpleschememayevenbesecure!Specifically,wereducethesecurityoftheschemetothehardnessoftheapproximateintegergreatestcommondivisors(approximateGCD)problemwhich,roughlyspeaking,saysthatitishardtorecoverpgiventhexi’s.Thisproblem,forthecaseoftwoxi’s,w
