资源描述：
《Fully Homomorphic Encryption Using Ideal Lattices》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、FullyHomomorphicEncryptionUsingIdealLatticesCraigGentryStanfordUniversityandIBMWatsoncgentry@cs.stanford.eduABSTRACTducedbyRivest,AdlemanandDertouzos[54]shortlyaf-tertheinventionofRSAbyRivest,AdlemanandShamirWeproposeafullyhomomorphicencryptionscheme–i.e.,[55
2、].BasicRSAisamultiplicativelyhomomorphicencryp-aschemethatallowsonetoevaluatecircuitsoverencryptedtionscheme–i.e.,givenRSApublickeypk=(N,e)anddatawithoutbeingabletodecrypt.Oursolutioncomeseinthreesteps.First,weprovideageneralresult–that,QciphertextsQ{ψi←πimod
3、N},onecanefficientlycomputeeψi=(πi)modN,aciphertextthatencryptsthetoconstructanencryptionschemethatpermitsevaluationiiproductoftheoriginalplaintexts.Rivestetal.[54]askedofarbitrarycircuits,itsufficestoconstructanencryptionanaturalquestion:Whatcanonedowithanencryp
4、tionschemethatcanevaluate(slightlyaugmentedversionsof)schemethatisfullyhomomorphic:aschemeEwithaneffi-itsowndecryptioncircuit;wecallaschemethatcanevaluatecientalgorithmEvaluateEthat,foranyvalidpublickeypk,its(augmented)decryptioncircuitbootstrappable.anycircuit
5、C(notjustacircuitconsistingofmultiplicationNext,wedescribeapublickeyencryptionschemeusingideallatticesthatisalmostbootstrappable.Lattice-basedgates),andanyciphertextsψi←EncryptE(pk,πi),outputscryptosystemstypicallyhavedecryptionalgorithmswithlowψ←EvaluateE(pk
6、,C,ψ1,...,ψt),circuitcomplexity,oftendominatedbyaninnerproductcomputationthatisinNC1.Also,ideallatticesprovideavalidencryptionofC(π1,...,πt)underpk?Theiranswer:bothadditiveandmultiplicativehomomorphisms(moduloaonecanarbitrarilycomputeonencrypteddata–i.e.,onec
7、anpublic-keyidealinapolynomialringthatisrepresentedasprocessencrypteddata(queryit,writeintoit,doanythingalattice),asneededtoevaluategeneralcircuits.toitthatcanbeefficientlyexpressedasacircuit)withoutUnfortunately,ourinitialschemeisnotquitebootstrap-thedecryptio
8、nkey.Asanapplication,theysuggestedpri-pable–i.e.,thedepththattheschemecancorrectlyevalu-vatedatabanks:ausercanstoreitsdataonanuntrustedatecanbelogarithmicinthelatticedimension,justlikethe
