Paper 2026/811

Low-Depth Bootstrapping for Matrix-Native FHE

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\theta\varphi(p)+2\) to \(2\varphi(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\times\)-\(3.12\times\) speedup in amortized per-slice StC latency and a \(1.09\times\)-\(1.16\times\) speedup in amortized per-slice complex-bootstrap latency.