Homomorphic Encryption Basics for Privacy-Preserving Spatial Analytics

Two telematics insurers want to know how many of their policyholders’ vehicles habitually park within 200 metres of each other’s flagged high-risk zones — a proximity statistic that would expose precise GPS traces if either side handed over raw points. Homomorphic encryption (HE) is the compute primitive that lets the join run on ciphertext: each operator evaluates squared distances and range filters directly over encrypted coordinate vectors, and only an authorised party ever sees a plaintext result. Operating inside the broader Secure Multi-Party Computation in Spatial Analytics architecture, HE is the layer that turns the masked, secret-shared envelopes produced upstream by coordinate masking protocols into computable encrypted geometry.

This guide details a production-ready HE pipeline for Python data-engineering stacks: cryptographic parameterisation, deterministic coordinate encoding, homomorphic distance evaluation, and a synchronised differential privacy (DP) release stage. Every parameter is tied to a concrete guarantee — the scaling factor to coordinate precision, the modulus chain to operator depth, and the noise scale to a measurable $\varepsilon$ — so a regulated deployment under HIPAA, GDPR, or GLBA can defend each setting in an audit.

Prerequisites

The pipeline below depends on a leveled HE backend plus the standard numerical stack. Pin versions: HE libraries change their parameter APIs between releases, and a silent default change to the modulus chain alters your security level.

• Runtime: Python 3.10+.
• HE backend: tenseal>=0.3.14 (CKKS), which wraps Microsoft SEAL. Pyfhel is an acceptable substitute when you need BFV/BGV exact integer arithmetic instead of CKKS approximate reals.
• Numerics: numpy>=1.24 for the Nx2 coordinate arrays and the plaintext baseline used during validation.
• Privacy budget accounting: a Rényi Differential Privacy (RDP) accountant (for example Opacus’s RDPAccountant) so the post-decryption Laplace/Gaussian noise can be expressed as a spent $(\varepsilon, \delta)$ budget before any result leaves the trust boundary.
• Key custody: a hardware-backed enclave (AWS Nitro, Azure Confidential Computing) or a threshold key vault. The secret key must never sit in long-lived application memory.
• Assumed reference frame: all inputs are projected to EPSG:4326 decimal degrees, or to a single projected CRS in metres, before entry. A coordinate reference system (CRS) mismatch silently corrupts the fixed-point encoding — see Failure Modes below.

The encoding contract here matches the CKKS scaling factor used upstream, so masked envelopes from the masking stage feed this circuit without re-quantising. For the privacy-model trade-offs that decide whether HE or central versus local differential privacy is the right tool for a given join, start from the privacy-model comparison before committing to a cryptographic backend.

Step-by-Step Procedure

Step 1 — Cryptographic parameterisation and key generation

Spatial analytics requires floating-point arithmetic, making the CKKS scheme the standard choice: it supports approximate computation on real-valued coordinates with fixed-point scaling. Three parameters dominate the precision / depth / ciphertext-size trade-off:

• Polynomial modulus degree ($N$): sets SIMD packing capacity and security level. $N = 8192$ or $N = 16384$ is typical for vectorised coordinate batches.
• Ciphertext modulus chain ($q$): a sequence of prime moduli that depletes with each multiplication. It must exceed the multiplicative depth of your spatial operators — squared Euclidean distance over per-axis ciphertexts needs depth 1, while chained range filters need depth 2–3.
• Scaling factor ($\Delta$): aligns plaintext precision with the ciphertext representation. Use $2^{30}$ to $2^{40}$ for geospatial coordinates; below $2^{30}$ sub-metre accuracy collapses.

import tenseal as ts
import numpy as np
from typing import Tuple

def initialize_ckks_context(poly_modulus_degree: int = 8192,
                            coeff_mod_bit_sizes: list = [40, 21, 21, 21, 40],
                            scaling_factor: int = 2**21) -> ts.Context:
    """
    Initialize CKKS context with explicit noise budget tracking.
    Compliant with NIST IR 8413 recommendations for parameter selection.
    """
    # TenSEAL's `ts.context` does not accept `scaling_factor` directly;
    # set it via `global_scale` after construction.
    context = ts.context(
        ts.SCHEME_TYPE.CKKS,
        poly_modulus_degree=poly_modulus_degree,
        coeff_mod_bit_sizes=coeff_mod_bit_sizes,
    )
    # Generate evaluation keys for relinearization and rotation (SIMD shifts)
    context.generate_galois_keys()
    context.generate_relin_keys()
    context.global_scale = scaling_factor
    # Stash the chain configuration on the context so downstream validators
    # can introspect it without relying on a private TenSEAL attribute.
    context.coeff_mod_bit_sizes = coeff_mod_bit_sizes
    return context

# Validation: verify ciphertext modulus chain depth matches operator requirements
def validate_modulus_chain(context: ts.Context, required_depth: int = 3) -> None:
    available_levels = len(context.coeff_mod_bit_sizes) - 2  # exclude initial/terminal primes
    if available_levels < required_depth:
        raise ValueError(f"Insufficient modulus chain depth: {available_levels} < {required_depth}")
    print(f"[VALID] Modulus chain supports depth {available_levels}")

For distributed compute topologies, coordinate key generation with secret sharing for coordinates so the private key is split across a quorum and decryption is gated by a $t$-of-$n$ threshold rather than trusting any single node.

Step 2 — Coordinate encoding and plaintext preparation

Raw latitude/longitude or projected X/Y values must be deterministically mapped to the HE plaintext space. Floating-point drift during homomorphic evaluation can corrupt topological relationships, so encoding is strict: normalise to a bounded range, apply fixed-point scaling aligned with $\Delta$, quantise to prevent precision leakage across multiplications, then pack into ciphertext slots in row-major order for vectorised distance calculations.

def encode_and_encrypt_coordinates(
    context: ts.Context, coords: np.ndarray
) -> Tuple[ts.CKKSVector, ts.CKKSVector]:
    """
    Encode spatial coordinates into two packed CKKS ciphertexts: one
    holding all x-coordinates, one holding all y-coordinates. This
    layout supports slot-wise subtraction and squaring for distance
    computations without rotation-based axis disentangling.
    coords: shape (n_points, 2)
    """
    if coords.ndim != 2 or coords.shape[1] != 2:
        raise ValueError("Coordinates must be 2D array with shape (n, 2)")

    enc_x = ts.ckks_vector(context, coords[:, 0].tolist())
    enc_y = ts.ckks_vector(context, coords[:, 1].tolist())
    return enc_x, enc_y

# Validation: ensure scaling alignment and slot capacity
def validate_encoding_capacity(context: ts.Context, n_points: int, poly_modulus_degree: int) -> None:
    max_slots = poly_modulus_degree // 2
    required_slots = n_points
    if required_slots > max_slots:
        raise OverflowError(f"Coordinate batch exceeds SIMD capacity: {required_slots} > {max_slots}")
    print(f"[VALID] Encoding capacity sufficient: {required_slots}/{max_slots} slots used")

Packing both axes into two per-axis ciphertexts is the layout decision that keeps multiplicative depth at 1: subtraction and squaring stay slot-aligned, so no Galois rotation is needed to line coordinates up. Quantising to the same grid resolution used to calibrate the dataset’s spatial sensitivity score means the encoding step does double duty as a coarsening control rather than an afterthought.

Step 3 — Homomorphic evaluation and DP release

Spatial computations execute directly on ciphertexts. Common operators are encrypted squared Euclidean distance, range filtering, and centroid aggregation. Because CKKS is approximate, precision bounds must be tracked alongside DP accounting. HE and DP compose cleanly when the noise is calibrated to query sensitivity at the trust boundary: compute the spatial metric homomorphically, decrypt to an authorised enclave, apply calibrated Laplace or Gaussian noise sized by the $(\varepsilon, \delta)$ budget, then release.

For a Laplace mechanism on a query of sensitivity $\Delta f$, the noise scale is $b = \Delta f / \varepsilon$. For bounded coordinates, the sensitivity of a Euclidean distance is the maximum coordinate range, so a tighter quantisation grid both reduces sensitivity and lets you spend less budget per release.

def compute_encrypted_euclidean_distances(
    enc_a_x: ts.CKKSVector, enc_a_y: ts.CKKSVector,
    enc_b_x: ts.CKKSVector, enc_b_y: ts.CKKSVector,
) -> ts.CKKSVector:
    """
    Compute squared Euclidean distance: ||a - b||^2 = (a_x - b_x)^2 + (a_y - b_y)^2

    With x and y stored in separate ciphertexts (see encode_and_encrypt_coordinates),
    each subtraction and square is slot-aligned — no rotation needed, and the
    multiplicative depth is exactly 1.
    """
    diff_x = enc_a_x - enc_b_x
    diff_y = enc_a_y - enc_b_y

    sq_x = diff_x * diff_x
    sq_y = diff_y * diff_y

    return sq_x + sq_y

def apply_dp_noise(decrypted_distances: np.ndarray, sensitivity: float, epsilon: float) -> np.ndarray:
    """
    Post-decryption DP calibration. Sensitivity for Euclidean distance on
    bounded coordinates is typically the max coordinate range. Returns
    non-negative sanitized distances ready for release.
    """
    scale = sensitivity / epsilon            # Laplace scale b = Δf / ε
    noise = np.random.laplace(loc=0.0, scale=scale, size=decrypted_distances.shape)
    return np.maximum(decrypted_distances + noise, 0.0)  # enforce non-negative distances

In a multi-node deployment, the encrypted batches and their decryption requests move across the message broker described in async routing for MPC; bind each ciphertext to a round nonce so a stale batch can never be replayed into an aggregate.

Reference Implementation

The runnable harness below wires all three stages together against a plaintext baseline and asserts that the encrypted squared-distance result tracks the cleartext computation within the CKKS error tolerance. Fail the build on any violation rather than reviewing tolerances by hand.

import numpy as np
import tenseal as ts


def run_he_spatial_harness() -> None:
    """End-to-end validation: encode → encrypt → distance → decrypt vs. plaintext."""
    context = initialize_ckks_context(
        poly_modulus_degree=8192,
        coeff_mod_bit_sizes=[40, 21, 21, 21, 40],
        scaling_factor=2**21,
    )
    validate_modulus_chain(context, required_depth=1)

    # Two small batches of bounded, projected coordinates (metres / 1e5 scale).
    rng = np.random.default_rng(42)
    a = rng.uniform(0.0, 1.0, size=(64, 2))
    b = rng.uniform(0.0, 1.0, size=(64, 2))
    validate_encoding_capacity(context, n_points=a.shape[0], poly_modulus_degree=8192)

    enc_a_x, enc_a_y = encode_and_encrypt_coordinates(context, a)
    enc_b_x, enc_b_y = encode_and_encrypt_coordinates(context, b)

    enc_sq = compute_encrypted_euclidean_distances(enc_a_x, enc_a_y, enc_b_x, enc_b_y)
    decrypted = np.asarray(enc_sq.decrypt())

    # Plaintext baseline for the same squared-distance operator.
    baseline = np.sum((a - b) ** 2, axis=1)

    rel_err = np.max(np.abs(decrypted - baseline) / np.maximum(baseline, 1e-9))
    assert rel_err < 1e-3, f"CKKS precision out of tolerance: {rel_err:.2e}"

    # DP release must never emit a negative distance.
    released = apply_dp_noise(decrypted, sensitivity=1.0, epsilon=1.0)
    assert np.all(released >= 0.0), "DP release produced a negative distance"

    print(f"[PASS] HE spatial harness — max relative error {rel_err:.2e}")


if __name__ == "__main__":
    run_he_spatial_harness()

Threat Model Considerations

The adversary model for an encrypted spatial join differs from the gradient-leakage model of federated learning workflows: here the ciphertext itself is exposed to semi-honest compute nodes, so the threats centre on malleability, precision side channels, and key custody.

• Ciphertext malleability: a node tampers with encrypted coordinates to skew the spatial result without ever decrypting.
• Noise/precision exhaustion: an adversary drives evaluation past the modulus-chain depth to force decryption failures whose error structure leaks information.
• Key compromise: a single leaked secret key exposes every plaintext batch retroactively.
• DP–HE composition leakage: correlated queries exploit CKKS precision to recover more than the declared $\varepsilon$ budget should permit.

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 bound — PASS if decrypted outputs track the plaintext baseline within a relative error of $< 10^{-3}$ across the harness above. This is the assertion in run_he_spatial_harness; fail the build on any violation.
2. Modulus-chain depth — PASS if the available levels meet or exceed the multiplicative depth of every planned operator before evaluation begins. Reject the circuit at configuration time, not at decrypt time.
3. Noise-budget monitoring — PASS if remaining levels stay above a 10-bit floor after each operation; dropping below triggers recomputation or bootstrapping rather than a silent garbage decrypt.
4. DP composition accounting — PASS if the cumulative $(\varepsilon, \delta)$ spent across batched spatial queries stays under the declared ceiling, tracked with an RDP accountant. Tie the figure to the obligations in the compliance framework mapping — for example, expressing a GDPR Article 25 data-minimisation requirement as a maximum grid-cell resolution and a per-release $\varepsilon$.
5. Key-custody attestation — PASS if the secret key is provably held only inside the enclave or threshold vault, with signed key-rotation and budget-expenditure logs retained for the regulatory retention window.

Failure Modes & Remediation

Encrypted spatial pipelines rarely fail loudly — they fail by silently degrading either precision or privacy. The high-frequency failure modes:

• CRS mismatch. A batch arrives in EPSG:3857 metres (or with lat/lon swapped) and the fixed-point encoder produces values that are numerically valid but spatially meaningless. Detection: range-check that latitudes fall in $[-90, 90]$ and longitudes in $[-180, 180]$ (or within the projected envelope) before encoding. Recovery: re-project at ingestion and quarantine the offending batch before it reaches the encrypt stage.
• Noise-budget exhaustion mid-query. A circuit deeper than the modulus chain supports returns garbage on decrypt. Detection: the pre-evaluation depth check in control 2 fails for the planned operator. Recovery: raise the polynomial modulus degree, add a level to the chain, or split the computation — covered in depth in practical homomorphic encryption for spatial queries.
• Scaling-factor drift. A masked envelope encoded at a different $\Delta$ than the evaluator expects produces modulus-switching artefacts and coordinate drift past the compliance tolerance. Detection: the relative-error assertion crosses $10^{-3}$. Recovery: pin a single $\Delta$ across masking and evaluation, and re-encode the mismatched batch.
• Privacy-budget exhaustion. Repeated releases over the same population deplete the $(\varepsilon, \delta)$ budget, so further outputs no longer carry the claimed guarantee. Detection: the RDP accountant crosses its ceiling. Recovery: halt releases for that population, coarsen the quantisation grid to spend less per query, or rotate to a fresh cohort.
• Node dropout under threshold decryption. With $t$-of-$n$ key sharing, fewer than $t$ available nodes makes the result unrecoverable. Detection: a missing decryption share at round-completion timeout. Recovery: fail the round atomically (the nonce makes partial state unusable) and re-run, or provision additional standby key holders.

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.

• Practical Homomorphic Encryption for Spatial Queries — the production debugging, validation, and query-routing layer built on these basics.
• Coordinate Masking Protocols — the deterministic front end that produces the masked envelopes this circuit consumes.
• Secret Sharing for Coordinates — the $t$-of-$n$ construction for splitting decryption authority across a quorum.
• Async Routing for MPC — how nonced ciphertexts and decryption requests move across a resilient broker.
• Compliance Framework Mapping — how to translate HIPAA, GDPR, and GLBA mandates into the grid resolution and $\varepsilon$ thresholds used above.