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]
Related papers¶
- this paper follow up of Fully Homomorphic Encryption for Matrix Arithmetic — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
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