資源描述:
《Fully Homomorphic Encryption Using Ideal Lattices》由會(huì)員上傳分享,免費(fèi)在線(xiàn)閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
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},onecane?cientlycomputeeψi=(πi)modN,aciphertextthatencryptsthetoconstructanencryptionschemethatpermitsevaluationiiproductoftheoriginalplaintexts.Rivestetal.[54]askedofarbitrarycircuits,itsu?cestoconstructanencryptionanaturalquestion:Whatcanonedowithanencryp
4、tionschemethatcanevaluate(slightlyaugmentedversionsof)schemethatisfullyhomomorphic:aschemeEwithane?-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.toitthatcanbee?cientlyexpressedasacircuit)withoutUnfortunately,ourinitialschemeisnotquitebootstrap-thedecryptio
8、nkey.Asanapplication,theysuggestedpri-pable–i.e.,thedepththattheschemecancorrectlyevalu-vatedatabanks:ausercanstoreitsdataonanuntrustedatecanbelogarithmicinthelatticedimension,justlikethe