VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets
VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets
复制标题
DOI：
10.1007/978-3-662-54970-4_9
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
A. Abadi;S. Terzis;Changyu Dong
中科院分区：
文献类型：
--
作者：
A. Abadi;S. Terzis;Changyu Dong
私有集交(PSI)协议有许多实际应用。随着云计算的出现，出现了对外包数据集执行PSI的需求，其中计算委托给云。然而，由于云行为不当的可能性，必须验证任何外包数据集的完整性以及任何委托计算的结果。在不泄露任何数据信息的私有数据集上进行可验证计算是非常具有挑战性的，特别是在不同客户独立外包数据集的情况下。本文提出了VD-PSI协议，该协议允许多个客户外包他们的私有数据集，并将集合相交的计算委托给云，同时能够验证结果的正确性。客户可以独立地准备和上传他们的数据集，并且在他们的同意下可以无限次可验证地委托集合交集的计算，而不需要下载或维护他们的数据的本地副本。该协议确保云对数据集和交集一无所知。VD-PSI的验证代价与交集基数呈线性关系，计算和通信代价与数据集基数(上界)呈线性关系，因此是有效的。此外，我们还在标准模型中提供了形式化的安全分析。
Private set intersection (PSI) protocols have many real world applications. With the emergence of cloud computing the need arises to carry out PSI on outsourced datasets where the computation is delegated to the cloud. However, due to the possibility of cloud misbehavior, it is essential to verify the integrity of any outsourced datasets, and results of any delegated computation. Verifiable Computation on private datasets that does not leak any information about the data is very challenging, especially when the datasets are outsourced independently by different clients. In this paper we present VD-PSI, a protocol that allows multiple clients to outsource their private datasets and delegate computation of set intersection to the cloud, while being able to verify the correctness of the result. Clients can independently prepare and upload their datasets, and with their agreement can verifiably delegate the computation of set intersection an unlimited number of times, without the need to download or maintain a local copy of their data. The protocol ensures that the cloud learns nothing about the datasets and the intersection. VD-PSI is efficient as its verification cost is linear to the intersection cardinality, and its computation and communication costs are linear to the (upper bound of) dataset cardinality. Also, we provide a formal security analysis in the standard model.