Paper 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.

Metadata
Available format(s)
-- withdrawn --
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. The 18th International Conference on Information and Communications Security
DOI
10.1007/978-3-319-50011-9_34
Keywords
secure tow-party protocol
Contact author(s)
sd iitkgp @ gmail com
History
2019-04-16: withdrawn
2016-12-30: received
See all versions
Short URL
https://ia.cr/2016/1180
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.