Welcome to the resource topic for 2020/864
Title:
Linear Complexity Private Set Intersection for Secure Two-Party Protocols
Authors: Ferhat Karakoç, Alptekin Küpçü
Abstract:In this paper, we propose a new private set intersection (PSI) protocol with bi-oblivious data transfer that computes the following functionality. One of the parties P_1 inputs a set of items X and a set of data pairs D_1 = \{ (d_0^j,d_1^j)\} and the other party P_2 inputs a set of items Y. While P_1 outputs nothing, P_2 outputs a set of data D_2 = \{ d_{b_j}^j \mid b_j \in \{0,1\}\} dependent on the intersection of X and Y. This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation such as threshold PSI or any function of the whole intersecting set in general. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this type of 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 membership results and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the membership results with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time batch oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results.
ePrint: https://eprint.iacr.org/2020/864
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .