摘要
私有持续计数是差分隐私中的一个基础问题：给定长度为 $n$ 的二进制流，每个 $1$ 代表一个个体的贡献，目标是在保护每个个体隐私的同时释放所有运行计数。标准算法是二叉树机制，其高斯噪声变体在近似差分隐私下实现的预期 $\ell_\infty$ 误差与 $\log^{3/2} n$ 成正比。然而，这种对流长度的依赖是否是必要的，仍然是一个核心未解问题。
在本研究中，我们通过证明每个用于持续计数的差分隐私机制必须产生预期的 $\ell_\infty$ 误差 $\Omega(\log^{3/2} n)$ 来解决这一依赖问题。这表明，二叉树机制在近似差分隐私设置下是渐近最优的。
作为结果，我们还获得了遗传差异和私有 $\ell_\infty$ 误差之间最大的可能分离，显示出已知的遗传差异的一般上界在查询数量方面具有最优依赖性。
博主点评： 本文通过严谨的数学证明，确立了二叉树机制在近似差分隐私持续计数中的最优性，填补了长期以来的理论空白，并对未来的差分隐私机制设计提供了重要指导。其对流长度的依赖性证明了算法设计中的复杂性，值得深入研究。