Secret Sharing for Coordinates

Picture two regional ambulance services and a public-health analytics team that need to know how many high-acuity patients live within a five-minute drive of each other’s catchment boundaries — a spatial overlap that is operationally vital but would expose precise home coordinates the moment either service handed over raw points. Secret sharing for coordinates is the control that lets this computation run on infrastructure no single party trusts: each latitude–longitude pair is split into n mathematically meaningless fragments, distributed across independent compute nodes, and reconstructed only when a configured quorum of t nodes cooperate. Below that threshold the shares leak nothing — not an approximate region, not a bounding box, not a single bit of the original coordinate.

This guide sits inside the Secure Multi-Party Computation in Spatial Analytics architecture, where masking, sharing, routing, and encryption form one pipeline. Secret sharing is the distribution layer that follows coordinate masking protocols: masking deterministically normalises and quantises the geometry, and sharing then disperses it under an information-theoretic guarantee. Where you need to compute on the protected values rather than merely store them across a trust boundary, homomorphic encryption is the heavier alternative — the privacy model comparison spells out when each is the right tool. This page covers the threshold construction, the finite-field arithmetic it depends on, and the production controls that keep it from silently degrading in deployment.

Prerequisites & Cryptographic Environment

Before any coordinate is split, provision a threshold-cryptography stack that performs exact modular arithmetic over a large prime field. The reference implementation here needs only the Python standard library: the secrets module for cryptographically secure random coefficient generation and the three-argument pow() built-in for modular exponentiation and inversion. Production deployments typically add the cryptography library for the TLS 1.3 transport and a cloud KMS or HSM binding for storing the threshold parameters and per-node transport keys.

Three environmental invariants must hold before the pipeline runs:

• Canonical CRS. Every input must be verified as EPSG:4326 decimal degrees at ingestion. Mixing projected metres (EPSG:3857) or swapped axes into the field mapping produces residues that are arithmetically valid but spatially meaningless — a class of silent corruption covered under failure modes below.
• Fixed-point integer domain. Coordinates are never shared as IEEE 754 floats. They are quantised to integers (microdegrees or finer) so that polynomial evaluation and Lagrange interpolation are exact; a single rounding error in floating point makes reconstruction non-deterministic.
• A declared privacy-budget accountant. Secret sharing is information-theoretically secure on its own, but the moment a reconstructed coordinate is released to a downstream model it must pass through a differential-privacy mechanism. Stand up a Rényi differential-privacy (RDP) accountant up front and tie its $(\varepsilon, \delta)$ ceiling to a concrete control in the compliance framework mapping — for example, GDPR Article 25 data-minimisation expressed as a maximum release resolution.

For the prime modulus, choose $p > 2^{64}$ so the quantised continental coordinate range never approaches the field boundary; a 256-bit safe prime such as $p = 2^{256} - 189$ leaves ample headroom and matches the modulus used in the child guide on Shamir secret sharing for GPS coordinate protection.

Step 1: Coordinate Quantization & Field Mapping

Raw decimal degrees are scaled to integers and biased into the non-negative range $[0, p)$. A scaling factor of $10^7$ (microdegrees) gives GPS-grade accuracy of roughly 1.1 cm at the equator, producing integers of at most $\pm 1.8 \times 10^9$ for latitude and $\pm 3.6 \times 10^9$ for longitude — values that sit comfortably inside a 256-bit field. The bias offset moves negative southern and western coordinates into field elements without two’s-complement ambiguity, and the operation is fully reversible within the agreed precision.

from typing import Tuple

SCALE: int = 10**7          # microdegree resolution (~1.1 cm at equator)
BIAS: int = 180 * SCALE     # shifts [-180, 180] into [0, 360 * SCALE]

def quantize(lat: float, lon: float) -> Tuple[int, int]:
    """Map an EPSG:4326 (lat, lon) pair to non-negative field integers.

    Raises ValueError on out-of-range input so a mis-projected CRS cannot
    silently produce a spatially meaningless residue.
    """
    if not (-90.0 <= lat <= 90.0) or not (-180.0 <= lon <= 180.0):
        raise ValueError(f"Coordinate out of WGS84 range: ({lat}, {lon})")
    qlat: int = round(lat * SCALE) + BIAS
    qlon: int = round(lon * SCALE) + BIAS
    return qlat, qlon

def dequantize(qlat: int, qlon: int) -> Tuple[float, float]:
    """Inverse of quantize(), recovering decimal degrees within +/- 1/SCALE."""
    return (qlat - BIAS) / SCALE, (qlon - BIAS) / SCALE

Latitude and longitude are quantised and shared as two independent secrets. Reusing one polynomial across both axes correlates them and lets an attacker who recovers one axis constrain the other, so the implementation always keeps the dimensions separate.

Step 2: Polynomial Construction & Share Generation

For each axis, sample a random polynomial $f(x) = a_0 + a_1 x + \dots + a_{t-1} x^{t-1} \pmod p$, where $a_0$ is the quantised coordinate and the threshold $t$ sets how many shares must cooperate to reconstruct it. The shares are the points $(i, f(i))$ for $i \in \{1, \dots, n\}$. The information-theoretic guarantee rests entirely on sampling $a_1 \dots a_{t-1}$ uniformly from the field: any subset of fewer than $t$ shares is consistent with every possible secret, so it reveals nothing.

import secrets
from typing import List, Tuple

class CoordinateSecretSharing:
    """Shamir (t, n) threshold sharing over a prime field, sized for
    fixed-point geospatial integers. Each coordinate axis is shared
    independently to prevent cross-axis correlation leakage."""

    def __init__(self, prime: int, threshold: int, num_shares: int) -> None:
        if not all(isinstance(v, int) and v > 0
                   for v in (prime, threshold, num_shares)):
            raise ValueError("prime, threshold, num_shares must be positive ints")
        if threshold > num_shares:
            raise ValueError("threshold cannot exceed total shares")
        self.p: int = prime
        self.t: int = threshold
        self.n: int = num_shares

    def split(self, secret: int) -> List[Tuple[int, int]]:
        """Generate n shares (x, f(x)) for one quantized coordinate axis."""
        if not (0 <= secret < self.p):
            raise ValueError("secret must lie within the field [0, p)")
        # a_0 = secret; a_1..a_{t-1} sampled uniformly from [1, p-1]
        coeffs: List[int] = [secret] + [
            secrets.randbelow(self.p - 1) + 1 for _ in range(self.t - 1)
        ]
        shares: List[Tuple[int, int]] = []
        for x in range(1, self.n + 1):
            y: int = 0
            for power, coeff in enumerate(coeffs):
                y = (y + coeff * pow(x, power, self.p)) % self.p
            shares.append((x, y))
        return shares

Coefficients are always generated locally on the node that owns the data. Synchronising or exchanging coefficients across nodes would break the non-interactive property of the sharing phase and create exactly the centralised view the architecture exists to avoid.

Step 3: Secure Distribution & Synchronization

Each share goes to one designated compute node over a mutually authenticated TLS 1.3 channel, encrypted at rest under a node-specific key and stripped of any metadata that could re-link it to a subject. In a real deployment nodes drop, networks partition, and latency spikes — so distribution is wrapped in async routing for MPC rather than a blocking fan-out. The router enforces a per-share timeout, retries with backoff, and falls back to a secondary quorum if a primary node goes dark, while every node verifies share integrity before acknowledging receipt.

import hashlib
from typing import Dict, List, Tuple

def envelope(node_id: int, share: Tuple[int, int], round_nonce: bytes) -> Dict[str, str]:
    """Wrap a share with a per-round integrity tag before distribution.

    The nonce binds the share to one sharing round so a replayed or
    cross-round share is rejected at the receiving node.
    """
    x, y = share
    payload: bytes = f"{node_id}:{x}:{y}".encode() + round_nonce
    tag: str = hashlib.sha3_256(payload).hexdigest()
    return {"node_id": str(node_id), "x": str(x), "y": str(y), "tag": tag}

def verify_envelope(env: Dict[str, str], round_nonce: bytes) -> bool:
    """Constant-work integrity check the receiving node runs on arrival."""
    payload: bytes = f"{env['node_id']}:{env['x']}:{env['y']}".encode() + round_nonce
    expected: str = hashlib.sha3_256(payload).hexdigest()
    return secrets.compare_digest(expected, env["tag"])

The secrets.compare_digest comparison is constant-time, which matters: a byte-by-byte tag check would leak validity timing that a colluding node could exploit to forge envelopes.

Step 4: Threshold Reconstruction & Differential-Privacy Integration

When an analytical query needs a coordinate resolved, at least $t$ nodes contribute their shares and the secret is recovered by Lagrange interpolation evaluated at $x = 0$ over the field. Reconstruction must never expose the raw value directly to a model: the moment the quantised coordinate is recovered it passes through a calibrated DP mechanism, so plaintext geometry exists only transiently inside the reconstruction boundary and never crosses into downstream storage or analytics.

    def reconstruct(self, shares: List[Tuple[int, int]]) -> int:
        """Recover the secret from >= t shares via Lagrange interpolation at x=0."""
        if len(shares) < self.t:
            raise ValueError(f"insufficient shares: {len(shares)} < {self.t}")
        subset: List[Tuple[int, int]] = shares[: self.t]
        secret: int = 0
        for i, (xi, yi) in enumerate(subset):
            num: int = 1
            den: int = 1
            for j, (xj, _) in enumerate(subset):
                if i != j:
                    num = (num * (0 - xj)) % self.p
                    den = (den * (xi - xj)) % self.p
            # Modular inverse via Python's three-argument pow (p is prime)
            lagrange: int = (num * pow(den, -1, self.p)) % self.p
            secret = (secret + yi * lagrange) % self.p
        return secret

After reconstruct returns, add Laplace noise scaled to $b = \Delta f / \varepsilon$ — where $\Delta f$ is the spatial query sensitivity and $\varepsilon$ the per-release budget — before the coordinate reaches any model, and debit the spend from the RDP accountant. Calibrate $\varepsilon$ against the measured risk tier from the spatial sensitivity scoring models: a dense urban catchment where a single home is highly identifying warrants a tighter budget than a sparse rural one. Noise is applied to the reconstructed value only — never to individual shares, which would destroy the linear structure interpolation depends on.

Threat Model Considerations

Secret sharing changes the adversary’s job from “steal a coordinate” to “compromise a quorum,” but several attack surfaces remain specific to the geospatial setting:

• Quorum collusion. The information-theoretic guarantee holds only while fewer than $t$ nodes collude. Set $t$ from your real trust boundaries — distinct legal entities, distinct cloud accounts, distinct key custodians — not from a convenient round number. A $t$ chosen below the number of nodes one operator controls offers no protection against that operator.
• Cross-axis correlation. Reusing a polynomial or its randomness across latitude and longitude lets recovery of one axis constrain the other. Independent per-axis polynomials with independently sampled coefficients close this channel.
• Precision side-channels. Floating-point reconstruction can leak sub-metre artefacts that fingerprint a location. Fixed-point quantisation over the integer field removes the channel entirely.
• Reconstruction timing attacks. Data-dependent branches in interpolation or envelope verification leak information through wall-clock variance. Use constant-time comparisons and batch share processing so timing does not correlate with secret content.
• Replay and cross-round mixing. A share captured in one round and replayed into another can corrupt or partially leak state. The per-round nonce in the envelope binds each share to a single round and makes replays detectable.
• Metadata re-linkage. Even meaningless shares become identifying if shipped with subject IDs, timestamps, or source IPs. Strip metadata before distribution and treat envelopes as opaque.

Validation & Compliance Checklist

Wire each control into CI and a compliance dashboard with a measurable pass/fail criterion rather than reviewing it by eye:

1. Threshold boundary — PASS if exactly $t$ shares reconstruct the original quantised coordinate for 100% of a $\ge 10^5$-point property test, and every $(t-1)$-share subset fails to do so. This is the core security invariant; fail the build on any violation.
2. Field-overflow safety — PASS if boundary secrets ($0$, $p-1$, and the bias-mapped equivalents of $\pm180°$) round-trip through split/reconstruct without modular collision.
3. Cross-axis independence — PASS if latitude and longitude are shared with separately seeded polynomials; assert that recovering one axis’s shares yields no information about the other (the polynomials must not share coefficients).
4. DP budget accounting — PASS if every released coordinate has Laplace noise $b = \Delta f / \varepsilon$ applied after reconstruction and the composed spend stays under the $(\varepsilon, \delta)$ ceiling declared in the compliance mapping. Record spent budget per release.
5. Integrity & replay — PASS if every envelope verifies against its round nonce with a constant-time comparison, and a share replayed from a prior round is rejected.
6. Partition tolerance — PASS if dropping any $n-t$ nodes mid-reconstruction still recovers the coordinate, and dropping $n-t+1$ fails cleanly with a raised error rather than a wrong value.

The harness below exercises invariants 1, 2, and 6 directly and is safe to run in CI:

def _validate() -> None:
    p: int = (1 << 256) - 189
    sss = CoordinateSecretSharing(prime=p, threshold=3, num_shares=5)

    qlat, qlon = quantize(40.748817, -73.985428)   # a Manhattan point
    for secret in (qlat, qlon, 0, p - 1):
        shares = sss.split(secret)
        assert len(shares) == 5
        # exactly t shares reconstruct
        assert sss.reconstruct(shares[:3]) == secret
        # more than t shares still reconstruct
        assert sss.reconstruct(shares) == secret
        # any t-1 shares must NOT reveal the secret
        assert sss.reconstruct.__self__.t == 3
        try:
            sss.reconstruct(shares[:2])
        except ValueError:
            pass
        else:
            raise AssertionError("t-1 shares must fail reconstruction")
        # partition tolerance: any 3 of 5 nodes suffice
        assert sss.reconstruct([shares[0], shares[2], shares[4]]) == secret

    # full round-trip back to decimal degrees within quantization error
    rlat, rlon = dequantize(sss.reconstruct(sss.split(qlat)),
                            sss.reconstruct(sss.split(qlon)))
    assert abs(rlat - 40.748817) <= 1 / SCALE
    assert abs(rlon + 73.985428) <= 1 / SCALE
    print("all secret-sharing invariants hold")

if __name__ == "__main__":
    _validate()

Failure Modes & Remediation

Secret sharing rarely fails loudly; it fails by quietly returning a wrong coordinate or by stalling a round. The high-frequency production failures:

• CRS mismatch. A batch arrives in EPSG:3857 metres or with swapped axes; quantize either raises or — if range checks are skipped — produces a valid-looking but meaningless field element. Detection: enforce the WGS84 range check at ingestion. Recovery: re-project and quarantine the offending batch before it reaches the sharing stage.
• Threshold set below a single operator’s footprint. If one party controls $\ge t$ nodes, that party can reconstruct unilaterally. Detection: audit node ownership against $t$. Recovery: raise $t$, or redistribute nodes across independent custodians until no single operator holds a quorum.
• Node dropout below quorum. With more than $n-t$ nodes offline a round cannot be reconstructed. Detection: fewer than $t$ envelopes at the round-completion timeout. Recovery: fall back to a secondary quorum via the async router, or provision a larger $n$ relative to $t$ to widen the dropout margin.
• Floating-point contamination. A coordinate that slips through as a raw float makes interpolation non-deterministic and reconstruction unreliable. Detection: assert integer types entering split. Recovery: route everything through quantize and reject non-integer secrets at the field boundary.
• Privacy-budget exhaustion. Repeated releases over the same population deplete the $(\varepsilon, \delta)$ budget, after which reconstructed-and-noised outputs no longer carry the claimed guarantee. Detection: the RDP accountant crosses its ceiling. Recovery: halt releases for that population, coarsen the release resolution to spend less per query, or rotate to a fresh cohort.

Frequently Asked Questions

When should I use secret sharing instead of homomorphic encryption for coordinates?

Choose secret sharing when the goal is threshold-based access control and storage across nodes you do not individually trust, and reconstruction happens at well-defined query points. Its arithmetic is cheap — additions and one interpolation — so it scales to high-throughput spatial aggregation. Reach for homomorphic encryption when you must compute arbitrary functions directly on protected coordinates without ever reconstructing them, accepting the much higher per-operation cost. The privacy model comparison walks through the decision in full.

How do I choose the threshold t and share count n?

Set $t$ from your trust boundaries: it must exceed the number of nodes any single operator, cloud account, or key custodian controls, otherwise that party can reconstruct alone. Set $n$ from your availability target — the round tolerates $n - t$ simultaneous dropouts, so a $(3, 5)$ scheme survives two offline nodes while still requiring three independent parties to cooperate. Widen the gap between $t$ and $n$ when node churn is high; narrow it when collusion risk dominates.

Do the shares count as personal data under GDPR or HIPAA?

Below the threshold, a share is consistent with every possible coordinate and reveals nothing, so individual shares held by a single node are pseudonymised data rather than personal data under most frameworks. That status is conditional: it holds only while the quorum is genuinely split across independent custodians and the reconstructed value is DP-noised before release. Tie that condition to a concrete control in the compliance framework mapping — collapse the custody split and the same shares revert to personal data.

Why quantize coordinates instead of sharing the floats directly?

Secret sharing is exact arithmetic over a finite field; IEEE 754 floats are not exact, so a single rounding difference between split and reconstruct yields a wrong coordinate or a non-deterministic result. Quantising to fixed-point integers makes every polynomial evaluation and interpolation exact, and as a side effect removes the sub-metre floating-point artefacts that could fingerprint a location.

Related

This guide is part of the Secure Multi-Party Computation in Spatial Analytics reference — start there for how masking, sharing, routing, and encryption fit into one pipeline.

• Shamir Secret Sharing for GPS Coordinate Protection — the deep-dive on prime selection, bias mapping, and incident response for telemetry traces.
• Coordinate Masking Protocols — the deterministic front end that normalises and quantises geometry before it reaches this sharing layer.
• Homomorphic Encryption Basics — the compute-on-ciphertext alternative for when reconstruction is not acceptable.
• Async Routing for MPC — how share envelopes and round nonces move across a partition-tolerant broker.
• Spatial Sensitivity Scoring Models — how to calibrate the post-reconstruction $\varepsilon$ to a measured risk tier.

Up: Secure Multi-Party Computation in Spatial Analytics