一句话：通过算法-硬件协同设计重构 TFHE 盲旋转与 NTT，显著提升 GPU 自举性能。
全同态加密可在密文上计算，但 TFHE 自举计算开销极高，且仅靠硬件算力扩展受限于算法并行度不足与硬件行为理解不够。本文提出 GPU 方案 Maverick，进行算法-硬件协同设计。算法层将盲旋转的测试向量由预加载改为后注入，把长度 n 的单链重构为 √n 条深度 √n 的子链，使外积（EP）并行度从 1 提升到理论上界 √n。硬件层采用部分域变换，阶段感知地提前终止 NTT，将计算选择性下移并重划算子边界，以均衡 EP 算子负载。实验显示，Maverick 在可编程自举上比最佳 CPU、GPU 基线分别快 331.2× 和 3.4×，在电路自举上较 CPU 最高加速 108.5×。
Fully homomorphic encryption (FHE) enables arbitrary computation over encrypted data (ciphertext) without compromising confidentiality. Within this family, TFHE features versatile bootstrapping mechanisms that is attractive for security-critical applications. However, its prohibitive computational cost severely limits practical deployment. While hardware acceleration is promising, mere compute scaling fails to overcome the inherent barriers. In particular, the combination of limited algorithmic parallelism and inadequate understanding of hardware behaviors prevents full exploitation of the available performance headroom. In this paper, we present Maverick, a GPU-based solution that rethinks TFHE bootstrapping acceleration through joint algorithm–hardware co-design. At the algorithmic level, we reconstruct blind rotation by shifting test vectors from pre-loading to post-injection. This reformulation turns the original length-n single chain into a multi-chain structure with √n sub-chains of depth √n, raising external-product (EP) parallelism from 1 to the theoretical bound of √n. At the hardware level, we introduce a partial-domain transformation strategy that terminates the NTT early in a stage-aware manner and selectively shifts computation to downstream operators, redefining operator boundaries to balance the workload across EP operators. Experimental results show that Maverick delivers state-of-the-art GPU acceleration. It outperforms the best existing CPU and GPU baselines by 331.2× and 3.4×, respectively, on programmable bootstrapping, and achieves up to 108.5× speedup over CPU-based circuit bootstrapping. Together, these results highlight the substantial potential of algorithm–hardware co-design for advancing FHE performance on general-purpose platforms.
@inproceedings{WangHZN0026,
title = {Maverick: Rethinking TFHE Bootstrapping on GPUs via Algorithm-Hardware Co-Design},
author = {Zhiwei Wang and Haoqi He and Lutan Zhao and Qingyun Niu and Dan Meng and Rui Hou},
booktitle = {ASPLOS},
year = {2026},
doi = {10.1145/3779212.3790186}
}