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, withdrawn 16 Apr 2019

Contact author: sd iitkgp at gmail com

Available format(s): (-- withdrawn --)

Version: 20190416:093256 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]