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

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.
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

Fingerprint

Network protocols
Cloud computing
Costs
Communication

Keywords

  • private set intersection protocols
  • cloud computing
  • datasets

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). Berlin Heidelberg. https://doi.org/10.1007/978-3-662-54970-4
Abadi, Aydin ; Terzis, Sotirios ; Dong, Changyu. / VD-PSI : verifiable delegated private set intersection on outsourced private datasets. Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers. editor / Jens Grossklags ; Bart Preneel. Vol. 9603 Berlin Heidelberg, 2016. pp. 149-168 (Lecture Notes in Computer Science).
@inproceedings{ebb0350bb6474a7da7e07758512293a9,
title = "VD-PSI: verifiable delegated private set intersection on outsourced private datasets",
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.",
keywords = "private set intersection protocols, cloud computing, datasets",
author = "Aydin Abadi and Sotirios Terzis and Changyu Dong",
year = "2016",
month = "6",
day = "10",
doi = "10.1007/978-3-662-54970-4",
language = "English",
isbn = "978-3-662-54969-8",
volume = "9603",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "149--168",
editor = "Jens Grossklags and Bart Preneel",
booktitle = "Financial Cryptography and Data Security",

}

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, Lecture Notes in Computer Science, vol. 9603, Berlin Heidelberg, pp. 149-168, Financial Cryptography and Data Security, Barbados, 22/02/16. https://doi.org/10.1007/978-3-662-54970-4

VD-PSI : verifiable delegated private set intersection on outsourced private datasets. / Abadi, Aydin; Terzis, Sotirios; Dong, Changyu.

Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers. ed. / Jens Grossklags; Bart Preneel. Vol. 9603 Berlin Heidelberg, 2016. p. 149-168 (Lecture Notes in Computer Science; Vol. 9603).

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

TY - GEN

T1 - VD-PSI

T2 - verifiable delegated private set intersection on outsourced private datasets

AU - Abadi, Aydin

AU - Terzis, Sotirios

AU - Dong, Changyu

PY - 2016/6/10

Y1 - 2016/6/10

N2 - 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.

AB - 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.

KW - private set intersection protocols

KW - cloud computing

KW - datasets

UR - http://fc16.ifca.ai/program.html

UR - http://www.springer.com/gp/book/9783662549698

U2 - 10.1007/978-3-662-54970-4

DO - 10.1007/978-3-662-54970-4

M3 - Conference contribution book

SN - 978-3-662-54969-8

VL - 9603

T3 - Lecture Notes in Computer Science

SP - 149

EP - 168

BT - Financial Cryptography and Data Security

A2 - Grossklags, Jens

A2 - Preneel, Bart

CY - Berlin Heidelberg

ER -

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