Coordinate Masking Protocols

Consider three hospital networks that need to compute how many shared patients live within 500 metres of each other’s outpatient clinics — a proximity join that would expose precise home coordinates if either side handed over raw points. Coordinate masking protocols are the control layer that makes this join possible: they transform raw latitude–longitude pairs into discretised, secret-shared, and homomorphically maskable representations before any geometry leaves a participant’s trust boundary. Operating inside the broader Secure Multi-Party Computation in Spatial Analytics architecture, masking is the deterministic front end that every downstream cryptographic stage depends on — get the normalisation or padding wrong here and the secret sharing and homomorphic encryption layers inherit the leak.

This guide details a production-ready masking pipeline for Python data-engineering stacks: deterministic coordinate normalisation, constant-time padding, cryptographic synchronisation, additive threshold distribution, and homomorphic-ready envelope construction. Every parameter is tied to a concrete privacy guarantee — grid resolution to spatial uniqueness, padding width to timing leakage, and the privacy budget to a measurable $\varepsilon$.

Prerequisites

The masking pipeline depends only on the Python standard library for its cryptographic core, with NumPy for vectorised field arithmetic. Avoid third-party “anonymisation” packages that silently use the non-cryptographic random module for jitter.

• Runtime: Python 3.11+ (required for the three-argument pow(x, -1, p) modular inverse used during reconstruction tests).
• Numerics: numpy>=1.24 for the Nx2 coordinate arrays, and the standard-library decimal module for drift-free grid quantisation. Floating-point quantisation accumulates error across large batches and breaks downstream field arithmetic.
• Randomness: the standard-library secrets module (CSPRNG). Never seed share generation from random, numpy.random, or a wall-clock value.
• Integrity: hashlib for SHA3-256 envelope hashing; hmac if you bind envelopes to a session key.
• Optional homomorphic backend: tenseal (CKKS) or Pyfhel when the masked envelopes feed a real homomorphic circuit rather than a downstream secret-sharing engine. The encoding contract here matches the CKKS scaling factor discussed in Homomorphic Encryption Basics.
• Privacy budget accounting: a Rényi Differential Privacy (RDP) accountant (for example Opacus’s RDPAccountant) so that the jitter buffer and grid resolution can be expressed as a spent $(\varepsilon, \delta)$ budget before data crosses a trust boundary.

Assumed reference frame: all inputs are projected to EPSG:4326 decimal degrees before entry. A coordinate reference system (CRS) mismatch at this stage silently corrupts the prime-field encoding — see Failure Modes below.

Step-by-Step Masking Procedure

The pipeline is a single CoordinateMaskingPipeline class whose methods correspond to the four masking stages. Each stage is shown below as a focused excerpt; the complete, runnable class follows in the Reference Implementation section.

Step 1 — Coordinate preprocessing and spatial normalisation

Raw geospatial inputs require deterministic standardisation before they touch any cryptographic primitive. Coordinates are quantised to a fixed grid resolution and aligned to grid centres, collapsing micro-locations into statistically equivalent bins. This is what reduces spatial uniqueness: at grid resolution $g$ degrees, every original point is mapped to within $\pm g/2$ of a shared bin centre, so high-precision linkage against an external dataset can no longer pin an individual. Calibrate $g$ against the target spatial sensitivity score for the dataset rather than picking a round number.

jitter_lat = (Decimal(str(lat)) / grid_resolution).quantize(Decimal("1")) * grid_resolution

Batches are then padded to a constant multiple of min_batch so that the wire size of a masked round never reveals how many real points a party contributed — a count that is itself sensitive in low-density regions.

Step 2 — Cryptographic sync initialisation

Before shares are generated, participating nodes complete a handshake that negotiates ephemeral session material and a per-round nonce. The nonce binds every envelope to a single round and prevents replay of last round’s shares. In a distributed deployment this handshake runs over the message broker described in Async Routing for MPC; strict timeouts and state rollback ensure a partial handshake never leaks partial coordinate state.

def initialize_sync(self) -> bytes:
    self._nonce = secrets.token_bytes(32)  # bind all envelopes to this round
    return self._nonce

Step 3 — Threshold secret-sharing application

Each normalised coordinate is scaled into a large prime field and split into additive shares such that no strict subset of nodes can reconstruct the point. The implementation below uses additive $(n, n)$ sharing — every share is required — which gives an information-theoretic guarantee against any party short of the full set. When an operational $(t, n)$ threshold (tolerating node dropout) is needed instead, swap in the Shamir polynomial construction from Secret Sharing for Coordinates; the rest of the pipeline is unchanged.

field_array = self._scale_to_field(coord_array)   # rint(coord * 1e7) mod p
# split each secret S into s_0..s_{n-1} with  S ≡ Σ s_i (mod p)

Step 4 — Homomorphic-ready masking and envelope construction

Finally, each node’s share array is serialised into an integrity-checked envelope. The envelope payload is the exact byte layout a homomorphic circuit consumes to compute masked spatial relationships — squared Euclidean distance, spatial joins, aggregation — without decrypting individual shares. Keeping the fixed-point scale (COORD_SCALE) consistent with the CKKS scaling factor lets a downstream evaluator reuse the same encoding for encrypted spatial queries without re-quantising.

payload_hash = hashlib.sha3_256(payload + self._nonce).digest()  # round-bound integrity

Reference Implementation

The complete pipeline is type-hinted and validation-aware: it integrates constant-time padding, CSPRNG share generation, and a structured interface for homomorphic evaluation. A runnable harness at the end asserts reconstruction correctness, padding invariants, and field-range bounds.

import secrets
import pickle
import numpy as np
from decimal import Decimal, getcontext
from typing import List, Tuple, Dict, Optional
import hashlib
import time

# Set precision to avoid floating-point leakage in spatial coordinates
getcontext().prec = 12

# Large prime field for fixed-point modular arithmetic over scaled coordinates.
FIELD_PRIME = (1 << 127) - 1  # Mersenne prime — fits in two 64-bit limbs.
COORD_SCALE = 10_000_000      # Preserves ~1.1cm precision for lat/lon.


class CoordinateMaskingPipeline:
    def __init__(self, total_shares: int = 3):
        # Additive (n, n) sharing: every party's share is required to
        # reconstruct. For a true (t, n) threshold scheme use Shamir
        # (see secret-sharing-for-coordinates).
        if total_shares < 2:
            raise ValueError("Need at least 2 parties for secret sharing.")
        self.grid_resolution = Decimal("0.001")
        self.total_shares = total_shares
        self._nonce: Optional[bytes] = None

    def normalize_and_pad(self, coords: List[Tuple[float, float]], min_batch: int = 1024) -> np.ndarray:
        """Discretize coordinates, snap to grid centres, and pad to uniform length."""
        if not coords:
            raise ValueError("Coordinate batch cannot be empty.")

        # Deterministic snap aligned to grid resolution
        normalized = []
        for lat, lon in coords:
            lat_dec = Decimal(str(lat))
            lon_dec = Decimal(str(lon))
            jitter_lat = (lat_dec / self.grid_resolution).quantize(Decimal('1')) * self.grid_resolution
            jitter_lon = (lon_dec / self.grid_resolution).quantize(Decimal('1')) * self.grid_resolution
            normalized.append((float(jitter_lat), float(jitter_lon)))

        # Constant-size padding to prevent length-based timing/volume attacks.
        # Round the batch up to the next multiple of `min_batch`.
        target_len = max(min_batch, ((len(normalized) + min_batch - 1) // min_batch) * min_batch)
        padded = np.zeros((target_len, 2), dtype=np.float64)
        for i, (lat, lon) in enumerate(normalized):
            padded[i] = [lat, lon]
        return padded

    def _scale_to_field(self, coord_array: np.ndarray) -> np.ndarray:
        """Map float coordinates into the prime field as positive residues."""
        scaled = np.rint(coord_array * COORD_SCALE).astype(np.int64)
        return np.mod(scaled.astype(object), FIELD_PRIME)

    def generate_shares(self, coord_array: np.ndarray) -> Dict[int, np.ndarray]:
        """Generate additive (n, n) shares for spatial coordinates over F_p.

        Each row's secret S is split into n shares s_0..s_{n-1} drawn from
        the os CSPRNG such that S ≡ Σ s_i (mod p). All n shares are
        required to reconstruct — there is no information-theoretic leak
        from any strict subset.
        """
        if coord_array.ndim != 2 or coord_array.shape[1] != 2:
            raise ValueError("Coordinate array must be Nx2.")

        field_array = self._scale_to_field(coord_array)
        n_rows = field_array.shape[0]
        shares: Dict[int, np.ndarray] = {
            i: np.zeros_like(field_array) for i in range(self.total_shares)
        }

        for i in range(n_rows):
            acc_lat = 0
            acc_lon = 0
            for j in range(self.total_shares - 1):
                s_lat = secrets.randbelow(FIELD_PRIME)
                s_lon = secrets.randbelow(FIELD_PRIME)
                shares[j][i, 0] = s_lat
                shares[j][i, 1] = s_lon
                acc_lat = (acc_lat + s_lat) % FIELD_PRIME
                acc_lon = (acc_lon + s_lon) % FIELD_PRIME
            shares[self.total_shares - 1][i, 0] = (int(field_array[i, 0]) - acc_lat) % FIELD_PRIME
            shares[self.total_shares - 1][i, 1] = (int(field_array[i, 1]) - acc_lon) % FIELD_PRIME

        return shares

    def initialize_sync(self) -> bytes:
        """Establish cryptographic sync and generate a per-round nonce."""
        self._nonce = secrets.token_bytes(32)
        # In production: integrate TLS 1.3 handshake and certificate validation
        return self._nonce

    def mask_for_homomorphic_eval(self, shares: Dict[int, np.ndarray]) -> Dict[int, bytes]:
        """Serialize shares into cryptographic envelopes for HE circuit evaluation."""
        if self._nonce is None:
            raise RuntimeError("Sync initialization required before masking.")

        masked_envelopes = {}
        for node_id, share_data in shares.items():
            payload = share_data.tobytes()
            payload_hash = hashlib.sha3_256(payload + self._nonce).digest()
            envelope = {
                "share_id": node_id,
                "payload": payload,
                "integrity": payload_hash,
                "timestamp": int(time.time()),
            }
            # Use pickle (or msgpack in production) so binary fields
            # round-trip; str() on a dict containing raw bytes loses data.
            masked_envelopes[node_id] = pickle.dumps(envelope, protocol=4)
        return masked_envelopes


# --- Runnable validation harness -------------------------------------------
def _reconstruct(shares: Dict[int, np.ndarray]) -> np.ndarray:
    """Sum all additive shares mod p to recover the scaled field values."""
    acc = None
    for arr in shares.values():
        acc = arr.copy() if acc is None else (acc + arr)
    return np.mod(acc, FIELD_PRIME)


if __name__ == "__main__":
    pipe = CoordinateMaskingPipeline(total_shares=3)
    raw = [(40.748817, -73.985428), (51.500729, -0.124625)]

    padded = pipe.normalize_and_pad(raw, min_batch=1024)
    # Padding invariant: length is a multiple of min_batch and >= batch size.
    assert padded.shape == (1024, 2)
    assert padded.shape[0] % 1024 == 0

    # Grid invariant: every real point sits within +/- grid_resolution/2 of input.
    g = float(pipe.grid_resolution)
    for (lat, lon), row in zip(raw, padded):
        assert abs(row[0] - lat) <= g / 2 + 1e-9
        assert abs(row[1] - lon) <= g / 2 + 1e-9

    pipe.initialize_sync()
    shares = pipe.generate_shares(padded)

    # Reconstruction invariant: shares sum back to the scaled field encoding.
    expected = pipe._scale_to_field(padded)
    assert np.array_equal(_reconstruct(shares), expected)

    # Subset-leak invariant: any single share is uniform, not the secret.
    assert not np.array_equal(np.mod(shares[0], FIELD_PRIME), expected)

    envelopes = pipe.mask_for_homomorphic_eval(shares)
    assert set(envelopes) == {0, 1, 2}
    print("All masking invariants hold.")

Threat Model Considerations

An adversary against the masking layer is assumed to be honest-but-curious on up to $n-1$ compute nodes, with the ability to observe wire sizes and timing. The capabilities that matter for this stage:

• Linkage and re-identification: correlating masked output against an external high-precision dataset to invert the grid mapping.
• Volume and timing inference: reading batch length or per-batch latency to estimate point density in a region.
• Share collusion: combining fewer than the required shares to reconstruct a coordinate.
• Round replay: re-injecting a previous round’s envelopes to skew an aggregate or force re-evaluation.
• Noise-budget exhaustion: driving a homomorphic evaluation past its noise ceiling to trigger decryption failures that leak structure.

Validation & Compliance Checklist

Each control has a measurable pass/fail criterion; wire them into CI and a compliance dashboard rather than reviewing them by hand.

1. Precision drift — PASS if every discretised coordinate is within $\pm g/2$ of its input across a property-based test of $\ge 10^5$ random points. This is the assertion baked into the harness above; fail the build on any violation.
2. Share reconstruction — PASS if summing all $n$ shares mod $p$ reproduces the scaled encoding for 100% of rows, and any strict subset does not. Run the reconstruction audit nightly and log the success rate.
3. Constant-time behaviour — PASS if masking wall-time variance across batch sizes stays within $\pm 5\%$ of the mean measured with time.perf_counter_ns(). Larger variance signals a data-dependent branch and a timing channel.
4. Privacy-budget accounting — PASS if the composed jitter and grid resolution satisfy the declared $(\varepsilon, \delta)$ before data leaves the trust boundary. For a Laplace mechanism on a query of sensitivity $\Delta f$, the noise scale is $b = \Delta f / \varepsilon$; record the spent budget per release. Tie the figure to the obligations enumerated in the compliance framework mapping — for instance, GDPR Article 25 data-minimisation expressed as a maximum grid-cell resolution.
5. CRS conformance — PASS if every input is verified as EPSG:4326 decimal degrees at ingestion; reject or re-project anything else before quantisation.

Failure Modes & Remediation

Masking rarely fails loudly in production — it fails by silently degrading either privacy or utility. The high-frequency failure modes:

• CRS mismatch. A batch arrives in EPSG:3857 metres (or swapped lat/lon) and _scale_to_field produces residues that are mathematically valid but spatially meaningless. Detection: range-check that latitudes fall in $[-90, 90]$ and longitudes in $[-180, 180]$ before scaling. Recovery: re-project at ingestion and quarantine the offending batch; never let it reach the share stage.
• Privacy-budget exhaustion. Repeated releases over the same population deplete the $(\varepsilon, \delta)$ budget; further masked outputs no longer carry the claimed guarantee. Detection: the RDP accountant crosses the configured ceiling. Recovery: halt releases for that population, widen the grid resolution to spend less per query, or rotate to a fresh cohort.
• Node dropout under additive sharing. With $(n,n)$ sharing, a single offline node makes the round unreconstructable. Detection: a missing envelope at round-completion timeout. Recovery: fail the round atomically (the nonce makes partial state unusable) and re-run, or migrate the deployment to Shamir $(t,n)$ so the round tolerates $n-t$ dropouts.
• Precision collapse. A grid resolution chosen too coarse for utility snaps distinct facilities into one bin, destroying the proximity signal. Detection: downstream join selectivity drops below an expected floor. Recovery: tighten $g$ and re-cost the privacy budget — resolution and budget trade directly against each other.
• Homomorphic noise overflow. A masked envelope feeds a circuit deeper than its modulus chain supports, and decryption returns garbage. Detection: pre-evaluation noise-budget check fails for the planned operator depth. Recovery: raise the polynomial modulus degree or split the computation, as covered under Homomorphic Encryption Basics.

Related Guides

This page is part of the Secure Multi-Party Computation in Spatial Analytics reference — start there for the end-to-end architecture and how masking, sharing, routing, and encryption fit together.

• Secret Sharing for Coordinates — the Shamir $(t,n)$ construction to swap in when you need dropout tolerance.
• Homomorphic Encryption Basics — the CKKS encoding contract masked envelopes must match.
• Async Routing for MPC — how round nonces and envelopes move across a resilient message broker.
• Spatial Sensitivity Scoring Models — how to calibrate grid resolution $g$ to a measured risk tier.