将近似差分隐私转为纯差分隐私,提升安全性且保持高效
Purifying Approximate Differential Privacy with Randomized Post-processing
- 通过随机后处理加噪,消除δ参数实现纯差分隐私
- 在多种任务中实现接近最优的隐私-效用平衡
- 适合需要严格δ=0的高安全场景设计
我们提出一种框架,可在特定条件下将$(\varepsilon, \delta)$-近似差分隐私(DP)机制转化为$(\varepsilon', 0)$-纯差分隐私机制,这一过程称为“净化”。该算法技术利用校准噪声的随机后处理,消除δ参数,同时在纯差分隐私下实现近乎最优的隐私-效用权衡。该方法开启了一种新的纯差分隐私算法设计策略:先运行满足条件的近似差分隐私算法,再进行净化。这使得可借助强组合、提议-测试-释放等依赖$\delta>0$的技术,设计出$\delta=0$的纯差分隐私方法。我们在差分隐私经验风险最小化(DP-ERM)、基于稳定性的发布和查询发布等多种场景中应用此框架。据我们所知,这是首个在统计和计算上均高效的从近似差分隐私到纯差分隐私的还原方法。最后,我们展示了该还原在证明近似差分隐私约束下的下界时的应用,可显式体现对$\delta$的依赖,避免了复杂的指纹码构造。
原文摘要 · Abstract (English)
We propose a framework to convert $(\varepsilon, δ)$-approximate Differential Privacy (DP) mechanisms into $(\varepsilon', 0)$-pure DP mechanisms under certain conditions, a process we call ``purification.'' This algorithmic technique leverages randomized post-processing with calibrated noise to eliminate the $δ$ parameter while achieving near-optimal privacy-utility tradeoff for pure DP. It enables a new design strategy for pure DP algorithms: first run an approximate DP algorithm with certain conditions, and then purify. This approach allows one to leverage techniques such as strong composition and propose-test-release that require $δ>0$ in designing pure-DP methods with $δ=0$. We apply this framework in various settings, including Differentially Private Empirical Risk Minimization (DP-ERM), stability-based release, and query release tasks. To the best of our knowledge, this is the first work with a statistically and computationally efficient reduction from approximate DP to pure DP. Finally, we illustrate the use of this reduction for proving lower bounds under approximate DP constraints with explicit dependence in $δ$, avoiding the sophisticated fingerprinting code construction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。