Practical Homomorphic Encryption for Spatial Queries

Running proximity searches, bounding-box filters, and polygon-containment checks directly over ciphertext is the operational payoff of homomorphic encryption basics: the cluster establishes the CKKS scheme, coordinate encoding, and noise-budget accounting, and this page turns those primitives into a query engine you can debug, validate, and audit. It sits inside the broader secure multi-party computation in spatial analytics architecture, where homomorphic evaluation is the single-party compute path that keeps raw coordinates inaccessible while a metropolitan-scale workload still answers “is this point within r metres of that one?” The hard part in production is not the cryptography — it is keeping floating-point coordinate precision, multiplicative noise consumption, and regulatory drift thresholds aligned across every query. This guide covers the exact knobs, a focused reference engine, a runnable validation harness, and the incident-response paths for the failures that actually surface in the field.

Parameter Configuration and Calibration

Spatial queries impose constraints that generic homomorphic workloads do not: real-valued WGS84 coordinates, non-linear distance metrics, and a precision floor set by regulation rather than by taste. Each knob below has a concrete privacy or correctness consequence, so tune it deliberately instead of copying defaults between deployments.

The squared Euclidean distance the engine evaluates homomorphically is

d2=(λq−λt)2+(ϕq−ϕt)2d^2 = (\lambda_q - \lambda_t)^2 + (\phi_q - \phi_t)^2

which has multiplicative depth 1 per axis when latitude and longitude are packed into separate ciphertexts, so the modulus chain must carry at least one rescale level with margin.

  • poly_modulus_degree — ring dimension (≥ 16384 for metropolitan extents). Sets both the SIMD slot count and the security level. 8192 is fine for a single point pair; metropolitan bounding-box batches need 16384 so a full coordinate vector packs into one ciphertext without rotation gymnastics. Larger degrees raise security and depth headroom at the cost of ciphertext size — the ≤ 4KB/query budget below is what bounds it.
  • scaling_factor (Δ) — fixed-point precision (2^40). Aligns plaintext precision with the ciphertext representation. At 2^40 the quantization error on a latitude/longitude pair stays well under the ±0.5 m tolerance that healthcare and financial releases require; drop to 2^30 and sub-metre joins start failing shadow validation. Δ must match the library’s per-level rescale prime or you get systematic coordinate drift.
  • noise_threshold_bits — pre-decrypt budget floor (15). Distance and aggregation consume the noise budget multiplicatively. A pre-query estimator that rejects any ciphertext below 15 remaining bits prevents the silent decryption failures that break audit trails. Treat this as a hard gate, not a warning.
  • tolerance_meters — utility/drift ceiling (0.5). The maximum decryption drift a release may exhibit while still counting as faithful. This is a compliance parameter: HIPAA Safe Harbor practice for location data and GLBA data-minimization both depend on the assertion that obfuscation never degrades the answer past a stated bound. Above ±1.2 m the result is treated as a drift incident, not a rounding artefact.

Before encryption, resolve spatial partitioning — H3, S2, or GeoHash cells — in plaintext, because CKKS ciphertexts cannot traverse a B-tree or quadtree. Encode grid membership as one-hot boolean vectors and evaluate containment with a homomorphic dot product. When the masking layer is in play, align the masking vector to the same plaintext space described in coordinate masking protocols so modulus switching does not introduce drift during spatial joins, and split decryption authority across regional boundaries with secret sharing for coordinates so no single node ever reconstructs raw plaintext. Map every parameter to a binding clause through the compliance framework mapping so an auditor can trace scaling_factor and tolerance_meters back to the regulation that fixed them.

Compliance requirement HE control Validation metric
HIPAA Safe Harbor (geo < 20k pop) CKKS scaling + coordinate masking Decryption drift ≤ ±0.5 m
GLBA data minimization Pre-encryption grid hashing Ciphertext size ≤ 4 KB/query
PCI-DSS tokenization Noise-budget thresholding Budget ≥ 15 bits pre-decrypt
Encrypted spatial query: noise gate, homomorphic distance, decrypt, drift triage A left-to-right flowchart. An "Encrypted spatial query" box flows into a hexagonal gate "Noise budget at least 15 bits?". The pass edge continues to "Homomorphic d² — rescale after each multiply", then "Authorized decrypt (scalar only)", then "Drift check". The drift check fans out to three outcomes: a teal box for drift at or below 0.5 metres which is released, a violet box for drift between 0.5 and 1.2 metres which is flagged for audit, and a coral box for drift above 1.2 metres which is quarantined and re-masked. The gate's fail edge and the quarantine outcome both route into a "Re-encrypt — higher poly_modulus_degree, realign masking vector" box, which loops back up into the encrypted query at the start of the pipeline. Encrypted spatial query — gate, evaluate, decrypt, triage drift Encrypted spatial query Noise budget ≥ 15 bits? Homomorphic d² rescale after each multiply Authorized decrypt scalar only Drift check ≤ 0.5 m release 0.5 – 1.2 m flag + audit > 1.2 m quarantine + re-mask pass fail < 15 bits Re-encrypt ↑ poly_modulus_degree · realign masking vector quarantined batch rebuilt off-thread re-enter

Reference Implementation

The engine below is backend-agnostic: subclass it for TenSEAL, SEAL-Python, or OpenFHE and override the cryptographic hooks. The base class enforces the noise gate, explicit rescaling discipline, and the drift tolerance before any result leaves the boundary. Inline comments mark the points where a choice has a privacy consequence.

python
from __future__ import annotations

from typing import Protocol, Sequence


class CKKSBackend(Protocol):
    """Minimal cryptographic surface the engine depends on."""

    def encrypt(self, values: Sequence[float]) -> object: ...
    def sub(self, a: object, b: object) -> object: ...
    def mul(self, a: object, b: object) -> object: ...
    def add(self, a: object, b: object) -> object: ...
    def rescale_to_next(self, ct: object) -> object: ...
    def noise_budget_bits(self, ct: object) -> float: ...
    def decrypt(self, ct: object) -> float: ...


class SpatialHEQueryEngine:
    """CKKS spatial proximity evaluator with explicit noise-budget tracking
    and compliance-aware drift validation.

    The engine answers an encrypted "within r metres" predicate without ever
    exposing plaintext coordinates. Every tunable here has a privacy meaning:
    the noise gate prevents silent decryption failure, and the metre tolerance
    is the regulatory faithfulness bound, not a cosmetic rounding choice.
    """

    def __init__(
        self,
        backend: CKKSBackend,
        scaling_factor: int = 2 ** 40,
        noise_threshold_bits: int = 15,
        tolerance_meters: float = 0.5,
    ) -> None:
        self.backend = backend
        self.scaling_factor = scaling_factor
        self.noise_threshold_bits = noise_threshold_bits
        self.tolerance_meters = tolerance_meters

    def encrypt_point(self, lat: float, lon: float) -> tuple[object, object]:
        """Encrypt a WGS84 point into two axis-aligned ciphertexts.

        Splitting lat/lon keeps each squared difference at multiplicative
        depth 1 — no rotation needed and the modulus chain lasts longer.
        """
        return self.backend.encrypt([lat]), self.backend.encrypt([lon])

    def evaluate_proximity(
        self,
        query: tuple[object, object],
        target: tuple[object, object],
        radius_m: float,
    ) -> bool:
        """Return True iff target is within radius_m of query.

        Raises if the noise budget cannot guarantee a faithful decrypt — a
        degraded ciphertext must fail loudly, never silently leak a wrong
        membership answer into a released result.
        """
        if self.backend.noise_budget_bits(query[0]) < self.noise_threshold_bits:
            raise RuntimeError("Noise budget exhausted; re-encrypt required.")

        # (q_lat - t_lat)^2 + (q_lon - t_lon)^2, rescaled after every multiply
        # so the lattice scale stays aligned with scaling_factor.
        d_lat = self.backend.sub(query[0], target[0])
        d_lon = self.backend.sub(query[1], target[1])
        sq_lat = self.backend.rescale_to_next(self.backend.mul(d_lat, d_lat))
        sq_lon = self.backend.rescale_to_next(self.backend.mul(d_lon, d_lon))
        dist_sq = self.backend.add(sq_lat, sq_lon)

        # Decrypt only the scalar distance, never the coordinates themselves.
        decrypted = self.backend.decrypt(dist_sq)
        # Compare in metres via an equirectangular metres-per-degree factor.
        m_per_deg = 111_320.0
        return decrypted * (m_per_deg ** 2) <= radius_m ** 2

    def assert_drift_within_tolerance(
        self, encrypted_distance_m: float, plaintext_distance_m: float
    ) -> None:
        """Deterministic shadow check against a synthetic plaintext baseline.

        Exceeding tolerance is a compliance event: it means the cryptographic
        pipeline, not the data, moved the answer beyond the stated bound.
        """
        drift = abs(encrypted_distance_m - plaintext_distance_m)
        if drift > self.tolerance_meters:
            raise AssertionError(
                f"Drift {drift:.3f} m exceeds ±{self.tolerance_meters} m; "
                "trace to scaling_factor / rescale misalignment."
            )

Validation Checkpoint

Encrypted query logic must never reach production untested — a misaligned rescale is a silent correctness fault that no downstream system will catch. The harness below uses a deterministic plaintext test double so the invariants (noise gating, rescale discipline, drift tolerance, membership correctness) run in CI without a crypto backend installed.

python
from dataclasses import dataclass


@dataclass
class _PlainCT:
    value: float
    budget: float = 60.0


class _PlaintextBackend:
    """Exact, deterministic stand-in for a CKKS backend — for tests only."""

    def encrypt(self, values):
        return _PlainCT(float(values[0]))

    def sub(self, a, b):
        return _PlainCT(a.value - b.value, min(a.budget, b.budget))

    def mul(self, a, b):
        return _PlainCT(a.value * b.value, min(a.budget, b.budget) - 10)

    def add(self, a, b):
        return _PlainCT(a.value + b.value, min(a.budget, b.budget))

    def rescale_to_next(self, ct):
        return _PlainCT(ct.value, ct.budget - 5)

    def noise_budget_bits(self, ct):
        return ct.budget

    def decrypt(self, ct):
        return ct.value


def _test_spatial_he_engine() -> None:
    engine = SpatialHEQueryEngine(_PlaintextBackend())

    q = engine.encrypt_point(40.7128, -74.0060)        # NYC
    near = engine.encrypt_point(40.7129, -74.0061)      # ~14 m away
    far = engine.encrypt_point(40.7300, -74.0060)       # ~1.9 km away

    # 1. Membership predicate is correct in both directions.
    assert engine.evaluate_proximity(q, near, radius_m=50.0) is True
    assert engine.evaluate_proximity(q, far, radius_m=50.0) is False

    # 2. The noise gate fails loudly below threshold, never silently decrypts.
    starved = (_PlainCT(0.0, budget=5.0), _PlainCT(0.0, budget=5.0))
    try:
        engine.evaluate_proximity(starved, near, radius_m=50.0)
        raise AssertionError("starved ciphertext was not rejected")
    except RuntimeError:
        pass

    # 3. Drift inside tolerance passes; drift past it is a compliance failure.
    engine.assert_drift_within_tolerance(123.40, 123.45)   # 0.05 m, ok
    try:
        engine.assert_drift_within_tolerance(123.0, 125.0)  # 2.0 m
        raise AssertionError("excess drift was accepted")
    except AssertionError as exc:
        assert "exceeds" in str(exc)

    print("All spatial HE query invariants hold.")


if __name__ == "__main__":
    _test_spatial_he_engine()

Incident Response and Edge Cases

A passing unit test does not guarantee a safe production query. The failures below are the ones that surface under live load, each with a concrete remediation path.

  • Precision drift past the metre ceiling. When audit sampling shows decryption drift above ±1.2 m, the cause is almost always a scaling_factor misaligned with the library’s default rescale prime, or a missing rescale_to_next after a spatial multiplication. Remediation: quarantine the affected ciphertext batch, force explicit rescales after every multiply, regenerate the coordinate masking vector, and re-encrypt at a higher poly_modulus_degree. Log the full noise-consumption trajectory to prove the drift was cryptographic, not data corruption or unauthorized plaintext exposure.
  • Noise budget exhausted mid-query. Deep aggregations (centroids over large cohorts, chained distance filters) can deplete the budget below 15 bits before the result is ready, yielding a garbage decrypt. Remediation: pre-compute operator depth from the modulus chain, gate at the threshold before dispatch, and either bootstrap or fall back to a deterministic plaintext-with-noise predicate rather than releasing an unfaithful answer.
  • Post-encryption grid lookup fails. A query that tries to traverse an H3 or quadtree index after encryption silently returns no matches, because ciphertexts cannot participate in tree traversal. Remediation: resolve all partition IDs in plaintext before encryption, encode cell membership as one-hot vectors, and evaluate containment via homomorphic dot product.
  • Masking divergence across query and dataset. Applying different masking vectors to the query point and the stored coordinates injects systematic bias that compounds through spatial joins and shows up as coordinate drift. Remediation: bind a single masking vector to both sides before encryption and verify alignment in the shadow baseline. For asynchronous dispatch that retries failed ciphertexts, route re-encryption through async routing for MPC so a quarantined batch is rebuilt off the main transaction thread, and reconcile the model choice against the privacy model comparison when HE alone proves too heavy for the latency budget.

Frequently Asked Questions

Why CKKS instead of BFV or BGV for spatial queries?

Spatial coordinates are real-valued and carry inherent measurement uncertainty from GPS and survey instruments. CKKS performs approximate arithmetic on real numbers natively, so its controlled precision loss aligns with the data’s own error bars. BFV and BGV are exact integer schemes — usable only after quantizing coordinates to integers, which adds an encoding layer and wastes the very tolerance that makes CKKS efficient here.

How do I keep coordinate precision within a regulatory tolerance?

Set scaling_factor to 2^40 so fixed-point quantization error stays well under the ±0.5 m faithfulness bound, force an explicit rescale_to_next after every spatial multiplication so the ciphertext scale never drifts from the plaintext scale, and run a deterministic shadow baseline that fails the build when drift exceeds tolerance. Treat the metre tolerance as a compliance parameter traced through your compliance mapping, not a cosmetic rounding choice.

Can homomorphic ciphertexts use a spatial index like H3 or a quadtree?

No. Encrypted values cannot be compared for ordering or traversed in a tree, so any index lookup must happen in plaintext before encryption. Resolve the H3, S2, or GeoHash cell first, encode membership as a one-hot boolean vector, and evaluate containment with a homomorphic dot product against the encrypted vector.

What should trigger a re-encryption rather than a retry?

Re-encrypt whenever the pre-query noise estimate falls below 15 bits or audit sampling shows drift above the ±1.2 m incident threshold. A plain retry reuses the same degraded ciphertext and reproduces the fault; re-encryption at a higher poly_modulus_degree with a freshly aligned masking vector restores both budget headroom and precision.

Up: Homomorphic encryption basics · Secure Multi-Party Computation in Spatial Analytics