Enabling Two-Party Secure Computation on Set Intersection

We propose the first linear secure-computation private set intersection (PSI) protocol computing the following functionality. <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P_{X}$</tex-math></inline-formula> inputs a set <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$X = \lbrace x_{j} \mid 1 \le j \le n_{X}\rbrace$</tex-math></inline-formula>, whereas <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P_{Y}$</tex-math></inline-formula> inputs a set <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$Y = \lbrace y_{i} \mid 1\le i \le n_{Y} \rbrace$</tex-math></inline-formula> and a data set <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$D_{Y} = \lbrace (d_{i}^{0},d_{i}^{1}) \mid 1 \le i \le n_{Y}\rbrace$</tex-math></inline-formula>. While <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P_{Y}$</tex-math></inline-formula> outputs nothing, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P_{X}$</tex-math></inline-formula> outputs <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$D_{X} = \lbrace d_{i}^{b_{i}} \mid b_{i} = 1 \rm{ if } y_{i} \in X, b_{i} = 0 \rm{ otherwise}\rbrace$</tex-math></inline-formula>. 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.