.png){kind=icon}
.png){kind=icon}
Return
Enabling Two-Party Secure Computation on Set Intersection
.png){kind=icon}
PRE
AI
DOI：10.1109/TDSC.2025.3561472.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 \leq j \leq n_{X}\rbrace$, whereas $P_{Y}$ inputs a set $Y = \lbrace y_{i} \mid 1\leq i \leq n_{Y} \rbrace$ and a data set $D_{Y} = \lbrace (d_{i}^{0},d_{i}^{1}) \mid 1 \leq i \leq n_{Y}\rbrace$. While $P_{Y}$ outputs nothing, $P_{X}$ outputs $D_{X} = \lbrace d_{i}^{b_{i}} \mid b_{i} = 1 \text{ if } y_{i} \in X, b_{i} = 0 \text{ 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.
Keywords:
Private set intersection
two-party computation
bloom filters
oblivious transfer
cuckoo hashing
circuit-PSI
OPPRF
Journal
IF:
7.5
Papers:
2.4K
Citations:
9.6K