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 two-stage 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 the evaluated configurations, the faster GL axis order gives amortized per-slice StC speedups of 3.44x-4.10x at one thread and 7.75x-9.04x at 32 threads over the matched CKKS baselines. For full complex bootstrapping, the CKKS-to-GL per-slice latency ratios are 0.78-1.21 at one thread and 1.05-1.95 at 32 threads.