為方便閱讀，故將《The Algorithmic Foundations of Differential Privacy》翻譯項目內容搬運至此；

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

中文翻譯版 Github 項目地址1：https://github.com/guoJohnny/algorithmic-foundation-of-dp-zh-cn

中文翻譯版 Github 項目地址2：https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn

感謝前輩的翻譯工作！

前言

隱私保護數據分析的問題由來已久，涉及多個學科。隨著有關個人的電子數據變得越來越詳細，并且隨著技術能夠更強大地收集和管理這些數據，對隱私的魯棒性、隱私的意義和隱私在數學上嚴格的定義需求不斷增長，對滿足隱私定義的算法需求也在不斷增長。差分隱私就是這樣的定義。

在討論了差分隱私的含義之后，本書主要介紹了實現差分隱私的基本技術，并將這些技術應用于創造性的結合中（第3-7節），其中使用了’查詢發布問題’作為示例。其中最重要的是：對比單純用差分隱私計算替換非隱私的每個計算步驟這種實現方法，通過重新思考計算目標能有更好的結果。

盡管有一些驚人的強大的計算結果，但仍然存在根本的局限性——不僅局限于使用差分隱私可以實現什么目標，而且還局限于什么方法可以防止隱私被完全破壞（泄露）（第8節）。

實際上，本書中討論的所有算法都針對不同計算能力的對手保持著不同的隱私。某些算法是計算密集型的，其他算法則為高效率的。攻擊者和算法的計算復雜度均在第9節中討論。

在第10節和第11節中，我們從基礎知識轉向查詢發布以外的應用程序，討論了用于機制設計和機器學習的差分私有方法。關于差分私有算法的絕大多數文獻都考慮了要進行大量分析的單個靜態數據庫。在第12節中討論了其他模型中的差分隱私，包括分布式數據庫和數據流計算。

最后，這本書是對差分隱私問題和技術的全面介紹，但并不是要進行詳盡的調查，因為到目前為止，在差分隱私方面有大量研究，我們可以只覆蓋一小部分。

一、差分隱私的承諾

差分隱私 描述了數據持有者對數據主體的承諾：“無論您將數據用于任何研究或分析，都不會受到不利影響或其他影響。” 差分數據庫機制可以使機密數據廣泛用于準確的數據分析，而無需訴諸數據清洗，數據使用協議，數據保護計劃，或其他受限方面。但是，保證隱私性的同時，將消耗數據實用性：《信息恢復基本法》指出，對太多問題的過于準確的回答將以一種驚人的方式破壞隱私。關于差分隱私的算法研究的目標是將這種不可避免性推遲盡可能長的時間。

差分隱私解決了一個問題，即分析人員通過數據集學習整體信息的同時（趨勢、統計信息），無法獲取個人的詳細信息。

醫學數據庫可能會告訴我們，吸煙會導致癌癥，影響保險公司對吸煙者長期醫療費用的看法。吸煙者受到分析的傷害了嗎？如果保險公司知道他吸煙，他的保險費可能會上漲。他可能也會得到幫助。但保險公司學習他的健康風險，使他進入戒煙計劃。吸煙者的隱私被侵犯了嗎？當然，研究結束后對他的了解比以前更多，但他的信息是不是“泄露”了？差分隱私將認為它不是，理由是對吸煙者的影響是相同的獨立于他是否在研究中。是這項研究得出的結論影響了吸煙者，而不是他在數據集中的存在與否影響了實驗得出的結論。

差分隱私在滿足隱私保護需求下，同時保證了分析數據集能得出相同的結論，例如，吸煙會導致癌癥，這與是否有人的數據選是否在數據集中無關。具體地說，任何個體的存在或不存在這個數據集中，差分隱私能確保輸出（對查詢的響應）在“本質上”發生的概率是相同的。這里，概率被差分隱私機制（由數據持有者控制）所做的隨機選擇所取代，這里術語“本質上”被抽象為參數 $?$。較小的 $?$ 將產生更好的隱私（和更不準確的響應）。

差分隱私在滿足隱私保護需求下，同時保證了分析數據集能得出相同的結論，例如，吸煙會導致癌癥，這與是否有人的數據選是否在數據集中無關。具體地說，任何個體的存在或不存在這個數據集中，差分隱私能確保輸出（對查詢的響應）在“本質上”發生的概率是相同的。這里，概率被差分隱私機制（由數據持有者控制）所做的隨機選擇所取代，這里術語“本質上”被抽象為參數 $\epsilon$。較小的 $\epsilon$ 將產生更好的隱私（和更不準確的響應）。

差分隱私是一個定義，而不是一個算法。對于給定的計算任務 $T$ 和給定的 $\epsilon$ 值，將有許多不同的私有算法以 $\epsilon$-差分隱私 方式實現 $T$。有些算法會比其他算法更準確。當 $\epsilon$ 很小時，很難為任務 $T$ 找到一個高精度的$\epsilon$-差分隱私算法，就像為一個特定的計算任務找到一個數值穩定的算法一樣。

1.1 隱私保護的數據分析

差分隱私是針對隱私保護數據分析問題而提出的一種隱私定義。我們簡要地討論了解決隱私保護的其他方式的一些問題（個人認為：此處的其他方式應該是：屬性隱藏、匿名、少量數據等隱私保護方式）。

數據不能完全匿名并且仍然有用

一般來說，數據越豐富，就越有趣和有用。這就產生了“匿名化”和“刪除可識別個人信息”的概念，這些概念希望部分數據記錄可以被掩蓋，其余部分可以發布并用于分析。

然而，由于數據的豐富性使得“個人”數據屬性可能與其他領域的數據屬性相重合，比如郵政編碼、出生日期和性別的組合，甚至三個電影的名字和一個獨立的人觀看這些電影的大致日期。這種“命名”功能可用于聯動攻擊，以將不同數據集中的“匿名”記錄與非匿名記錄進行匹配。有如下兩個事例：

• 1.通過將匿名醫療遭遇數據與（公開提供的）選民登記記錄相匹配，確定了馬薩丘塞特政府的醫療記錄。

• 2.通過與互聯網電影數據庫（IMDB）的鏈接，確定了 Netflix 用戶，其觀看歷史記錄包含在 Netflix 發布的匿名電影記錄集合中，作為推薦競賽的訓練數據。

差分隱私能中和聯動攻擊：因為差分隱私是數據訪問機制的一個屬性，并且與對手可用的輔助信息（背景知識）的存在或不存在無關，訪問 IMDb 用戶數據將不能對存在 Netflix 訓練集中的用戶數據進行聯動攻擊,換言之，攻擊在數據集中的用戶成功的可能性不會超過不在數據集中的用戶。

重標識“匿名”記錄并非唯一風險

“匿名”數據記錄的重新標識顯然是不可取的，這不僅是因為重新標識本身（這肯定揭示了數據集中的成員身份），而且還因為記錄可能包含損害信息，如果它與個人相關聯，則可能會造成損害。在給定日期從特定緊急護理中心收集的醫療遭遇記錄可能只列出少量不同的投訴或診斷。鄰居在相關日期訪問設施的附加信息給出了鄰居病情的一系列可能診斷結果。可能無法將特定記錄與鄰居匹配這一事實為鄰居提供了最低限度的隱私保護。

個人理解：此處的重標識“匿名”記錄應該指的是上一小節中通過其他數據集共有屬性對匿名數據進行標識。個人認為此處的鄰居診斷例子是指，通過關聯特定信息，雖然無法確切知道這個人患了什么病，但卻縮小了其患病的種類，排除了多余信息，這樣是否是種變相的隱私泄露？因為這樣只能提供很小的隱私保護。

不具有保護性的大數據集查詢

對于特定個體的查詢無法準確地得到安全的回答，事實上，人們可能希望直接拒絕他們（如果在計算上無法識別他們）。但如下面的差分攻擊所示，強迫查詢超過大型集并不是萬能的。假設攻擊者已知X先生在某個醫學數據庫中。綜上所述，這兩個大問題的答案是 ：

• 1.“數據庫中有多少人具有鐮狀細胞特征？”

• 2.“數據庫中除了X外，還有多少人有鐮狀細胞的特征？”

通過這兩個數據查詢得出數據，交出X先生是否有鐮狀細胞特征。

個人理解：如果某種查詢是不允許針對特定個人（這里指的是X）進行查詢，只能針對大規模數據統計類查詢，這種數據發布的方式也是不具有保護性的，能通過差分攻擊攻擊得到隱私數據，如標題所示，對大數據集的查詢不具有保護性。

查詢審查存在的問題

查詢審核有問題。如果根據歷史記錄，回答當前的查詢會損害隱私，那么人們可能會傾向于審查查詢和響應的序列，以阻止任何響應。例如，審核員可能在尋找可能構成差分攻擊的成對查詢。這種方法有兩個困難。首先，拒絕回答一個問題本身就有可能被披露。第二，查詢審計在計算上是不可行的；事實上，如果查詢語言足夠豐富，則甚至不存在算法過程來判斷一對查詢是否構成差分攻擊。（審核、防止差分攻擊語句是不現實的）

“不安全”的摘要統計

在某種意義上，將摘要統計作為隱私解決方案是失敗的，是直接來自上述差分攻擊。摘要統計的其他問題包括針對數據庫的各種重建攻擊，數據庫中每個人都有一個要保護的“秘密位”。有用性目標可以是允許，例如，形式的問題“滿足屬性 p 的多少人具有秘密比特值 1 ？”。另一方面，對手的目標是增加猜測個人秘密的機會。第 8.1 節中描述的重建攻擊顯示了即使是這種類型的線性查詢數也難以保護：除非引入足夠的不精確性，否則幾乎所有的秘密比特都可以重建。

公布匯總統計數據的風險的一個顯著例證是，應用統計技術，最初是為了確認或駁斥個人 DNA 在法醫學混合物中的存在，以裁定個人是否參與全基因組關聯研究。根據人類基因組計劃的一個網站，“單核苷酸多態性”（SNPs，發音為“snips”）是當基因組序列中的單核苷酸（A、T、C或G）改變時發生的 DNA 序列變異。例如，一個 SNP 可能會改變 AAGGCTAA 到 ATGGCTAA 的 DNA 序列。“在這種情況下，我們說有兩個等位基因：A 和 T。對于這樣一個 SNP，我們可以問，給定一個特定的參考群體，這兩個可能等位基因的頻率是多少？考慮到參考群體中 SNP 的等位基因頻率，我們可以研究這些頻率對于有特定疾病的亞群（即“病例”組）可能有什么不同，尋找與疾病相關的等位基因。因此，全基因組關聯研究可能包含大量snp病例組的等位基因頻率。根據定義，這些等位基因頻率只是聚合的統計數據，而（錯誤的）假設是，通過這種聚合，它們保留了隱私。然而，考慮到個體的基因組數據，理論上有可能確定個體是否屬于病例組（并且，因此，有疾病）。作為回應，國家衛生研究院和 Wellcome信托基金終止了公眾從他們資助的研究中獲取總頻率數據的途徑。

（受制于相關知識缺失，未能理解此段重建攻擊和 DNA 事例，需要對第 8.1 節進行了解）

這是一個具有挑戰性的問題，即使是對于差分隱私，因為涉及到大量的——數十萬甚至一百萬——測量，這些測量包含和關聯了大群體中的小數量的個體。

長期的事實并不“好”

如果一個數據主體隨著時間的推移而被跟蹤，那么揭露數據個體長期的行為（例如購買面包）可能會有問題。舉個例子，假設某人，他年復一年地定期買面包，直到突然轉向很少買面包。一位分析師可能會得出結論，某人很可能被診斷為2型糖尿病。分析員可能是正確的，也可能是不正確的；不管怎樣，某人的隱私都會受到傷害。

（此處原文為Ordinary Fact，根據下文內容來看，更應該表示為一種長期的普遍性結果，故將其翻譯為“長期”）

“少數人”原則

在某些情況下，一種特定的技術實際上可以為數據集的“典型”成員提供隱私保護，或者更普遍地說，為“大多數”成員提供隱私保護。在這種情況下，人們經常聽到這樣的說法，即這種技術是足夠的，因為它損害了“少數”參與者的隱私。撇開那些對隱私最重要的人來說可能是離群者這一擔憂不談，“少數人”原則在本質上并不是沒有價值的：需要做出社會判斷，權衡成本和收益。一個清晰的隱私定義與“少數人”的理念相一致，但還沒有發展出來；但是，對于單個數據集，“只有少數”的隱私可以通過隨機選擇行的子集并將其全部釋放來實現（引理4.3，第4節）。抽樣界限描述了統計分析的質量，可以在隨機子樣本上執行，它控制要釋放的行數。當“少數人”的原則被拒絕時，差分隱私提供了另一種選擇。

（個人理解為離群點更容易遭受差分攻擊，需要在之后深入理解）

1.2 參考文獻

Sweeney [81] linked voter registration records to “anonymized” medical encounter data; Narayanan and Shmatikov carried out a linkage attack against anonymized ranking data published by Netflix [65]. The work on presence in a forensic mix is due to Homer et al. [46]. The first reconstruction attacks were due to Dinur and Nissim [18].

---

目錄導航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附錄):https://blog.csdn.net/AdamCY888/article/details/146457601