一种高效的关于两方集合并/交集基数的隐私计算方法

Efficient Approach Regarding Two-Party Privacy-Preserving Set Union/Intersection Cardinality

隐私保护计算技术已逐步从理论设想发展为可应用的实践技术,两方集合并交集基数的隐私计算(Private Set Union/Private Set Intersection Cardinality,PSU/PSI-CA)问题是隐私算领域中一类基础又重要的问题.而当前解决这一问题的相关协议在使用场景、可用性、具体效率上都有着许多不足.如当前最先进的协议之一的Dong-Loukides协议离线计算开销较大,不适用于数据集频繁更新的场景.此外由于它在在线阶段只能串行执行,因此在广域网设置下执行时间较长.为解决Dong-Loukides协议总体计算开销较大且广域网设置下执行时间长的问题,输入集合的布隆过滤器,本文基于离线-在线(offlineonline)框架提出一种新协议,并给出了新协议在半诚实模型下的基于模拟的安全性证明.该协议的在线通信轮数为常数轮,且计算开销几乎为零.在本文进行的与Dong-Loukides的PSU-CA协议的对比实验中,我们分别选定了10^(3),10^(4),10^(5)量级的输入数据,在局域网环境下,结果显示新协议的总耗时相对于Dong-Loukides协议的总耗时分别为20.4%,12.4%,9.3%.

Privacy-preserving computing technology has gradually evolved from a theoretical idea to a practical technology.Two-party Private Set Union/Intersection Cardinality(PSU/PSI-CA)problems are fundamental and vital problems in the field of privacy-preserving computing.However,existing protocols on this problem still have some shortcomings in terms of availability and efficiency.For example,the Dong-Loukides protocol,one of the most advanced protocols at present,has a large offline computation overhead and is not suitable to scenarios where the data set is frequently updated.In addition,because it can only be executed serially in the online phase,it needs much time under the WAN setting.To reduce the large computational cost of the Dong-Loukides protocol and the execution time under the WAN setting,this study proposes a new protocol based on the offlineonline framework with Bloom filters as input.Also this paper gives some simulation-based security proof of the new protocol under the semi-honest model.The proposed protocol is with constant rounds of communication and has negligible computational cost in the online phase.In the comparison experiment with Dong-Loukides’PSU-CA protocol,with input data scale of 10^(3),10^(4),10^(5),respectively in the local area network environment,the results show that the total time of the proposed protocol versus the total time of the Dong-Loukides protocol are 20.4%,12.4%,9.3%,respectively.