arXiv:2601.19154cs.DScs.CR2026-01中稿 · PODS 2026被引 7

提出新指标衡量混淆机制隐私增益,突破传统纯本地差分隐私限制。

Analysis of Shuffling Beyond Pure Local Differential Privacy

  • 用单一参数χ替代ε₀,直接分析混淆对隐私的放大效果
  • 发现χ与隐私增益单调相关,可作为混淆效率的代理指标
  • 开发快速算法计算有限n下的隐私界,适合实际应用验证

混淆是提升本地随机化机制隐私性的有效手段。现有分析多基于纯本地差分隐私参数ε₀,但该框架难以处理不满足纯本地DP的机制(如高斯机制)。本文重新审视Balle等人的隐私毯子界(blanket divergence),提出一种绕开ε₀的渐近分析方法。关键发现:渐近情况下,毯子界仅依赖于局部机制的一个标量参数χ,且该依赖关系单调。因此,χ可作为混淆效率的代理指标,称为混淆指数。通过上下界分析,得到混淆机制隐私保证的区间,其范围由混淆指数决定。进一步推导出局部随机化器满足该区间收缩的充要条件:k-RR家族(k≥3)满足此条件;广义高斯机制可能不满足,但其区间仍保持紧致。最后,提出基于FFT的算法,在有限n下高效计算毯子界,具有可控相对误差和近线性时间复杂度,支持实际数值分析。

原文摘要 · Abstract (English)

Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis. Most existing analyses of how shuffling amplifies privacy are based on the pure local differential privacy (DP) parameter $\varepsilon_0$. This paper raises the question of whether $\varepsilon_0$ adequately captures the privacy amplification. For example, since the Gaussian mechanism does not satisfy pure local DP for any finite $\varepsilon_0$, does it follow that shuffling yields weak amplification? To solve this problem, we revisit the privacy blanket bound of Balle et al. (the blanket divergence) and develop a direct asymptotic analysis that bypasses $\varepsilon_0$. Our key finding is that, asymptotically, the blanket divergence depends on the local mechanism only through a single scalar parameter $χ$ and that this dependence is monotonic. Therefore, this parameter serves as a proxy for shuffling efficiency, which we call the shuffle index. By applying this analysis to both upper and lower bounds of the shuffled mechanism's privacy profile, we obtain a band for its privacy guarantee through shuffle indices. Furthermore, we derive a simple structural, necessary and sufficient condition on the local randomizer under which this band collapses asymptotically. $k$-RR families with $k\ge3$ satisfy this condition, while for generalized Gaussian mechanisms the condition may not hold but the resulting band remains tight. Finally, we complement the asymptotic theory with an FFT-based algorithm for computing the blanket divergence at finite $n$, which offers rigorously controlled relative error and near-linear running time in $n$, providing a practical numerical analysis for shuffle DP.

隐私保护差分隐私混淆机制算法分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。