Approximating Private Set Union/Intersection Cardinality With Logarithmic Complexity
Approximating Private Set Union/Intersection Cardinality With Logarithmic Complexity
复制标题
DOI：
10.1109/tifs.2017.2721360
复制
发表时间：
2017-11-01
影响因子：
6.8
通讯作者：
Loukides, Grigorios
中科院分区：
文献类型：
--
作者：
Dong, Changyu;Loukides, Grigorios
私有集并/交基数(PSU-CA/PSI-CA)的计算是隐私保护数据挖掘中研究最深入的问题之一。然而，现有的协议在计算上太昂贵，不能在现实世界的PPDM应用中使用。对此，我们提出了高效的近似协议，其精度可以根据应用需求进行调整。我们首先提出了一个基于Flajolet-Martin Sketches的两方PSU-CA协议。该协议具有对数计算/通信复杂性，并且主要依赖于对称密钥运算。因此，它比现有的协议更高效和可伸缩。此外，我们的协议可以隐藏其输出。此功能在PPDM应用程序中是必需的，因为并基数通常是不能公开的中间结果。然后，我们提出了一种双方PSI-CA协议，该协议是从PSU-CA协议衍生而来的，实际上是零成本的。我们的两方协议都可以很容易地扩展到多方设置。我们还为((1)(N))-OT设计了一个有效的掩码方案。该方案用于优化两方协议，当n较大时，它可以显著加快((1)(N))-OT，具有独立的意义。最后，通过实验验证了协议的有效性和高效性。
The computation of private set union/intersection cardinality (PSU-CA/PSI-CA) is one of the most intensively studied problems in privacy preserving data mining (PPDM). However, the existing protocols are computationally too expensive to be employed in real-world PPDM applications. In response, we propose efficient approximate protocols, whose accuracy can be tuned according to application requirements. We first propose a two-party PSU-CA protocol based on Flajolet-Martin sketches. The protocol has logarithmic computational/communication complexity and relies mostly on symmetric key operations. Thus, it is much more efficient and scalable than existing protocols. In addition, our protocol can hide its output. This feature is necessary in PPDM applications, since the union cardinality is often an intermediate result that must not be disclosed. We then propose a two-party PSI-CA protocol, which is derived from the PSU-CA protocol with virtually no cost. Both our two-party protocols can be easily extended to the multiparty setting. We also design an efficient masking scheme for ((1)(n))-OT. The scheme is used in optimizing the two-party protocols and is of independent interest, since it can speed up ((1)(n))-OT significantly when n is large. Finally, we show through experiments the effectiveness and efficiency of our protocols.