指紋編碼與幾何學相遇：私密查詢釋放與自適應數據分析的改進下界

指紋編碼與差異隱私

指紋編碼是一種重要的工具，用來證明差異隱私中的下限。它們被用來證明幾個基本問題的緊密下限，特別是在「低準確度」的情況下。與重建或差異方法不同，指紋編碼更適合用來證明最壞情況下的下限，這些查詢集自然地來自於指紋編碼的建構。在這項研究中，我們提出了一個通用框架，用於證明指紋類型的下限，這使我們能夠根據查詢集的幾何形狀來調整技術。我們的方法讓我們能夠證明幾個新的結果。

新結果一

首先，我們展示了任何（樣本和人口）準確的算法，用於回答任意自適應計數查詢，對於一個宇宙 X\mathcalXX 的準確度 α\alphaα 需要 Ω(log⁡∣X∣⋅log⁡Qα3)\Omega(\frac\sqrt\mathcalX\cdot \log Q\alpha^3)Ω(α3log∣X∣​⋅logQ​) 樣本。這顯示基於差異隱私的方法對這個問題是最佳的，並且顯著改善了之前已知的下限 log⁡Qα2\frac\log Q\alpha^2α2logQ​ 和 min⁡(Q,log⁡∣X∣)/α2\min(\sqrtQ, \sqrt\mathcalX)/\alpha^2min(Q​,log∣X∣​)/α2.

新結果二

其次，我們展示了任何 (ε,δ)(\varepsilon,\delta)(ε,δ)-DP 算法，用於回答 QQQ 計數查詢，對於準確度 α\alphaα 需要 Ω(dlog⁡(1/δ)log⁡Qεα2)\Omega\left( \frac\sqrtd \log(1/\delta) \log Q\varepsilon \alpha^2 \right)Ω(εα2dlog(1/δ)​logQ​) 樣本。我們的框架允許直接證明這個下限，並且改善了 log⁡(1/δ)\sqrt\log(1/\delta)log(1/δ)​ 由 Bun、Ullman 和 Vadhan (2013) 使用組合方法所證明的下限。第三，我們描述了在近似差異隱私下回答一組隨機 0-1 查詢的樣本複雜度。為了達成這個目標，我們提供了新的上限和下限，這些結合現有的下限使我們能夠完成整個圖景。