Additive Secret Sharing for Coordinates in Python

Additive secret sharing is the workhorse of privacy-preserving spatial aggregation: a quantized coordinate is split into n random shares that sum to the secret modulo a prime p, and reconstruction requires every one of them. It is the cheap, non-threshold cousin of the polynomial scheme in the parent guide on secret sharing for coordinates — no Lagrange interpolation, no field inversion, just modular addition — which is exactly why it, and not Shamir secret sharing for GPS coordinate protection, is what backs high-throughput share-and-sum protocols across the Secure Multi-Party Computation in Spatial Analytics architecture. This page is the narrow, implementation-first treatment of the n-of-n additive construction over $\mathbb{Z}_p$: how it differs from a $t$-of-$n$ threshold, how to size the modulus for a summation rather than a single value, and how to add shares locally so an aggregator learns a regional total without ever seeing a coordinate.

Parameter Configuration and Calibration

Additive sharing trades Shamir’s fault tolerance for speed and composability. Where the threshold scheme lets any $t$ of $n$ shares rebuild the secret, an additive split of $s$ into $s_1, \dots, s_n$ with $\sum_i s_i \equiv s \pmod p$ is strictly n-of-n: drop a single share and the secret is information-theoretically gone. That property is a liability for storage but an asset for summation, because shares add coordinate-wise — party $j$ can fold the $j$-th share of a thousand records into one running total without ever talking to another party. This is the primitive underneath federated secure aggregation protocols, where the server must learn only the sum of client contributions.

Four knobs govern a correct deployment. Each is a correctness or privacy lever, not a performance dial.

The modulus rule is the one that catches people migrating from Shamir. There, $p$ only has to exceed a single biased coordinate plus its random coefficients. In additive share-and-sum, reconstruction is $\sum_i s_i \bmod p$, so if the true aggregate of $N$ quantized coordinates exceeds $p$ it silently wraps and the recovered total is wrong by a multiple of $p$. Size $p$ so that

$$p \;>\; N_{\max} \cdot q_{\max}, \qquad q_{\max} = 360 \times 10^{6} \approx 3.6\times 10^{8},$$

where $N_{\max}$ is the largest number of records you will ever sum. With $p = 2^{61}-1 \approx 2.3\times10^{18}$ you can aggregate well over $10^{9}$ coordinates before the field boundary is in play — ample for city- or nation-scale density counts, and small enough that shares are single 64-bit integers on the wire. Unlike Shamir, additive sharing does not require a prime at all (any modulus, including $2^{k}$, gives a perfectly uniform share distribution); a prime is chosen only so the same field interoperates with multiplicative sub-protocols and matches the rest of the pipeline.

Reference Implementation

The AdditiveSharing class below is pure standard-library Python: secrets.randbelow for cryptographically uniform shares and integer arithmetic for everything else. It exposes exactly three operations — split, reconstruct, and the secure_sum that is the reason to reach for this scheme. Inline comments flag the lines where a choice has a privacy consequence.

from __future__ import annotations

import secrets
from typing import List, Sequence

SCALE: int = 10 ** 6          # microdegrees, ~0.11 m at the equator
BIAS: int = 180 * SCALE       # shift [-180, 180] into non-negative field elements


def quantize(deg: float) -> int:
    """Map one WGS84 axis (decimal degrees) to a non-negative integer in Z_p.

    Fixed-point integers make modular addition exact; sharing raw IEEE 754
    floats would make the share sum non-deterministic and leak sub-metre
    artefacts that can fingerprint a location.
    """
    if not (-180.0 <= deg <= 180.0):
        raise ValueError(f"axis out of WGS84 range: {deg}")
    return round(deg * SCALE) + BIAS


class AdditiveSharing:
    """n-of-n additive secret sharing over Z_p.

    A quantized coordinate `s` is split into `n` shares whose sum is
    congruent to `s` mod p. Each share is uniform on its own, so any
    strict subset of the n shares reveals nothing about `s`. Unlike a
    Shamir t-of-n threshold scheme there is NO fault tolerance: all n
    shares are required, and one lost share makes `s` unrecoverable.
    """

    def __init__(self, num_parties: int, modulus: int = (1 << 61) - 1) -> None:
        if num_parties < 2:
            raise ValueError("additive sharing needs at least 2 parties")
        if modulus <= 0:
            raise ValueError("modulus must be positive")
        self.n: int = num_parties
        self.p: int = modulus

    def split(self, secret: int) -> List[int]:
        """Split one quantized coordinate into n additive shares.

        The first n-1 shares are drawn uniformly from Z_p with a CSPRNG;
        the final share is fixed to close the sum. That uniform sampling
        is the entire security argument — never seed it from a coordinate.
        """
        if not (0 <= secret < self.p):
            raise ValueError("secret must lie in [0, p)")
        shares: List[int] = [secrets.randbelow(self.p) for _ in range(self.n - 1)]
        last: int = (secret - sum(shares)) % self.p   # closes sum to s mod p
        shares.append(last)
        return shares

    def reconstruct(self, shares: Sequence[int]) -> int:
        """Recover the secret. Requires ALL n shares — there is no threshold."""
        if len(shares) != self.n:
            raise ValueError(
                f"n-of-n scheme: need all {self.n} shares, got {len(shares)}"
            )
        return sum(shares) % self.p

    def secure_sum(self, share_vectors: Sequence[Sequence[int]]) -> int:
        """Aggregate several secrets from their shares without reconstructing any.

        `share_vectors[k]` is the n-share vector of secret k. Party j adds
        the j-th share of every secret locally (a column sum); only those n
        party-local partial sums are ever revealed, and their total equals
        the plaintext sum of the secrets mod p. No single coordinate is
        materialised at any point in the protocol.
        """
        partial_sums: List[int] = [0] * self.n
        for vec in share_vectors:
            if len(vec) != self.n:
                raise ValueError("every share vector must hold n shares")
            for j in range(self.n):
                # this update happens ON party j's node — shares never pool centrally
                partial_sums[j] = (partial_sums[j] + vec[j]) % self.p
        return sum(partial_sums) % self.p

The design keeps the secure_sum reduction explicit so it maps onto real infrastructure: in production the inner partial_sums[j] update executes on party $j$’s own node, and only the $n$ scalars partial_sums cross the network. Because those partials are themselves an additive sharing of the aggregate, revealing all $n$ of them discloses only the total — the same reason a lone share discloses nothing about a single record.

① Split one quantized coordinate — all n shares required

def _validate() -> None:
    p: int = (1 << 61) - 1
    scheme = AdditiveSharing(num_parties=4, modulus=p)

    # 1. Shares sum to the secret mod p, at the field edges and a real point.
    for secret in (0, 1, p - 1, quantize(40.748817), quantize(-73.985428)):
        shares = scheme.split(secret)
        assert len(shares) == 4
        assert scheme.reconstruct(shares) == secret
        assert sum(shares) % p == secret

    # 2. n-of-n: any n-1 shares must NOT reconstruct (there is no threshold).
    shares = scheme.split(123_456_789)
    try:
        scheme.reconstruct(shares[:-1])
    except ValueError:
        pass
    else:
        raise AssertionError("n-1 shares must not reconstruct")

    # 3. The first n-1 shares are uniform and independent of the secret:
    #    two different secrets can be split under an identical (n-1)-prefix,
    #    with only the closing share differing. This is why a strict subset
    #    leaks nothing — it is consistent with every possible coordinate.
    prefix = [secrets.randbelow(p) for _ in range(scheme.n - 1)]  # any uniform prefix
    for target in (quantize(51.5074), quantize(-0.1278)):
        closing = (target - sum(prefix)) % p                 # unique closing share
        assert scheme.reconstruct(prefix + [closing]) == target

    # 4. secure_sum over several coordinates equals the plaintext sum mod p,
    #    without any coordinate being reconstructed.
    plain = [quantize(v) for v in (40.7128, 34.0522, 51.5074, -33.8688)]
    vectors = [scheme.split(s) for s in plain]
    assert scheme.secure_sum(vectors) == sum(plain) % p

    print("all additive-sharing invariants hold")


if __name__ == "__main__":
    _validate()