Paper 2020/864

Linear Complexity Private Set Intersection for Secure Two-Party Protocols

Ferhat Karakoç and Alptekin Küpçü

Abstract

In this paper, we propose a new private set intersection (PSI) protocol that computes the following functionality. The two parties ($P_1$ and $P_2$) input two sets of items ($X$ and $Y$, respectively) and one of the parties outputs a function of the intersection ($f(X \cap Y)$). This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this functionality, which has linear complexity only in communication. While there are PSI protocols with linear computation and communication complexities in the classical PSI setting where the intersection itself is revealed to one party, to the best of our knowledge, there is no PSI protocol, which outputs a function of the intersection and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the intersection with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results.