提供差分隱私保護(hù)的線性查詢新方法.pdf

1、差分隱私是一種處理敏感數(shù)據(jù)分析任務(wù)時(shí)的隱私保護(hù)原理，在許多的場合下都得到了成功的應(yīng)用。差分隱私與許多更早的隱私保護(hù)原理不同，它定義了十分嚴(yán)謹(jǐn)?shù)碾[私擔(dān)保形式，并要求其數(shù)據(jù)分析技術(shù)都能夠從數(shù)學(xué)上嚴(yán)格證明滿足所定義的隱私擔(dān)保。簡單來說，差分隱私在數(shù)據(jù)發(fā)布過程中對任何個(gè)人敏感數(shù)據(jù)參與發(fā)布過程所招致的風(fēng)險(xiǎn)進(jìn)行了定量的控制，從而使任何攻擊者都無法從發(fā)布結(jié)果推斷出任何單個(gè)參與者的敏感信息。目前，研究者們已經(jīng)對差分隱私進(jìn)行了大量的研究工作，并提出了許多

2、有效的敏感數(shù)據(jù)分析方法。然而，差分隱私作為一個(gè)新的研究領(lǐng)域，仍然有許多新的問題有待解決。在這篇論文中，我們提出了三種在差分隱私下進(jìn)行數(shù)據(jù)查詢的新方法，顯著提高了敏感數(shù)據(jù)查詢的效率與有效性。
　　實(shí)現(xiàn)差分隱私的一個(gè)最簡單有效的方法是Laplace機(jī)制，它通過往查詢結(jié)果中引入獨(dú)立同分布的Laplace噪聲來隱藏個(gè)人信息。雖然這個(gè)方法十分簡單且被廣泛應(yīng)用，但它卻要求查詢結(jié)果對個(gè)體參與者的全局敏感度必須是有限而且較小的。對于許多復(fù)雜查詢，

3、例如SQL查詢結(jié)果上的聚合以及子圖計(jì)數(shù)，查詢結(jié)果卻很可能有著過大甚至無限的全局敏感度?，F(xiàn)有的差分隱私機(jī)制并不能夠處理如此復(fù)雜的查詢。我們首先提出了一個(gè)基于經(jīng)驗(yàn)敏感度的查詢機(jī)制，它可以處理跟個(gè)體參與者之間有著復(fù)雜關(guān)系的查詢，并且允許查詢有無限大的全局敏感度。除此之外，我們的機(jī)制還能用于處理任意的子圖計(jì)數(shù)查詢并實(shí)現(xiàn)節(jié)點(diǎn)差分隱私，而這在過去是無法做到的。
　　對于許多線性查詢，Laplace機(jī)制所引入的獨(dú)立噪聲并不是最優(yōu)的。為了優(yōu)化查詢

4、精度，一些機(jī)制往查詢結(jié)果引入相關(guān)的噪聲來減小所需噪聲的大小。然而，當(dāng)查詢序列是用戶任意給定時(shí)，這些機(jī)制為了找到最優(yōu)的噪聲分布需要的計(jì)算開銷非常大，隨數(shù)據(jù)維度增加呈指數(shù)增長。因此，這些機(jī)制在實(shí)踐中無法用于高維數(shù)據(jù)集。我們提出了一個(gè)基于子敏感度概念的改進(jìn)機(jī)制，它不但可以通過往查詢結(jié)果引入相關(guān)的噪聲來優(yōu)化查詢精度，且其計(jì)算開銷隨數(shù)據(jù)維度增加僅呈多項(xiàng)式增長。岡此，它在實(shí)踐中的效率和可用性跟以往的方法相比有著顯著的提高。
　　最后，我們提出