THOR: Non-Interactive Transformer Inference with Pure HE

0. At a Glance

In one sentence: THOR is a non-interactive, pure-HE Transformer inference system — the server holds plaintext weights, the activations stay in CKKS ciphertext throughout, and the client performs exactly one upload and one download with zero intermediate rounds of communication; it rewrites matrix multiplication as "diagonal element-wise products + rotation accumulation", then uses compact packing with c = 16 together with two scheduling strategies (blocking and BSGS) to drive the rotation count down, cutting the end-to-end latency of BERT-base with 128 tokens from NEXUS's 2.7 hours to 602 s (10.04 minutes) on a single GPU.

Four numbers (full provenance in §3):

How to read it: this paper does exactly one thing — cut down rotations (= key switches). It introduces no new cryptographic assumption, does not change the encoding theory, and does not touch the threat model; all of the gain comes from "a better arrangement of the same mathematical identity". And once the cutting is done, 56% of the remaining time is bootstrapping, and that ratio is itself the most informative conclusion of the paper: the next battleground for pure-HE inference is no longer matrix multiplication but the bootstrap.

1. Problem and Positioning

1.1 Three routes, three ways of being "expensive"

Pure HE is extremely attractive in principle: 0 rounds of interaction, a communication volume equal only to the ciphertext size (independent of the number of layers), no per-layer masks to prepare on the server, and no online generation of correlated randomness. The price is that three hard constraints press in at the same time:

1. Few slots: N = 2^16 → s = 2^15 = 32768 CKKS slots; yet a 128 × 768 activation holds 98304 numbers, which does not fit into one ciphertext.
2. Limited multiplicative depth: 13 levels, whereas diagonal multiplication with n = 128 inherently needs a Mult/Rot chain of log n levels or more.
3. Rotations are the most expensive: every rotation costs one key switch, and every rotation amount requires an evaluation key uploaded in advance.

The bet the authors place is stated bluntly: "diagonal representation + compact packing", plus one inconspicuous engineering decision with global consequences — push all transposes to the plaintext side.

1.2 Divergence from BOLT (the one judgment in this paper most worth recording)

BOLT is an MPC-HE hybrid framework (BFV leveled HE + secret sharing to reset noise), and its primary optimization target is keeping multiplicative depth low, so that BFV can avoid bootstrapping. THOR's judgment is: the tuition BOLT pays to be "bootstrap-free" (more key switches, a heavier ciphertext-by-ciphertext protocol) is more expensive than bootstrapping itself. So THOR goes the other way — accept bootstrapping, and shape matrix multiplication so that it rotates very little, buying a bootstrap only where the non-linear operations genuinely need one. This trade-off is the skeleton of the whole paper, and §2.4 and §5.4 return to it repeatedly.

1.3 How much substance the five contributions have

2. Anatomy of the Method

2.1 System architecture and threat model

Two parties: the client (data owner, holds the keys) and the server (model owner, holds the plaintext weights). The protocol is single-round: the client uploads a ciphertext → the server computes the entire network → returns ciphertext logits → the client decrypts.

Three explicit non-goals: it does not protect the model weights (this is not model-private inference), it does not defend against a malicious server (semi-honest only), and it does not cover training/fine-tuning. The security argument is a single sentence: CKKS is semantically secure under RLWE; and key-recovery attacks on CKKS do not apply, because the decryption result only ever returns to the holder of the key.

One easily overlooked consequence: plaintext model weights mean the server may precompute anything — all rotation masks, the diagonal encodings, and the W_Q inside Q^T = W_Q^T X^T can all be computed without the client's knowledge. Almost everything "cheap" about THOR comes from this asymmetry.

2.2 One identity carries the whole paper

Let A ∈ R^{n×m}, B ∈ R^{m×n}, C = AB, with n ≥ m and m | n. Let U_k(A) denote the row vector obtained by flattening the k-th upper diagonal of A, and L_ℓ(B) the flattening of the ℓ-th lower diagonal.

Proposition 3.6 (diagonal multiplication identity)
 
  L_r(AB) = Σ_{ℓ∈[m]}  ρ^r( U_{ℓ−r}(A) ) ⊙ L_ℓ(B)        r = 0, 1, …, m−1
 
  where ρ is "cyclic shift right by r positions" (= one ciphertext rotation),
  the subscript ℓ−r of U_{ℓ−r}(A) is taken modulo m, and ⊙ is slot-wise multiplication.

Reading: the r-th lower diagonal of C equals the sum of the element-wise products of the upper diagonals of A, offset by r positions, with the corresponding lower diagonals of B. The whole of AB is therefore "one rotation per diagonal, m of them + m element-wise products + one summation".

Figure 1: Diagonal multiplication, n = 3. Each color is one diagonal; each row is one ρ^r(U) ⊙ L, and the three rows add up to one diagonal of the output ciphertext.

The identity itself is not new (every diagonal-packing scheme since Gazelle uses it); THOR's contribution is the arrangement built around it. To understand every later optimization, the key is to first remember the relative price of the four kinds of operation in CKKS:

Operation            Symbol  Price        Why
Addition             +       free         no noise growth, no key
Ciphertext×plaintext PMult   cheap        one multiplication + rescale (rescale can be saved with lazy)
Ciphertext×ciphertext Mult   expensive    must relinearize after the tensor product (one key switch)
Rotation             ρ       most expensive  always a key switch; the rotation amount fixes the key set, so it must be pre-uploaded

The paper has exactly one optimization target: cut rotations (and the key switches they bring). Nowhere does it try to save additions, and nowhere does it try to save multiplications — because additions are free to begin with, and multiplications are far cheaper than rotations.

2.3 Four cost levers (plus two small ones)

All four levers act on the same formula, but they save different resources:

Lever 1: Push the transpose to the plaintext side

X ∈ R^{n×d} is transposed on the client into X^T ∈ R^{d×n} before upload, so:

Q^T = W_Q^T · X^T        plaintext × ciphertext, zero rotations
K^T, V^T likewise        W is pre-transposed by the server offline; the client never transposes a ciphertext
when a "transposed activation" is needed   use the U/L swap of viewpoint instead of a real transpose (Lemma 3.3)
a genuine ciphertext transpose             one rotation + index reversal, costing about n rotations (Lemma 3.4)

Lemma 3.3 gives the key free relation U_k(A) = L_k(A^T) (indices unchanged, only the viewpoint swapped), and Lemma 3.4 gives L_ℓ(A) = ρ^{−m+ℓ}( U_{m−ℓ}(A) ) (one rotation + the flip ℓ ↔ m−ℓ). The entire inference therefore runs in the "transposed state": only X^T goes in and X^T comes out, and the shape of W is pre-transposed by the server. This is the cheapest trick in the paper and the easiest one to miss when reproducing it — it turns the cost of transposition from "n² rotations per layer" into "zero".

Lever 2: c = 16 compact packing

A diagonal has length only n, while there are 32768 slots — using them directly wastes 99.6%, leaving only 0.39% utilized. THOR does two-level packing:

First level, interlace: interleave the H heads along the diagonal direction
  L̄_ℓ(A)[t] = L_ℓ( A^{(t mod H)} )[ ⌊t/H⌋ ]        t ∈ [nH]
 
Second level, concat: concatenate c blocks into one ciphertext
  L̂_j(A) = ( L̄_{cj} | L̄_{cj+1} | … | L̄_{c(j+1)−1} ) ∈ R^s
 
Constraint: s = c·n·H, with c = ⌊s/(nH)⌋ rounded down to a power of two
  Plugging in n=128, H=12, s=2^15 → c ≤ 21.3 → c = 16

Result: the input/output boundary of one encoder layer needs only 8 ciphertexts (n/c), with 75% slot utilization; and the c blocks can draw on one another via "internal rotation" (a within-slot shift that costs no key switch), further removing cross-block rotations. c is not a free parameter: it is pinned down by s/(nH), and Table 1 shows that the rotation count decreases monotonically with c, so the real ceiling is the slot count s (and the slower ciphertexts that a larger N brings).

Lever 3: DiagBlock PC-MM

Applying Proposition 3.6 directly to R^{d×d} × R^{d×n} gives d = 768 diagonals, one rotation each → the rotation count is proportional to d, and d is exactly the largest dimension. THOR blocks it: partition A into d/n sub-blocks of size n×n, apply one n-diagonal multiplication per sub-block, then merge the contributions across sub-blocks with "in-block diagonalization". Cost table (Table 1):

The key structure (the original formulas in Table 1): Basic is d + 2d/c and DiagBlock is n + 2d/c; plugging in d=768, n=128, c=16 gives 864 → 224 (3.9×). DiagBlock lowers the term proportional to d from d to n (the sub-block side length, independent of d), at the price of leaving the 2d/c term in the multiplication count essentially unchanged (6240 → 6192) — what is saved is rotations, not multiplications. Note that the ratio is not c×: both sides keep the 2d/c term, so for large d the ratio approaches c/2 + 1 = 9; the gain therefore grows with d (for the FFN's d=3072 it is 3456 → 512, 6.75×), but the ceiling is 9× rather than 16×.

Cut A into d/n sub-blocks A^{(j)} of size n×n, and C likewise into d/n blocks
  C^{(j)} = Σ_{i} DiagBlock( A^{(i)}, B^{(i,j)} )
  each sub-block performs one "n-diagonal" multiplication
⇒ rotations = n (within blocks) + 2d/c (alignment across blocks)
   plugging in d=768, n=128, c=16: 864 → 224 (3.9×); as d grows this approaches c/2+1 = 9×

Lever 4: BSGS CC-MM

QK^T and αV are the two places with ciphertext×ciphertext. The naive approach must "rotate first, then multiply" for every diagonal, costing 2mn/c rotations. BSGS (baby-step giant-step) splits this into two steps: the baby steps handle ⌈√m⌉ small rotations and the giant step composes them from ⌈√m⌉ large strides, bringing the rotation count down to about 2√m; THOR's variant is to move the rotations from the data to the masks — the data copies perform only n/c internal rotations, while the mask side is rotated d/c times in advance, giving mn/c → mn/(2c) overall, with the number of relinearizations/rescales halved as well.

Naive CC-MM: for each (i, j), rotate both ciphertexts into place and then multiply
             ⇒ 2mn/c rotations, and the relinearizations double with them
BSGS:        split the index into a small step b and a large stride g
             small step: only "in-slot rotations" of the copies of B (no key switch)
             large step: only ρ^{gG} on the masks of A, d/c times in total
             ⇒ rotations mn/c (÷2), relin/rescale halved as well

Figure 5: CC-MM, (a) naive and (b) BSGS-optimized. The number of copies of ct_A in the left column drops from 6 to 4 (a toy example with d = 4), and the accumulation on the right needs only two ρ^-4 to obtain ct_C0; the mask side is rotated in advance, which avoids rotating the data once per product.

Note a counter-intuitive conclusion: none of the four levers saves "multiplicative depth". The depth is fixed solely by the depth of the non-linear approximations (GELU alone needs 11 levels, out of a total budget of 13), so bootstrapping cannot be avoided at all — which directly determines the judgment in §2.4 and §5.4.

2.4 Non-linear layers: the cost is not in the operator but in the bootstrap

This is the single comparison most worth remembering from the whole paper (Table 5, for 256 softmaxes of dimension 128):

The authors themselves spell out the mechanism: the softmax "itself" accounts for under 3% of the total time in both methods, and the entire 2.64× comes from cutting 8 bootstraps down to 3. So "optimizing the non-linearity" in this system correctly translates to "optimizing the number of bootstraps", not "optimizing the polynomial degree". This also explains why THOR would rather spend 2.8 bits of accuracy to save 5 bootstraps.

2.5 Full data flow of one encoder layer

Figure 6: Data flow of one encoder layer. Blue = PC-MM (ciphertext×plaintext), orange = CC-MM (ciphertext×ciphertext), white boxes = element-wise or row-wise non-linearity; the label L× outside the dashed box on the left indicates that the layer is repeated L times.

The input is X^T ∈ R^{d×n} (not X), stored transposed throughout. There are only two CC-MMs: QK^T and αV; PC-MM has four call sites (the QKV projection, the W_O projection, and W_1 and W_2 in the FFN), and the 6 blue boxes in the figure are because Q/K/V are each drawn once — if one counts "two PC-MMs inside attention and four in the whole layer including the FFN", the two statements do not conflict; they merely count at different granularity.

(Per-layer values = the 12-layer totals of Table 6 ÷ 12; share of end-to-end = the item's 12-layer total ÷ 602.26.)

Two implementation details are worth recording separately: the K^T of the attention scores is not actually a transpose — by Lemma 3.4 the server only needs one rotation + index reversal of the K ciphertext to obtain L(K^T), and then pastes the 16 copies of Q^T straight in (Algorithm 4); the u/L viewpoint switches back and forth throughout attention, which is what the "diagonal representation" looks like in actual code.

2.6 Paper concept ↔ code correspondence

The authors open-sourced the BERT implementation; the correspondence between a few key functions and the paper is as follows (paths relative to related_work/thor/code/src/thor/):

Reading the code confirms something the paper does not state clearly: the rotation keys are enumerated in advance (the rotation set is reported as 55 keys), so "optimizing rotations" is engineering-equivalent to "optimizing the key set", and this becomes the reproduction burden in §5.4.

3. Key Numbers Table

4. Relation to the Sibling Papers

(a) Its place in the survey ./01-private-transformer-inference-survey.mdx: the survey splits solutions into two main lines, MPC-based and HE-based, and THOR lands in the non-interactive branch of the HE-based line — the same cell as NEXUS (semi-honest, single-round, protects only the input), and a different cell from BOLT (BOLT is a hybrid framework, interacts layer by layer, and also protects the model). Under the survey's classification by "optimization means", THOR belongs to the branch that changes the arrangement (packing) rather than the mathematics (approximation): the linear layers lose no accuracy at all, and only the non-linear layers pay accuracy (see the accuracy table in §3).

(b) Against BOLT ./02-bolt-mpc-he-inference.mdx: BOLT is the baseline that is surpassed, and also the methodological counter-example. BOLT uses BFV leveled HE + secret sharing to reset noise, column-wise ciphertext packing + Gazelle diagonal plaintext packing, and an outer-product representation + partial rotation for ciphertext×ciphertext; its design goal (squeeze the depth, avoid the bootstrap) is exactly the opposite of THOR's (accept the bootstrap, squeeze the rotations). On the four MHA layouts of Table 4, THOR drives the key-switch count from 297/24468/21420/177 down to 192/460/492/122, and obtains 5.3×/36.0× speedups on individual operators.

(c) Against Odin ./04-odin-themis-llama3-fhe.mdx: Odin pushes the same pure-HE line from BERT to a Llama-3-8B decoder. The three things THOR deliberately avoids — the causal mask, the KV cache, and autoregressive incremental decoding — are precisely the whole of Odin's difficulty; and Odin in turn treats THOR as a baseline (reporting a 4.51× speedup, with a 1651.9 s "THOR-style" implementation as the denominator, which cannot be audited). This lineage can be put in one sentence: Iron/BOLT is the "hybrid + interactive" branch, NEXUS is the "pure-HE debut", THOR is responsible for getting pure-HE arithmetic right, and Odin is responsible for pushing it to decoders and large models.

5. Limitations and Open Questions

5.1 Task scope: this is a classifier, not a language model

It only does BERT masked language understanding, with no causal mask, no KV cache, and no autoregression. The sequence length has a hard ceiling of 128 tokens, whereas BERT itself supports 512; the paper does not report the effect of truncating long sentences to 128 on downstream accuracy — a trade-off made without a cost statement. Generative tasks (per-token decoding) are entirely out of range, and that is precisely the setting everyone actually cares about after 2025.

5.2 Model scope: weights are not confidential, and the client must hold 21.8% of the model

The server holds plaintext weights → model confidentiality is zero. Compared with BOLT's 2PC, this is speed bought by protecting one asset less, and it cannot be argued as "equally secure". The more practical problem is that the embedding table (23.8M parameters, about 21.8% of BERT-base) must sit on the client: the client has to do one embedding lookup + forward pass locally, so this part is not included in the 602 s; and for a large model, where the embedding layer alone routinely has a billion parameters, this assumption that "the client shoulders a little of the server's work" collapses immediately. The paper discusses PIR as a way out but does not implement it.

5.3 Security scope: semi-honest, no correctness verification, sequence length leaked

A malicious server can return any two numbers, and the client cannot tell after decryption — correctness is in the definition rather than in the protocol. In addition, the attention mask is encoded in plaintext, so n_tokens is leaked directly to the server; padding cannot hide the true length either. Every "semi-honest only" HE inference paper has this problem, but THOR has one extra layer because of its "plaintext weights": the server can even mount a model-side side channel against specific inputs.

5.4 Systems scope: the real bottleneck is the bootstrap, and it cannot be read

56.10% of the end-to-end time goes to bootstrapping, and the bootstrap implementation in the repository is obfuscated with PyArmor — the largest cost item in the paper is neither auditable nor reproducible. This directly caps the room for "how much more can optimizing matrix multiplication buy": even if the remaining 43.4% became 0, that would be only 1.76×. Conversely, any improvement at the bootstrap level (fewer levels, better sparsification, a different scheme) is where the order-of-magnitude opportunity lies. In addition, the 602 s does not include: the client-side embedding forward pass, encryption, the upload of the 112 evaluation keys (55 of which are rotation keys, on the order of GB), decryption, and post-processing; nor does the paper give a complete accounting of communication volume (it only gives BOLT's 25.74 GB in the comparison paragraph).

5.5 Experimental scope: fairness issues in the three comparisons

1. "Rotations cut to 2%–5% of BOLT" holds only for the two CC-MM cases: in Table 4, Case 2 is 460/24468 ≈ 1.9% and Case 3 is 492/21420 ≈ 2.3%; the two PC-MM cases only reach 65% (192/297) and 69% (122/177) of BOLT. The speedups 5.3×/36× and the key-switch ratios are not the same thing — a single key switch in BOLT does not cost the same as in THOR (BFV vs CKKS, different parameters), so the two numbers cannot corroborate each other.
2. NEXUS's 2.7 hours is a cited value, not a measured one: in Table 6 only THOR itself is measured; everything else comes from the original papers or from the paper's own recomputation.
3. The accuracy attribution is clean, but only on the one model BERT: the columns of Table 7 (plaintext / GELU approximation only / GELU+LN approximation / full ciphertext) show that the approximations themselves cost almost nothing (some tasks even improve slightly), and the roughly 1-percentage-point drop comes from CKKS noise — this attribution holds up, but it has been validated on only a 110-million-parameter model.

5.6 Five questions worth pursuing

• Raising c from 16 to 32 requires doubling N (s ≥ 49152), and both ciphertext size and multiplication cost grow — is the net gain actually positive? The paper does not give this curve.
• If BERT is replaced by a 7B model with d = 4096: the DiagBlock rotation count n + 2d/c still grows linearly with d, only with the slope reduced from 1 + 2/c to 2/c; is the 13-level multiplicative-depth budget still enough? How many bootstraps are needed?
• Is the PyArmor obfuscation of the bootstrap a fig leaf for "not reproducible"? Is there an independent CKKS bootstrap implementation that gives times of the same order?
• With plaintext weights on the server, can the framework of "precompute the weights + the client sends a single ciphertext" be used for model confidentiality (for example, encrypting the weights too but under a different key)? What would it cost?
• The paper's 5.3×/36× are single-operator microbenchmarks, while the end-to-end speedup relative to NEXUS is 16× (2.7 h → 10 min); how much of this 16× comes from the algorithm and how much from the GPU implementation and parameter choices? The paper does not break it down.

6. Self-Test Questions (answers follow)

Q1. Why does THOR write Q^T = W_Q^T X^T instead of first computing Q = X W_Q and then transposing?

A: Because a plaintext transpose is free (Lemma 3.3), whereas a ciphertext transpose costs about n rotations (Lemma 3.4). Once the transpose is permanently pushed to the plaintext side, the whole network runs in the "transposed state": input X^T, output X^T, every projection is "plaintext weight × ciphertext activation", and the rotation requirement drops to zero. This is the cheapest trick in the paper, and the hardest one to think of when reproducing it.

Q2. How is c = 16 determined? Can one simply take it as large as possible?

A: c ≤ s/(nH) = 2^15/(128 × 12) ≈ 21.3, and the largest power of two not exceeding it is 16. The larger c is, the more both the number of ciphertexts at a layer boundary n/c and the DiagBlock rotation count n + 2d/c decrease monotonically, so under the cost model of Table 1 "the larger the better"; the real ceiling is the slot count s — taking 32 would require doubling N, and ciphertext size and the cost of every multiplication would grow with it. So c is not tuned, it is computed.

Q3. Softmax accounts for only 2.6% of end-to-end time, so why does it deserve a section of its own?

A: Because its cost is not in the operator but in the bootstrap it triggers. Table 5 shows that the softmax "itself" is under 3% of the time in both the old and the new method, and the whole 2.64× speedup comes from cutting 8 bootstraps to 3. In this system, "optimizing the non-linearity" correctly translates to "optimizing the number of bootstraps", not "optimizing the polynomial degree" — which is also why the authors are willing to trade 2.8 bits of accuracy for 5 bootstraps.

Q4. Does DiagBlock save multiplications or rotations? By how much?

A: Rotations. With d=768, n=128, c=16 they drop from 864 to 224 (3.9×), while ciphertext×plaintext drops only from 6240 to 6192 (0.8%). The mechanism is that the formula changes from d + 2d/c to n + 2d/c: the O(d) term is replaced by the sub-block side length n; because both sides keep 2d/c, the ratio approaches c/2 + 1 = 9 as d grows, and it is 6.75× for the FFN (d=3072).

Q5. If the client wants to know whether the server computed correctly, what does THOR provide?

A: Nothing. Under the semi-honest assumption, correctness is part of the definition, not a verifiable property; a malicious server can return any two numbers, and the client cannot tell after decryption. Verifiable inference is a separate line of research, and THOR explicitly does not do it.

Q6. Which part of the 602 s can the authors themselves not explain?

A: The 337.86 s (56.10%) of bootstrapping. Its implementation is obfuscated with PyArmor and cannot be read from the repository; and the 112 rotation keys, the GB-scale setup/upload, and the client's embedding forward pass and decryption are all outside this 602 s. In other words, this "10 minutes" is server online computation time, not end-to-end user-experienced time.

7. Locator Index into the Original Paper