### Private Set Intersection with Linear Communication from General Assumptions

Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky

##### Abstract

This work presents a hashing-based algorithm for Private Set Intersection (PSI) in the honest-but-curious setting. The protocol is generic, modular and provides both asymptotic and concrete efficiency improvements over existing PSI protocols. If each player has $m$ elements, our scheme requires only $O(m \secpar)$ communication between the parties, where $\secpar$ is a security parameter. Our protocol builds on the hashing-based PSI protocol of Pinkas et al. (USENIX 2014, USENIX 2015), but we replace one of the sub-protocols (handling the cuckoo stash'') with a special-purpose PSI protocol that is optimized for comparing sets of unbalanced size. This brings the asymptotic communication complexity of the overall protocol down from $\omega(m \secpar)$ to $O(m\secpar)$, and provides concrete performance improvements (10-15\% reduction in communication costs) over Kolesnikov et al. (CCS 2016) under real-world parameter choices. Our protocol is simple, generic and benefits from the permutation-hashing optimizations of Pinkas et al. (USENIX 2015) and the Batched, Relaxed Oblivious Pseudo Random Functions of Kolesnikov et al. (CCS 2016).

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.Workshop on Privacy in the Electronic Society, 2019
DOI
10.1145/3338498.3358645
Contact author(s)
fbrett @ cis upenn edu
dgnoble @ cis upenn edu
History
2019-10-02: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/238

CC BY

BibTeX

@misc{cryptoeprint:2018/238,
author = {Brett Hemenway Falk and Daniel Noble and Rafail Ostrovsky},
title = {Private Set Intersection with Linear Communication from General Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2018/238},
year = {2018},
doi = {10.1145/3338498.3358645},
note = {\url{https://eprint.iacr.org/2018/238}},
url = {https://eprint.iacr.org/2018/238}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.