Cryptology ePrint Archive: Report 2018/238

Private Set Intersection with Linear Communication from General Assumptions

Brett Hemenway Falk and 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).

Category / Keywords: cryptographic protocols /

Original Publication (with minor differences): Workshop on Privacy in the Electronic Society, 2019

Date: received 1 Mar 2018, last revised 2 Oct 2019

Contact author: fbrett at cis upenn edu, dgnoble@cis upenn edu

Available format(s): PDF | BibTeX Citation

Note: Added doi link to WPES version.

Version: 20191002:155721 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]