差分隱私尋根

紫式晦澀每日一篇文章第6天

前言

1. 今天是2022年第4天, 第一週的第一個週二. 今天來思考差分隱私最基礎的定義.

2. 今天的素材是Cynthia Dwork與Aaron Roth的The Algorithmic Foundations of Differential Privacy 的第二章所節選的材料.

差分隱私故事: 背景, 期望, 隱私洩露

3. 差分隱私背景: 保護隱私的數據分析問題由來已久，橫跨多個學科。隨著關於個人的電子數據變得越來越詳細，以及技術使這些數據的收集和整理變得越來越強大，對一個強大的、有意義的、數學上嚴格的隱私定義的需求也在增加，同時也需要一個滿足這個定義的計算豐富的算法(a robust, meaningful, and mathematically rigorous definition of privacy, together with a computationally rich class of algorithms)類別。差分隱私就是滿足這樣定義的一系列演算法。

4. 對隱私保護的期望: ”差分隱私 “描述了數據持有者對數據主體做出的承諾。“如果允許你的數據被用於任何研究或分析，無論其他研究、數據集或信息來源如何，你都不會受到不利或其他的影響。” 在最好的情況下，不同的私有數據庫機制可以使機密數據廣泛用於準確的數據分析，而不需要依賴於數據清洗、數據使用協議、數據保護計劃或限制訪問。

5. 回答太清楚, 隱私就洩漏: 儘管如此，數據的效用最終還是會被消耗掉：信息恢復的基本法則(Fundamental Law of Information Recovery )指出，對太多問題的過度準確的回答會以驚人的方式破壞隱私。差別隱私的算法研究的目標是盡可能推遲這種不可避免性。

6. 差分隱私是一個定義，不是一種算法: 對於一個給定的計算任務$T$和一個給定的$\varepsilon$值，將有許多差分隱私算法以$\varepsilon$-差分隱私的方式實現$T$。有些算法會比其他算法有更好的準確性。當$\varepsilon$較小時，為$T$找到一個高度精確的$\varepsilon$-差分隱私算法可能是困難的，就像為一個特定的計算任務找到一個數值穩定的算法一樣困難。

形式化基礎元素-輸出值機率向量, 隨機演算法, 其差分隱私性質.

7. 機率單純型: 裡面的每個$x$都代表著一個「機率向量」, 對應每個可能輸出值的機率.

Definition 2.1 (Probability Simplex). Given a discrete set $B$, the probability simplex over $B$, denoted $\Delta(B)$ is defined to be: $$\Delta(B)={x \in \mathbb{R}^{|B|}: x_{i} \geq 0 \text { for all } i \text { and } \sum_{i=1}^{|B|} x_{i}=1}$$

8. 隨機演算法: 看作一個隨機映射, 對一個固定的輸入a, 有一定的概率輸出b. 這個機率向量被前面的機率單純型給描述.一般來說，一個具有域$A$和（離散）範圍$B$的隨機算法將與一個從$A$到$B$上的概率單線的映射有關，表示為$\Delta(B)$ 。

Definition 2.2 (Randomized Algorithm). A randomized algorithm $\mathcal{M}$ with domain $A$ and discrete range $B$ is associated with a mapping $M: A \rightarrow \Delta(B) .$ On input $a \in A$, the algorithm $\mathcal{M}$ outputs $\mathcal{M}(a)=b$ with probability $(M(a))_{b}$ for each $b \in B$. The probability space is over the coin flips of the algorithm $\mathcal{M}$.

9. 數據庫的長度: 我們將認為「數據庫$x$」是來自宇宙$\mathcal{X}$的記錄集合。用直方圖來表示數據庫往往很方便：$x\in\mathbb{N}^{|\mathcal{X}|}$，其中每個條目$x_{i}$代表數據庫$x$中$i\in\mathcal{X}$類型的元素數量。在這種表述中，兩個數據庫$x$和$y$之間距離的自然度量將是它們的$\ell_{1}$距離。

$|x|{1}$是衡量數據庫$x$的大小（即它所包含的記錄數. $|x-y|{1}$是衡量$x$和$y$之間有多少記錄不同。

10. 隨機算法的差分隱私性質: 我們現在準備正式定義差異化隱私。直觀上, 保證了隨機化算法, 在類似的輸入數據庫上, 輸出是相似的。

Definition 2.4 (Differential Privacy). A randomized algorithm $\mathcal{M}$ with domain $\mathbb{N}^{|\mathcal{X}|}$ is $(\varepsilon, \delta)$-differentially private if for all $\mathcal{S} \subseteq \operatorname{Range}(\mathcal{M})$ and for all $x, y \in \mathbb{N}^{|\mathcal{X}|}$ such that $|x-y|_{1} \leq 1$ : $$ \operatorname{Pr}[\mathcal{M}(x) \in \mathcal{S}] \leq \exp (\varepsilon) \operatorname{Pr}[\mathcal{M}(y) \in \mathcal{S}]+\delta $$where the probability space is over the coin flips of the mechanism $\mathcal{M}$. If $\delta=0$, we say that $\mathcal{M}$ is $\varepsilon$-differentially private.

11. 保護隱私失敗的機率$\delta$:通常情況下，我們對$\delta$的值感興趣，它小於數據庫規模的任何多項式的倒數。特別是，$\delta$的值在$1 /|x|_{1}$的數量級上是非常危險的：它們允許通過公佈少數數據庫參與者的完整記錄來 “保護隱私”.

12. 有沒有失敗機率, 解釋起來很不同:然而，即使$\delta$可以忽略不計，在$(\varepsilon, 0)$和$(\varepsilon, \delta)$差異性隱私之間也有理論上的區別。其中最主要的是相當於量化順序的轉換。前者的輸出會差不多, 但後者的輸出可以差很多

• $(\varepsilon, 0)$差分隱私確保，對於機制$\mathcal{M}(x)$的每一次運行，觀察到的輸出（幾乎）同樣可能在每個相鄰的數據庫中同時被觀察到。
• 相反，$(\varepsilon, \delta)$差分隱私說，對於每一對相鄰的數據庫$x, y$，事後觀察到的值$\mathcal{M}(x)$在數據庫為$x$時比在數據庫為$y$時產生的可能性要大得多或小得多，這是極其不可能的。
• 然而，給定一個輸出$x_i\sim\mathcal{M}(x)$，有可能找到一個數據庫$y$，使$x_i$在$y$上產生的可能性遠遠大於數據庫為$x$時的可能性。也就是說，$x_i$ 在$\mathcal{M}(y)$分布中的質量可能大大高於它在$\mathcal{M}(x)$分布中的質量。

這樣來說，$(\varepsilon, \delta)$差分隱私雖然保護隱私, 但也讓之後相關的機器學習任務很難做.

隱私損失: 控制隱私預算, 免疫後處理轉換

13. 定義隱私損失: 關鍵量是 $$\mathcal{L}_{\mathcal{M}(x) | \mathcal{M}(y)}^{(\xi)}=\ln \left(\frac{\operatorname{Pr}[\mathcal{M}(x)=\xi]}{\operatorname{Pr}[\mathcal{M}(y)=\xi]}\right).$$ 我們把它稱為觀察$\xi$所產生的隱私損失。

• 這種損失可能是正的（當一個事件在$x$下比在$y$下更可能發生），也可能是負的（當一個事件在$y$下比在$x$下更可能發生）。
• 正如我們在Lemma 3.17中看到的，$(\varepsilon, \delta)$差分隱私確保對於所有相鄰的$x, y$，隱私損失的絕對值將被$\varepsilon$所約束，概率至少為$1-\delta$。

14. 這個定義是把$e^{\epsilon}$的部分做了個轉換; 可否把這個想成policy的decision變化的程度? 但感覺與隱私沒什麼關係. 這個寫法的好處可以跟似然比接起來, 也難怪可以用假設檢定的框架來做.

15. 差分隱私對後處理是免疫的: 數據分析員在沒有關於私人數據庫的額外知識的情況下，不能計算私人算法$\mathcal{M}$的輸出的函數並使其減少差異性隱私。

• 也就是說，如果一個算法保護了個人的隱私，那麼數據分析員不能增加隱私損失, 無論是在正式定義下還是在任何直觀意義上。
• 從形式上看，與數據無關的「後處理映射$f$」與$(\varepsilon, \delta)-$差分隱私算法$\mathcal{M}$的組合也是$(\varepsilon, \delta)$差分隱私。

也是這個特點, 讓隱私處理後的資料可以被公開做研究.

後記

16. 到此我們看過了Cynthia Dwork與Aaron Roth的The Algorithmic Foundations of Differential Privacy 的第二章的節選內容. 在「說太清楚就隱私洩露」的事實下, 我們需要給隨機演算法增加「差分隱私」的性質, 以免惡意人士透過觀察隨機演算法的輸出值, 來還原特定的數據. 形式化框架下, 經過差分隱私處理後的數據, 在後處理下不會造成額外的隱私洩露. 對形式化的學術研究而言, 「隱私損失」會是重點分析目標.

17. 至此, 對差分隱私又多瞭解了一點, 也可以理解其形式化細節會與似然比, 假設檢定等等技術有關係. 很多統計的結果都可以套上這層外衣. 之後可以多想想這些基礎的關聯.

2022.01.04. 紫蕊 於 西拉法葉, 印第安納, 美國.