天天看點

差分隐私理論入門科普

        在基于隐私保護的資料釋出研究中,主要考慮兩個因素:1)隐私的保護性,即確定資料不會造成隐私洩漏;2)資料的有效性,即資料隐私保護後資料仍具有效用,在後續資料挖掘等工作中仍然具有較高的精确度

差分隐私主要分為4類,本地化差分隐私、中心化差分隐私、分布式差分隐私和混差分隐私。

1、本地化差分隐私(ε-LDP)

在本地化差分隐私中,一個統計資料庫的查詢結果不會受到任何單一隐私資料的影響,它能在確定處理後統計資訊可用的需求下保護個人資訊不被洩露。其主要思想是利用對敏感問題響應的不确定性實作對原始資料的隐私保護,進而研究對敏感屬性值的隐私化處理及其頻數、均值的統計校正處理和釋出。

噪聲機制

本地化差分隐私中,每個使用者将各自的資料進行擾動後,再上傳至資料收集者處,而任意兩個使用者之間并不知曉對方的資料記錄,本地化差分隐私中并不存在全局敏感性的概念。目前,随機響應(randomized response) 技術是本地化差分隐私保護技術的主流擾動機制

随機響應算法( Randomized Response,RR) 是最典型的 LDP 算法。但 RR 存在一個不足,它對于超過兩種取值的資料并不适用,僅對包含兩種取值的離散型資料進行響應。為此,一個更普遍使用的随機響應 GRR( Generalized randomized response)算法被提出。即對于收集到的每一條私有資料 x ∈ X x\in X x∈X,X=Z=[k],使用者以p的機率發送x的真實值,并以機率1-p從X{x} 中發送随機選擇的值x^\prime,擾動函數如下公式所示.

差分隐私理論入門科普

①、擾動性統計

        引入一個現實場景:有n個使用者,假設AIDS患者的真實比例為\pi。我們希望對其比例進行統計,于是發起一個敏感的問題:“你是否為AIDS患者?”,每個使用者對此進行響應,第i個使用者的答案為X_i是或否,但出于隐私性考慮,使用者不會直接響應真實答案.假設其借助于一枚非均勻的硬币來給出答案,其正面向上的機率為p,反面向上的機率為1-p 。抛出該硬币,若正面向上,則回答真實答案,反面向上,則回答相反的答案。

        首先,進行擾動性統計。利用上述擾動方法對n個使用者的回答進行統計,可以得到艾滋病患者人數的統計值.假設統計結果中,回答“是”的人數為n_1,則回答“否”的人數為n-n_1。 顯然,按照上述統計,回答“是”和“否”的使用者比例如下:

P( X i X_i Xi​=“yes”)= π \pi π p+(1- π \pi π)(1-p)

P( X i X_i Xi​=“no”)=(1- π \pi π)p+ π \pi π(1-p)

②、校正

顯然,上述統計比例并非真實比例的無偏估計,是以需要對統計結果進行校正。

是以,建構以下似然函數:

L=[πp+(1-p)(1-π)]n1[(1-π)p+π(1-p)]n-n1

并得到\pi的極大似然估計:

π ^ \hat{\pi} π^= p − 1 2 p − 1 \frac{p-1}{2p-1} 2p−1p−1​+ n 1 ( 2 p − 1 ) n \frac{n_1}{(2p-1)n} (2p−1)nn1​​

π ^ \hat{\pi} π^的數學期望證明 π ^ \hat{\pi} π^是真實 π \pi π的無偏估計:

E( π ^ \hat{\pi} π^)= 1 2 p − 1 [ p − 1 + 1 n ∑ i = 1 n X i ] = 12 p − 1 [ p − 1 + 1 n n P r ( X i = " y e s " ) ] \frac{1}{2p-1}[p-1+\frac{1}{n}\sum_{i=1}^{n}X_i]=12p-1[p-1+1nnPr(Xi="yes")] 2p−11​[p−1+n1​∑i=1n​Xi​]=12p−1[p−1+1nnPr(Xi="yes")]

即 E ( π ^ ) = 1 2 p − 1 [ p − 1 + π p + ( 1 − π ) ( 1 − p ) ] = π (\hat{\pi})=\frac{1}{2p-1}[p-1+\pi p+(1-\pi)(1-p)]=π (π^)=2p−11​[p−1+πp+(1−π)(1−p)]=π

由此可以得到校正的統計值,其中N表示統計得到的AIDS人數估計值:

N= π ^ × n = p − 1 2 p − 1 n + n 1 2 p − 1 \hat{\pi}\times n=\frac{p-1}{2p-1}n+\frac{n_1}{2p-1} π^×n=2p−1p−1​n+2p−1n1​​

差分隐私理論入門科普

2、中心化差分隐私

        差分隐私方法最初被提出時大多采用中心化的形式,通過一個可信的第三方資料收集者彙總資料,并對資料集進行擾動進而實作差分隐私。在中心化差分隐私保護技術中要求一個可信的第三方資料收集者來對資料分析結果進行隐私化處理。

噪聲機制

        拉普拉斯機制(連續型資料查詢),指數機制(離散型資料查詢)兩種機制都和查詢函數的全局敏感度相關,而全局敏感性則是定義在至多相差一條記錄的近鄰資料集之上,使得攻擊者無法根據統計結果推測個體記錄,即将個體記錄隐藏在統計結果之中。

例:表1顯示了一個醫療資料集D,其中的每個記錄表示某個人是否患有癌症(1表示是,0表示否).資料集為使用者提供統計查詢服務(例如計數查 詢),但不能洩露具體記錄 的值.設使用者輸入參數Si,調用查詢函數f(i)=count(i)來得到資料集前i行中滿足“診斷結 果”=1的記錄數量,并将函數值回報給使用者.假設攻擊者欲推測Alice是否患有癌症,并且知道Alice在資料集的第5行,那麼可以用count(5)-count(4)來推出正确的結果。

差分隐私理論入門科普

        但是,如果f是一個提供ε-差分隐私保護的查詢函數,例如f(i)=count(i)+noise,其中noise是服從某種随機分布的噪聲.假設f(5)可能的輸出來自集合{2,2,5,3},那麼,f(4)也将以幾乎完全相同的機率輸出{2,2,5,3}中的任一可能的值,是以攻擊者無法通過f(5)-f(4)來得到想要的結果.這種針對統計輸出的随機化方式使得攻擊者無法得到查詢結果間的差 異,進而能保證資料集中每個個體的安全。

3、分布式差分隐私

分布式差分隐私指的是在若幹個可信中間節點上先對部分使用者發送的資料進行聚合并實施隐私保護,然後傳輸加密或擾動後的資料到伺服器端,確定伺服器端隻能得到聚合結果而無法得到資料。該方案需要用戶端首先完成計算并進行簡單的擾動( 例如較高隐私預算的本地化差分隐私) 或加密,将結果發送至一個可信任的中間節點,然後借助可信執行環境( Trusted ExecutionEnvironment,TEE)、安全多方計算、安全聚合( Secure Aggregation)或安全混洗( Secure Shuffling)等方法,在中間節點實作進一步的隐私保護,最終将結果發送至伺服器端。

4、混合差分隐私

混合差分隐私方案由Avent等提出,它通過使用者對伺服器信任關系的不同對使用者進行分類。舉例而言,最不信任伺服器的使用者可以使用最低隐私預算的本地化差分隐私,而最信任伺服器的使用者甚至可以直接發送原始參數; 伺服器也将根據使用者的信任關系對資料進行不同程度的處理。該方案的問題是同樣需要一定的通信成本,并且還需要付出額外的預處理成本以劃分信任關系。

繼續閱讀