2.2 基于差分隱私的安全機制

差分隱私（圖2-2）采用了一種隨機機制，使得當輸入中的單個樣本改變之后，輸出的分布不會有太大的改變^[12，24]。例如，對于差別只有一條記錄的兩個數據集，查詢它們獲得相同的輸出的概率非常接近。這將使用戶即使獲取了輸出結果，也無法通過結果推測出輸入數據來自哪一方。

在現有的隱私保護方法中，由于差分隱私對隱私損失進行了數學上的定義，并且其實現過程比較簡捷，系統開銷更小，所以得到了廣泛的應用。差分隱私最開始被開發用來促進在敏感數據上的安全分析。隨著機器學習的發展，差分隱私再次成為機器學習社區中一個活躍的研究領域。來自差分隱私的許多令人激動的研究成果都能夠被應用于面向隱私保護的機器學習^[91，94]。

2.2.1 差分隱私的定義

差分隱私是由Dwork在2006年首次提出的一種隱私定義^[91]，是在統計披露控制的場景下發展起來的。它提供了一種信息理論安全性保障，即函數的輸出結果對數據集里的任何特定記錄都不敏感。因此，差分隱私能被用于抵抗成員推理攻擊。

按照數據收集方式的不同，當前的差分隱私可以分為中心化差分隱私和本地化差分隱私，它們的區別主要在于差分隱私對數據處理的階段不同。中心化差分隱私依賴一個可信的第三方來收集數據，用戶將本地數據發送到可信第三方，然后在收集的數據中進行差分隱私處理。但可信的第三方在現實生活通常是很難獲得的，因此本地化差分隱私將數據隱私化的工作轉移到每個參與方，參與方自己來處理和保護數據，再將擾動后的數據發送到第三方，由于發送的數據不是原始數據，因此也就不要求第三方是可信的。下面我們分別介紹這兩種差分隱私的定義。圖2-3展示的是中心化差分隱私和本地化差分隱私在處理流程上的區別。

中心化差分隱私

我們首先給出中心化差分隱私的（?，δ）-差分隱私定義。

定義2-3 （?，δ）-差分隱私^[92] 對于只有一個記錄不同的兩個數據集D和D^′，一個隨機算法M，以及對于任意的輸出S ? Range（M），我們稱隨機算法M提供（?，δ）-差分隱私保護，當且僅當其滿足：

式中，?表示隱私預算（privacy budget），δ表示失敗概率。當δ=0時，便得到了性能更好的?-差分隱私。

在差分隱私定義中，隱私保護預算?用于控制算法M在鄰近數據集D和D^′上獲得相同輸出的概率比值。式（2.5）表明，?的值越小，那么算法M在鄰近數據集D和D^′上獲得相同輸出的概率就越接近，因此，用戶通過輸出結果，無法區分輸入數據到底是來自數據集D還是來自數據集D^′，即無法察覺數據集的微小變化，從而達到隱私保護的目的。特別地，當?=0時，算法M在D和D^′上得到相同的輸出的概率是一樣的。反之，?的值越大，其隱私保護的程度就越低。

中心化差分隱私在實際的應用中，有兩個非常重要的性質：串行組合和并行組合。

定義2-4 串行組合^[202] 設有n個算法M₁，M₂，· · ·，M_n，算法M_i滿足?_i-差分隱私性質，對于同一個數據集D，將這些算法串行作用于D上，構成新的組合算法

滿足-差分隱私保護。

定義2-5 并行組合^[202] 設有n個算法M₁，M₂，· · ·，M_n，算法M_i滿足?_i-差分隱私性質，對于數據集D，將其拆分成n個集合，分別記為D₁，D₂，· · ·，D_n，將算法M_i獨立作用于數據集D_i上，構成新的組合算法

滿足max_i{?_i}-差分隱私保護。

這兩個性質非常有用，比如根據定義2-4，如果一個攻擊者想試圖攻破一個差分隱私安全系統，那么最簡單直接的方法是對該系統進行多次查詢訪問。從系統角度看，這樣相當于增大了隱私保護預算值，從而降低了系統的隱私性；從攻擊者的角度看，將多次查詢訪問獲取的結果進行平均，根據大數定理，查詢次數越多，這個均值的結果和真實值就越接近。這也是當前很多安全系統都設置查詢上限的原因，目的就是為了防止惡意攻擊。

本地化差分隱私

本地化差分隱私（Local Differential Privacy，LDP）^[43，9]可以將數據隱私化的工作轉移到每個參與方，參與方自己來處理和保護數據，進一步降低了隱私泄露的可能性，它的定義如下。

定義2-6 本地化差分隱私 ^[43，9]對于一個任意本地化差分隱私函數f（?），其定義域（domain）為Dom（f），值域（range）為Ran（f），對任意的輸入x，x^′ ∈Dom（f），輸出y∈Ran（f），我們稱函數f提供（?）-本地化差分隱私保護，當前僅當其滿足：

在本式中，?表示隱私預算。

比較定義2-6和定義2-3，我們不難發現，中心化差分隱私是定義在任意兩個相鄰數據集的輸出相似性上的，而本地化差分隱私是定義在本地數據任意兩條記錄的輸出相似性上的。此外，本地化差分隱私同樣繼承了組合特性，即它同樣滿足并行組合和串行組合的性質。

這種差異性，導致其實現方法也有很大的不同。中心化差分隱私需要保護全體數據的隱私，具有全局敏感性的概念，采用的擾動機制可以包括高斯噪聲機制、拉普拉斯噪聲機制、指數噪聲機制等^[201]。在本地化差分隱私中，數據隱私化的工作轉移到每個參與方，而每一個參與方并不知道其他參與方的數據，因此它并沒有全局隱私敏感性的概念，它采用的擾動機制一般通過隨機響應實現（Randomized Response，RR）^{[43，9]}。

我們注意到，本地化差分隱私的概念與聯邦學習有點相似。事實上，在聯邦學習的實現中，可以結合本地化差分隱私的思想，比如給每一參與方的上傳梯度或者模型參數加上噪聲來更好地保護模型參數。我們將在15.2節詳解如何利用差分隱私技術來實現聯邦學習。

2.2.2 差分隱私的實現機制

目前實現差分隱私保護的主流方法是添加擾動噪聲數據。前面提到，差分隱私可以分為中心化差分隱私和本地化差分隱私，其中：中心化差分隱私采用的擾動機制可以包括拉普拉斯噪聲機制、指數噪聲機制等；而本地化差分隱私一般通過隨機響應（Randomized Response）^[277]來實現（隨機響應是1965年由Warner提出的一種隱私保護技術）。限于篇幅，本節主要針對中心化差分隱私的三種機制進行分析，對于本地化差分隱私的隨機響應算法，讀者可以參考文獻[277]了解更多細節。

要想知道不同算法函數M需要添加多少噪聲才能提供（?，δ）-差分隱私保護，就需要先定義該算法在當前數據上的全局敏感度。全局敏感度根據計算距離的方式不同，一般可以區分為L₁全局敏感度和L₂全局敏感度。

定義2-7 L₁全局敏感度^[92] 對于一個算法函數M，D和D^′為任意兩個相鄰的數據集，L₁全局敏感度定義如下：

即L₁全局敏感度反映了一個函數M在一對相鄰數據集D和D^′上進行操作時變化的最大范圍。

當使用2-范數（即歐氏距離）來衡量函數在相鄰數據集上的輸出變化時，我們得到如下的L₂全局敏感度定義。

定義2-8 L₂全局敏感度^[92] 對于一個算法函數M，D和D^′為任意兩個相鄰的數據集，L₂全局敏感度定義如下：

不管是L₁敏感度還是L₂敏感度，它的結果與提供的數據集無關，只由函數本身決定。從直觀上理解，當全局敏感度比較大時，說明數據集的細微變化可能導致函數M的輸出有很大的不同，我們需要添加較大的噪聲數據，才能使函數M提供（?，δ）-差分隱私保護；相反，當全局敏感度比較小時，說明數據集的細微變化不會對函數M的輸出產生很大的影響，我們只需要添加較小的噪聲數據，就能使函數M提供（?，δ）-差分隱私保護。下面介紹在差分隱私中常用的三種添加噪聲的機制。

定義2-9 拉普拉斯機制^[91] 給定數據集D，設有函數f，其L₁敏感度為?f（定義2-7），那么隨機算法M=f（D）+L提供（?，0）-差分隱私保護，其中L～為添加的隨機噪聲概率密度函數，即服從參數μ=0，λ=的拉普拉斯分布。

拉普拉斯機制實現非常簡單，被廣泛應用于數值型查詢的隱私保護機制。對于查詢結果，只需要加入一個滿足拉普拉斯分布的噪聲數據，就能實現（?，0）-差分隱私保護。

高斯機制為數值型查詢結果隱私保護提供了另一種實現。與拉普拉斯機制不同，高斯機制的定義使用的是L₂全局敏感度，其定義如下。

定義2-10 高斯機制^[95，90] 給定數據集D，設有函數f，其L₂敏感度為?f（定義2-8），對于任意的δ∈（0，1），，那么隨機算法M=f（D）+L提供（?，δ）-差分隱私保護，其中L～Gaussian（0，σ²）為添加的隨機噪聲概率密度函數，即服從參數μ=0，的高斯分布。

指數機制是用于非數值型差分隱私保護的一種實現方式，它使用L₁敏感度作為參數構造，其定義如下。

定義2-11 指數機制^[201] 給定數據集D，設有函數q，輸出為結果為r，記為q（D，r），其敏感度為 ?q，隨機算法M以正比于的概率輸出r，那么隨機算法M提供（?，0）-差分隱私保護。

在定義2-11中，?（q）表示L₁敏感度，若D和D^′表示的是任意兩個相鄰數據集，r表示的是任意的一個輸出，其定義為

差分隱私的實現方式還有很多種，有興趣的讀者可以參考文獻[92]。表2-1總結了常用的三種機制，包括它們各自的函數形式以及適用范圍等。

前面介紹的是在查詢狀態下對輸出結果實現差分隱私保護的機制。在機器學習中應用差分隱私技術，其情況會更加復雜，因為我們要保護的信息，不僅包括輸入數據和輸出數據，還包括算法模型參數、算法的目標函數設計等。因此，在機器學習領域應用差分隱私算法，一個關鍵的問題是何時、何階段添加噪聲數據。為此，差分隱私算法根據噪聲數據擾動使用的方式和使用階段的不同，將其劃分為下面幾類。

（1）輸入擾動：噪聲數據被加入訓練數據。

（2）目標擾動：噪聲數據被加入學習算法的目標函數。

（3）算法擾動：噪聲數據被加入中間值，例如迭代算法中的梯度。

（4）輸出擾動：噪聲數據被加入訓練后的輸出參數。

在不同階段，采用的擾動機制也有不同的考慮。鑒于本書的寫作目的和篇幅，我們不在這里繼續展開，有興趣的讀者可以參考差分隱私相關的文獻[92，95，94，28]，更加深入地理解差分隱私的詳細實現過程。