On the complexity of two-party differential privacy
On the complexity of two-party differential privacy
复制标题
论两方差分隐私的复杂性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Eliad Tsfadia
中科院分区：
文献类型：
--
作者：
Iftach Haitner;N. Mazor;Jad Silbak;Eliad Tsfadia
在分布式差分隐私中，各方对他们的联合数据进行分析，同时保留两个数据集的隐私。有趣的是，对于一些基本的两方函数，如内积和汉明距离，分布式解决方案的准确性远远落后于客户端-服务器设置中可实现的精度。McGregor，Mironov，Pitassi，Reingold，Talwar和Vadhan [FOCS '10]证明了这种差距是固有的，显示了这些函数的（任何）分布式解决方案的精度上限。当解决计算差分隐私时，可以绕过这些限制，其中数据仅在计算有限的观察者眼中是差分隐私的，使用不经意传输。我们证明了使用公钥密码是绕过McGregor等人的限制所必需的，证明了内积或汉明距离的非平凡解意味着密钥协商协议的存在。我们的界限意味着一个组合证明的事实，即独立（强）Santha-Vazirani源的非布尔内积是一个很好的冷凝器。我们得到我们的主要结果表明，内积的（单一的，强）SV源均匀随机种子是一个很好的冷凝器，即使当种子和源是相关的。
In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS ’10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using oblivious transfer. We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent.