FHE Homomorphic Multiply:
168us to 24us (86% Faster)

Homomorphic multiplication is the most expensive operation in FHE. It's what enables computation on encrypted data, but it's also what makes FHE slow. We took our multiply operation from 168 microseconds to 24 microseconds - an 86% reduction that makes real-time encrypted computation possible.

Why Homomorphic Multiply is Hard

In BFV encryption, ciphertexts are polynomials with very large coefficients. A single coefficient might be 109 bits. When you multiply two ciphertexts:

• You're multiplying polynomials of degree 4,096+
• Each coefficient multiplication can overflow 128 bits
• The result needs modular reduction back to the ciphertext space
• Relinearization is required to keep ciphertext size bounded

Our initial implementation handled this correctly but slowly. Every multiplication involved arbitrary-precision arithmetic to handle overflow, followed by expensive modular reduction.

In H33's production BFV configuration, we use N=4096 with a single 56-bit modulus Q and plaintext modulus t=65537. This parameter set targets 128-bit security while keeping the polynomial ring small enough for sub-millisecond operations. The challenge is that even at N=4096, a naive polynomial multiply requires N-squared coefficient multiplications -- over 16 million operations. The Number Theoretic Transform (NTT) reduces this to O(N log N), but the constants still matter enormously when you need to sustain 1.595 million authentications per second across 96 parallel workers.

The RNS Breakthrough

The key insight is the Residue Number System (RNS). Instead of working with one giant 109-bit modulus, we decompose it into several smaller moduli that fit in 64 bits:

The Chinese Remainder Theorem guarantees we can reconstruct the full result from the residues. But the magic is: for most operations, we never need to reconstruct. We can add, subtract, and multiply entirely in RNS form.

// Before: Big integer multiplication
let result = bigint_mul(a, b);  // Slow, allocates
let reduced = result % Q;       // Even slower

// After: RNS multiplication (parallel)
let r1 = (a.r1 * b.r1) % q1;   // 64-bit, fast
let r2 = (a.r2 * b.r2) % q2;   // 64-bit, fast
// No reconstruction needed for most operations!

Montgomery Reduction: Eliminating Division

Even with RNS, each 64-bit modular multiplication still requires a modular reduction step. The textbook approach uses integer division, which on ARM Graviton4 costs 20-40 cycles per operation. Across 4,096 coefficients and multiple RNS channels, that adds up to tens of microseconds of pure division overhead.

Montgomery reduction replaces division with a sequence of multiplications and bit-shifts. The idea is to work in a transformed "Montgomery domain" where reduction is achieved by multiplying by a pre-computed inverse and right-shifting by R (a power of two). Entering and leaving the domain each costs one multiplication, but once inside, every reduction is division-free.

// Montgomery REDC: no division in the hot path
fn mont_reduce(t: u128, q: u64, q_inv: u64) -> u64 {
    let m = (t as u64).wrapping_mul(q_inv);
    let reduced = (t + (m as u128) * (q as u128)) >> 64;
    if reduced >= q as u128 { (reduced - q as u128) as u64 }
    else { reduced as u64 }
}

In H33's NTT pipeline, twiddle factors are stored permanently in Montgomery form. The secret key is also kept in NTT-domain Montgomery representation after keygen. This means the forward and inverse NTT transforms -- which dominate the cost of multiply -- never leave the Montgomery domain. The net effect: two REDC operations per butterfly instead of two divisions, a roughly 2x improvement in the NTT inner loop.

NEON Vectorization

With RNS, our coefficients fit in 64 bits. This unlocks SIMD parallelism. ARM NEON can process two 64-bit multiplications simultaneously:

// Process 2 coefficient multiplications at once
let a_vec = vld1q_u64(&a_coeffs[i]);
let b_vec = vld1q_u64(&b_coeffs[i]);
let prod = vmulq_u64(a_vec, b_vec);
let result = montgomery_reduce_neon(prod, q_vec);
vst1q_u64(&mut out[i], result);

Combined with Montgomery reduction (from our encryption optimizations), each coefficient multiply-reduce takes just a few cycles. One important caveat: ARM NEON lacks a native 64x64-to-128-bit multiply instruction, so the full Montgomery REDC must extract to scalar for the widening multiply and then repack. NEON still wins on the add, subtract, and compare steps of the butterfly, and the vectorized loads and stores eliminate memory stalls that would otherwise dominate at N=4096.

The Complete Picture

The final 10% gain -- from 26.7us to 24us -- came from Harvey lazy reduction, where butterfly outputs are kept in the range [0, 2q) rather than fully reduced to [0, q) between NTT stages. This eliminates one conditional subtraction per butterfly, which at 4,096 * log2(4,096) = 49,152 butterflies per transform, saves roughly 50,000 branch predictions.

vs Microsoft SEAL

SEAL is the industry standard for FHE. It's well-engineered and widely used. Here's how we compare:

The difference comes from:

• Better RNS implementation - Our RNS base switching is more efficient
• ARM-first design - We optimized for NEON from day one; SEAL targets AVX-512
• Zero-copy operations - Pre-allocated buffers eliminate malloc overhead

Production Impact: 32 Users Per Ciphertext

Fast multiply is necessary but not sufficient. The real production win comes from SIMD batching: H33 packs 32 user biometric templates into a single BFV ciphertext using 4,096 plaintext slots (4,096 slots / 128 embedding dimensions = 32 users). This means one homomorphic inner product -- which involves multiply_plain followed by accumulate -- processes an entire batch of 32 authentications simultaneously.

What This Enables

At 24 microseconds per multiply, encrypted computation becomes practical for real-time applications:

• Biometric matching: Compare encrypted face embeddings in ~260us total
• Encrypted search: Run queries over encrypted databases
• Private ML inference: Neural network inference on encrypted data

When your competitors are at 180+ microseconds per multiply, you can do 7x more computation in the same time budget. That's the difference between "FHE is a research toy" and "FHE is production ready."

Key Takeaways

1. RNS is mandatory - If you're doing FHE without RNS representation, you're not competitive.
2. Design for SIMD from the start - Retrofitting vectorization is painful. We designed our data structures for NEON from day one.
3. Montgomery + RNS is the winning combo - Each technique gives you 2-4x; together they compound.
4. Stay in the transform domain - Converting between coefficient and NTT form is expensive. Keep ciphertexts, keys, and twiddles in their optimal domain and minimize round-trips.
5. Measure at production scale - Micro-benchmarks lie. An optimization that wins on a single core can regress under 96-worker contention due to L1 cache pressure. Always validate on the target hardware at full parallelism.

This is part 3 of our performance series. Next: we'll show the complete optimization journey and what it means for quantum-resistant authentication.