Frequency Estimation in the Shuffle Model with Almost a Single Message
Frequency Estimation in the Shuffle Model with Almost a Single Message
复制标题
几乎单个消息的 Shuffle 模型中的频率估计
DOI：
10.1145/3548606.3560608
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
K. Yi
中科院分区：
文献类型：
--
作者：
Qiyao Luo;Yilei Wang;K. Yi
我们在差分隐私 (DP) 的混洗模型中提出了一种用于频率估计问题的协议，该协议实现了误差 ω(1) ⋅ O(log n)，几乎与中央 DP 精度相匹配，每个用户有 1 + o(1) 条消息。这表现出一种急剧的转变现象，因为如果每个用户只允许发送一条消息，则存在 Ω 的下限 (n1/4)。以前，只有当域大小 B 为 o(n) 时才知道这样的结果。对于大型域，我们还需要一种有效的方法来识别重要元素（即足够频繁的元素）。为此，我们设计了一个 shuffle-DP 协议，每个用户使用 o(1) 条消息，并且可以识别 B 中时间多对数的所有重击者。最后，通过结合我们的频率估计和重击者检测协议，我们展示了如何在高维设置 B=Ω(n) 下解决 B 维 1 稀疏向量求和问题，实现最优中心 DP MSE Õ(n) 1 + 每个用户 o(1) 条消息。除了错误和消息数量之外，我们的协议还在消息大小和运行时间方面进行了改进。它们也很容易实现。实验结果表明，与之前的工作相比，有了数量级的改进。
We present a protocol in the shuffle model of differential privacy (DP) for the frequency estimation problem that achieves error ω(1) ⋅ O(log n), almost matching the central-DP accuracy, with 1 + o(1) messages per user. This exhibits a sharp transition phenomenon, as there is a lower bound of Ω (n1/4) if each user is allowed to send only one message. Previously, such a result is only known when the domain size B is o(n). For a large domain, we also need an efficient method to identify the heavy hitters (i.e., elements that are frequent enough). For this purpose, we design a shuffle-DP protocol that uses o(1) messages per user and can identify all heavy hitters in time polylogarithmic in B. Finally, by combining our frequency estimation and the heavy hitter detection protocols, we show how to solve the B-dimensional 1-sparse vector summation problem in the high-dimensional setting B=Ω(n), achieving the optimal central-DP MSE Õ(n) with 1 + o(1) messages per user. In addition to error and message number, our protocols improve in terms of message size and running time as well. They are also very easy to implement. The experimental results demonstrate order-of-magnitude improvement over prior work.
DOI：
10.4230/lipics.itc.2020.1
发表时间：
2019-11
期刊：
--
影响因子：
--
作者：
Victor Balcer;Albert Cheu
通讯作者：
Victor Balcer;Albert Cheu
DOI：
--
发表时间：
2017-08
期刊：
--
影响因子：
--
作者：
Tianhao Wang;Jeremiah Blocki;Ninghui Li;S. Jha
通讯作者：
Tianhao Wang;Jeremiah Blocki;Ninghui Li;S. Jha