Optimizing Fully Homomorphic Encryption for Real-Time Transformer Inference

Abstract

Fully Homomorphic Encryption (FHE) allows Transformer inference to run end to end over encrypted inputs, but where its cost originates has remained unsettled: the encryption scheme, the Transformer's structure, or the library implementing it. This paper answers that question with an operation-level, measurement-first characterisation of a Transformer encoder layer under RNS-CKKS, implemented in TenSEAL over Microsoft SEAL at N = 16384 and Δ = 2⁴⁰. Three results are established by execution. First, the usable multiplicative depth of a chain of L primes is L − 2, not L − 1: a nine-prime chain of 400 bits admits exactly seven sequential ciphertext–ciphertext multiplications, and SEAL accepts that chain while rejecting a ten-prime chain of 440 bits against a 438-bit ceiling. Second, a level-by-level trace shows that a complete softmax requires eleven multiplicative levels and a complete encoder layer thirty-three, against the seven available; the softmax attempt aborts with a scale-overflow exception at the operation the trace identifies, so the depth wall is observed rather than asserted. Third, fully encrypted single-head attention (n = 8, dₖ = 16) reproduces the plaintext reference to a maximum absolute error of 3.19×10⁻⁶ and a cosine similarity of 0.9999999993, executing 384 ciphertext–plaintext multiplications, 2048 ciphertext–ciphertext multiplications and 1536 rotations counted by instrumentation. A cost model built on these counts places the compute-only latency of one encoder layer at 268.7 s under the layout implemented and 7.0 s under diagonal packing — a 38-fold span identifying ciphertext packing, not parameter choice, as the dominant lever. We further report three effects belonging to the library rather than the mathematics: an algebraically identical rewriting accelerates the Goldschmidt reciprocal by 29 to 31×; the vector-packing helper silently consumes one multiplicative level; and the ciphertext copy costs several times the reduction beside it. Because execution was on a shared virtual machine, host interference was measured rather than assumed and the full measurement set was run twice. Both sessions exceeded the discard threshold (coefficients of variation 38.7 % and 24.4 %), and the pair separates the results by class: all seven deterministic quantities are identical, the interleaved paired ratios agree to within 4.6 %, and absolute latencies differ by up to 27 %. Absolute latencies are therefore quoted as intervals and marked provisional; the depth accounting, level traces, operation counts, fidelity and parameter validation are final. Encrypted Transformer inference remains three to four orders of magnitude from the sub-100 ms real-time target; the contribution is an itemised, reproducible budget with an explicit account of which entries are measurements and which are projections.