Coordinate Masking with Paillier Encryption

The additively-homomorphic Paillier cryptosystem masks coordinates so that an untrusted aggregator can compute sums and means of encrypted points — a privacy-preserving regional centroid, a masked count over a bounding box — without ever decrypting a single location. This page is the Paillier deep-dive inside the parent guide on coordinate masking protocols, and it complements that page’s deterministic front end rather than repeating it: where the parent quantises and secret-splits geometry for downstream storage, this technique keeps each coordinate encrypted end to end and lets the untrusted party do arithmetic on the ciphertexts. It sits within the broader Secure Multi-Party Computation in Spatial Analytics architecture and shares its number-theoretic foundations with homomorphic encryption basics; when you need thresholded reconstruction instead of compute-on-ciphertext, secret sharing for coordinates is the alternative. The single defining property to hold in mind: Paillier gives you $E(a)\cdot E(b) = E(a+b)$, which is exactly enough for encrypted summation and not one operation more.

Parameter Configuration and Calibration

Paillier coordinate masking exposes four knobs, and each carries a correctness or security consequence rather than a performance-only trade-off. Because the scheme is additive, the plaintext must be a non-negative integer that stays strictly below the modulus $n$ even after every point in the aggregate has been summed — so the interesting calibration is between the quantisation resolution, the batch size, and the key length.

• key_bits — bit-length of the modulus $n = pq$. This is the security parameter. A 1024-bit $n$ is a runnable demonstration size only; production Paillier needs $n \ge 2048$ bits with two independently sampled strong primes of equal length. The private key is $\lambda = \operatorname{lcm}(p-1, q-1)$, so the confidentiality of every encrypted coordinate rests on the difficulty of factoring $n$.
• COORD_SCALE — fixed-point quantisation ($10^6$, microdegrees). Decimal degrees are scaled to integers before encryption because Paillier plaintexts are elements of $\mathbb{Z}_n$, not floats. Microdegrees preserve roughly 0.11 m at the equator — ample for a centroid. Raising the scale sharpens precision but enlarges each plaintext and eats into the overflow headroom below.
• COORD_BIAS — sign-handling offset ($180 \times$ COORD_SCALE). The plaintext space is non-negative, so a raw negative longitude cannot be encrypted directly. A fixed $+180°$ bias shifts the entire WGS84 range into $[0, 360\times\text{SCALE})$ before encryption; the offset is stripped after decryption, but note it accumulates $k$ times across a $k$-point sum (see Incident Response).
• Plaintext overflow headroom. The decrypted aggregate is computed modulo $n$. If the true sum of $k$ biased coordinates exceeds $n$ it silently wraps, so require $n > k_{\max}\cdot 360\cdot\text{SCALE}$ with generous margin. At 2048-bit $n$ and microdegree scale this permits sums of astronomically many points; the constraint only bites with tiny demo moduli or very high scale factors.

Because Paillier is probabilistic — each encryption draws a fresh randomiser $r \in \mathbb{Z}_n^{*}$ — two encryptions of the same coordinate produce different ciphertexts. That is what stops the aggregator from testing whether two devices reported the same location, and it is a property the deterministic parent masking layer deliberately does not have.

Reference Implementation

The class below is a focused, type-annotated implementation of textbook Paillier specialised for quantised coordinates. It performs key generation from two primes, probabilistic encryption, decryption, the homomorphic addition an untrusted aggregator uses, and scalar multiplication for weighted means. It is pure-Python integer arithmetic with no third-party dependency. The docstrings and inline comments flag every point where a choice has a privacy consequence — and flag loudly that textbook Paillier needs cryptographically secure prime generation and side-channel-hardened arithmetic before it goes anywhere near production.

from __future__ import annotations

import secrets
from math import gcd
from typing import NamedTuple, Optional, Tuple

# --- primality helpers (demo-grade; production must use a vetted CSPRNG prime gen) ---
def _is_probable_prime(n: int, rounds: int = 40) -> bool:
    """Miller-Rabin probable-primality test."""
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(rounds):
        a = secrets.randbelow(n - 3) + 2      # CSPRNG witness, never `random`
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def _gen_prime(bits: int) -> int:
    """Sample a random `bits`-bit probable prime with the top bit set."""
    while True:
        candidate = secrets.randbits(bits) | (1 << (bits - 1)) | 1
        if _is_probable_prime(candidate):
            return candidate


class PaillierKeypair(NamedTuple):
    n: int       # public modulus n = p*q
    n_sq: int    # n^2, the ciphertext space
    g: int       # public generator (here g = n + 1)
    lam: int     # PRIVATE: lambda = lcm(p-1, q-1)
    mu: int      # PRIVATE: mu = (L(g^lambda mod n^2))^{-1} mod n


class PaillierCoordinateMask:
    """Additively-homomorphic coordinate masking over textbook Paillier.

    Coordinates are quantised to non-negative integers, encrypted under a
    shared PUBLIC key, and summed by an untrusted aggregator via ciphertext
    multiplication. Only the holder of the PRIVATE key ever decrypts, and it
    decrypts the aggregate alone -- individual coordinates never appear in
    the clear anywhere in the pipeline.

    WARNING: this is textbook Paillier for exposition. Production use needs
    n >= 2048 bits, safe primes from a vetted generator, blinding against
    timing/power side channels, and rejection of malformed ciphertexts.
    """

    COORD_SCALE: int = 10 ** 6            # microdegrees (~0.11 m at equator)
    COORD_BIAS: int = 180 * COORD_SCALE   # shift signed degrees into Z_n^+

    def __init__(self, key_bits: int = 1024,
                 _keypair: Optional[PaillierKeypair] = None) -> None:
        # key_bits is the size of n; 1024 runs fast for tests, prod needs >= 2048.
        self.keypair: PaillierKeypair = _keypair or self._keygen(key_bits)

    @staticmethod
    def _keygen(key_bits: int) -> PaillierKeypair:
        """Generate a Paillier keypair from two primes of equal length."""
        half = key_bits // 2
        while True:
            p, q = _gen_prime(half), _gen_prime(half)
            n = p * q
            # n must be exactly key_bits and coprime to phi(n): guarantees the
            # decryption inverse below exists and blocks degenerate moduli.
            if p != q and n.bit_length() == key_bits and gcd(n, (p - 1) * (q - 1)) == 1:
                break
        n_sq = n * n
        g = n + 1                                   # standard g = n+1 simplification
        lam = (p - 1) * (q - 1) // gcd(p - 1, q - 1)  # lcm(p-1, q-1) -> PRIVATE key
        l_val = (pow(g, lam, n_sq) - 1) // n          # L(x) = (x-1)//n
        mu = pow(l_val, -1, n)                         # modular inverse (3-arg pow)
        return PaillierKeypair(n=n, n_sq=n_sq, g=g, lam=lam, mu=mu)

    def quantize(self, degree: float) -> int:
        """Decimal degree -> non-negative integer plaintext (sign-safe).

        Paillier plaintexts live in Z_n (non-negative), so a raw negative
        longitude cannot be encrypted. The +180-degree bias maps the whole
        WGS84 range into [0, 360*SCALE) losslessly within quantisation error.
        """
        if not -180.0 <= degree <= 180.0:
            raise ValueError(f"degree out of WGS84 range: {degree}")
        return round(degree * self.COORD_SCALE) + self.COORD_BIAS

    def encrypt(self, m: int) -> int:
        """Probabilistic encryption of a quantised coordinate m in [0, n)."""
        n, n_sq, g = self.keypair.n, self.keypair.n_sq, self.keypair.g
        if not 0 <= m < n:
            raise ValueError("plaintext must lie in [0, n) -- check overflow")
        # Fresh randomiser r per ciphertext gives semantic security: reusing r
        # would let the aggregator test whether two devices are co-located.
        while True:
            r = secrets.randbelow(n - 1) + 1
            if gcd(r, n) == 1:                 # r must be a unit in Z_n
                break
        return (pow(g, m, n_sq) * pow(r, n, n_sq)) % n_sq

    def decrypt(self, c: int) -> int:
        """Recover the plaintext with the private key. Aggregator never calls this."""
        n, n_sq = self.keypair.n, self.keypair.n_sq
        lam, mu = self.keypair.lam, self.keypair.mu
        l_val = (pow(c, lam, n_sq) - 1) // n   # L(c^lambda mod n^2)
        return (l_val * mu) % n

    def add(self, c1: int, c2: int) -> int:
        """Homomorphic addition: E(a) (x) E(b) = E(a + b).

        Multiplying two ciphertexts mod n^2 yields an encryption of the SUM of
        the plaintexts. This is the ONLY operation the untrusted aggregator
        runs; it holds no private key, so a, b and a+b stay encrypted.
        """
        return (c1 * c2) % self.keypair.n_sq

    def scalar_mul(self, c: int, k: int) -> int:
        """Scalar multiply: E(a)^k = E(k * a) for a PUBLIC integer weight k.

        Enables weighted sums and weighted means with no decryption. Only a
        public scalar is permitted -- Paillier cannot multiply two ciphertexts,
        so there is no E(a)*E(b) = E(a*b), and squared distances are out of
        reach. Use CKKS for products of two encrypted values.
        """
        if k < 0:
            raise ValueError("weight must be non-negative in the plaintext space")
        return pow(c, k, self.keypair.n_sq)

    def encrypt_coordinate(self, lat: float, lon: float) -> Tuple[int, int]:
        """Quantise and encrypt a (lat, lon) pair independently per axis."""
        return self.encrypt(self.quantize(lat)), self.encrypt(self.quantize(lon))

Validation Checkpoint

A Paillier bug fails silently — a wrong modulus or a wrapped sum returns a plausible wrong coordinate, never an exception — so the invariants below belong in CI, not in a code review. The harness proves the additive homomorphism on two coordinates, then proves that an encrypted sum of several quantised coordinates decrypts to the plaintext sum and that the encrypted mean matches the cleartext mean.

def _validate() -> None:
    mask = PaillierCoordinateMask(key_bits=1024)

    # 1. Additive homomorphism: E(x) (x) E(y) decrypts to x + y for coordinates.
    x = mask.quantize(40.748817)     # a Manhattan latitude
    y = mask.quantize(51.500729)     # a London latitude
    c_sum = mask.add(mask.encrypt(x), mask.encrypt(y))
    assert mask.decrypt(c_sum) == x + y

    # 2. Encrypted centroid: aggregator sums k ciphertexts, key holder decrypts once.
    lats = [40.748817, 40.741895, 40.752655, 40.760800]
    q = [mask.quantize(v) for v in lats]
    enc = [mask.encrypt(v) for v in q]
    agg = enc[0]
    for c in enc[1:]:
        agg = mask.add(agg, c)              # untrusted aggregator: ciphertext-only
    decrypted_sum = mask.decrypt(agg)       # single decryption of the aggregate
    assert decrypted_sum == sum(q)          # encrypted sum == plaintext sum

    # 3. Encrypted mean matches the cleartext mean once the k*BIAS offset is stripped.
    k = len(q)
    mean_lat = ((decrypted_sum - k * mask.COORD_BIAS) / k) / mask.COORD_SCALE
    assert abs(mean_lat - sum(lats) / len(lats)) <= 1 / mask.COORD_SCALE

    # 4. Weighted mean via scalar multiply with PUBLIC integer weights.
    weights = [3, 1, 1, 1]
    wagg = mask.scalar_mul(enc[0], weights[0])
    for c, w in zip(enc[1:], weights[1:]):
        wagg = mask.add(wagg, mask.scalar_mul(c, w))
    assert mask.decrypt(wagg) == sum(w * v for w, v in zip(weights, q))

    print("all Paillier coordinate-masking invariants hold")


if __name__ == "__main__":
    _validate()

The diagram below shows the trust topology these assertions encode: nodes encrypt under a shared public key, the untrusted aggregator multiplies ciphertexts to obtain the encrypted sum, and only the key holder — a separate party — ever decrypts, and only the aggregate.

A note on key management, because it is the property that makes or breaks the guarantee. The public key $(n, g)$ is shared with every node and with the aggregator — anyone can encrypt and anyone can add. The private key $(\lambda, \mu)$ must live with a party that is not the aggregator: a data-owner consortium, a dedicated key-management service, or a threshold-decryption committee. If the aggregator ever holds the private key, homomorphic masking buys nothing — it can decrypt each incoming ciphertext and read every coordinate. For high-assurance deployments, split the private key across custodians with threshold Paillier so no single party can decrypt even the aggregate alone.

Incident Response and Edge Cases

Paillier masking fails quietly, degrading correctness or confidentiality without raising. The failures that surface on real deployments:

• Plaintext modulus overflow. The decrypted aggregate is taken modulo $n$; if the true sum of $k$ biased coordinates exceeds $n$ it wraps to a small residue and the centroid is silently wrong. Detection: before a campaign, assert $k_{\max}\cdot 360\cdot\text{SCALE} < n$, and range-check that every decrypted sum falls inside the expected geographic envelope. Remediation: raise key_bits (a 2048-bit $n$ absorbs enormous batches), lower COORD_SCALE, or partition the region and sum sub-batches.
• Negative-bias accumulation. The $+180°$ bias is added to every coordinate, so a $k$-point sum carries a $k\times\text{BIAS}$ offset. Forgetting to subtract it before dividing yields a mean shifted by exactly 180°. Detection: a computed centroid that is a clean ~180° off the expected location. Remediation: always strip $k\cdot\text{COORD\_BIAS}$ from the decrypted sum before dividing by $k$, as the Validation Checkpoint does; track $k$ as public metadata alongside the aggregate ciphertext.
• Key compromise or aggregator custody. If the private key leaks — or is ever handed to the aggregator — every intercepted ciphertext becomes plaintext, retroactively. Detection: audit that the aggregator process has no access path to $(\lambda, \mu)$ and that key material sits in an HSM or KMS with separate custody. Remediation: rotate to a fresh keypair, re-encrypt live streams under the new public key, and move to threshold decryption so no single custodian can decrypt; treat past ciphertexts encrypted under the compromised key as exposed.
• Attempting a distance or product. A team tries to compute a squared distance $\sum (a_i - b_i)^2$ and finds Paillier cannot multiply two ciphertexts — there is no $E(a)\cdot E(b) = E(ab)$. Detection: the requirement calls for a product of two encrypted values, not a public scalar. Remediation: keep Paillier for the additive parts and move the multiplicative part to a levelled scheme — see encrypted spatial range queries with CKKS and the parent homomorphic encryption basics.

Frequently Asked Questions

Related

• Coordinate Masking Protocols — the parent guide; its deterministic quantise-and-split front end is the counterpart to this encrypt-and-sum technique.
• Homomorphic Encryption Basics — the broader scheme family, and where to go for multiplicative depth Paillier cannot provide.
• Encrypted Spatial Range Queries with CKKS — the levelled scheme for distances and range predicates on encrypted coordinates.
• Secret Sharing for Coordinates — the threshold-reconstruction alternative when you do not need compute-on-ciphertext.
• Secure Multi-Party Computation in Spatial Analytics — the end-to-end architecture these masking layers plug into.

Up: Coordinate Masking Protocols · Secure Multi-Party Computation in Spatial Analytics