Distance-Aware Private Set Intersection

Private set intersection (PSI) allows two mutually-untrusting parties to compute an intersection of their respective sets, without revealing any information to each other about items that are not in the intersection. This work introduces a variant of the problem called {\em distance-aware} PSI (DA-PSI) for computing intersection of items in defined metric spaces. The intersection contains pairs of items that are within a specified distance threshold of each other. This paper puts forward constructions for two such metric spaces: (i) Minkowski distance of order 1 over the set of integers (i.e., for integers $a$ and $b$, their distance is $|a-b|$); and (ii) Hamming distance over the set $\{0,1\}^\ell$. The communication volume scales logarithmically in the distance threshold, and linearly in the set size for the Minkowski DA-PSI protocol. On the other hand, the communication volume scales quadratically in the distance threshold for the Hamming DA-PSI protocol and is independent of the number of dimensions. Applying the Minkowski DA-PSI protocol to compare IP addresses contacting honeypots for private collaborative blacklisting both improves findings relative to PSI, doubling the number of IPs in the intersection, and reduces communication and computation by $10\times$ relative to a naive baseline. Applying the Hamming DA-PSI protocol to the task of Iris recognition reduces communication volume by $4\times$ over a generic 2PC baseline.