Computation on Randomized Data

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

1、ComputationonRandomizedDataFlorianKerschbaumSAPResearchKarlsruhe,Germanyflorian.kerschbaum@sap.comAbstractCryptographictools,suchassecurecomputationorhomomorphicencryption,areverycomputation-allyexpensive.Thismakestheiruseforconfidentialityprotectionofclient’sdataagainstanuntrustedserviceprovider

2、uneconomicalinmostapplicationsofcloudcomputing.Inthispaperwepresenttech-niquesforrandomizingdatausinglight-weightoperationsandthensecurelyoutsourcingthecomputationtoaserver.Wediscusshowtoformallyassessthesecurityofourapproachandpresentlinearprogram-mingasacasestudy.1IntroductionWhitDiffieiscommonl

3、yquotedwith“cryptographywillnotbethesolutionforsecurityofcloudcomputing”duetoeconomicreasons[9].Cryptographictools,suchassecurecomputation[6,11,23]orhomomorphicencryption[10,17]arecomputationallyexpensive.Recentresults[5,12,14,18]indicatethatwhiletheyarefeasibleforsmallcomputationstheyareorderso

4、fmagnitudeslowerthannon-securecomputations.Thegeneralargumentisthenthatnon-secure,localcomputation–evenoncomputationalweakdevicessuchasmobilephones–ismoreeconomicalthancryptographicallyprotectedcloudcomputing.Inthispaperwepresentanalternativeapproachbasedonrandomizationofinputdata.Theclientscomp

5、utealightweightfunctiony=f(x,r)ontheirinputxusingrandomcointossesr.Theoutputyissenttothecloudserviceproviderwhocomputes–theusuallyunmodified–functionz=g(y)andreturnsittotheclient.Theclientthende-randomizesusingthefunctionf′(z,r).Theideaisthatforcorrectnessf′(g(f(x,r)),r)=g(x)Twoperformanceobjecti

6、vesshouldbeobserved.First,thefunctionfshouldbeeasytocompute.Weproposeasadesignprincipletoonlyuselightweightrandomizationoperations.Forscalardataonlythefollowingoperationsshouldbeused:•additionofrandomnumbers•multiplicationwithrandomnumbersForvectordataonlythefollowingoperationsshouldbeused:•perm

7、utation•creationofnewelements•splittingofelementsAlltheseoperationscanbeperformedmuchfasteroncurrenthardwarethanoperationscommonlyusedincryptographicprotection,suchasmodularexponentiation.Thesecondperformanceobjectiveisthatc