Separating Local & Shuffled Differential Privacy via Histograms
Separating Local & Shuffled Differential Privacy via Histograms
复制标题
DOI：
10.4230/lipics.itc.2020.1
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Victor Balcer;Albert Cheu
中科院分区：
文献类型：
--
作者：
Victor Balcer;Albert Cheu
最近在差异隐私方面的研究突显出，置乱模型是一种在将原始数据保留在用户手中的同时计算准确统计数据的有前途的方法。我们在这个模型中提出了一种协议，该协议估计直方图的误差与域大小无关。这意味着混洗模型和局部模型之间的样本复杂性有任意大的差距。另一方面，当我们施加纯差分隐私和单消息随机子的约束时，模型是等价的。
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.