Paper 2018/238

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

Note: Added doi link to WPES version.

Metadata
Available format(s)
PDF
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
2018-03-05: received
See all versions
Short URL
https://ia.cr/2018/238
License
Creative Commons Attribution
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.