A real workload: an FHE bootstrap

Fully homomorphic encryption lets a server compute on encrypted data. Its most expensive step is the bootstrap, which refreshes a ciphertext’s noise budget. A CKKS bootstrap runs four stages: ModRaise, CoeffToSlot (homomorphic linear transforms built from rotations and key switching), EvalMod (a polynomial approximation of the modular reduction) and SlotToCoeff. Every stage is full of number-theoretic transforms over many residue limbs, which is why a photonic NTT engine is interesting here.

This chapter replays two real bootstraps recorded from instrumented OpenFHE: sparse16 (N = 65,536, 1,732 kernels) and full14 (N = 16,384, 3,917 kernels), on an FPGA card with HBM, a PCIe host link and the module behind one QSFP56 port.

Each kernel of the trace becomes a demand on six resources: HBM bytes (limbs, evaluation keys and plaintexts unless cached in on-chip SRAM), FPGA add-equivalents, optical symbol slots on the module, bits through the port in each direction, and PCIe for the ciphertext. Kernels run in recorded order (OpenFHE ran single-threaded); a kernel takes its largest demand over capacity plus a latency. A SimPy replay then cuts kernels into bursts that contend for the same servers and SRAM buffers, which gives the utilisation over time shown above.

The capacities: HBM at 819 GB/s datasheet with 0.8 illustrative achievable, one port at 25 GB/s datasheet, 64 illustrative butterfly units at 400 MHz illustrative, and the module at 14 GBd paper on 1 paper wavelength. The replay’s FPGA-only time is within a fraction of the analytic bound (ratio 1.011 for sparse16).

FPGA-only, memory binds the key-switching stages. A bootstrap takes 87.44 ms (sparse16) and 95.59 ms (full14) on 64 butterfly units. CoeffToSlot and SlotToCoeff stream evaluation keys from HBM and are HBM-bound (CoeffToSlot is HBM-bound for 70.6 % of its time insparse16), while EvalMod and ModRaise are dominated by NTTs and bound by FPGA compute. Over the whole bootstrap HBM binds for 42.4 % of the time in sparse16 and 61 % in full14.

With the NTTs on the module, the module binds every stage. At the paper’s operating point the bootstrap is 51.55× slower for sparse16 (4.507 s) and 31.98× slower forfull14. The module is busy 93.7 % of the time and the return port 50.9 %: a w-bit butterfly costs w symbol slots, and one wavelength at this baud delivers far fewer butterflies than the FPGA’s units. Splitting the NTT stages between FPGA and module (hybrid) halves the damage but does not remove it.

The ceiling is low anyway. NTTs are 46.2 % of the FPGA-only time in sparse16 and 28.6 % in full14, so even infinitely fast NTTs would give at most 1.858× and 1.402×. More FPGA logic makes the bootstrap HBM-bound (from 87.44 ms at the default down to 52.97 ms at the largest swept FPGA, where memory has the last word); more HBM bandwidth alone gets sparse16to 61.05 ms at the top of the HBM sweep. Keeping up with the fastest swept module (112 GBd × 8 λ) would take 34.76 QSFP56 ports’ worth of bandwidth.

The trace is real: kernel kinds, counts and order come from OpenFHE. The costs are not. The FPGA’s logic budget and cost per butterfly, the HBM efficiency and latency, the SRAM caching policy, and the module’s framing and port behaviour are illustrative or datasheet values. To trust the absolute times one would need a real FPGA implementation of the bootstrap kernels (resources, clock and power), measured HBM traffic per kernel, and the module’s sustained throughput and latency behind a real port, including its framing and retries. The direction of the result is robust to all of these: the module would have to get orders of magnitude faster, and its port with it, before NTT placement matters more than HBM.