News Homomorphic encryption

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

1、NewsHomomorphicencryption CraigGentrysubmittedhisthesis"AFullyHomomorphicEncryptionScheme"totheStanfordComputerScienceDepartmentinSeptember2009.ThetalkhegaveonthetopicatSTOC2009(The41stannualACMsymposiumonTheoryofcomputing)backinJunedoesnotseemtohavepe

2、netratedthemainstreammediaatthetime,butraisedaconsiderablestirinonlinenewslettersandlistsassociatedtotheworldofdatasecurity:averyuseful"popularexplanation"byHalFinneyontheCryptographymailinglist(June16),alongwithreportsinVoltageSuperconductor(June24),F

3、orbes.com(June24),eWeek.com(June25)andComputerworld(June25).ThereisalsoausefulreportontheIBMwebsite.ThestoryfinallymadeittoBusinessWeekinaposting("IBM'sEncryptionBreakthroughfortheWeb")byStephenBakeronSeptember30.ThecommonlyusedRSAcodeisonlyhomomorphic

4、withrespecttomultiplication.If(N,k)isyourpublickey,youencodexasxkmodN.Sincexkyk=(xy)k,andsince(amodN)(bmodN)=(abmodN),itfollowsthatthecodeforxyistheproductofthecodesforxandy.Soyoucouldcorrectlymultiplytwoencryptednumberswithouteverknowingwhatthenumbers

5、were.Ifanencryptionisfullyhomomorphic,youcansendyourtaxaccountantanencryptedcopyofallyourfinancialdata,andgetbackanencryptedcopyoftheamountyouowe,withoutrevealinganythingaboutyouractualincomeandexpenses.(ThisexamplefromAndyGreen'sarticleonForbes.com).T

6、hetroublewiththefullyhomomorphicencryptionschemesknownbeforeGentryisthatafterasmallnumberofoperationstheyloseaccuracyandcannotbereliablydecrypted.Gentrymanagedtodeviseaninitialencryption(alatticeencryption,notanRSAcode;insteadoffactorizationitusesadiff

7、erenthardproblem)thatwashomomorphicenoughtoimplementitsowndecryptingalgorithm,plusalittleextra.HalFinney:"IhavetogobacktoGödel'sandTuring'sworktothinkofacomparableexampleexploitingthepowerofself-embedding."Onceyouhavea"homomorphicenough"encryptionalgor

8、ithmE,Gentryexplainshowtohomomorphicallyimplementafunctionfofarbitrarycomplexity;thisisillustratedinthe"bootstrapping"diagrambelow.Youchooseenoughdifferent(publickey,privatekey)pairssothatthe"littleextra"sadduptoenoughforyourjob.Youencr