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

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

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

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

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