差分隐私保护研究综述

2012-03-162012-04-28610741852010B0903010421980-、1981-、1979-、。*abbaba．b．510006、。、PINQprivacyintegratedqueries。TP309A1001-3695201209-3201-05doi10．3969/j．issn．1001-3695．2012．09．001SurveyofresearchondifferentialprivacyLIYangabWENWenbXIEGuang-qiangaba．SchoolofAutomationb．SchoolofComputersGuangdongUniversityofTechnologyGuangzhou510006ChinaAbstractDifferentialprivacyapproachmakesdatadistortiontopreserveprivacybymeansofaddingnoise．Toarigorousde-finedattackingmodeldifferentialprivacyensuresthataddinglittleamountofnoisehavealowriskofprivacydisclosure．ThispapersurveyedthedefinitionofdifferentialprivacyshowedthenewestresultsinresearchintroducedalgorithmsofclassifyclusteringondifferentiallyprivatelearningandpresentedadifferentialprivacyapplicationframeworkPINQprivacyintegrat-edqueries．Finallythispaperdiscusseddirectionsforfutureresearch．Keywordsdifferentialprivacyprivacypreservingdatadistortiondataminingdatareleasing0。AOL。、、。。、。、。、1。。k-l-diversity。k-SamaratiSweeneyk－123。k-homogeneityat-tackbackgroundknowledgeattack4。k-Machanavajjhalal-diversity5。k-ll-diversity。l-diversity1/l。l-diver-sitysimilarityattack4。k-l-di-versity。2006Dworkdifferentialprivacy。、。。。。29920129ApplicationResearchofComputersVol.29No.9Sep．2012。Cormode6、。Sarathy7。Dwork89pan-privacy。。Li10k-。Zhou11、PCA。Vu12。Gehrke13。Zhang14。115～21。。1D1D2RangeKKPrEsEsKε-SRangeKPrKD1∈S≤expε×PrKD2∈S1K。1D1D2ε-。KK1。fXfX。KfX。fε-KfX+lapΔf/εkΔff1。1f∶D→RkfΔf=maxD1D2‖fD1－fD2‖12D1D2。fΔf。PΔf=1。fX。lapb=exp－x/b槡2bb=Δf/εpx=exp－x/b/2bDx=1/21+sgnx1－expx/b。Δf、εΔf。εlapΔf/εεf。2。ε-ε。ε。attackingmodelk-l-diversity。。1D1D2D1D2“”。2。2008Blum22“”“”VC。222324。Hardt25k-。L1k-。26。Roth27·2023·29。。2.12010。Xiao23Haar。H。Hay24。Li262324。。。2.2。Blum22On2/3nDwork282922。Gup-ta30Hardt31。Roth27n2/3logklogX1/3ε1/3。Hardt32n1/2logklogX1/4ε。ε-nkX。2012Gupta3327323031IDC。IDC。3。。。。3.1contingencytable、marginals。2005Chawla34。2006Dwork35、。2011Dwork20kk11。。3.2K-means2005Blum36K-meansε-K-means。K-means。。Sj。ε。2011Dwork20K-means。01dd+1Dworkε。Nlapd+1N/εε-d+1ε/2d+1ε/4“”。。3.33.3.1ERM2008Chaudhuri37Dwork·3023·9。2011Chaudhuri3837ERMERM———。Dwork。D=ziεpΛc。fpriv。aJprivfD=JfD+1nbTf。JfDbvb=1αe－β‖b‖αβ=εp。bε'p=εp－log1+2cnΛ+c2n2Λ()2。ε'p＞0Δ=0Δ=cneεp/4－1－Λ。ε'p=εp/2β=ε'p/2vb=1αe－β‖b‖。log1+2cnΛ+c2n2Λ()2。cfpriv=argminJprivf()D+12Δ‖f‖2。Chaudhuri。。3.3.2Jagannathan39。ID3。。。Pathak40。4PINQPINQprivacyintegratedqueries41Dwork。PINQLINQAPI。3PINQ。。“25”。ε。、、。5、、。。。125。。。2。42。。1．J．2009325847-861．2SWEENEYL．k-anonymityamodelforprotectingprivacyJ．Inter-nationalJournalonUncertaintyFuzzinessandKnowledge-basedSystems2002105557-570．3SWEENEYL．Achievingk-anonymityprivacyprotectionusinggener-alizationandsuppressionJ．IntemationalJournalonUncertainty·4023·29FuzzinessandKnowledge-basedSystems2002105571-588．4LiNing-huiLITian-chengVENKATASUBRAMANIANS．t-close-nessprivacybeyondk-anonymityandl-diversityC//Procofthe23rdInternationalConferenceonDataEngineering．WashingtonDCIEEEComputerSociety2007106-115．5MACHANAVAJJHALAAKIFERDGEHRKEJetal．l-diversityprivacybeyondk-anonymityC//Procofthe22ndInternationalCon-ferenceonDataEngineering．WashingtonDCIEEEComputerSocie-ty200624-35．6CORMODEGPROCOPIUCMSRIVASTAVAD．etal．DifferentiallyprivatepublicationofsparsedataJ．ArxivPreprintarXiv1103．08252011．7SARATHYRMURALIDHARK．Someadditionalinsightsonapply-ingdifferentialprivacyfornumericdataC//ProcofInternationalConferenceonPrivacyinStatisticalDatabases．BerlinSpringer-Ver-lag2010210-219．8DWORKCNAORMPITASSITetal．Pan-privatestreamingalgo-rithmsC//Procofthe1stSymposiumonInnovationsinComputerScience．BeijingTsinghuaUniversityPress2010．9DWORKCNAORMPITASSITetal．DifferentialprivacyundercontinualobservationC//Procofthe42ndACMSymposiumonTheoryofComputing．NewYorkACMPress2010715-724．10LINing-huiQARDAJIWSUDong．Provablyprivatedataanony-mizationork-anonymitymeetsdifferentialprivacyCERIASTR2010-24R．WestLafayetteCenterforEducationandResearchIn-formationAssuranceandSecurityPurdueUniversity2010．11ZHOUShu-hengLIGETTKWASSERMANL．DifferentialprivacywithcompressionC//ProcofIEEEInternationalSymposiumonIn-formationTheory．WashingtonDCIEEEComputerSociety20092718-2722．12VUDSLAVKOVICA．Differentialprivacyforclinicaltrialdatapre-liminaryevaluationsC//Procofthe9thIEEEInternationalConfer-enceonDataMining．WashingtonDCIEEEComputerSociety2009138-143．13GEHRKEJLUIEPASSR．Towardsprivacyforsocialnetworksazero-knowledgebaseddefinitionofprivacyC//Procofthe8thCon-ferenceonTheonyofCryptography．BerlinSpringer-Verlag2011432-449．14ZHANGNingLIMingLOUWen-jing．DistributeddataminingwithdifferentialprivacyC//ProcofIEEEInternationalConferenceonCommunications．20111-5．15DWORKC．DifferentialprivacyC//Procofthe33rdInternationalColloquiumonAutomataLanguagesandProgramming．BerlinSpringer-Verlag2006．16DWORKC．DifferentialprivacyasurveyofresultsC//Procofthe5thInternationalConferenceonTheoryandApplicationsofModelsofComputation．BerlinSpringer-Verlag20081-9．17DWORKC．ThedifferentialprivacyfrontierC//Procofthe6thIn-ternationalConferenceonTheoryofCryptographyConference．BerlinSpringer-Verlag2009496-502．18DWORKC．DifferentialprivacyinnewsettingsC//Procofthe21stAnnualACM-SIAMSympo