资源描述：
《Lecture 19 Homomorphic Encryption》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Lecture19
2、HomomorphicEncryption1:De nitionandApplicationtoPrivateInformationRetrieval,Zeroknowledge.BoazBarakApril12,2010HomomorphicencryptionWestressedthatCPAsecuritydoesnotpreventanattackerfromtamperingwiththeencryptedmessage,changingforexampleanen
3、cryptionofthemessagexintoanencryptionofxwithitslastbit
ipped.Homomorphicencryptiontakesthistoanextremeandactuallyrequiresthatitispossibletotamperwiththeencryptioninanarbitraryway(whilestillmaintainingCPAsecurity!).Thequestionifthisispossiblewas rstra
4、isedin1978byRivest,Adleman,andDertouzos,andovertheyearsmanyconjecturedthatthisisinfactimpossible.LastyearGentrygaveverystrongevidencethatsuchencryptionsexist,byconstructingsuchaschemethatissecureunderrelativelyreasonablecomputationalassumptions.De ni
5、tionWesaythataCPA-securepublickeyencryptionscheme(G;E;D)withonebitmes-sagesisfullyhomomorphicifthereexistsanalgorithmNANDsuchthatforevery(e;d)G(1n),a;b2f0;1g,and^aEe(a),^bEe(b),NANDe(^a;^b)Ee(aNANDb)wheredenotesstatisticalindistinguishability(i.e.,
6、n !(1)statisticaldistance),andaNANDbdenotes:(a^b).(Thereareseveralvariantsofthede nition,andwechosethesimplestandstrongestone.)WestressthatthealgorithmNANDdoesnotgetthesecretkeyasinput.Otherwiseitwouldbetrivial:justdecrypt^a;^b,computeaNANDbandre-enc
7、rypt.Belowwe'lloftendroptheadjective"fully".UniversalityofNANDIt'sstraightforwardtoshowthateveryloggatecanbeexpressedusingfewNANDs,andsoobtainthefollowingclaim(leftasexercise):If(G;E;D)isahomomorphicencryptionthenthereisanalgorithmEVALthatforevery(e;
8、d)G(1n),x1;:::;xm2f0;1g,if^xi=Ee(xi)andCisaBooleancircuitmappingf0;1gmtof0;1g,thenEVALe(C;x^1;:::;x^m)jCj(n)Ee(C(x1;:::;xn))wherewesaythatDD0iftheirstatisticaldistanceisatmost,issomenegligiblefunction,andjCjdenotesthenumberofgatesofC.Inparticul
9、arifCispolynomialsizethenthesetwodistributionsarestatisticallyindistin-guishable.1Whatishomomorphicencryptionusefulfor?Canonicalapplicationiscloudcomputing":Alicewantstostoreher lex2f0;1gmonBob'sserver.SoshesendsBobEe(x1)Ee(xm).Thenshewantstodoco
