Efficient delegated private set intersection on outsourced private datasets

Aydin Abadi, Sotirios Terzis, Roberto Metere, Changyu Dong

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.
LanguageEnglish
Pages1-15
Number of pages15
JournalIEEE Transactions on Dependable and Secure Computing
Early online date26 May 2017
DOIs
Publication statusE-pub ahead of print - 26 May 2017

Fingerprint

Cloud computing
Cryptography
Polynomials
Outsourcing

Keywords

  • private set intersection
  • secure computation
  • cloud computing

Cite this

@article{f5c95d5869464dc3a0d9004c0eea1a0a,
title = "Efficient delegated private set intersection on outsourced private datasets",
abstract = "Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.",
keywords = "private set intersection, secure computation, cloud computing",
author = "Aydin Abadi and Sotirios Terzis and Roberto Metere and Changyu Dong",
note = "{\circledC} 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2017",
month = "5",
day = "26",
doi = "10.1109/TDSC.2017.2708710",
language = "English",
pages = "1--15",
journal = "IEEE Transactions on Dependable and Secure Computing",
issn = "1545-5971",

}

Efficient delegated private set intersection on outsourced private datasets. / Abadi, Aydin; Terzis, Sotirios; Metere, Roberto; Dong, Changyu.

In: IEEE Transactions on Dependable and Secure Computing, 26.05.2017, p. 1-15.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient delegated private set intersection on outsourced private datasets

AU - Abadi, Aydin

AU - Terzis, Sotirios

AU - Metere, Roberto

AU - Dong, Changyu

N1 - © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2017/5/26

Y1 - 2017/5/26

N2 - Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.

AB - Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.

KW - private set intersection

KW - secure computation

KW - cloud computing

UR - http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=8858

U2 - 10.1109/TDSC.2017.2708710

DO - 10.1109/TDSC.2017.2708710

M3 - Article

SP - 1

EP - 15

JO - IEEE Transactions on Dependable and Secure Computing

T2 - IEEE Transactions on Dependable and Secure Computing

JF - IEEE Transactions on Dependable and Secure Computing

SN - 1545-5971

ER -