資源描述：
《提供差分隱私保護(hù)的線性查詢新方法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、萬(wàn)方數(shù)據(jù)摘要差分隱私是一種處理敏感數(shù)據(jù)分析任務(wù)時(shí)的隱私保護(hù)原理，在許多的場(chǎng)合下都得到了成功的應(yīng)用。差分隱私與許多更早的隱私保護(hù)原理不同，它定義了十分嚴(yán)謹(jǐn)?shù)碾[私擔(dān)保形式，并要求其數(shù)據(jù)分析技術(shù)都能夠從數(shù)學(xué)上嚴(yán)格證明滿足所定義的隱私擔(dān)保。簡(jiǎn)單來(lái)說(shuō)，差分隱私在數(shù)據(jù)發(fā)布過(guò)程中對(duì)任何個(gè)人敏感數(shù)據(jù)參與發(fā)布過(guò)程所招致的風(fēng)險(xiǎn)進(jìn)行了定量的控制，從而使任何攻擊者都無(wú)法從發(fā)布結(jié)果推斷出任何單個(gè)參與者的敏感信息。目前，研究者們已經(jīng)對(duì)差分隱私進(jìn)行了大量的研究工作，并提出了許多有效的敏感數(shù)據(jù)分析方法。然而，差分隱私作為一個(gè)新的研究領(lǐng)域，仍然有許多
2、新的問題有待解決。在這篇論文中，我們提出了三種在差分隱私下進(jìn)行數(shù)據(jù)查詢的新方法，顯著提高了敏感數(shù)據(jù)查詢的效率與有效性。實(shí)現(xiàn)差分隱私的一個(gè)最簡(jiǎn)單有效的方法是Laplace機(jī)制，它通過(guò)往查詢結(jié)果中引入獨(dú)立同分布的Laplace噪聲來(lái)隱藏個(gè)人信息。雖然這個(gè)方法十分簡(jiǎn)單且被』。泛應(yīng)用，但它卻要求查詢結(jié)果對(duì)個(gè)體參與者的全局敏感度必須是有限而且較小的。對(duì)于許多復(fù)雜查詢，例女NSQL查詢結(jié)果上的聚合以及子圖計(jì)數(shù)，查詢結(jié)果卻很可能有著過(guò)大甚至無(wú)限的全局敏感度?，F(xiàn)有的差分隱私機(jī)制并不能夠處理如此復(fù)雜的查詢。我們首先提出了一個(gè)基二=F經(jīng)
3、驗(yàn)敏感度的查詢機(jī)制，它可以處理跟個(gè)體參與者之間有著復(fù)雜關(guān)系的查詢，并且允許查詢有無(wú)限大的全局敏感度。除此之外，我們的機(jī)制還能用于處理任意的子圖計(jì)數(shù)查詢并實(shí)現(xiàn)節(jié)點(diǎn)差分隱私，而這在過(guò)去是無(wú)法做到的。對(duì)于許多線性查詢，Laplace機(jī)制所引入的獨(dú)立噪聲并不是最優(yōu)的。為了優(yōu)化查詢精度，一些機(jī)制往查詢結(jié)果引入相關(guān)的噪聲來(lái)減小所需噪聲的大小。然而，當(dāng)查詢序列是用戶任意給定時(shí)，這些機(jī)制為了找到最優(yōu)的噪聲分布需要的計(jì)算開銷非常大，隨數(shù)據(jù)維度增加呈指數(shù)增長(zhǎng)。因此，這些機(jī)制在實(shí)踐中無(wú)法用于高維數(shù)據(jù)集。我們提出了一個(gè)基于子敏感度概念的改進(jìn)
4、機(jī)制，它不但可以通過(guò)往查詢結(jié)果引入相關(guān)的噪聲來(lái)優(yōu)化查詢精度，且其計(jì)算開銷隨數(shù)據(jù)維度增加僅呈多項(xiàng)式增長(zhǎng)。岡此，它在實(shí)踐巾的效率和可用性跟以往的方法相比有著顯著的提高。最后，我們提出了一種用于整合所有已知查詢結(jié)果的后處理技術(shù)，以利用查詢中隱藏的冗余性和相關(guān)性來(lái)提高查詢的精度。我們的方法還可以在隱私預(yù)算完全耗盡的場(chǎng)合下根據(jù)已知的信息給新查詢返回有意義的估計(jì)結(jié)果。這個(gè)方法的一個(gè)重要優(yōu)點(diǎn)是，它避免了在整個(gè)數(shù)據(jù)域上顯式地構(gòu)造柱狀圖，對(duì)于許多重要的查詢類型它的計(jì)算開銷隨數(shù)據(jù)維度增加僅呈多項(xiàng)式增長(zhǎng)，因此可適用于高維數(shù)據(jù)集。關(guān)鍵字：隱
5、私保護(hù)，差分隱私，Laplace機(jī)制，全局敏感度，局部敏感度，遞歸機(jī)制，平滑敏感度，經(jīng)驗(yàn)敏感度，子敏感度機(jī)制，K—norm機(jī)制，主成分分析，最大熵。萬(wàn)方數(shù)據(jù)AbstractDifferentialprivacyisarobustprincipleforprivacypreservingdataanalysistasks，andhasbeensuccessfullyappliedtoavarietyofapplications．Differingfrommanyearlierprivacypreservingprinc
6、iple，differentialprivacydefinesaformalprivacyguaranteeinaveryrigorousInanner．Alldifferentiallyprivatedataanalysistechniquesshouldbeabletobeprovedtosatisfydifferentialprivacybymathematics．Roughlyspeaking，theriskforanindividualincurredbyparticipatinginaprivatedat
7、apublishingisquantitativelycontrolledbydifferentialprivacy,hencenoadversarycaninfersensitiveinformationforanyparticipantfrompublisheddata．Todate，differentialprivacyhasbeenstudiedbyavastofresearchers，andmanyeffectivetechniquesforprivatedataanalysistaskshavebeenp
8、roposed．Asanewresearchdomain，however，manynewproblemsarestillleftopen．Inthispaper，weproposethreenewqueryprocessingmethodsunderdifferentialprivacy,whichsignificantlyimprovethe
