Spatial PSI for Proximity Queries

Exact-match private set intersection answers a binary question — do two parties hold an identical location token — but real spatial joins almost never turn on exact equality. Two delivery fleets, two mobility providers, or a health authority and a venue operator rarely share a coordinate to the metre; they want to know whether any point in set A lies within a distance d of any point in set B, and to learn only that one fact. This page extends the DH/OPRF construction from private set intersection for spatial joins to proximity, and sits inside the broader Secure Multi-Party Computation in Spatial Analytics architecture. The trick is deliberately narrow: rather than re-derive the cryptographic PSI, we change only the encoding that feeds it — expanding every point into the geohash cell that contains it plus the ring of eight neighbouring cells, at a precision whose cell edge approximates d, so a proximity match collapses into an ordinary exact-match on tokens. Geometry is assumed already normalised to canonical WGS84 by the upstream coordinate masking protocols.

The security of the join is entirely inherited from the parent’s oblivious-PRF primitive — the neighbour expansion happens locally, on plaintext geohashes, and each resulting token is blinded through the OPRF exactly as an exact-match token would be. The party running the intersection never sees a raw cell string. What changes is only how a point becomes a set of tokens, and that encoding is the whole subject here.

Parameter Configuration and Calibration

The proximity encoder has one dominant knob — the geohash precision p — and it is chosen from the target distance d, not from a convenient default. A geohash cell at precision p has a fixed edge length L (in degrees, converted to metres at the working latitude). The calibration rule is simple and safety-critical:

L≥d  ⟹  any point within d of A lands in A’s 3×3 neighbourhoodL \ge d \implies \text{any point within } d \text{ of } A \text{ lands in } A\text{'s } 3\times3 \text{ neighbourhood}

If the cell edge is at least the proximity threshold, then a point within d of a base point is at most one cell away in every direction, so it must fall inside the base point’s eight-neighbour ring — guaranteeing zero false negatives. Choosing L as close to d as possible from above keeps the ring tight and minimises false positives, because the neighbourhood’s true reach (corner-to-opposite-corner) is roughly 2L. Cells only come in discrete sizes, so pick the finest precision whose edge still satisfies L \ge d.

Target d Geohash precision p Cell edge at equator Typical use
~5 km 5 4.9 km × 4.9 km regional catchment overlap
~1.2 km 6 1.2 km × 0.61 km neighbourhood-scale co-location
~150 m 7 153 m × 153 m street-block proximity
~40 m 8 38 m × 19 m building-scale contact
~5 m 9 4.8 m × 4.8 m curb / lane precision

Three further parameters shape the privacy/utility balance:

  • Ring cardinality (8 vs 4 neighbours). Use the full Moore neighbourhood — the eight king-move cells — not the four edge-adjacent (von Neumann) cells. A pair straddling a cell corner within d is only reachable through a diagonal neighbour; dropping the corners reintroduces false negatives exactly at cell vertices.
  • One-sided vs two-sided expansion. The safety rule needs only one party to expand: keep set A as exact single-cell tokens and expand set B to its neighbourhoods (or vice-versa). Expanding both sides doubles the effective match reach to roughly 2L on each side and inflates both false positives and the token count. Expand one side when you can control which party is the “probe”; expand both only when the protocol must be symmetric.
  • Padding budget. Each expanded point emits up to nine tokens, so an un-padded token list leaks a ~9× upper bound on set size. Pad every party’s token multiset to a fixed budget with random decoy geohashes before the OPRF so the observable cardinality is constant. Calibrate the precision and d to the risk tier from the spatial sensitivity scoring models; where d is fixed by regulation — the CCPA precise-geolocation radius of ~564 m, for instance — precision 6 (edge ~610 m ≥ d) is the natural floor, as covered under CCPA mobility data obligations.
Proximity encoding — a point's geohash cell plus its 3×3 neighbour ring turns a within-d match into a shared token On the left, a three-by-three grid of geohash cells. The centre cell holds point A and is labelled c; the eight surrounding cells are labelled n-one through n-eight and form the Moore neighbourhood. A dashed circle of radius d is centred on A. Point B lies in the east neighbour cell but falls inside the dashed circle, so B is within distance d of A. Because A's proximity encoder emits the centre cell plus all eight neighbours, and B's containing cell is the east neighbour, the two encoded token sets share that cell token. The right panel states the encoding: proximity_encode(A) yields the nine tokens c and n-one to n-eight; B's geohash equals the east neighbour token; that token lies in A's set, so the PSI reports proximity without either party revealing its points. A closing note records that when the cell edge L is at least d, any point within d of A necessarily lands inside the ring, so there are no false negatives. Proximity encoding — geohash cell + 8 neighbours makes a within-d match an exact-token match n₁ n₂ n₃ (E) n₄ n₅ n₆ n₇ n₈ c d A B 3×3 geohash neighbourhood (Moore ring) at precision where edge L ≈ d proximity_encode(A) = { c, n₁, n₂, n₃, n₄, n₅, n₆, n₇, n₈ } 9 geohash tokens — the cell plus its ring geohash(B) = n₃ (east neighbour of c) B is within d, so its cell is in A's ring n₃ ∈ proximity_encode(A) ⇒ shared token PSI reports proximity — neither point set revealed cell edge L ≥ d ⇒ every point within d of A lands in the ring ⇒ no false negative; false positives up to ≈ 2L

Reference Implementation

The module below is self-contained standard library — a small base-32 geohash encoder, the proximity_encode expander, and proximity_psi_match. It computes the eight neighbours by re-encoding the point offset by one cell span in each direction, which sidesteps the notoriously long geohash adjacency-lookup tables and naturally handles antimeridian wrap. In production the returned tokens are the input to the OPRF, never released directly; here they are intersected as plaintext so the proximity logic is unit-testable in isolation.

python
from __future__ import annotations

from typing import List, Set, Tuple

_BASE32: str = "0123456789bcdefghjkmnpqrstuvwxyz"


def _geohash(lat: float, lon: float, precision: int) -> str:
    """Standard base-32 geohash of a WGS84 point (no external deps)."""
    lat_lo, lat_hi = -90.0, 90.0
    lon_lo, lon_hi = -180.0, 180.0
    bits: Tuple[int, ...] = (16, 8, 4, 2, 1)
    out: List[str] = []
    bit = 0
    ch = 0
    even = True  # even bit positions refine longitude, odd positions latitude
    while len(out) < precision:
        if even:
            mid = (lon_lo + lon_hi) / 2.0
            if lon >= mid:
                ch |= bits[bit]; lon_lo = mid
            else:
                lon_hi = mid
        else:
            mid = (lat_lo + lat_hi) / 2.0
            if lat >= mid:
                ch |= bits[bit]; lat_lo = mid
            else:
                lat_hi = mid
        even = not even
        if bit < 4:
            bit += 1
        else:
            out.append(_BASE32[ch]); bit = 0; ch = 0
    return "".join(out)


def _cell_span_deg(precision: int) -> Tuple[float, float]:
    """(lat_span, lon_span) in degrees for one geohash cell at this precision."""
    lon_bits = (5 * precision + 1) // 2   # even positions refine longitude
    lat_bits = (5 * precision) // 2
    return 180.0 / (2 ** lat_bits), 360.0 / (2 ** lon_bits)


def proximity_encode(lat: float, lon: float, precision: int) -> Set[str]:
    """Expand one point to its geohash cell plus the 8 neighbouring cells.

    Returns the 3x3 Moore neighbourhood of geohash tokens. When the cell edge
    L is chosen so that L >= d, two points within distance d are guaranteed to
    share at least one token, turning a *proximity* test into an *exact-match*
    token test that the DH/OPRF PSI primitive can run unchanged. All eight
    diagonal neighbours are included (not just the four edge-adjacent cells)
    so a pair straddling a cell *corner* within d is never missed.

    Privacy note: this expansion runs locally on plaintext geohashes; each
    emitted token is fed through the OPRF exactly as an exact-match token
    would be, so the intersecting party never sees a raw cell. The only new
    exposure is a ~9x inflation of token count, which leaks an *upper bound*
    on set size unless the token list is padded to a fixed budget.
    """
    if precision < 1:
        raise ValueError("precision must be >= 1")
    lat_span, lon_span = _cell_span_deg(precision)
    tokens: Set[str] = set()
    for dlat in (-1, 0, 1):
        for dlon in (-1, 0, 1):
            nlat = max(-90.0, min(90.0, lat + dlat * lat_span))
            # wrap longitude across the antimeridian so ±180 stays continuous
            nlon = ((lon + dlon * lon_span + 180.0) % 360.0) - 180.0
            tokens.add(_geohash(nlat, nlon, precision))
    return tokens


def proximity_psi_match(encoded_a: Set[str], encoded_b: Set[str]) -> Set[str]:
    """Intersect two parties' encoded token sets.

    In production each argument is the OPRF image of the *union* of that
    party's per-point neighbourhoods; here we intersect the geohash tokens
    directly so the proximity logic is testable without the crypto layer. A
    non-empty result means at least one A-point lies within the neighbour
    reach of at least one B-point — the existential proximity join. It does
    not reveal *which* pair, only that such a pair exists.
    """
    return encoded_a & encoded_b

Validation Checkpoint

A miscalibrated precision fails silently: too fine and a genuine within-d pair falls outside the ring (a missed match); too coarse and everything collides. The harness below pins the three invariants the encoding must satisfy — near points share a token, far points do not, and a pair straddling a cell boundary still matches through the ring — plus the set-level existential join. Run it in CI, not by eye.

python
import math


def _haversine_m(lat1: float, lon1: float, lat2: float, lon2: float) -> float:
    """Great-circle distance in metres between two WGS84 points."""
    r = 6_371_000.0
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dp, dl = math.radians(lat2 - lat1), math.radians(lon2 - lon1)
    a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * r * math.asin(math.sqrt(a))


def _validate() -> None:
    PREC = 7  # ~153 m cell edge, targeting d ~ 150 m (L >= d holds)

    # 1. Two points within d share at least one token.
    a = (40.748817, -73.985428)          # Empire State Building
    near = (40.749300, -73.985100)       # ~60 m away
    assert _haversine_m(*a, *near) < 150
    assert proximity_encode(*a, PREC) & proximity_encode(*near, PREC)

    # 2. Two far-apart points share no token.
    far = (40.782000, -73.965300)        # ~4 km away, Central Park
    assert _haversine_m(*a, *far) > 1000
    assert not (proximity_encode(*a, PREC) & proximity_encode(*far, PREC))

    # 3. Boundary case: a pair metres apart straddling a cell edge still
    #    matches, because each point's ring bridges the boundary.
    _, lon_span = _cell_span_deg(PREC)
    base = (0.0, lon_span * 0.9)          # inside cell [0, lon_span)
    across = (0.0, lon_span * 1.1)        # inside next cell [lon_span, 2·lon_span)
    assert _geohash(*base, PREC) != _geohash(*across, PREC)   # different cells
    assert _haversine_m(*base, *across) < 150
    assert proximity_encode(*base, PREC) & proximity_encode(*across, PREC)

    # 4. Existential proximity join over point *sets* (aggregate union).
    set_a = set().union(*(proximity_encode(la, lo, PREC) for la, lo in (a, far)))
    set_b = proximity_encode(*near, PREC)
    assert proximity_psi_match(set_a, set_b)          # near is within a's ring

    print("all spatial-PSI proximity invariants hold")


if __name__ == "__main__":
    _validate()

Incident Response and Edge Cases

Proximity PSI degrades quietly — a wrong precision does not raise, it just returns the wrong answer. The failures that surface on real deployments:

  • Silent false negatives from L < d. Someone tightens precision for a smaller cell without re-checking the rule, and a within-d pair now sits two cells apart, outside the ring. The join reports “no proximity” for points that genuinely touch. Detection: a property test that samples random pairs at exactly d, asserts a shared token for 100% of them, and fails the build otherwise. Remediation: pick the finest precision with L \ge d and treat that inequality as an invariant, not a suggestion.
  • Antimeridian and pole wrap. Neighbours computed by lat/lon offset near ±180° longitude or ±90° latitude either wrap or clamp, and a naive re-encode can silently drop a neighbour. Detection: run the round-trip test with base points at 179.999° E and 89.999° N. Remediation: the reference encoder wraps longitude modulo 360 and clamps latitude; keep both, and accept that the geohash grid is genuinely discontinuous at the antimeridian — a pair spanning it needs the wrapped neighbour to be present on both sides.
  • High-latitude cell anisotropy. Longitude cells narrow by cos⁡φ\cos\varphi with latitude, so at 60° N a precision-7 cell is ~153 m tall but only ~76 m wide. An east–west d threshold set from the equatorial edge then under-covers, producing false negatives along the longitude axis. Detection: compute the real metric edge at the working latitude, not the equatorial figure. Remediation: choose precision from the narrower (longitude) dimension at that latitude, or widen the probe to a 5×5 ring when a single dataset spans a wide latitude band.
  • Set-size leakage from unpadded expansion. Each point emits up to nine tokens, so the observable token count reveals a tight upper bound on how many points a party holds — a metadata channel the exact-match PSI did not have. Remediation: pad every party’s token multiset to a fixed budget with random decoy geohashes drawn from the working region before the OPRF, so cardinality is constant regardless of set size, and expand only one side to halve the inflation.

Frequently Asked Questions

Why expand to all eight neighbours instead of the four edge-adjacent cells?

The safety guarantee — that any point within distance d lands inside the ring — only holds for the full Moore neighbourhood. Two points can sit within d of each other while straddling a cell corner diagonally; the only cell that bridges them is a diagonal neighbour. Dropping the four corners (using the von Neumann neighbourhood) reintroduces false negatives precisely at cell vertices, which are the hardest cases to notice in testing because they are a measure-zero slice of the grid.

How do I pick the geohash precision for a target distance d?

Convert each precision's cell edge to metres at your working latitude and choose the finest precision whose edge L still satisfies L greater than or equal to d. That inequality guarantees zero false negatives; picking L as close to d as possible from above keeps the ring tight and limits false positives, whose reach is roughly twice the cell edge. Because cells come in discrete sizes, you usually cannot hit d exactly — round to the safe side and accept a modest false-positive margin rather than risk missed matches.

Doesn't the neighbour expansion leak how many points each party holds?

Yes, if left unpadded. Each point expands to up to nine tokens, so the observable token count is a tight upper bound on set size — a metadata channel the exact-match construction does not have. Pad every party's token list to a fixed budget with random decoy geohashes before the oblivious PRF so the cardinality the other party sees is constant, and expand only one side of the join where the protocol allows it to halve the inflation in the first place.

How is this different from the exact-match PSI in the parent guide?

The cryptography is identical — the same DH/OPRF blinding, the same intersection. Only the encoding changes. Exact-match PSI turns each point into one token and reports equality; proximity PSI turns each point into its cell plus eight neighbours so that geometric nearness becomes token equality. Nothing else in the protocol is aware that a proximity test is happening, which is exactly why the security properties carry over unchanged and the only new consideration is the token-count inflation.

Up: Private Set Intersection for Spatial Joins · Secure Multi-Party Computation in Spatial Analytics