Math Documentation

Full mathematical exposition for the BlindRoute engine. Sources: Fan & Vercauteren (2017), Cheon–Kim–Kim–Song (Eurocrypt 2017), Brakerski–Gentry–Vaikuntanathan (2012).

CLI Quick Start

BlindRoute is a usable CLI toolchain. Download a prebuilt binary from releases or cargo install blindroute, then:

# Generate a key pair
blindroute keygen --out keys/

# Encrypt data (JSON array or one-number-per-line)
echo '[120, 95, 132, 88, 110]' > data.json
blindroute encrypt --pub keys/pub.json --in data.json --out ct.json

# Decrypt
blindroute decrypt --sec keys/sec.json --in ct.json

# Compute on ciphertext
blindroute compute add ct_a.json ct_b.json --out sum.json
blindroute compute mul ct_a.json ct_b.json --out prod.json

1. The ring

Every RLWE scheme works in the cyclotomic ring:

R = Z_q[x] / (x^N + 1),   N a power of two

Ciphertexts are polynomials with coefficients mod a prime q. The dominant cost of every operation is polynomial multiplication modulo x^N + 1.

2. Parameters

The NTT demo uses the small prime:

q = 12289,   q − 1 = 12288 = 2^12 · 3

q ≡ 1 (mod N) for every N = 2k ≤ 2048, so a primitive N-th root of unity exists modulo q for all supported sizes. g = 11 is a primitive root of the multiplicative group.

The CKKS scheme uses a larger 64-bit Goldilocks/Solinas prime:

Q = 2^64 − 2^32 + 1 = 0xFFFFFFFF00000001
Q − 1 = 2^32 · (2^32 − 1)       (NTT roots up to N = 2^32)
N = 128,  Δ = 2^24            (64 complex slots, ~7 decimal digits)

3. NTT / INTT

The Number-Theoretic Transform is the finite-field analogue of the FFT. It maps coefficient multiplication (O(N²)) to O(N log N) pointwise multiplies:

NTT(a)[k] = Σ_j a[j] · ω^{j·k}  (mod q)

We use an iterative, in-place Cooley–Tukey radix-2 DIT with a bit-reversal permutation and a primitive N-th root ω = g^{(q−1)/N}. The inverse uses ω⁻¹ and scales by N⁻¹.

4. RLWE negacyclic multiply

Multiplication modulo x^N + 1: because x^N ≡ −1, the product of two degree-

f    = a · b                (zero-padded to length 2N)
r_j  = f_j − f_{j+N}        for j < N

This is computed with a size-2N cyclic NTT (the embedding trick), reusing the shared NTT core. Bit-exact against schoolbook multiplication.

5. Modular arithmetic

Products a·b reach ≈2⁶⁰, far beyond 32 bits. We use Barrett reduction with a two-word multiplier precomputed once per modulus:

μ     = ⌊2^64 / q⌋                     (precomputed)
q_est = ⌊(value · μ) / 2^64⌋           (u128 intermediate)
r     = value − q_est · q               (≤ one or two corrections)

A single-word multiplier is only accurate when the product fits in 32 bits — which it does not in FHE. The GPU kernel that maps this onto 32-bit lanes (multi-word emulation) is on the roadmap.

6. GPU NTT architecture

The NTT/INTT and pointwise modular multiplication run as WGSL compute shaders dispatched via wgpu, targeting Vulkan, Metal, DX12, and WebGPU from a single shader source.

Kernel dispatch

Each NTT stage is a single compute dispatch: N/2 butterfly pairs per stage across log₂(N) stages. The forward transform reads from a source buffer, applies the Cooley–Tukey butterfly in-place, and writes to a ping-pong buffer. The inverse follows the same pattern with ω⁻¹ and a final scaling by N⁻¹.

32-bit lane emulation

GPUs lack native u64 × u64 → u128 multiply. BlindRoute splits each 64-bit coefficient into two 32-bit limbs and computes the full product via Karatsuba decomposition across four u32 × u32 → u64 multiplies, then reduces with Barrett. The result is bit-exact against the CPU reference.

Benchmark (RTX 3060, Vulkan)

NTT forward  (N=2048):  0.08 ms  (15× vs WASM CPU)
    NTT inverse  (N=2048):  0.09 ms  (14×)
    Pointwise mul (N=2048):  0.004 ms (12×)
    Negacyclic mul (N=1024): 0.14 ms  (13×)

7. CKKS scheme

Canonical embedding

The CKKS encoding maps a complex vector z ∈ ℂ^{N/2} to a polynomial m(X) ∈ ℂ[X]/(X^N+1) such that evaluating m at the primitive 2N-th roots yields z (up to scale Δ):

σ(m)_k = m(ζ^{2k+1})    where ζ = exp(πi/N),  k = 0,…,N−1

In terms of the size-N FFT with twist factor ζj:

σ(m) = N · IDFT( twisted ),   twisted_j = m_j · ζ^j
σ⁻¹(v): m_j = ζ^{−j} · DFT(v)_j / N

RLWE encryption

sk  ← ternary(−1,0,1)           (secret key)
pk  = (−a · sk + e,  a)         (public key, RLWE)
ct  = (v · pk₀ + e₀ + m,  v · pk₁ + e₁)
dec: m ≈ c₀ + c₁ · sk  (mod x^N+1, Q)

Homomorphic operations

add:   (c₀+c'₀, c₁+c'₁)                    (mod x^N+1)
mult:  (c₀c'₀, c₀c'₁+c₁c'₀, c₁c'₁)           (3-component)
dec:   c₀ + c₁·sk + c₂·sk² ≈ m₁·m₂           (product decryption)

8. Threshold secret sharing

To average n values without revealing any:

1. Split each value v into n additive shares r₁,…,rₙ where Σ rⱼ ≡ v (mod p), with p = 2³¹−1 (Mersenne prime, exact in JavaScript).
2. Party j holds the j-th share of every value. Any n−1 shares reveal nothing about v (statistically independent).
3. Summing all shares reconstructs Σ v; the mean is (Σ v)/n as an exact fraction.

This is the honest-MPC building block behind FHE analytics and powers the browser demo.

9. Error / noise budget (roadmap)

Real CKKS/BFV/BGV tracks a noise budget: each multiplication roughly squares the error. Rescaling (modulus switching) and relinearization keep the noise under control. BlindRoute v0.1 supports a single modulus — a full modulus chain (RNS representation) is the next milestone and reuses the exact same NTT core.

10. Tutorials

Encrypted workflow

The complete FHE pipeline with separated roles: Alice generates keys, Bob/Carol/Dave encrypt data, the cloud computes on ciphertext, and Alice decrypts only the final result. No party sees any other's plaintext.

cargo run --example encrypted_workflow

Encrypted average

Five parties compute the mean of their values without revealing any individual value. Each party splits its value into additive shares; shares are summed and the mean is reconstructed from the total.

cargo run --example encrypted_average

Encrypted dot product

Two vectors are encrypted under RLWE and their dot product is computed homomorphically. The result decrypts to the inner product without exposing the input vectors.

cargo run --example encrypted_dot_product

GPU benchmark

Run the NTT/INTT compute shaders on any GPU (Vulkan, Metal, DX12, WebGPU) via wgpu. Measures throughput against the CPU reference — verified bit-exact on RTX 3060.

cargo run --release --bin gpu-bench