Enabling Two-Party Secure Computation on Set Intersection
Ferhat Karakoç, Alptekın Küpçü · IEEE Transactions on Dependable and Secure Computing · 2025
We propose the first linear secure-computation private set intersection (PSI) protocol computing the following functionality.$P_{X}$inputs a set$X = \lbrace x_{j} \mid 1 \le j \le n_{X}\rbrace$, whereas$P_{Y}$inputs a set$Y = \lbrace y_{i} \mid 1\le i \le n_{Y} \rbrace$and a data set$D_{Y} = \lbrace (d_{i}^{0},d_{i}^{1}) \mid 1 \le i \le n_{Y}\rbrace$. While$P_{Y}$outputs nothing,$P_{X}$outputs$D_{X} = \lbrace d_{i}^{b_{i}} \mid b_{i} = 1 \rm{ if } y_{i} \in X, b_{i} = 0 \rm{ otherwise}\rbrace$. This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party computation protocol. Existing protocols for similar functionalities have a cuckoo table mapping in the functionality, and therefore the output is not directly indexed on the intersection but on the cuckoo table mapping of the intersection, which complicates the application of different secure computation techniques on top of the output. We introduce a conversion technique based on additively homomorphic encryption used in the construction of our PSI protocol as a separate protocol and show that it can be utilized to convert the existing circuit and secure-computation PSI protocols into the protocols realizing the functionality not having the mapping.