On Distributed Differential Privacy and Counting Distinct Elements
On Distributed Differential Privacy and Counting Distinct Elements
复制标题
关于分布式差分隐私和计算不同元素
DOI：
10.4230/lipics.itcs.2021.56
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pasin Manurangsi
中科院分区：
文献类型：
--
作者：
Lijie Chen;Badih Ghazi;Ravi Kumar;Pasin Manurangsi
我们研究这样一种情形：$n$个用户中的每一个都持有来自一个离散集合的一个元素，目标是在$(\epsilon, \delta)$ - 差分隐私约束下，计算所有用户中不同元素的数量：
- 在非交互本地设置中，我们证明对于任何常数$\epsilon$以及$n$的任何逆多项式形式的$\delta$，任何协议的加性误差是$\Omega(n)$。
- 在单消息洗牌设置中，对于任何常数$\epsilon$以及$n$的某些逆拟多项式形式的$\delta$，我们证明误差的下界是$\Omega(n)$。我们通过基于分布估计文献中的矩匹配方法来做到这一点。
- 在多消息洗牌设置中，对于任何常数$\epsilon$以及$n$的任何逆多项式形式的$\delta$，我们给出一个协议，期望每个用户最多有一条消息，且误差为$\tilde{O}(\sqrt{n})$。我们的协议也是鲁棒的洗牌隐私的，并且我们的$\sqrt{n}$误差与这类协议的一个已知下界相匹配。
我们的证明技术依赖于一个新概念，我们称之为占优协议，它也可用于针对选择和学习奇偶性这些被充分研究的问题，获得针对多消息洗牌协议的第一个非平凡下界。
我们对于估计不同元素数量的第一个下界在局部差分隐私中提供了全局敏感度和误差之间的第一个$\omega(\sqrt{n})$分离，从而回答了Vadhan（2017）的一个开放问题。我们还提供了一个简单构造，它在两方差分隐私中给出了全局敏感度和误差之间的$\tilde{\Omega}(n)$分离，从而回答了McGregor等人（2011）的一个开放问题。
We study the setup where each of $n$ users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of $(\epsilon, \delta)$-differentially privacy:
- In the non-interactive local setting, we prove that the additive error of any protocol is $\Omega(n)$ for any constant $\epsilon$ and for any $\delta$ inverse polynomial in $n$.
- In the single-message shuffle setting, we prove a lower bound of $\Omega(n)$ on the error for any constant $\epsilon$ and for some $\delta$ inverse quasi-polynomial in $n$. We do so by building on the moment-matching method from the literature on distribution estimation.
- In the multi-message shuffle setting, we give a protocol with at most one message per user in expectation and with an error of $\tilde{O}(\sqrt(n))$ for any constant $\epsilon$ and for any $\delta$ inverse polynomial in $n$. Our protocol is also robustly shuffle private, and our error of $\sqrt(n)$ matches a known lower bound for such protocols.
Our proof technique relies on a new notion, that we call dominated protocols, and which can also be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of selection and learning parity.
Our first lower bound for estimating the number of distinct elements provides the first $\omega(\sqrt(n))$ separation between global sensitivity and error in local differential privacy, thus answering an open question of Vadhan (2017). We also provide a simple construction that gives $\tilde{\Omega}(n)$ separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011).
DOI：
10.4230/lipics.itc.2020.1
发表时间：
2019-11
期刊：
--
影响因子：
--
作者：
Victor Balcer;Albert Cheu
通讯作者：
Victor Balcer;Albert Cheu