Paper 2017/215

SEVDSI: Secure, Efficient and Verifiable Data Set Intersection

Ozgur Oksuz, Iraklis Leontiadis, Sixia Chen, Alexander Russell, Qiang Tang, and Bing Wang

Abstract

We are constantly moving to a digital world, whereby the majority of information is stored at the weakest link: users' devices and data enclaves -- vulnerable to attacks by adversaries. Users are often interested to share some information, such as the set intersection of their data sets. So as to reduce the communication bandwidth, cloud based protocols have been proposed in the literature, with a rather weak security model. Either there is a semi-honest cloud, which is far from realistic nowadays, or the leakage from the protocol puts the data at risk. In this paper, we achieve the best of the two worlds: We design and analyze a non-interactive, cloud based private set intersection (PSI) protocol secure in a stronger security model. Our protocol assures privacy on data set inputs in case of a malicious cloud and enforces authorized only computations by the users. Moreover the computation is verifiable and the asymptotic communication cost for the computation of the intersection is linear on the common elements $k$. Our protocol is secure in the random oracle model under standard assumptions and a new mathematical assumption whose security evidence is given in the generic group model.