VD-PSI: verifiable delegated private set intersection on outsourced private datasets

Aydin Abadi, Sotirios Terzis, Changyu Dong

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

25 Downloads (Pure)

Abstract

Private set intersection (PSI) protocols have many real world applications. With the emergence of cloud computing the need arises for PSI protocols on outsourced datasets where the computation is delegated to the cloud. However, due to the possibility of cloud misbehaviors, it is essential to verify the correctness of any delegated computation, and the integrity of any outsourced datasets. 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 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
Pages149-168
Number of pages20
Volume9603
DOIs
Publication statusPublished - 10 Jun 2016
EventFinancial Cryptography and Data Security - , Barbados
Duration: 22 Feb 201626 Feb 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9603
ISSN (Print)0302-9743

Conference

ConferenceFinancial Cryptography and Data Security
CountryBarbados
Period22/02/1626/02/16

Keywords

  • private set intersection protocols
  • cloud computing
  • datasets

Fingerprint Dive into the research topics of 'VD-PSI: verifiable delegated private set intersection on outsourced private datasets'. Together they form a unique fingerprint.

  • Research Output

    • 1 Conference contribution book

    VD-PSI: verifiable delegated private set intersection on outsourced private datasets

    Abadi, A., Terzis, S. & Dong, C., 10 Jun 2016, Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers. Grossklags, J. & Preneel, B. (eds.). Berlin Heidelberg, Vol. 9603. p. 149-168 20 p. (Lecture Notes in Computer Science; vol. 9603).

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

    Open Access
    File
  • 25 Downloads (Pure)

    Cite this

    Abadi, A., Terzis, S., & Dong, C. (2016). VD-PSI: verifiable delegated private set intersection on outsourced private datasets. In J. Grossklags, & B. Preneel (Eds.), Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers (Vol. 9603, pp. 149-168). (Lecture Notes in Computer Science; Vol. 9603).. https://doi.org/10.1007/978-3-662-54970-4