O-PSI: Delegated Private Set Intersection on Outsourced Datasets

Aydin Kheirbakhsh Abadi, Sotirios Terzis, Changyu Dong

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


Private set intersection (PSI) has a wide range of applications such as privacy-preserving data mining. With the advent of cloud computing it is now desirable to take advantage of the storage and computation capabilities of the cloud to outsource datasets and delegate PSI computation. In this paper we design O-PSI, a protocol for delegated private set intersection on outsourced datasets based on a novel point-value polynomial representation. Our protocol allows multiple clients to independently prepare and upload their private datasets to a server, and then ask the server to calculate their intersection. The protocol ensures that intersections can only be calculated with the permission of all clients and that datasets and results remain completely confidential from the server. Once datasets are outsourced, the protocol supports an unlimited number of intersections with no need to download them or prepare them again for computation. Our protocol is efficient and has computation and communication costs linear to the cardinality of the datasets. We also provide a formal security analysis of the protocol.
Original languageEnglish
Title of host publicationICT Systems Security and Privacy Protection
Subtitle of host publication30th IFIP TC 11 International Conference, SEC 2015, Hamburg, Germany, May 26-28, 2015, Proceedings
EditorsHannes Federrath, Dieter Gollmann
Place of PublicationCham
PublisherSpringer International Publishing
Number of pages15
ISBN (Electronic)978-3-319-18467-8
ISBN (Print)978-3-319-18466-1
Publication statusPublished - 9 May 2015

Publication series

NameIFIP Advances in Information and Communication Technology
PublisherSpringer International Publishing
ISSN (Print)1868-4238


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

Cite this