Paper 2024/682

Approximate PSI with Near-Linear Communication

Abstract

Private Set Intersection (PSI) is a protocol where two parties with individually held confidential sets want to jointly learn (or secret-share) the intersection of these two sets and reveal nothing else to each other. In this paper, we introduce a natural extension of this notion to approximate matching. Specifically, given a distance metric between elements, an approximate PSI (Approx-PSI) allows to run PSI where ``close'' elements match. Assuming that elements are either ``close'' or sufficiently ``far apart'', we present an Approx-PSI protocol for Hamming distance that improves the overall efficiency compared to all existing approximate-PSI solutions. In particular, we achieve a near-linear $\tilde{O}(n)$ communication complexity, an improvement over the previously best-known $\tilde{O}(n^2)$. We also show Approx-PSI protocols for Edit distance (also known as Levenstein distance), Euclidean distance and angular distance by deploying results on low distortion embeddings to Hamming distance. The latter two results further imply secure Approx-PSI for other metrics such as cosine similarity metric. Our Approx-PSI for Hamming distance is up to 20x faster and communicating 30% less than best known protocols when (1) matching small binary vectors; or (2) matching large threshold; or (3) matching large input sets. We also apply our technique to analyze private approximate membership computation, which can be viewed as asymmetric case of approximate PSI, and obtain a protocol with sublinear communication.

Note: Correction and additional results and analysis.