Paper 2018/238
Private Set Intersection with Linear Communication from General Assumptions
Brett Hemenway Falk and Daniel Noble and Rafail Ostrovsky
Abstract
This work presents an improved 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 \lambda)$ communication between the parties, where $\lambda$ is a security parameter. This is the first protocol to achieve PSI using only asymptotically linear communication under standard cryptographic assumptions and without Random Oracles. Our protocol also provides 10-15\% reduction in communication costs under real-world parameter choices. 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 \lambda)$ to $O(m\lambda)$, and provides concrete performance improvements over the most efficient existing PSI protocols. 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 (CCS 2016).
Note: Fixed typos. Updated references to include comparisons to new PSI protocols.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- fbrett @ 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
-
CC BY