Random Differential Privacy
Rob Hall Alessandro Rinaldo Larry Wasserman
Abstract
We propose a relaxed privacy definition called random differential privacy (RDP). Differential privacy requires that adding any new observation to a database will have small effect on the output of the data-release procedure. Random differential privacy requires that adding a randomly drawn new observation to a database will have small effect on the output. We show an analog of the composition property of differentially private procedures which applies to our new definition. We show how to release an RDP histogram and we show that RDP histograms are much more accurate than histograms obtained using ordinary differential privacy. We finally show an analog of the global sensitivity framework for the release of functions under our privacy definition.
中文速览
差分隐私（Differential Privacy, DP）能提供极强的隐私保护，但代价是发布的数据精度大幅下降——尤其当直方图维度 k 很大时，最优 DP 算法的误差以 k/αn 的速率增长，在稀疏场景下代价极高。本文提出一种名为"随机差分隐私"（Random Differential Privacy, RDP）的放宽定义：不再要求对任意新增观测都保持输出稳定，而只要求对从同一数据分布中随机抽取的新增观测保持稳定，从而将隐私保护的最坏情形限定在"典型用户"而非"最极端用户"上。作者证明了 RDP 版本的组合性质（composition lemma）成立，构造了满足 RDP 的直方图发布机制，并通过理论分析表明：RDP 直方图的误差下界仅依赖于直方图的实际支撑大小（即非零格子数），而非全部维度 k，这在稀疏直方图场景下比传统 DP 精度显著更高。这一工作为探索隐私与统计精度之间的权衡提供了新的理论框架，对需要在有限隐私预算下处理高维稀疏数据的实际场景具有重要参考价值。
原文 arXiv:1112.2680;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1112.2680v1