Approximate PSI with Near-Linear Communication

Wutichai Chongchitmate; Steve Lu; Rafail Ostrovsky

Paper 2024/682

Approximate PSI with Near-Linear Communication

Wutichai Chongchitmate, Chulalongkorn University

Steve Lu, Stealth Software Technologies, Inc.

Rafail Ostrovsky, University of California, Los Angeles

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 communication complexity, an improvement over the previously best-known . 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Private Set Intersection PSI Hamming distance
Contact author(s): wutichai ch @ chula ac th
steve @ stealthsoftwareinc com
rafail @ cs ucla edu
History: 2024-10-13: revised; 2024-05-04: received; See all versions
Short URL: https://ia.cr/2024/682
License: CC BY-NC

BibTeX

@misc{cryptoeprint:2024/682,
      author = {Wutichai Chongchitmate and Steve Lu and Rafail Ostrovsky},
      title = {Approximate {PSI} with Near-Linear Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/682},
      year = {2024},
      url = {https://eprint.iacr.org/2024/682}
}