差分隱私：團體隱私的界限是否嚴格？

假設機制 $ M $ 是 $ (\epsilon, \delta) $ -差分私有。對於數據集 $ x $ 和 $ x’’ $ 相差2個元素，我們有 $$ Pr[M(x)=y] \le e^{\epsilon} Pr[M(x’)=y] + \delta \le e^{2\epsilon} Pr[M(x’’)=y] + (1+e^\epsilon)\delta $$ 在哪裡 $ x $ 和 $ x’ $ 是相鄰的， $ x’ $ 和 $ x’’ $ 是相鄰的。此綁定是來自組隱私的綁定。這個綁得很緊嗎？如果是這樣，誰能給我一個具體的機制例子來說明這個界限很緊？我正在考慮隨機響應，但似乎沒有達到 $ (2\epsilon, (1+e^\epsilon)\delta)) $ - 無法區分 $ M(x) $ 和 $ M(x’’) $ .

非常感謝！

是的，這個界限很緊。

本文介紹的最優分區選擇機制達到了界限：每一步“用盡”所有的 $ (\varepsilon,\delta) $ 可用的預算，並針對特定情況 $ k=2 $ , 釋放分區的機率正好是 $ (1+e^\varepsilon)\delta $ , 而這個機率是 $ 0 $ 為了 $ k=0 $ . 遞歸關係為您提供了任何 $ k $ .

（免責聲明：我是本文的作者之一。）

引用自：https://crypto.stackexchange.com/questions/83903