Find Nearby Friends

Alice picks a region, Bob has a location, and Alice should learn only whether Bob is inside. Here is how our paper (ACM) cuts any region into pieces it can test privately.

Alice’s region

or draw

Alice’s region
rectangle
residual point
the piece holding Bob

Resolution r = 1

Best for

How it works

Partitioner (Section 3). Take the bounding box of the region, cut it into cells of r × r lattice points, keep the cells that lie wholly inside, and fuse neighbours that share a whole side until none do. The N_r rectangles and the L_r points of the region they miss (the residual points) together hold every lattice point of the region exactly once.
Cost (Section 4). Each rectangle becomes its own small ℓ_∞ test, which costs Bob work for every one of them; a residual point costs Alice one entry. Counting the protocol’s steps: Cost(r) = Σ_k,i 2⌊log₂(2δ_k,i+1)⌋ + L_r + (d+1)·N_r·J_S, J_S = Π_i(⌊log₂(2δ_max,i+1)⌋+1) that is, Alice’s padded strings per rectangle side, her residual points, and the N_r·J_S answers Bob computes (d = 2 lookups each) and Alice checks: the terms of the paper’s complexity theorem. r* is the r with the smallest cost. The paper gives no explicit formula for the cost; “Best for” lets you minimise both sides’ work (this one), one side’s, or the bytes sent, each read off the same theorem and protocol figure.
DASA (Section 2). Along each axis a rectangle is an interval of 7-bit numbers. Alice writes it as the few prefixes whose subtrees fit wholly inside (the rest of the bits are wildcards *). Bob writes his coordinate with 0, 1, 2, … of its last bits as wildcards, as many as the widest rectangle needs. He is inside a rectangle exactly when one of his strings equals one of Alice’s, in x and in y. A residual point is matched as a whole.
Who learns what. Alice learns one bit: inside or not (the answers come shuffled, so not even which rectangle). Bob learns the rectangle sizes he needs for his strings, not where they are, and no answer.
The map. St. Gallen’s old town from OpenStreetMap, about 520 m across, as a lattice of 128 × 128 points, one every 4 m. The image is part of this page: your browser fetches nothing from OpenStreetMap.

This page shows the geometry in the clear. In the protocol Alice’s strings travel inside an oblivious key-value store and Bob answers with re-randomised Diffie-Hellman pairs, so the matching above happens under encryption, in two messages, with no server in between. From I. Katis, K. Mitrokotsa, F. Papadopoulos, Privacy-preserving Proximity Testing from Geometric Fuzzy Matching, ACM ASIA CCS 2026 (ACM Digital Library). Map data © OpenStreetMap contributors.