Skip to content

Trace-Factored BigSwitch for Matrix-Friendly FHE

Authors: Park, Jeong, Jeong, Oh, Lee, Kim
Year: 2026
Venue: IACR ePrint 2026/2058

type: scheme collection: catalogue, schemes status: auto

Links: ePrint 2026/2058

Summary

Auto-extracted summary (unreviewed)

Proposes Trace-Factored BigSwitch (TFB) for the Gentry-Lee matrix-native FHE framework: by exploiting the rank-one tensor structure of the Trace-generated key, the large product-secret evaluation key is eliminated and replaced by an sY-to-sX switch followed by ordinary base-ring relinearization, giving an exact (n-1)/(2n) (about 50%) evaluation-key memory saving. A companion technique, FRee-L, accumulates K Trace products in the four-component domain and runs BigSwitch once per output tile to amortize the extra relinearization. In an OpenFHE-linked prototype at n=256 the BigSwitch key footprint drops from 768.0 to 385.5 MiB, peak RSS by 15.31% and cold key preparation by 51-63%, while on GPT-2 attention kernels the overhead falls to 5.90% at K=4 and below 0.2% for K>=160.

Abstract

Evaluation keys represent a primary memory and initialization bottleneck in matrix-native fully homomorphic encryption (FHE). In the Gentry–Lee (GL) framework, each Trace product yields a four-component ciphertext whose BigSwitch procedure requires two extended-ring keys, dominated by a massive product-secret key (sXsY →sX). We present Trace-Factored BigSwitch (TFB), which structurally eliminates this product-secret evaluation key by exploiting the rank-one tensor structure of the Trace-generated key, (1, sX, sY , sXsY ) = (1, sY ) ⊗(1, sX). By routing the product secret through an sY →sX switch followed by standard base-ring s2 X →sX relinearization, TFB achieves an exact evaluation-key memory saving of (n −1)/(2n) (≈50%) without ever generating or storing evkXY →X. To amortize TFB’s recurring base-ring relinearization cost in blocked matrix multiplication, we introduce FRee-L (Fused Relinearization with noise reduction). FRee-L accumulates K Trace products componentwise in the four-component domain and invokes BigSwitch only once per output tile, reducing post-processing noise injections from K to one and amortizing the latency overhead as O(1/K). In our OpenFHE-linked prototype (n = 256), TFB reduces the coefficient-domain BigSwitch key footprint from 768.0 to 385.5 MiB (49.80%), peak RSS by 15.31%, and cold key preparation by 51–63%. On real GPT-2 attention kernels (K = 4), FRee-L lowers TFB’s paired overhead to 5.90%, which further diminishes to 0.1933% (K = 160) and 0.0618% (K = 512) in deep accumulation workloads, confirming that substantial key savings are achieved with negligible workload-level compute penalty.
Source: pdf

Extracted details

Field Value Source Confidence
contribution Trace-Factored BigSwitch (TFB) that structurally eliminates the product-secret evaluation key evk_{XY->X} in Gentry-Lee matrix-native FHE llm 0.85
contribution exact evaluation-key memory saving of (n-1)/(2n), about 50% llm 0.85
contribution FRee-L (Fused Relinearization with noise reduction) amortizing BigSwitch post-processing over K accumulated Trace products, reducing noise injections from K to one llm 0.85
contribution OpenFHE-linked, DCRTPoly-backed GL prototype with custom quotient-ring arithmetic, RNS/NTT kernels, exact fast Trace, Direct BigSwitch and TFB llm 0.85
contribution measurements on real GPT-2 attention kernels and deep-accumulation workloads llm 0.85
schemes Gentry-Lee matrix-native FHE llm 0.85
schemes RLWE llm 0.85
libraries OpenFHE llm 0.85
models GPT-2 llm 0.85
tasks encrypted matrix multiplication llm 0.85
tasks encrypted attention (transformer inference kernels) llm 0.85
interaction non-interactive FHE llm 0.85
limitations TFB is a capacity-first transformation, not a per-call latency optimization: the isolated post-processing overhead is 40.36% llm 0.85
limitations FRee-L applies only when compatible partial products contribute additively to the same output and remain within the aggregate decoding budget llm 0.85
limitations FRee-L neither eliminates input-encryption and Trace errors nor makes the extra TFB relinearization free llm 0.85
limitations large-K results are measured-component-composed statistics, not independent end-to-end model timings llm 0.85
limitations integration with representation conversions, scale management, nonlinear operations and bootstrapping is left to future work llm 0.85
llm relevance medium llm 0.85
key result BigSwitch evaluation-key footprint: 768.0 MiB -> 385.5 MiB (-49.80%) (n = 256, OpenFHE-linked GL prototype, coefficient domain) llm 0.85
key result peak RSS reduction: 15.31% (n = 256, variant-isolated) llm 0.85
key result cold key preparation time reduction: 51-63% (n = 256) llm 0.85
key result standalone BigSwitch post-processing time: 2.979 s (Direct) vs 4.181 s (TFB), +40.36% (microbenchmark of the post-processing stage only) llm 0.85
key result TFB kernel-level overhead with FRee-L: 5.90% (down from 15.27% with eager processing) (GPT-2 post-softmax O = PV, K = 4) llm 0.85
key result TFB overhead in deep accumulation: 0.1933% (K = 160), 0.0618% (K = 512) (model-mapped one-output-tile, measured-component-composed statistics) llm 0.85

System card: Trace-Factored BigSwitch (GL keys)

Group 4. Alternative FHE schemes
Family GL scheme key switching
Arithmetic Approximate real matrices
Interaction Non-interactive
Model scale -
Status Active SOTA (emerging)
Relation to the SoK Removes the largest GL evaluation key.
Note Targets the evaluation-key memory bottleneck of matrix-native FHE.
Systems page Trace-Factored BigSwitch (GL keys)

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Matrix-native FHE 8 [p.1], CKKS 2 [p.4], BFV 2 [p.4], BGV 2 [p.4]
  • library: OpenFHE 9 [p.1], Concrete (Zama) 1 [p.14]
  • model: GPT 19 [p.1], LLaMA 8 [p.3]
  • technique: Relinearization 50 [p.1], Softmax 12 [p.3], Key switching 10 [p.1], RNS 7 [p.3], Matrix multiplication 6 [p.1], NTT 5 [p.3], Compiler 5 [p.14], Bootstrapping 4 [p.21], Attention 2 [p.12], Quantization 2 [p.16]
  • assumption: RLWE 7 [p.4], LWE 6 [p.14], IND-CPA 6 [p.14], Lattice-based 4 [p.14]
  • task: Language modeling / generation 4 [p.11]
  • topic: Homomorphic encryption 28 [p.1], Benchmark 7 [p.4]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-134_trace-factored-bigswitch-for-matrix-friendly-fhe.pdf catalogue 24 1023.2 KB 60eb9f21f0b5
references/schemes/s26-3_eprint-2026-2058.pdf schemes 24 1023.2 KB 60eb9f21f0b5 byte-identical to references/catalogue/4-134_trace-factored-bigswitch-for-matrix-friendly-fhe.pdf

Database key: trace-factored-bigswitch-for-matrix-friendly-fhe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set trace-factored-bigswitch-for-matrix-friendly-fhe COLUMN VALUE