Privacy-preserving Proximity Testing from Geometric Fuzzy Matching

Abstract: Geometric Fuzzy Matching (GFM) is a two-party primitive in which the receiver specifies an arbitrary bounded region of n-dimensional space and learns only whether the sender's point lies inside it, with nothing else revealed to either party. It generalises fuzzy matching, a variant of private set intersection (PSI) in which the only question that can be asked is whether two points lie within a fixed distance of each other. Restricting proximity to a fixed radius is limiting in practice. In privacy-preserving proximity testing (PPPT), where two parties want to learn whether they are near each other and nothing more, the question is rarely whether they are within, e.g., 500 meters of each other, and far more often whether one of them is inside this building, on that floor, or in the park across the road. In this talk I will present the two ingredients of GFM. First, an improved fuzzy matching protocol for the infinity norm in low dimensions that encodes intervals as binary prefixes, reducing receiver encoding cost from linear to near-logarithmic in the distance threshold. Second, partitioning algorithms that decompose any bounded region into axis-aligned hyper-rectangles plus leftover points, each handled by an instance of the first protocol and aggregated into one bit. I will close with concrete PPPT applications and an experimental evaluation, including region-based settings that no prior construction supports.

Joint work: Ioannis Katis, Katerina Mitrokotsa, Florias Papadopoulos.

Suggested readings

• Privacy-preserving Proximity Testing from Geometric Fuzzy Matching (ia.cr/2026/1155)
• Fuzzy Private Set Intersection with Large Hyperballs (ia.cr/2024/330)
• Distance-Aware Private Set Intersection (arxiv:2112.14737)