Paper 2017/215

SEVDSI: Secure, Efficient and Verifiable Data Set Intersection

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

Abstract

Private set intersection is one of the most well studied and useful secure computation protocols. Many specific two party secure computation protocols have been constructed for such a functionality, but all of them incur large communication between the parties. A cloud assisted protocol was also considered to provide better efficiency, but with the potential risk of leaking more information to the cloud. In this paper, we achieve the best of the two worlds: We design and analyze SEVDSI: a $\mathsf{S}$ecure, $\mathsf{E}$fficient and $\mathsf{V}$erifiable $\mathsf{D}$ata $\mathsf{S}$et $\mathsf{I}$ntersection protocol which is non-interactive and cloud based in a stronger security model. Our protocol assures privacy on data set inputs in case of a {\em malicious} cloud and enforces authorized only computations by the users. Moreover, the computation is verifiable and we achieve $O(m^3)$ asymptotic communication cost for $m$ users in contrast with the fastest two party computation protocols, which obtain a $O(m^4)$ communication complexity, in case of multiparty PSI. SEVDSI is provably secure in the random oracle model.