Approximate Private Set Intersection

Abstract: Private Set Intersection (PSI) is a protocol where two parties, each holding a confidential set, wish to jointly learn (or secret-share) the intersection of their sets without revealing any additional information.  By relaxing the strict requirement of exact match, the realm of Fuzzy PSI deals with matching under certain conditions (or "metrics") of closeness.  In this talk, we focus on a family of variants of fuzzy PSI that we collectively call Approximate PSI.  We present an improved protocol for when the metric is the Hamming distance, significantly improving overall efficiency compared to existing solutions.  Operating under lightweight and flexible assumptions, each protocol can be adapted to output a secret-shared result, enabling further secure computation.  Lastly, we show how this extends into Euclidean distance or cosine similarity, which applies to high-dimensional vector private approximate intersection or approximate membership.

Joint work: Wutichai Chongchitmate, Steve Lu, Rafail Ostrovsky

Suggested readings:

• Approximate PSI with Near-Linear Communication (ia.cr/2024/682)
• Assumption-Free Fuzzy PSI via Predicate Encryption (ia.cr/2025/217)
• Efficient Fuzzy Private Set Intersection from Fuzzy Mapping (ia.cr/2024/1462)
• Distance-Aware Private Set Intersection (arXiv:2112.14737)