Cryptology ePrint Archive: Report 2016/1180

How to Meet Big Data When Private Set Intersection Realizes Constatnt Communication Complexity

Sumit Kumar Debnath and Ratna Dutta

Abstract: Electronic information is increasingly often shared among unreliable entities. In this context, one interesting problem involves two parties that secretly want to determine intersection of their respective private data sets while none of them wish to disclose the whole set to other. One can adopt Private Set Intersection (PSI) protocol to address this problem preserving the associated security and privacy issues. This paper presents the first PSI protocol that achieves constant ($p(\kappa)$) communication complexity with linear computation overhead and is fast even for the case of large input sets, where $p(\kappa)$ is a polynomial in security parameter $\kappa$. The scheme is proven to be provably secure in the standard model against semi-honest parties. We combine somewhere statistically binding (SSB) hash function with indistinguishability obfuscation (iO) and Bloom filter to construct our PSI protocol.

Category / Keywords: cryptographic protocols / secure tow-party protocol

Original Publication (with major differences): The 18th International Conference on Information and Communications Security

Date: received 25 Dec 2016, last revised 25 Dec 2016

Contact author: sd iitkgp at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20161230:194609 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]