Peregrine: Accelerating TFHE Bootstrapping on GPUs via Multi-Level External Product Co-Design

Fully Homomorphic Encryption (FHE) is a ground-breaking cryptographic technology that enables computation directly on encrypted data, but its practical adoption continues to be hindered by high computational costs. GPUs have emerged as an increasingly attractive acceleration platform, offering massive parallelism and architectural flexibility to accommodate rapidly evolving FHE algorithms. Despite notable advances, most efforts remain confined to isolated, single-level optimizations, limiting their ability to push performance boundaries. In this paper, we present Peregrine, an efficient GPU-based TFHE acceleration built upon multi-level co-design of external product (EP) operations across parallelism, implementation, and scheduling. First, we propose a synchronization-free key unrolling technique that restructures the execution pipeline via operator decoupling, thereby unlocking greater EP-level parallelism. Second, we consolidate fragmented operators into a matrix-centric execution pattern, yielding a high-arithmetic-intensity kernel that substantially enhances external product efficiency. Third, we propose a hierarchical tiling strategy that reformats ring ciphertexts into the Module structure and schedules polynomiallevel tiles for fine-grained GPU mapping of EP operations. Experimental results show that Peregrine outperforms up to$176.9 \times$and$2.2 \times$over state-of-the-art CPU and GPU baselines, respectively, demonstrating its strong applicability to security-critical workloads.