Encrypted Spatial Range Queries with CKKS

A within-radius spatial predicate — is candidate point pp inside radius rr of query point qq? — is one line in plaintext and genuinely awkward under homomorphic encryption, because the CKKS scheme that makes encrypted floating-point geometry practical has no native comparison. You can add, subtract, and multiply ciphertexts, so an encrypted squared distance d2=dx2+dy2d^2 = dx^2 + dy^2 is cheap, but the final d² ≤ r² test has to be built out of arithmetic. This page shows how to evaluate an encrypted spatial range query end to end with CKKS: compute the encrypted distance over a SIMD-batched batch of candidate points, approximate the step function d² ≤ r² with an odd polynomial so the server returns an encrypted match mask it never learns, and manage the multiplicative depth that approximation costs. It sits under homomorphic encryption basics in the Secure Multi-Party Computation in Spatial Analytics architecture. Where you need an exact additive operation instead of approximate real arithmetic, reach for coordinate masking with Paillier encryption; where the join is set membership rather than a geometric radius, use private set intersection for spatial joins.

The defining property to keep in front of you: CKKS is approximate. Every ciphertext carries a small numeric error, and the polynomial that stands in for the comparison amplifies it near the decision boundary. That is acceptable for a coarse range flag — a point clearly inside or clearly outside r decrypts to a mask value close to 1 or 0 — but the error has to be bounded and measured, never assumed away. Unlike Paillier, which is exact but supports only ciphertext addition, CKKS buys you multiplication and SIMD batching at the cost of a controlled approximation budget.

Parameter Configuration and Calibration

The range predicate is a depth-hungry circuit: distance costs one multiplicative level, and each iteration of the polynomial that sharpens the step function costs several more. Size the modulus chain to that depth before you encrypt, because a chain one prime short returns garbage on decrypt rather than a small error.

Parameter Value Rationale
poly_modulus_degree 32768 Carries the ~12-level chain the comparison needs and packs 16384 candidate points into one ciphertext; 16384 is only deep enough for a coarse k ≤ 2 flag.
coeff_mod_bit_sizes [60, 40×11, 60] Head/tail primes at 60 bits for encode/decode precision; the eleven 40-bit rescale primes fund distance (1) + normalisation (1) + the sign iterations (~2 each).
global_scale (Δ) 2**40 Fixed-point precision. At 2402^{40} the encoding error on a normalised coordinate stays far below the polynomial’s own approximation error, so Δ is never the dominant term.
S — normalisation bound D_max² Public scalar that maps (r2−d2)(r^2 - d^2) into [−1,1][-1, 1], the domain where the odd sign polynomial converges. Set it to the squared diagonal of the working extent.
SIGN_ITERS (k) 5 Iterations of the sharpening polynomial. More iterations = a crisper step and a narrower guard band, but +2 levels each.
guard_m — guard band set by k, S Metric half-width around r where the mask is treated as indeterminate. A small radius relative to the extent compresses the inside band, so a coarse S widens the guard band.

The comparison itself is built from the normalised quantity t=(r2−d2)/S∈[−1,1]t = (r^2 - d^2)/S \in [-1, 1]: t>0t > 0 means inside, t<0t < 0 means outside. CKKS cannot branch on the sign of tt, so the circuit approximates sign⁡(t)\operatorname{sign}(t) with the classic odd polynomial g(x)=32x−12x3g(x) = \tfrac{3}{2}x - \tfrac{1}{2}x^3 composed kk times — each pass pushes values in [−1,1][-1, 1] toward ±1\pm 1 and flattens the middle. The match mask is then m=(g∘k(t)+1)/2m = (g^{\circ k}(t) + 1)/2, which decrypts near 11 for interior points and near 00 for exterior ones. The convergence is slowest for points near the radius, where t≈0t \approx 0 — the direct cause of the guard band — and for a small radius in a large extent the inside band t∈(0,r2/S]t \in (0, r^2/S] is narrow, so it needs either more iterations or a tighter S. Quantise the input coordinates to the same grid used for the dataset’s spatial sensitivity score so the encoding doubles as a coarsening control, and bind Δ and the guard band to a clause through the compliance framework mapping.

Encrypted spatial range query: encrypt, batched distance, polynomial comparison, decrypt mask Left to right. In the client zone (holds the secret key) the client encrypts the query point and squared radius to a ciphertext. Across a dashed trust boundary, the server's encrypted zone takes a batch of database points in N/2 SIMD slots, computes encrypted d² = dx² + dy² per slot at depth 1, normalises to t = (r² − d²)/S in the range −1 to 1, and evaluates the composed sign polynomial g(t) k times to an encrypted match mask at depth 2k. The mask returns across a second trust boundary to the client, which decrypts it to 1 for inside points and 0 for outside points, with an approximate guard band near the radius. Coordinates and the mask stay encrypted on the server; only the client decrypts. Encrypted range query — batched distance, polynomial comparison, encrypted mask Client · secret key Server · encrypted compute (semi-honest) Client · decrypt trust boundary trust boundary Encrypt query point (λᵽ, φᵽ) + radius² r² → ciphertext Batched DB points N/2 slots: (xᵢ, yᵢ) Encrypted d² dx² + dy² /slot depth 1 Normalise t=(r²−d²)/S → [−1, 1] Sign polynomial g∘g(t), k iters → encrypted mask depth 2k Decrypt mask 1 = inside r 0 = outside r approx near boundary enc. enc. mask Coordinates and the match mask stay encrypted on the server; only the client decrypts.

Reference Implementation

The function below is the HE path: it takes a CKKS context and encrypted per-axis vectors, computes the encrypted squared distance, normalises it, and applies the composed sign polynomial to return an encrypted match mask. It uses the TenSEAL API (tenseal), which wraps Microsoft SEAL. TenSEAL is frequently unavailable in CI, so the validation harness below mirrors the identical arithmetic in pure Python — the numbers, the polynomial, and the guard band are the same, only the ring is replaced by ordinary floats.

python
from __future__ import annotations

from typing import List

# --- HE PATH (requires: import tenseal as ts) --------------------------------
# This block runs against a real CKKS backend. The plaintext mirror used by the
# validation harness lives in the next section and reproduces the same maths.

SIGN_ITERS: int = 5          # composed passes of g(x) = 1.5x - 0.5x^3
NORM_BOUND: float = 2.0      # S: squared diagonal of the working extent


def _sign_poly_ct(x: "ts.CKKSVector", iters: int) -> "ts.CKKSVector":
    """Approximate sign(x) on [-1, 1] via g(x) = 1.5x - 0.5x^3, composed `iters`
    times. Each pass costs ~2-3 multiplicative levels; budget the modulus chain
    for `2 * iters` before encrypting or the decrypt returns noise, not a flag.
    """
    y = x
    for _ in range(iters):
        cube = y * y * y            # depth 2: y^2 then * y (relin auto)
        y = (y * 1.5) + (cube * -0.5)
    return y


def encrypted_range_mask(
    context: "ts.Context",
    enc_qx: "ts.CKKSVector", enc_qy: "ts.CKKSVector",   # query point, per axis
    enc_px: "ts.CKKSVector", enc_py: "ts.CKKSVector",   # batched DB points, per axis
    r_squared: float,
    norm_bound: float = NORM_BOUND,
    iters: int = SIGN_ITERS,
) -> "ts.CKKSVector":
    """Return an ENCRYPTED per-slot match mask for `d^2 <= r^2`.

    The server never learns which points fall inside the radius: it returns a
    ciphertext whose slots decrypt (client-side) to ~1 for interior points and
    ~0 for exterior points. CKKS is approximate, so slots within the guard band
    around r are indeterminate and MUST NOT be treated as a hard membership bit.
    """
    # Encrypted squared Euclidean distance, slot-aligned, depth 1.
    dx = enc_qx - enc_px
    dy = enc_qy - enc_py
    d2 = (dx * dx) + (dy * dy)                     # per-slot dx^2 + dy^2

    # Normalise to t = (r^2 - d^2)/S in [-1, 1]; t > 0 means inside.
    # (d2 - r^2) * (-1/S) keeps a single plaintext-scalar multiply.
    t = (d2 - r_squared) * (-1.0 / norm_bound)

    # Polynomial stand-in for the comparison: no native CKKS compare exists.
    s = _sign_poly_ct(t, iters)                   # -> ~+1 inside, ~-1 outside
    mask = (s + 1.0) * 0.5                         # -> ~1 inside, ~0 outside
    return mask

Every operation here is a ciphertext multiply or add — there is no branch, no decrypt, and no plaintext coordinate on the server. That is exactly why the comparison has to be a polynomial: a Paillier-style scheme could not multiply two ciphertexts to form d2d^2 at all, which is the concrete reason CKKS, not Paillier, is the right tool for a geometric radius test.

Validation Checkpoint

The harness below is the plaintext-reference path. It reproduces encrypted_range_mask with NumPy floats — same normalisation, same g(x)g(x), same guard band — so the invariants run in CI without TenSEAL installed. The assertion is the load-bearing one: the polynomial mask must agree with a direct NumPy range flag for every point clearly inside or outside the radius, within tolerance, and the round-trip distance must match np.sum((a-b)**2) exactly.

python
import numpy as np


def _sign_poly_plain(x: np.ndarray, iters: int) -> np.ndarray:
    """Plaintext mirror of _sign_poly_ct: g(x) = 1.5x - 0.5x^3, composed."""
    y = x
    for _ in range(iters):
        y = 1.5 * y - 0.5 * y ** 3
    return y


def range_mask_plain(
    q: np.ndarray, pts: np.ndarray, r_squared: float,
    norm_bound: float = 2.0, iters: int = 5,
) -> np.ndarray:
    """Plaintext reference for the encrypted circuit; returns per-point mask."""
    d2 = np.sum((pts - q) ** 2, axis=1)              # dx^2 + dy^2
    t = np.clip((r_squared - d2) / norm_bound, -1.0, 1.0)   # normalise to [-1, 1]
    s = _sign_poly_plain(t, iters)
    return (s + 1.0) * 0.5


def _validate() -> None:
    rng = np.random.default_rng(7)
    q = np.array([0.0, 0.0])
    pts = rng.uniform(-1.0, 1.0, size=(400, 2))      # working extent, S = 2.0
    r = 0.70
    r2 = r * r

    # 1. Encrypted-circuit distance must equal the direct NumPy distance.
    d2_ref = np.sum((pts - q) ** 2, axis=1)
    d2_direct = np.array([(p[0]-q[0])**2 + (p[1]-q[1])**2 for p in pts])
    assert np.allclose(d2_ref, d2_direct, atol=1e-12), "distance mismatch"

    # 2. The polynomial mask must match the true range flag away from r.
    #    Points inside the guard band around r are excluded by design — that is
    #    exactly where the approximation is untrustworthy.
    mask = range_mask_plain(q, pts, r2, norm_bound=2.0, iters=5)
    dist = np.sqrt(d2_ref)
    clearly_inside = dist < (r - 0.25)               # guard band below the radius
    clearly_outside = dist > (r + 0.35)              # guard band above the radius
    assert np.all(mask[clearly_inside] > 0.9), "interior points not flagged"
    assert np.all(mask[clearly_outside] < 0.1), "exterior points not rejected"

    # 3. The mask stays in [0, 1] everywhere, including the ambiguous band.
    assert mask.min() > -0.05 and mask.max() < 1.05, "mask escaped [0,1]"

    print("[PASS] CKKS range-query plaintext reference matches direct NumPy flag")


if __name__ == "__main__":
    _validate()

The tolerance is deliberate: points inside the guard band (r - guard < dist < r + guard) are excluded from the strict assertion because that is precisely where the approximation is untrustworthy, and pretending otherwise would encode a bug as a passing test.

Incident Response and Edge Cases

Encrypted range queries fail quietly — a wrong flag looks exactly like a right one until you decrypt something you can cross-check. The failures that actually surface:

  • Noise-budget / depth exhaustion. The sign polynomial at SIGN_ITERS=5 needs ~12 levels — far more than a chain sized for one multiply — so the mask decrypts to noise centred nowhere near 0 or 1. Detection: pre-compute circuit depth (11 for distance, 11 for normalisation, ≈2k\approx 2k for the polynomial) and reject any context whose available levels fall short before encrypting. Remediation: add rescale primes to coeff_mod_bit_sizes, raise poly_modulus_degree to 32768 or 65536, reduce iters (accepting a wider guard band), or bootstrap. The general depth-budgeting recipe is in practical homomorphic encryption for spatial queries.
  • Approximation error near the boundary. A point at d≈rd \approx r maps to t≈0t \approx 0, where g∘kg^{\circ k} is flat and the mask hovers near 0.50.5. Threshold it as a hard bit and you get non-deterministic membership right at the radius. Detection: audit-sample decrypted masks and flag any slot in [0.1,0.9][0.1, 0.9]. Remediation: widen guard_m, add a sign iteration, or return the raw mask for borderline slots and resolve them with a second, exact pass rather than rounding.
  • Scale / level mismatch. Adding or subtracting two operands at different rescale levels or scales — for example a freshly encrypted r² against a d² that has already been rescaled once — raises a scale-mismatch error or silently drifts the result. Detection: assert both operands report the same scale and level before every add. Remediation: mod-switch the shallower operand down to match, and fold r² in as a plaintext scalar (as the reference does) instead of a separate ciphertext so it never accrues a divergent scale.
  • Normalisation overflow. If S under-estimates the true extent, tt leaves [−1,1][-1, 1] and g(x)g(x) diverges instead of converging, turning the mask into an amplified error. Detection: range-check that the plaintext-reference tt stays in [−1,1][-1, 1] for the dataset’s bounding box. Remediation: set S to the squared diagonal of the actual working extent, not a unit box, and clip in the plaintext mirror to catch it in CI.

Frequently Asked Questions

CKKS has no comparison operator — how does it produce a range flag at all?

By approximating the step function arithmetically. Normalise the gap to t = (r² − d²)/S so it lands in [−1, 1] and its sign encodes inside/outside, then apply the odd polynomial g(x) = 1.5x − 0.5x³ composed two or three times. Each pass pushes values toward ±1 and flattens the middle, so the composition approaches sign(t). Rescale and shift to (g(t)+1)/2 and you get an encrypted mask that decrypts near 1 inside the radius and near 0 outside — all from adds and multiplies, with no branch and no decryption on the server.

CKKS is approximate — why is that acceptable for a range query?

Because a within-radius test is a coarse flag, not a precise measurement. A point well inside or well outside the radius decrypts to a mask value close to 1 or 0, and small numeric error there changes nothing. The error only bites in a narrow band around r itself, which is why the guard band exists: points within it are declared indeterminate rather than forced to a bit. The requirement is that the error be bounded and measured — validated against a plaintext reference and kept below the guard-band width — not that it be zero.

When should I use Paillier instead of CKKS for a spatial predicate?

Use Paillier when the operation is exact and additive-only — summing masked coordinate offsets, tallying counts, aggregating an encrypted histogram — where its exact integer arithmetic is a feature and you never need to multiply two ciphertexts. A radius test needs dx² + dy², a ciphertext-by-ciphertext multiplication Paillier cannot perform, plus a comparison. CKKS supports both multiplication and SIMD batching, at the cost of approximate reals and multiplicative-depth management. Choose Paillier for exact additive masking, CKKS for geometric distance and range logic.

How many candidate points fit in one ciphertext, and how does batching help?

A CKKS ciphertext at poly_modulus_degree 32768 holds N/2 = 16384 SIMD slots, so up to 16384 candidate points evaluate in a single distance-and-comparison circuit — one homomorphic pass returns 16384 encrypted flags. Pack each axis into its own ciphertext (all x-coordinates in one, all y in another) so subtraction and squaring stay slot-aligned and no rotation is needed. Batching is what makes the scheme viable for metropolitan-scale candidate sets: the expensive polynomial runs once across the whole batch rather than per point.

Up: Homomorphic encryption basics · Secure Multi-Party Computation in Spatial Analytics