A Survey on Privacy-Preserving Transformer Inference: A Five-Stop Map
Deep-read notes on arXiv 2412.08145: threat models, the division of labour between MPC and HE, the dispute over the 12.7% bottleneck, the routes for linear and non-linear layers, the two independent axes of evaluation, and errata E1–E14 in the original text.
0. At a Glance
In one sentence: this is a 24-page survey from the NTU team, published in December 2024, covering 30 PTI (private transformer inference) works from 2022–2024, organized by security assumption (setup) rather than by technique or chronology (Table 1, paper.txt:361–410, p8). Its real contribution is not the list but the explanation of why a given route only holds under a particular setup.
30-second overview: five core insights
- Privacy is bidirectional, and it protects only the protocol execution, not the inference result. Definition 1 requires both correctness (the output equals the plaintext model output) and security (the view of either party can be forged by a simulator), but explicitly does not cover attacks based on
y(model inversion, membership inference) — that is a separate problem (paper.txt:90–117). - MPC splits the secret apart; HE locks it up. The former pays in communication, the latter in computation; neither is absolutely better, only a better or worse match for bandwidth, compute, and latency (§2.3).
- Whether something is expensive is not a matter of FLOPs but of whether the shape of the operation matches the tools at hand. Addition and slot-wise multiplication are nearly free;
exp,erf,tanh,max, division, and square roots are not — and the billing unit is the number of cryptographic operations, not the number of floating-point operations (§4.1, §5–§6). - Which layer is the most expensive is decided by whether multiplication can be prepaid. In pure 2PC the bottleneck is MatMul (the original wording in §4.2; Iron's end-to-end communication is 280.99 GB, Table 12); once there is an extra role that can prepare material in advance, MatMul accounts for only 12.7%, and the remaining 87.3% falls entirely on the non-linear layers (§4.2, §5.2).
- Communication ↔ computation and accuracy ↔ approximation cost are two independent axes. They are not a single seesaw: one can have very little communication and high accuracy (NEXUS), or burn 3.6 GB on a single operator (Iron's Softmax). Compressing four quantities into one "efficiency" number is bound to produce wrong conclusions (§7).
Key numbers
| Number | Meaning | Source |
|---|---|---|
| 30 = 21 + 6 + 3 | Number of works covered, grouped as 2PC / 2PC-Dealer / 3PC (the counts are this note's own tally) | Table 1, paper.txt:361–410, p8 |
| 12.7% | Share of runtime taken by MatMul for BERT-Base under MPC (the original context is 2PC-Dealer) | §5.2, paper.txt:594–595, p12 |
| 87.3% | Share of the non-linear layers, derived as 100 − 12.7; the original does not give this number | derived in this note |
| 280.99 GB | Communication of Iron running BERT-Base (I./O. (128,1), 3 Gbps / 0.8 ms) | Table 12, p21 |
| 1756× | Ratio of Iron's communication to that of NEXUS (280.99 / 0.16) | derived in this note |
| 8.8 points | Accuracy loss of MPCFormer on STS-B (89.1 → 80.3) | Table 12, p21 |
| 0.16 points | Accuracy loss of NEXUS on RTE (70.04 → 69.88) | Table 12, p21 |
| 22× | Ratio of communication for the same Softmax operator between Iron and BumbleBee (3596.32 / 162.24 MB) | Table 8, p16 |
| 31.7× | The same Iron Softmax, 60 s on LAN versus 1900 s on WAN | Table 8, p16 |
How to use these notes: for revision, start with §0–§3; for a related work section use §2, §4, and §5; before citing anything, read §6 (errata) and §10 (open questions) — these two sections decide whether you can safely put a given sentence into a paper.
1. The Five-Stop Map
The physical order of the original is "definitions → cryptography → threat models → bottlenecks → linear → non-linear → evaluation". For revision a causal chain is more useful: how the problem is defined → what tools you have → the tools determine where the bottleneck lies → hence two solution routes → and finally how to measure it fairly.
| Stop | What this stop establishes | Core conclusion | Location in the original |
|---|---|---|---|
| ① Problem and definitions | The PTI scenario, Definition 1 (correctness + security), the two formal threat models | Privacy is bidirectional; security covers only the protocol execution, not the inference result | §2.1–§3, paper.txt:90–117, 280–292, p2–p3, p6 |
| ② Cryptography toolbox | The division of labour among FE / MPC / HE, three kinds of setup | MPC splits → communication, HE locks → computation; the setup decides whether multiplication can be prepaid | §2.3, §4.2, Appendix A, 203–279, 320–344, 1345–1375, p4–p6, p7, p24 |
| ③ The bottleneck dispute | The two bottlenecks, and how the bottleneck migrates with the setup | 2PC is stuck on MatMul; 2PC-Dealer / 3PC are stuck on non-linearity | §4.1–§4.2, 300–344, p6–p7 |
| ④ Solution routes | Packing for linear layers; three routes for non-linearity (replace the function / polynomial / LUT) | Linear layers save operations through permutation and are nearly free; non-linear layers save operations through approximation and pay in accuracy | §5–§6, 461–1083, p9–p19 |
| ⑤ Evaluation and cost | Table 11 model configurations, Table 12 end-to-end comparison, the two independent axes | Communication is relatively comparable, runtime is almost never comparable, accuracy is the most trustworthy | §7, Table 11/12, 1085–1134, 1102–1115, 1150–1198, p19–p21 |
This causal chain also explains in passing a structural weakness of the survey: of the five stops the first four are fully written, yet the "evaluation guidelines" promised by the fifth stop never become a section of its own (§1, line 73 mentions them; there is no corresponding subsection in the body), and the conclusion chapter is simply empty (E1). So this survey is good to cite as a map, not as a conclusion.
2. Basic Concepts
2.1 The Problem and Definition 1
The scenario is the most basic MLaaS (machine learning as a service): the client holds the input x, the server holds the model M, and neither side is willing to hand over its share. Note that "privacy" is bidirectional — the client's input and the server's model parameters and architecture are protected at the same time. Many papers stress only the former; when reading, keep an eye on the latter.
Definition 1 gives the standard security definition for a two-party protocol (paper.txt:90–117):
Let Π be a two-party protocol between C (client, holding x) and S (server, holding M).
Condition 1 (correctness): when Π terminates, C obtains y, and y = M(x).
Condition 2 (security): there exist PPT simulators, in both directions:
· corrupt C: Sim_C(x, y) ≈ View_C^Π(x, M)
· corrupt S: Sim_S(M) ≈ View_S^Π(x, M) (y is meant to be given to C anyway)
"≈" denotes computational indistinguishability; View is everything a party sees in the protocol (inputs, randomness, received messages).Three readings, miss one and you will misuse it:
- The two conditions are mutually independent. Correctness says "what is computed is right"; security says "the process leaks nothing beyond that". A protocol can be perfectly correct yet have no privacy at all (compute in plaintext, then encrypt the result and send it back), or be very private yet compute the wrong thing (over-approximation).
- The simulator paradigm proves "no information beyond the specified output". Security is not "the attacker cannot understand it" but "the attacker could have simulated it themselves, and therefore learns nothing".
- The boundary is explicit: attacks based on
yare not defended against. The survey itself writes that attacks such as model inversion and property inference are out of scope. So the sentence "PTI guarantees privacy" may only be used under the qualifier "the protocol execution".
2.2 Three Threat Models, Do Not Mix Them Up
| Model | Also known as | What the adversary can do | Hard constraint | Use in this survey |
|---|---|---|---|---|
| Semi-honest | semi-honest / honest-but-curious | Executes the protocol strictly as specified, but passively collects and analyses the transcript | Does not lie, does not alter inputs, does not abort early | The default assumption of the overwhelming majority of works (§3) |
| Malicious | malicious | Deviates arbitrarily from the protocol: lies, alters inputs, exits early | Requires extra consistency checks (MACs, cut-and-choose, etc.), which are costly | §3 does not define it formally; it appears only in the sentences on PrivFormer / PPTIF in §4.2 (paper.txt:342) |
| Honest majority | honest-majority | Assumes that a majority of the computing parties are honest and do not collude, and that the adversary corrupts at most a minority | At least 3 parties; "majority" refers to the number of computing parties | Only PrivFormer [1], PPTIF [32] (§4.2, §5.3) |
The key difference is not a linear ordering of "who is more secure" but whether the protocol has to pay for deviant behaviour. Under the semi-honest assumption it suffices that the transcript be simulatable; under the malicious assumption deviations must additionally be caught — for the same functionality the malicious version is usually an order of magnitude more expensive (this note's judgement; the survey gives no unified number).
Three frequently confused points:
- Semi-honest does not mean there is no threat. It means "the adversary's only weapon is transcript analysis", not "the adversary does not exist".
- Honest majority is not a protocol but an assumption. It requires at least 3 parties and "a majority that does not collude"; the dealer in 2PC-Dealer, which only deals cards, takes no part in the computation and receives no input, cannot be counted as "a party", so 2PC-Dealer is not 3PC.
- The malicious model has no subsection in the original. "Three threat models" is this note's revision framework; when citing, do not write "the survey defines three threat models".
2.3 MPC and HE in One Sentence Each
| MPC (secure multi-party computation) | HE (homomorphic encryption) | |
|---|---|---|
| Form of the secret | Split into shares scattered across several parties | Locked in a single ciphertext held by one party |
| Essence in one sentence | Nobody can see it, but everyone computes together | Nobody can see it, but one party alone can compute |
| Who computes | Several parties interacting | A single party, locally |
| Main bill | Communication (rounds × data per round) | Computation (ciphertext multiplication, rotation, noise budget) |
| Interactivity | Must interact | Non-interactive by nature (encrypt once, the server can compute alone to the end) |
| Suited to | Data centres with good bandwidth and no latency sensitivity | Mobile, edge, poor uplink bandwidth |
| Anchor in this survey | Iron's Softmax 3596.32 MB (Table 8) | NEXUS's Softmax 0 MB (Table 8); end-to-end 1125 s (Table 12) |
The selection intuition is a single sentence: if the bottleneck is the network, go toward HE; if the bottleneck is compute, go toward MPC. NEXUS pushes BERT-Base communication down to 0.16 GB (Table 12) at a cost of 1125 s; Iron takes only 475 s but communicates 280.99 GB. Neither is "better"; one simply fits the physical conditions of your link better.
2.4 Three Kinds of Setup: The Difference Is Who Can Prepare Material in Advance
| setup | Parties | Extra trust assumption | How multiplication becomes cheaper | Rating in Table 13 |
|---|---|---|---|---|
| 2PC | C + S, two parties | None (mutual distrust) | Cannot prepay: encrypt one side's share with HE on the spot, or generate a Beaver triple on the spot | 2 parties; Comm +; Practicality +; Scalability + |
| 2PC-Dealer | C + S compute, the dealer only deals during preprocessing | Trust that the dealer does not collude and takes no part in computation | Prepay: the dealer distributes input-independent correlated randomness ahead of time | 3 parties (Trusted Dealer); Computation +; Scalability ++ |
| 3PC | Three parties | honest-majority: at least two parties are honest and do not collude | Prepay + replicated secret sharing: 2-out-of-3 RSS, multiplication becomes local computation + re-sharing | 3 parties; Comm −; Computation +; Practicality −; Scalability ++ |
The plus signs in Table 13 are only a relative strength ordering (+++ strongest, + weakest), not scores, and not measured experimental values.
Now the crucial sentence: 2PC-Dealer and 3PC count as prepaying, not as sharing out. Sharing out means slicing the same amount of work among more machines to be done in parallel; total communication does not fall for that reason (it often rises). Prepaying means moving the input-independent part of the work to before the input arrives, so that the online multiplication degrades into a few local additions plus a tiny re-sharing.
This explains a counter-intuitive phenomenon: 3PC / 2PC-Dealer are not only faster, they also communicate less (in Table 13 the Comm of 3PC is −, lower than 2PC's +). If it were merely "one more machine helping to compute", communication could not drop. Conversely, any claim that "3PC shares out MatMul" has not yet understood what it is saying.
2PC : trust nobody, multiply on the spot → MatMul is expensive, the bill concentrates in matrix multiplication
2PC-Dealer : trust a dealer that only deals, not computes → multiplication prepaid → non-linearity surfaces
3PC : trust an honest majority, use RSS to → same as 2PC-Dealer, but pay one more share of communication
turn multiplication into local additionThe Beaver triple is the smallest example of prepaying. For 2PC to perform a multiplication on the spot, the standard recipe is: during preprocessing obtain shares of a random triple a, b, c = a·b; online, open d = x − a and e = y − b, so that
x·y = (a + d)(b + e) = c + a·e + d·b + d·ed and e are public masking values, while a, b, and c remain in shares, so each party can compute its own share locally, needing only one opening (disclosing d and e to each other). This shows exactly what prepaying prepays: the triple is input-independent and can be prepared in advance; online, only local additions and a single opening remain. 2PC, which does not let a third party prepare material, has to generate the triple online, which is why multiplication is expensive; a dealer or the RSS of 3PC moves that work away, which is why multiplication becomes cheap.
The cost is moving trust from cryptography to a social assumption: the authors themselves cite [20] to criticise "the assumption of a trusted dealer or non-colluding server parties is sometimes considered unrealistic in practice" (p7, paper.txt:344). So the three kinds of setup admit no total order of security strength, only "whom you are willing to trust".
3. The Bottleneck Dispute: 12.7% and 87.3%
3.1 How to Read That Ledger
The original has just one sentence (§5.2, paper.txt:594–595, p12):
matrix multiplications account for only 12.7% of the overall BERT-Base model runtime under MPC, and the communication overhead is also much lower than that of the non-linear layer.
Three things must be read together:
- 12.7% is a share of runtime, not a share of compute. 87.3% is derived as 100 − 12.7 and is not in the original; when citing, write "derived" or simply cite 12.7%.
- Be careful with attribution. This sentence "under MPC" appears in the paragraph discussing MPCFormer [28] / Wang et al. [59], and both of those are 2PC-Dealer. Reading it as "under pure 2PC, MatMul accounts for only 12.7%" is the most frequent misreading this note has encountered — the ledger for pure 2PC looks the opposite way: Iron needs 280.99 GB of communication to run the same BERT-Base (Table 12, p21).
- The survey's own conclusion is migration, not disappearance. According to §4.2, under 2PC all work is optimizing MatMul, because every element pair of
A·Bmust be protected; once there is a helper party, "the introduction of a 'helper party' has effectively eliminated matrix multiplication as a significant bottleneck" (paper.txt:343), and only then do the non-linear layers become the main battlefield.
3.2 Why the Bottleneck Migrates
2PC: A·B → every element pair must be protected → HE encryption / interaction → communication and computation both blow up
⇒ the bill concentrates in MatMul; non-linearity has only 3 kinds of operators, so it is a secondary item
2PC-Dealer / 3PC: multiplication can be prepaid → MatMul degenerates into local additions + a little re-sharing
⇒ MatMul drops to 12.7%; the remaining 87.3% is exp / max / division / erf / tanh / square root
⇒ these functions have no usable algebraic structure, so one can only replace, approximate, or look them upSo a bottleneck is not an objective property of the model but a function of model × tools × setup. The same BERT-Base has MatMul as its bottleneck under 2PC and Softmax, GeLU, and LayerNorm as its bottlenecks under 2PC-Dealer. This is precisely why the survey is organized by setup rather than by year.
3.3 Why Expensiveness Is Not About FLOPs
- FLOPs count the amount of mathematical work; cryptography bills the number of operations. In HE a single slot-wise multiplication covers
nscalar products and counts as one ciphertext multiplication; a single rotation movesnslots but costs one automorphism plus one key switching. So there is no monotone relation between "how many products were done" and "how much was paid". - It therefore does not follow that "the layer with the most parameters is the most expensive". BERT-Base's MLP is
3072wide and is pure MatMul; Softmax is only128 × 128, yet Iron needs 3596.32 MB for it (Table 8). - The right question for judging whether an operator is expensive: can it be written as addition + slot-wise multiplication? If not, how many levels of multiplicative depth does it need, does it need a lookup table, and how large is the table?
4. Solution Routes
4.1 Linear Layers: Diagonal Packing
The problem: C = A·B, C_{i,j} = Σ_k A_{i,k} B_{k,j}. HE's SIMD slots make slot-wise multiplication extremely cheap; the difficulty is spreading the inner product over the k dimension across slots — k lies "sideways" in the slots, and a direct multiplication yields only element-wise products, not a sum.
The solution is to slice the matrix along its diagonals (the approach of Gazelle [24], adopted by BOLT [43]):
n slots (n is the polynomial ring dimension, and also the number of SIMD slots)
rot(v, d)_i = v_{(i + d) mod n} ← cyclic left shift by d positions
diag_d(A)_i = A_{i, (i + d) mod n} ← the d-th diagonal of A
identity: A·x = Σ_{d=0}^{n-1} diag_d(A) ⊙ rot(x, d)Hand computation for 3×3 (n = 3):
A = [[a00, a01, a02], x = [x0, x1, x2]
[a10, a11, a12],
[a20, a21, a22]]
diag_0 = [a00, a11, a22] ⊙ x = [a00·x0, a11·x1, a22·x2]
diag_1 = [a01, a12, a20] ⊙ rot(x, 1) = [a01·x1, a12·x2, a20·x0]
diag_2 = [a02, a10, a21] ⊙ rot(x, 2) = [a02·x2, a10·x0, a21·x1]
────────────────────────
after summing, slot 0 = a00·x0 + a01·x1 + a02·x2 = (A·x)_0
after summing, slot 1 = a11·x1 + a12·x2 + a10·x0 = (A·x)_1
after summing, slot 2 = a22·x2 + a20·x0 + a21·x1 = (A·x)_2Cost comparison (n = 128):
| Approach | Ciphertext multiplications | Rotations | FLOPs |
|---|---|---|---|
| Naive element-wise | 16384 | 0 | 16384 scalar products |
| Diagonal packing | 128 | 128 | 16384 scalar products |
The FLOPs are identical, but the cryptographic bill differs by 128×. This is the cleanest illustration of billing by number of operations. Strictly speaking, "naive" in this table means the textbook version with element-wise encrypted multiplication; real implementations often use column packing to bring the number of plaintext-weight multiplications down to the n level as well, at the price of more ciphertext copies and reordering, so the "128×" is an order-of-magnitude intuition, not a measured ratio for an arbitrary implementation.
Then why is rotation said to be the most expensive? Three reasons, the third being the most easily overlooked:
- A rotation is not a "shift instruction" but an automorphism (Galois automorphism) + key switching: the Galois keys must be generated in advance (a very large evaluation key), and each switching in turn requires decomposition, multiplication, and addition.
- The cost of a single rotation is usually on the order of, or even higher than, one ciphertext multiplication;
nrotations meannsuch costs. - It cannot be amortized by SIMD. What SIMD gives for free is "one instruction covers
nslots", and rotation is exactly the step that moves thosenslots;nrearrangements arenindependent overheads.
So the residual bill of diagonal packing is n rotations. All subsequent packing optimizations essentially reduce the number of rotations or the amount of data moved per rotation, not the number of multiplications:
| Work | Packing technique | What it saves | Evidence |
|---|---|---|---|
| BOLT [43] | Ciphertexts packed by column + plaintext packed by diagonal | Computation: brings the number of ciphertext×ciphertext multiplications down to the n level | outer product + partial rotation accelerates Q·Kᵀ; the MPC-HE hybrid lets noise reset automatically, without bootstrapping (§5.3) |
| BumbleBee [34] | IntrLeave: interleave several polynomials into one ciphertext | Communication: fewer ciphertexts for the same number of slots | Softmax 162.24 MB, 1/22 of Iron in the same table (Table 8) |
| NEXUS [64] | RNS-CKKS + SIMD ciphertext compression + slots folding | Communication: compressed to nearly 0 | Softmax / GeLU / LayerNorm all at 0 MB in their respective tables (Tables 8–10) |
One reminder: "rotation = automorphism + key switching, costing on the order of one ciphertext multiplication" is standard knowledge in the HE field, but the survey only names Gazelle's diagonal packing and gives neither the identity nor the cost analysis — the passage above is this note's supplement.
4.2 Non-Linear Layers: Three Routes
Non-linearity contains only three kinds of operators: Softmax, GeLU, and LayerNorm. Yet they are the entire source of "cryptographic unfriendliness". The three routes are replace it / approximate it / look it up in a table, and they differ in where the error is put and where the cost is put.
| Route | Approach | Where the cost falls | Accuracy | Representative works |
|---|---|---|---|---|
| Replace the function | Replace it wholesale with a cryptographically friendly F | Training side (distillation is mandatory) + accuracy | Collapses, held up by KD | (x+c)²: MPCFormer [28], SecFormer [36]; ReLU: MPCViT [63]; (a·x+c)²: SAL-ViT [65]; (x+c)⁴: RNA-ViT [6] |
| Polynomial approximation | Taylor / Maclaurin / Chebyshev / piecewise low degree | Multiplicative depth and computation | Controllable, traded for by the degree | BOLT [43]'s piecewise degree 2.7/4; PUMA [12] and NEXUS [64]'s piecewise degree 3/6; BumbleBee [34]; CipherGPT [20]; Rovida [49]'s degree-6 Maclaurin; SecFormer [36]'s Fourier series |
| LUT lookup | Build the table in preprocessing, perform an oblivious lookup at runtime | Communication: the whole table has to be brought into the protocol | Almost lossless, only quantisation error remains | Iron [18], SIGMA [17], Curl [50], CipherGPT [20]'s reciprocal |
Replace the function: it saves the most cryptographic operations and has the largest error. There is also a hidden source of error: the approximation may not have been designed for this function at all — MPCFormer's 0.125x² + 0.25x + 0.5 was originally an approximation of ReLU by Chou et al. [9], and moved straight over to GeLU, the error is no longer just "low degree" but "the wrong approximation target". The reason is straightforward — the replacement function is numerically not the original function, so the model must be retrained or distilled on the replacement, otherwise the distribution simply drifts. The evidence is that MPCFormer falls from 89.1 to 80.3 on STS-B (8.8 points), and that is already the version with KD (Table 12). In the same paper QNLI drops only 1.1 points, which shows that the error depends on how sensitive the task is to the shape of the function; it is not uniform — which is also why the replace-the-function route must report per task; reporting only the average is misleading.
Polynomial approximation: the main devices are range clipping + piecewise + repeated squaring. exp has two tricks worth remembering: BOLT first splits x_i − x̂ into (−ln2)·z + p (z a non-negative integer, p in (−ln2, 0]), approximates exp(p) with the quadratic 0.3585(p+1.353)² + 0.344, and then shifts by 2^z; NEXUS / BumbleBee / CipherGPT / PUMA use repeated squaring (1 + x/2^r)^{2^r} and clip the interval below a to 0 outright (NEXUS a = −inf, r = 6; BumbleBee a = −13, r = 6; CipherGPT a = −16; PUMA a = −14, r = 5).
A higher degree is not always better. Rovida [49]'s reciprocal uses a degree-119 Chebyshev approximation, mathematically beautiful, but it trades saved communication for extra multiplicative depth, which in HE means more noise budget — a bill that is entirely invisible in a FLOPs table.
GeLU's piecewise form (Equation 20) deserves a separate note: the left tail takes the constant −c, the middle (a, b] uses degree 3 and (b, 3] degree 6, and the right tail takes x − c; PUMA / NEXUS take a = −4, b = −1.95, c = 0, BumbleBee takes a = −5, b = −2, c = 10⁻⁵. Both ends are linear or constant, which is the key to GeLU being eatable by low-degree polynomials; BOLT goes further with a degree-4 approximation of abs(x) plus 0.5x, making full use of the odd symmetry.
LUT: the communication bill is hard — the whole table (2^b entries) has to enter the protocol, and its size grows exponentially with the bit width. Iron's Softmax is 3596.32 MB while BumbleBee's is 162.24 MB for the same operator, a 22× difference (Table 8). The accuracy bill, however, is not as one-sided as one might imagine: a LUT introduces only quantisation error, and when done well it can reach the 10⁻⁵ level (Iron's Softmax is 3.2×10⁻⁵, Table 8), but it is by no means necessarily better than polynomials — in the same table BOLT is 1.4×10⁻⁶. NEXUS uses SIMD compression to push communication to 0 MB at the cost of 242 s — it trades communication for computation.
The hardest point of each of the three functions
| Function | Mathematical form | Hardest point | Representative works |
|---|---|---|---|
| Softmax | exp(x_i − x̂) / Σ_j exp(x_j − x̂) | Not the exponential but the max (comparison) and the 1/Σ (the reciprocal diverges near 0); order of difficulty: direct exponential easiest, max in the middle, reciprocal hardest | Iron LUT + SIRNN protocols; SIGMA low-bit-width LUT for max / negative exponential / reciprocal; NEXUS Goldschmidt division; BOLT decomposition + quadratic |
| GeLU | (x/2)(1 + erf(x/√2)) or a tanh approximation | erf / tanh have no algebraic structure; it must be piecewise, and the tails must be joined back to a linear function | THE-X / PowerFormer replace it with ReLU; MPCFormer uses 0.125x² + 0.25x + 0.5; BOLT's piecewise degree 4; SIGMA's near-linear form + δ correction |
| LayerNorm | γ(x_i − μ)/σ + β, σ = √(Σ(x_i − μ)²/d) | The 1/√· (rsqrt) and the global reduction; and one must be careful not to get the statistics wrong | NEXUS / PowerFormer Newton iteration; CipherGPT LUT; SIGMA 13-bit floating-point encoding index; PrivFormer uses FALCON's square-root inverse |
There is also a counter-example on LayerNorm, worth more than a positive one: Iron folds γ/σ and β into the next layer's weights, leaving only [x_i − μ] (Equation 25), which looks algebraically perfectly correct; but BOLT points out that it ignores the residual connection, and that performance becomes "close to random guessing" (paper.txt:1064). This is M16: an algebraically correct simplification is not necessarily a good optimization, because the term that was eliminated may be the pivot of the model's numerical stability.
4.3 Selection Principles
The three routes are not a question of "which is more advanced" but of "which resource you have in abundance": if the network is plentiful, use LUTs (Iron / SIGMA); if compute is plentiful, use polynomials (BOLT / NEXUS); if both are tight, replace the function and distil (MPCFormer). The survey gives no method for automatic selection, and that is itself a gap (§10).
5. Evaluation: Two Independent Axes
5.1 Two Axes, Not One Score
Axis one (system): communication ↔ computation ← determined by the MPC / HE ratio
Axis two (numeric): accuracy ↔ approximation cost ← determined by function replacement / polynomial degree / LUT bit width
the two axes are independent of each other: one can have low communication + high accuracy (NEXUS),
or high communication + low accuracy (some of Iron's operators).The cleanest contrast is the two extremes on BERT-Base:
| Work | Route | Communication | Runtime | Accuracy loss | Source |
|---|---|---|---|---|---|
| MPCFormer [28] | 2PC-Dealer + replace the function + KD | 12.089 GB | 55.320 s | STS-B drops 8.8 points | Table 12, p21 |
| Iron [18] | 2PC + LUT | 280.99 GB | 475 s | STS-B drops 0.21 points, MRPC / QNLI drop at the 0.1-point level, SST-2 / RTE actually improve | Table 12, p21 |
| NEXUS [64] | pure HE + compression | 0.16 GB | 1125 s | RTE drops 0.16 points | Table 12, p21 |
With only one axis, one cannot explain why NEXUS has the least communication and the best accuracy yet is the slowest. "Pure HE necessarily loses accuracy" is an illusion: NEXUS drops 0.16 points while MPCFormer drops 8.8, exactly the opposite direction. THE-X leaving ReLU for the user to decrypt and compute is the authors' engineering trade-off (they themselves call it an "aggressive approximation"), not the fate of HE.
5.2 Rules for Reading the Tables
| Dimension | Horizontally comparable? | Reason |
|---|---|---|
| Communication volume | Broadly comparable | Determined mainly by the protocol and packing, little affected by the network; but the I./O. size still has to be checked |
| Runtime | Almost never comparable | Affected jointly by network bandwidth and latency, hardware, batch, implementation quality, and timing methodology |
| Accuracy | The most trustworthy | Depends only on the model and the approximation, independent of the machine; but the dataset and whether KD was used must be checked |
| Communication setting | Must be reported alongside | The same implementation, with a different network, can differ by an order of magnitude |
There are at least five network tiers in the original, and the footnote of Table 8 reports LAN / WAN separately:
| Tier (original footnote) | Bandwidth / latency | Appears in |
|---|---|---|
| LAN1 | 1 Gbps / 0.5 ms | BumbleBee |
| WAN2 | 400 Mbps / 4 ms | BumbleBee |
| LAN3 | 3 Gbps / 0.8 ms | Iron, BOLT, NEXUS, CipherGPT |
| LAN4 | 9.4 Gbps / 0.05 ms | SIGMA |
| WAN5 | 100 Mbps / 80 ms | Iron, BOLT, NEXUS |
From this follow three hard rules:
- Even the seconds within one table cannot be lined up side by side. Iron's Softmax is 60 s on LAN and 1900 s on WAN (Table 8); the 31.7× gap comes from the network, not from the algorithm.
- Citing a runtime requires the full set of four: I./O. size, network conditions, hardware, and batch. Miss one and it is not reproducible.
- A bigger model does not mean more communication. BumbleBee's BERT-Large is 20.85 GB while LLaMA-7B is only 6.82 GB (Table 12), because the former's I./O. is
(128,1)and the latter's is(8,1). Seeing "a 7B model with less communication", do not be surprised — go and look at the I./O. size.
6. Errata E1–E14
This is the most important value-added part of these notes: the 14 items below were obtained by checking paper.txt line by line; they are not disagreements with the content or viewpoint but hard errors at the level of typesetting, citations, and data completeness. When citing this survey in a paper, wherever these locations are involved, either avoid them or correct them yourself.
| ID | Location (paper.txt line / table) | Problem | Suggested fix | Severity |
|---|---|---|---|---|
| E1 | 1136 | §8 CONCLUSION has only a title; the body is entirely blank | Write the conclusion, or delete the chapter | 🔴 high |
| E2 | 86 | §1 promises "In Section ??, we discuss challenges and future directions", but there is no such chapter anywhere in the paper | Write the chapter, or delete the promise | 🔴 high |
| E3 | 86, 296, 463, 525 | Four uncompiled cross-references: Section ??, (??)-(??) | Add \ref and recompile | 🟡 medium |
| E4 | 321, 340 | The body of §4.2 sends the reader to "Table 4", but the content described (who optimizes MatMul / GeLU / Softmax / LayerNorm) is in Table 1; Table 4 is about MPC backbones | Point to Table 1, or rewrite the sentence | 🟡 medium |
| E5 | 838 (Table 8), 889 (Table 9) | NEXUS is mislabelled [43], while [43] is BOLT | Relabel as [64] (line 1057 of Table 10 gets it right) | 🟡 medium |
| E6 | 500 (Table 4) | Curl is mislabelled [17], while [17] is SIGMA | Relabel as [50] (line 404 of Table 1 gets it right) | 🟡 medium |
| E7 | 280 | The heading of §3 is misspelled "PIVACY THREATS IN SECURE INFERENCE" | Change to "PRIVACY" | 🟢 low |
| E8 | 35–39 and 195–201 | A whole passage is repeated verbatim in §1 and at the end of §2.2 (data control, server misuse, risks of centralised storage) | Delete the later occurrence | 🟢 low |
| E9 | 74–79 | §1's contribution list says "summarized as follows" but lists only (1)(2) | Add (3)(4), aligning with the four items mentioned in lines 71–73 | 🟢 low |
| E10 | 81–87 | The chapter tour runs §2 → §4 → §5 → §6 → §7 → §? → §8, skipping §3 | Add §3 | 🟢 low |
| E11 | 342 | "two out of three parties are honest adversaries" is self-contradictory | Change to "are honest" | 🟢 low |
| E12 | 354 | A fragment ends with "...e.g., mobile devices. THE-X [7]" | Complete it or delete it | 🟢 low |
| E13 | Table 12 (p21) | In BumbleBee's BERT-Base row both communication and runtime are "−", while BERT-Large / LLaMA-7B / GPT2-Base / ViT-Base in the same group all have values | Supply the data, or note that this configuration was not measured | ⚪ data completeness |
| E14 | Table 12 (p21) | The THE-X row reports no communication or runtime at all, only accuracy | As above | ⚪ data completeness |
Two notes on usage:
- E1–E2 are structural problems, not typos: a survey with no conclusion and no challenges chapter is more of a "literature map" than a "field judgement". When citing its concluding sentences, it is best to go back to the primary papers it cites.
- Numbering slips such as E5–E6 are almost invisible in the PDF, but when you build a citation chain they lead the reader straight to the wrong paper. Such errors deserve to be kept in the notes for a long time.
Additional findings of this note (not in the original E list, also worth a look before citing):
- Table 3 (p9) labels BOLT as
[26], while [26] is CrypTen; BOLT's number is[43](as in both Table 1 and Table 8). - In Table 4 (p10), SecFormer
[36]appears once in the 2PC group and again in the 2PC-Dealer group (paper.txt:482and498), and the protocol and framework columns of the two rows are identical; at the same time Table 4 is missing CipherFormer[58]and Zimerman et al.[69]from Table 1. Table 1 has 30 rows, Table 4 has 29 (including the duplicate). - The setup attribution of 12.7% (see §3.1 and §10) is strictly speaking not an erratum but "the original wording permits misreading".
7. Common Misconceptions (10 Selected from M1–M16)
| # | Misconception | Correction |
|---|---|---|
| M1 | PTI protects only the client's input | Privacy is bidirectional: model parameters and architecture must be protected too; either party may be the adversary (Definition 1) |
| M4 | A semi-honest party will lie, alter inputs, or abort | It will not. A semi-honest party follows the protocol strictly and its only weapon is transcript analysis; the ones that can lie are in the malicious model |
| M5 | Honest majority is a protocol | It is a security assumption requiring at least 3 parties and a non-colluding majority; the protocol itself is a separate matter (RSS, re-sharing) |
| M6 | 2PC-Dealer is just 3PC | No. The dealer receives no input and takes no part in computation; it only distributes input-independent correlated randomness during preprocessing |
| M7 | 3PC / 2PC-Dealer share out MatMul | It is prepaying, not sharing out. Sharing out does not reduce total communication; prepaying does — which is why 3PC's Comm is lower instead |
| M9 | FLOPs can tell you which layer is the most expensive | The billing unit is the number of cryptographic operations; computing n scalar products and performing n rotations have completely different bills |
| M10 | Pure HE is necessarily less accurate | The opposite is true: NEXUS drops 0.16 points, MPCFormer drops 8.8 points. Accuracy depends on the approximation, not on MPC / HE |
| M11 | Accuracy and communication are a single seesaw | They are two independent axes: one can have low communication with high accuracy (NEXUS), or high communication with low accuracy (some of Iron's operators) |
| M13 | Runtimes from different papers can be compared directly | They cannot. I./O. size, network conditions, hardware, and batch are required; even LAN / WAN within one table can differ by 31.7× |
| M16 | An algebraically correct simplification is necessarily a good optimization | Iron's LayerNorm simplification is algebraically correct but ignores the residual connection; BOLT says it is "close to random guessing" |
8. Self-Test Questions (8)
Q1 (concept) What are the two conditions of Definition 1, and why is neither dispensable?
Answer: Correctness requires that the output equal the plaintext model output y = M(x); security requires the existence of PPT simulators that make View computationally indistinguishable from the simulation in both directions. Neither is dispensable: satisfying only correctness permits plaintext computation, and satisfying only security permits returning random numbers — the former has no privacy, the latter is useless.
Q2 (concept) What is the essential difference among the three setups? Why can 2PC-Dealer not be counted as 3PC?
Answer: The difference lies in whether multiplication can be prepaid, and in the trust assumption paid for it. 2PC multiplies on the spot; 2PC-Dealer has the dealer distribute input-independent correlated randomness before the input arrives; 3PC relies on honest-majority plus 2-out-of-3 RSS re-sharing online. The dealer receives no input and takes no part in computation, so it is not "a party"; calling 2PC-Dealer 3PC conflates two assumptions, "trusting a dealer" and "trusting a majority of computing parties".
Q3 (numbers) 12.7% is the share of what? Which setup does it belong to? How is 87.3% obtained?
Answer: It is the share of MatMul in the end-to-end runtime of BERT-Base (§5.2, paper.txt:594–595). The original wording is "under MPC", but the context is the 2PC-Dealer paragraph on MPCFormer / Wang et al., so it cannot be taken as a pure-2PC number. 87.3% is derived as 100 − 12.7 and is not in the original.
Q4 (numbers) How many times is Iron's communication that of NEXUS? With communication near zero, why is NEXUS end-to-end 2.4× slower than Iron?
Answer: 280.99 / 0.16 ≈ 1756× (Table 12). First strip out the network: the two run over 3 Gbps / 0.8 ms and 100 Mbps / 80 ms respectively, so the seconds are not directly comparable in the first place. NEXUS's 1125 s is mostly not transmission — 0.16 GB at 100 Mbps is only on the order of a dozen seconds (this note's estimate) — but the ciphertext multiplications and automorphisms of pure HE; it moves the cost from communication to computation. Communication and computation are two axes and cannot be offset against each other.
Q5 (concept) Diagonal packing brings a matrix-vector product of an n × n matrix from n² ciphertext multiplications down to n multiplications plus n rotations. Since the FLOPs do not change, why is it still faster?
Answer: Because a ciphertext multiplication is a cryptographic operation covering n slots at once, n² element-wise multiplications pay n² times the cost, whereas the diagonal method pays only n multiplications plus n rotations. Rotations are expensive (automorphism + key switching, close to one ciphertext multiplication) but still of order n, so the total is 2n rather than n².
Q6 (judgement) "MPCFormer drops 8.8 points on STS-B while NEXUS drops only 0.16, so HE is more accurate than MPC." What is wrong with this sentence?
Answer: It conflates the route (the MPC / HE ratio) and the approximation (replace the function / polynomial / LUT) into a single variable. MPCFormer drops more points because it replaces Softmax with (x+c)² and can only rely on KD, not because it uses MPC; NEXUS is accurate because under pure HE it uses high-precision polynomials and iterations (Softmax error 3.1×10⁻⁶, Table 8) and does not have to sacrifice degree for communication, not because of "HE" itself. The correct statement: accuracy depends on the approximation and on whether distillation is used, and is orthogonal to the choice of MPC / HE.
Q7 (judgement) Paper A reports BERT-Base inference in 50 s and paper B reports 100 s. Can one say A is twice as fast?
Answer: No. The I./O. size, network conditions, hardware, batch, and timing methodology must all be checked. In Table 8 the same Iron Softmax is 60 s on LAN and 1900 s on WAN — the network alone can cause a 31.7× difference; in Table 12, BumbleBee's BERT-Large communicates 20.85 GB, higher than LLaMA-7B's 6.82 GB, again only because the I./O. size differs.
Q8 (judgement) "3PC uses three machines in parallel, so the communication of MatMul is shared out." What is wrong with this?
Answer: The error is "shared out". The gain of 3PC comes from prepaying and RSS: multiplication becomes local computation on each party plus one re-sharing, and online communication falls; if the same amount of work were merely sliced in parallel, total communication would not fall. The evidence is that in Table 13 the Comm of 3PC is marked − (lower than 2PC's +), a direction of change that sharing out could not produce.
9. Locator Index for the Original
Line numbers refer to paper.txt (extracted with pdftotext -layout, 1380 lines); page numbers refer to PDF pages.
| Topic | Section / table | paper.txt lines | Page |
|---|---|---|---|
| Introduction, contribution list, chapter tour | §1 | 25–88 | p1–2 |
| PTI scenario and Definition 1 | §2.1 | 90–117 | p2–3 |
| Transformer background and privacy risks | §2.2 | 119–201 | p3–4 |
| FE / MPC / HE toolbox | §2.3 | 203–279 | p4–6 |
| Threat models (semi-honest, honest majority) | §3 | 280–292 | p6 |
| Cryptographic challenges | §4.1 | 300–317 | p6–7 |
| Three kinds of setup and bottleneck migration | §4.2 | 320–344 | p7 |
| Overview of the 30 works | Table 1 | 361–410 | p8 |
| Strengths and weaknesses of each work (incl. the note on THE-X's privacy flaw) | Table 2 | 420–442 | p9 |
| Available implementation links | Table 3 | 444–451 | p9 |
| Overview by MPC backbone (incl. duplicate rows) | Table 4 | 469–503 | p10 |
| Available backbone links | Table 5 | 506–518 | p10 |
| Linear layers: MatMul protocols | §5.1 | 528–565 | p11 |
| Linear layers: the MPC / HE / hybrid three routes | §5.2–§5.3 | 566–666 | p11–13 |
| The original sentence for 12.7% | §5.2 | 594–595 | p12 |
| HE scheme comparison (incl. the bootstrapping column) | Table 7 | 667–677 | p14 |
| Softmax: function replacement / exp approximation / reciprocal | §6.1 | 687–843 | p14–16 |
| Softmax single-operator comparison (incl. LAN / WAN) | Table 8 | 826–841 | p16 |
| GeLU: function replacement / piecewise polynomials / LUT | §6.2 | 844–1013 | p16–17 |
| GeLU single-operator comparison | Table 9 | 877–889 | p17 |
| LayerNorm: rsqrt and the risk of simplification | §6.3 | 1014–1083 | p18–19 |
| LayerNorm single-operator comparison | Table 10 | 1047–1057 | p19 |
| Evaluation comparison and the two axes | §7 | 1085–1134 | p19–20 |
Model configurations (layers / d / heads / MLP / parameter count) | Table 11 | 1102–1115 | p20 |
| Conclusion (body empty) | §8 | 1136 | p20 |
| End-to-end resources versus accuracy | Table 12 | 1150–1198 | p21 |
| Formal description of the three kinds of setup | Appendix A | 1345–1375 | p24 |
| Setup comparison matrix | Table 13 | 1363–1375 | p24 |
10. Open Questions and Citation Boundaries
This section is not about finding faults but about "whether this sentence can go straight into your paper". Five places need a qualifier:
- The setup attribution of 12.7%. The original "under MPC" is semantically broad, but the object of the paragraph is 2PC-Dealer. When citing, write "under the 2PC-Dealer setting (MPCFormer / Wang et al.)", not "in 2PC".
- 87.3% is not a number from the original. It is derived as 100 − 12.7. You may compute it yourself, but you must mark it derived, or just cite 12.7%.
- "Three threat models" is this note's framework, not the structure of the original. §3 formally defines only semi-honest and honest majority; the malicious model is mentioned in a single sentence in §4.2. When writing related work, it is more accurate to say "the survey discusses the semi-honest and honest-majority assumptions and mentions the malicious case".
- The positioning of FE. §2.3.1 says that FE puts only the first layer in ciphertext and computes the rest in plaintext, which would "leak some client data information to the server"; but the survey does not explicitly judge FE as failing Definition 1. "Lack of strict privacy protection" in Table 2 refers to THE-X's intermediate results, not to FE. The two sentences cannot be merged into a single citation.
- The rosters of Table 1 and Table 4 are inconsistent. The former has 30 rows, the latter 29 with SecFormer appearing twice; when doing systematic statistics (for example "21 papers under 2PC"), state that the basis is Table 1.
Three citation suggestions:
- When citing "30 works / three kinds of setup", use Table 1 and note that the counts are your own.
- When citing end-to-end numbers, the I./O. size and network conditions must be given at the same time (that is exactly what the
Comm. Set.column of Table 12 is for). - To cite "challenges and future directions", do not cite §8 (it is empty) — go back to §4.1, §7, and the primary papers cited, and summarise them yourself.
Related reading
Comments
Comments are not configured yet: deploy the Twikoo backend and set envId in lib/site.ts.