拉普拉斯差分隱私機制的四個面向

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

前言

1. 今天是2022年的第一天! 今天思考了許多關於差分隱私相關的問題. 今天針對最經典的差分隱私機制,「拉普拉斯差分隱私機制」, 來做文章思考.

2. 今天的素材是Cynthia Dwork與Aaron Roth的The Algorithmic Foundations of Differential Privacy 的章節3.3, 以及維基百科關於Additive noise mechanism 的條目.

場景: 數據庫查詢

3. 數據庫查詢: 問題起源於「數據庫查詢(Database queries)」: 當我們查詢數據庫, 獲得數值資料時, 算法會將數據庫映射為k個實數回傳. 這個映射寫作$$f:\text{數據庫}\mapsto \text{k個實數}.$$

4. 敏感性: 我們能多準確地完成這樣的查詢呢? 利用「敏感性」來妙術最壞情況下, 一個人的數據可以改變「查詢映射f」的程度。

5. 不確定性之必要: 萬一上述的敏感性很劇烈, 那麼惡意攻擊者就可以透過比較查詢結果, 來回推特定用戶的特定數據. 為了避免特定用戶的特定數據被還原出來, 增加不確定性是必要的.

6. 直觀: 一個「查詢映射f」的靈敏度, 給出了我們必須對其輸出進行多大的擾動, 才能保護隱私, 的上限。 (The sensitivity of a function gives an upper bound on how much we must perturb its output to preserve privacy. )

方案: 增加拉普拉斯分佈為不確定性

7. 拉普拉斯分佈: 拉普拉斯分布是指數分布的一個對稱版本。

8. 拉普拉斯機制: 拉普拉斯機制將簡單地計算「查詢映射f」，並用來自拉普拉斯分布的噪聲來擾動每個坐標。 微調噪聲的規模將被校准為「查詢映射f的敏感性」（除以ε）。

9. 拉普拉斯機制的隱私性質: 拉普拉斯機制保留了(ε,0)微分隱私。 處理前與處理後, 兩個查詢結果出現的機率, 不會差太多.

實例: 具體數據庫查詢任務

與機器學習的關係？

10. 計算查詢: (Counting queries) 在數據庫中，有多少元素滿足特定

11. 直方圖查詢: (Histogram queries) 將資料可能分佈的空間分割為單元格，查詢每個單元格中有多少數據庫元素

12. 姓氏查詢: 從10,000個潛在名字的列表中計算出哪些名字在2010年人口普查的參與者中最常見. 是一種直方圖查詢.

13. 差分隱私選取: (Differential private selection) 結果的空間是離散的，任務是產生一個 “最佳 “答案，在這種情況下，就是人口最多的直方圖單元。

14. 最常見的病症: 在一組受訪者的醫療史中，哪種病症（大約）是最常見的，所以這組問題是，對於所考慮的每種病症，個人是否曾經接受過這種病症的診斷。

推廣: 加性噪音機制

15. 推廣定義: 從預先確定的分布中, 添加受控的噪聲, 是設定「差分隱私機制」的一種方式。這種技術對於設計敏感數據上的實值函數的隱私機制很有用。常用於添加噪聲的分布包括拉普拉斯和高斯分布。

16. 推廣敏感性: 令$\mathcal{D}$為資料集; $f:\mathcal{D} \mapsto \mathbb{R}$ 為查詢映射。則查詢映射的敏感性$\Delta f$定義為 $$ \Delta f = \max |f(x)-f(y)|. $$ 這裡的最大值是在$\mathcal{D}$中, 只差一個元素的一對資料集$x$和$y$。對於維度高的查詢映射函數, 通常在$\ell_{1}$或$\ell_{2}$下測量敏感性。

17. 論證差分隱私性: 要論證該機制滿足$\epsilon$差分隱私，需證明「輸出分布」在乘法意義上是封閉的。技巧是利用分佈本身的似然比.

後記

18. 到此我們走完了一趟拉普拉斯機制相關的的基礎細節. 基本上, 問題的場景是對數據庫的各種查詢. 如果給準確的數值, 那惡意攻擊者有可能透過查詢結果來回推特定個體的某些數值. 因此, 根據查詢的特性本身針對資料變動的「敏感度」, 設計回傳的數值額外加上的不確定性, 就可以防止這類的惡意攻擊. 其中要量化隱私保護的程度, 就會用到拉普拉斯分佈的各種性質; 也不難想像「充分統計量」對應著「查詢映射」, 而「隱私保護查詢結果」對應著「不確定性部分的集中不等式」.

19. 十分有趣, 而這類的工作在2021已經被延伸到各種機器學習模型的訓練上, 造成很多機器學習任務表現被影響甚巨. 因此, 藉由做「模型審計」相關的研究, 來評估「基於隱私保護資料所訓練的機器學習模型」, 是一個基礎必須做的工作. 合成數據, 在這個分野上, 是有什麼樣的直覺可以解決這個問題呢?

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