差分隱私：數據持有者和對手之間的“遊戲”是什麼？
我已經閱讀了一段時間的差分隱私（DP）文獻來熟悉它。我對它的數學和統計基礎感到滿意，但我對響應發布的“設置”有點痛苦。
我不明白的是，差分隱私的傳統定義是說任何兩個鄰居在一個事件下都應該是無法區分的。由於這適用於任何鄰居和任何可能的事件，因此數據庫中的所有個人都是“隱藏的”。但是，這個定義背後的背景是什麼？例如，一些潛在的設置可能是（帶有反例）：
- 我們讓使用者（對手）發送關於手頭真實數據庫的相同查詢（比如 $ D $ )，並且由於我們有 DP，那麼對手將無法找到真正的查詢。 **反例：**對手可以多次詢問同一個查詢，平均響應，並獲得真正的查詢。
- 我們給使用者一個單一的響應。我們還讓使用者知道加性雜訊的真實分佈。然後，他可以嘗試任何可能的“候選”數據庫，並嘗試找到真正的數據庫，但由於 DP 定義成立，他將失敗。**反例：**在我們向使用者發送響應後，我們應該消失，使用者應該嘗試弄清楚 $ D $ 自己。這沒有任何意義。雖然，對我來說最方便的數學定義是“即使對手知道真實的雜訊分佈，並且只是我們響應的一個樣本，他也不會弄清楚 $ D $ "
- 我們讓使用者只詢問一次查詢，因此我們從不發布多個響應。**反例：**如果這是一次性的事情，那麼 DP 定義就沒有多大意義。我們可以只對標準的正常雜訊進行採樣，並且由於我們給出了響應的單個樣本，因此對手將無法弄清楚任何事情。所以DP應該在重複設置中使用。
我缺乏數據庫系統方面的知識。我只是想學習，DP定義在什麼情況下才有意義？數據持有者和對手之間正在進行什麼樣的博弈？
差分隱私保證的是查詢輸出最多可以通信 $ \varepsilon $ 關於任何個人（行）的資訊位。我現在評論您問題中概述的每個設置：
- 獨立重複的查詢構成了幾個不同的版本。有一個直接來自差分隱私的定義的直接組合定理（參見例如第3.5節）。它指出，聚合隱私損失最多是組成版本的個人隱私損失的總和。所以，在這種情況下，結果 $ k $ 重複查詢 $ \varepsilon $ - 差分私有機制共同構成一個 $ (k\cdot\varepsilon) $ - 不同的私人發布。如果攻擊者提供查詢，典型的緩解策略是強制執行查詢限制。您可能還需要擔心勾結。
- 這是一個非問題。再次，從定義 $ \varepsilon $ - 差分隱私，有人可以爭辯說，在觀察了發布的內容之後，對手的後部仍然逐點接近他們的前部。具體來說，對於任何候選“真實”數據庫，後驗生命與前驗生命的比率在 $ [e^{-\varepsilon}, e^\varepsilon] $ . 因此，當 $ \varepsilon $ 很小，這仍然接近 1，並且對手在他們最初的猜測上只能微不足道地改進。
- 這是有效的，並且不與差分隱私的定義相矛盾，即使在這種情況下，它也確保即使對手擁有大量的數據庫知識，甚至全部到一行，他們仍然無法得出結論它的存在與否是確定的。
為了確保我按要求回答問題，作為遊戲的一種表述如下：修復隱私機制， $ \mathcal{A} $ . 攻擊者選擇一對數據庫 $ D_1 $ ， 和 $ D_2 $ 僅通過插入（或刪除）單個記錄而有所不同，將這些提供給第三方，後者隨機評估 $ \mathcal{A}(D_1) $ 或者 $ \mathcal{A}(D_2) $ 並將結果返回給攻擊者，而不指示使用哪個數據庫作為輸入。攻擊者知道確切的內容 $ D_1 $ , $ D_2 $ , 並給出了隱私機制的完整規範 $ \mathcal{A} $ ，以便攻擊者可以獨立評估 $ \mathcal{A} $ 超過 $ D_1 $ , $ D_2 $ ，或他們選擇的任何輸入。攻擊者的目標是猜測提供的評估是否是 $ \mathcal{A}(D_1) $ 或者 $ \mathcal{A}(D_2) $ .
一個好的機制是攻擊者在隨機猜測上的成功仍然很小。直覺地說，如果攻擊者即使知道完整的內容也無法從結果中確定輸入數據庫 $ D_1 $ , $ D_2 $ ，並被允許完全了解和實驗 $ \mathcal{A} $ ，一定是結果攜帶的關於數據庫不同的行的資訊很少。