VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets

Aydin Kheirbakhsh Abadi, Sotirios Terzis, Changyu Dong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security
Subtitle of host publication20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers
EditorsJens Grossklags, Bart Preneel
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages20
ISBN (Electronic)978-3-662-54970-4
ISBN (Print)978-3-662-54969-8
Publication statusPublished - 17 May 2017
EventTwentieth International Conference of Financial Cryptography and Data Security 2016 - Accra Beach Hotel & Spa, Barbados
Duration: 22 Feb 201626 Feb 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


ConferenceTwentieth International Conference of Financial Cryptography and Data Security 2016
Abbreviated titleFC 2016
Internet address


Dive into the research topics of 'VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets'. Together they form a unique fingerprint.

Cite this