Efficient Delegated Private Set Intersection on Outsourced Private Datasets
Efficient Delegated Private Set Intersection on Outsourced Private Datasets
复制标题
外包私有数据集上的高效委托私有集交集
DOI：
10.1109/tdsc.2017.2708710
复制
发表时间：
2019-07-01
影响因子：
7.3
通讯作者：
Dong, Changyu
中科院分区：
文献类型：
--
作者：
Abadi, Aydin;Terzis, Sotirios;Dong, Changyu
私有集交集（PSI）是一种重要的加密协议，在现实世界中有许多应用。随着云计算能力和普及程度的迅速增长，现在需要利用云来存储私有数据集并将PSI计算委托给它。虽然已经设计了一套高效的PSI协议，但没有一个支持数据集和计算的外包。在本文中，我们提出了在外包私有数据集上委托PSI计算的两种协议。我们的协议具有独特的属性组合，使它们对云计算设置特别有吸引力。我们的第一个协议O-PSI通过使用加性同态加密和集合的点值多项式表示来满足这些性质。我们的第二个协议EO-PSI主要基于哈希表和点值多项式表示，它不需要公钥加密；同时，它保留了所有理想的特性，并且比第一种效率高得多。我们还对半诚实模型中的两个协议进行了正式的安全分析，并利用我们开发的原型实现分析了它们的性能。我们的性能分析表明，EO-PSI可扩展性很好，并且在大集合大小方面也比类似的最先进协议更有效。
Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.