Low-Depth Bootstrapping for Matrix-Native FHE¶
Authors: Shokri, Tsoutsos
Year: 2026
Venue: IACR ePrint 2026/811
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2026/811 · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
Shokri and Tsoutsos give the first concrete, low-depth complex bootstrapping procedure for the Gentry-Lee (GL) matrix-native approximate FHE scheme, combining a grouped depth-1 slot-to-coefficient transform (native plaintext-ciphertext matrix multiplication on the X axis, diagonal BSGS on the W axis) with a slice-wise adaptation of SHIP's half-bootstrap to the Gaussian (X, W) algebra, reducing online plaintext encodings to 2*phi(p)+2 per Y slice and accelerating the Rader NTT with fused kernels. With from-scratch C++ implementations of both CKKS SHIP and GL at 128-bit security (N = 2^13 to 2^15, single thread), GL achieves 2.55-3.12x faster amortized per-slice StC and 1.09-1.16x faster amortized per-slice complex bootstrapping than matched CKKS, consuming six levels per bootstrap.
Abstract¶
Fully homomorphic encryption (FHE) enables computation directly on encrypted data and is increasingly researched for privacy-preserving machine-learning inference. Such workloads are dominated by matrix multiplication, which is not represented natively by conventional vector-oriented FHE schemes. CKKS is widely used for approximate encrypted inference because it supports packed real and complex arithmetic; however, matrix multiplication generally requires specific packing formats that are tailored to certain models, and involves many expensive ciphertext rotations. Depending on the matrix dimensions and packing strategy, these techniques can introduce substantial latency and memory overhead. The recently proposed Gentry–Lee (GL) scheme instead provides native slot-encoded matrix arithmetic through a multivariate ring construction while retaining approximate packed computation. Although promising, the prime-p GL instances considered here require prime-length NTTs and a three-dimensional DFT message encoding, whose efficient implementation has received limited study. Moreover, the original scheme does not specify a concrete bootstrapping procedure, which is required to support the deep computations used by large neural-network models. In this work, we present a low-depth complex bootstrapping framework tailored to the GL scheme. Our construction combines a grouped, depth-1 GL StC, in which the X-axis inversion uses native plaintext–ciphertext matrix multiplication and the W-axis inversion uses a diagonal BSGS transform, with a slice-wise adaptation of SHIP to the Gaussian (X, W) algebra. The public masked-column candidates evaluate the complete W-axis monomial action and the fine X-axis residue, leaving only the coarse X-axis displacement for hidden HMux selection and eliminating encrypted W-axis selection. We further algebraically reduce the online plaintext-encoding requirement of the masked-column interface from the fully expanded candidate-family upper bound of 8θφ(p) + 2 to 2φ(p) + 2 plaintexts per Y slice and optimize the Rader NTT through fused kernels and other arithmetic optimizations. Across matched CKKS configurations, GL achieves a 2.55×–3.12× speedup in amortized per-slice StC latency and a 1.09×–1.16× speedup in amortized per-slice complex-bootstrap latency.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | First concrete low-depth complex bootstrapping framework for the Gentry-Lee matrix-native FHE scheme | llm | 0.85 |
| contribution | Grouped depth-1 GL StC using native plaintext-ciphertext matrix multiplication and diagonal BSGS | llm | 0.85 |
| contribution | Slice-wise SHIP-style half-bootstrap with X-only hidden HMux selection | llm | 0.85 |
| contribution | Reduction of online plaintext encodings from 8thetaphi(p)+2 to 2*phi(p)+2 per Y slice | llm | 0.85 |
| contribution | Fused-kernel Rader NTT and from-scratch C++ implementations of CKKS SHIP and GL | llm | 0.85 |
| schemes | Gentry-Lee (GL) matrix-native FHE | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| libraries | OpenBLAS | llm | 0.85 |
| tasks | FHE bootstrapping | llm | 0.85 |
| tasks | encrypted matrix arithmetic for privacy-preserving ML inference | llm | 0.85 |
| hardware | AMD Ryzen Threadripper 7970X CPU (32 cores, 160 GB RAM), single thread | llm | 0.85 |
| security level | 128-bit (dense uniform-ternary secret; sparse bootstrapping secret h = 31 under SHIP's bounded-window analysis) | llm | 0.85 |
| threat model | client-server private inference; server evaluates on ciphertexts without the key | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | SHIP comparison is implementation-level only: different hardware and SHIP uses hand-optimized AVX2 kernels | llm | 0.85 |
| limitations | Only prime-p GL instances are considered, which require prime-length NTTs and a 3D DFT encoding | llm | 0.85 |
| limitations | Not yet applied to private neural-network or transformer inference; GPU acceleration left for future work | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | amortized per-slice StC speed-up: 2.55x-3.12x (GL vs matched CKKS, N = 2^13-2^15, 128-bit security, single thread) | llm | 0.85 |
| key result | amortized per-slice complex bootstrap speed-up: 1.09x-1.16x (GL vs matched CKKS, six-level bootstrap) | llm | 0.85 |
| key result | CKKS SHIP reimplementation latency: 27.41 s (18.64-bit precision) vs reported SHIP 29.6 s (HT15 parameter set, N = 2^15) | llm | 0.85 |
| key result | CKKS SHIP reimplementation accuracy: within about 9% of reported SHIP latencies (LL13, LL14, HT14, HT15 parameter sets) | llm | 0.85 |
| key result | multiplicative depth outside bootstrapping: 8 levels (GL n1024p17 and CKKS HT15-secure, N = 2^15, log(PQ) = 861) | llm | 0.85 |
System card: Low-depth bootstrapping for matrix-native FHE¶
| Group | 4. Alternative FHE schemes |
| Family | GL scheme bootstrapping |
| Arithmetic | Approximate real matrices |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Active SOTA (emerging) |
| Relation to the SoK | Reduces bootstrapping depth in GL-style schemes. |
| Note | Same authors as Terrazzo. |
| Systems page | Low-depth bootstrapping for matrix-native FHE |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 84 [p.1], Matrix-native FHE 10 [p.1]
- model: CNN 1 [p.19]
- hardware: GPU 3 [p.2]
- technique: Bootstrapping 77 [p.1], Matrix multiplication 34 [p.1], Rotations 32 [p.1], Key switching 15 [p.3], NTT 13 [p.1], Rescaling 12 [p.3], Relinearization 6 [p.3], RNS 6 [p.6], Convolution 5 [p.4], SIMD packing 3 [p.2]
- assumption: RLWE 20 [p.1], LWE 4 [p.1], Lattice-based 2 [p.19]
- task: Language modeling / generation 3 [p.7]
- topic: Homomorphic encryption 30 [p.1], Privacy-preserving machine learning 4 [p.1], Private / secure inference 3 [p.1], Benchmark 3 [p.3]
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-133_low-depth-bootstrapping-for-matrix-native-fhe.pdf |
catalogue | 20 | 499.3 KB | 26c39bf6dd4a |
|
references/schemes/s26-2_eprint-2026-811.pdf |
schemes | 20 | 499.3 KB | 26c39bf6dd4a |
byte-identical to references/catalogue/4-133_low-depth-bootstrapping-for-matrix-native-fhe.pdf |
Database key: low-depth-bootstrapping-for-matrix-native-fhe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set low-depth-bootstrapping-for-matrix-native-fhe COLUMN VALUE