Enabling Two-Party Secure Computation on Set Intersection

Abstract

We propose the first linear secure-computation private set intersection (PSI) protocol computing the following functionality. PX inputs a set X = {x(j)divided by 1 <= j <= nX}, whereas PY inputs a set Y = {y(i)divided by 1 <= i <= n Y} and a data set DY={(d(i)(0),d(i)(1))divided by 1 <= i <= nY}. While PY outputs nothing, PX outputs DX={d(i)(bi)divided by b(i)=1 if y(i)is an element of X,bi=0 otherwise}. 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.