Distance-Aware Private Set Intersection
This work addresses privacy-preserving data matching for applications involving metric spaces, such as integer or binary string comparisons, offering a novel variant of PSI with potential domain-specific impact.
This paper tackles the problem of computing intersections of sets in a metric space while preserving privacy, introducing distance-aware private set intersection (DA-PSI) to return pairs of items within a specified distance threshold, with results showing communication complexities that scale logarithmically or quadratically in the threshold and experimental confirmation of more effective matching at lower cost than naive solutions.
Private set intersection (PSI) allows two mutually untrusting parties to compute an intersection of their sets, without revealing information about items that are not in the intersection. This work introduces a PSI variant called distance-aware PSI (DA-PSI) for sets whose elements lie in a metric space. DA-PSI returns pairs of items that are within a specified distance threshold of each other. This paper puts forward DA-PSI constructions for two 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 of binary strings of length $\ell$. In the Minkowski DA-PSI protocol, the communication complexity scales logarithmically in the distance threshold and linearly in the set size. In the Hamming DA-PSI protocol, the communication volume scales quadratically in the distance threshold and is independent of the dimensionality of string length $\ell$. Experimental results with real applications confirm that DA-PSI provides more effective matching at lower cost than naive solutions.