Welcome to the resource topic for 2023/609
Title:
Enabling Two-Party Secure Computation on Set Intersection
Authors: Ferhat Karakoç, Alptekin Küpçü
Abstract:In this paper, we propose the first linear two-party secure-computation private set intersection (PSI) protocol, in the semi-honest adversary model, computing the following functionality. One of the parties (P_X) inputs a set of items X = \{x_j \mid 1 \le j \le n_X\}, whereas the other party (P_Y) inputs a set of items Y = \{y_i \mid 1\le i \le n_Y \} and a set of corresponding data pairs D_Y = \{ (d_i^0,d_i^1) \mid 1 \le i \le n_Y\} having the same cardinality with Y. While P_Y outputs nothing, P_X outputs a set of data D_X = \{ d_i^{b_i} \mid b_i = 1 \text{ if } y_i \in X, b_i = 0 \text{ otherwise}\}. This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party computation such as threshold PSI or any function of the intersection in general. In literature, there are linear circuit and secure-computation PSI proposals, such as Pinkas et al. PSI protocol (Eurocrypt 2019), our PSI protocol (CANS 2020) and Chandran et al. PSI protocol (PETS 2022), for similar functionalities but having a cuckoo table mapping in the functionality, which complicates the application of different secure computation techniques on top of the output of the PSI protocol. We also show that the idea in the construction of our secure-computation PSI protocol having the functionality mentioned above can be utilized to convert the existing circuit PSI and secure-computation PSI protocols into the protocols realizing the functionality not having the cuckoo table mapping. We provide this conversion method as a separate protocol, which is one of the main contributions of this work. While creating the protocol, as a side contribution, we provide a one-time batch oblivious programmable pseudo-random function based on garbled Bloom filters.
ePrint: https://eprint.iacr.org/2023/609
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 .