Paper 2026/853

MRFHE: Mixed-Radix Fully Homomorphic Encryption with Better Batch Bootstrapping

Abstract

Fully homomorphic encryption is a promising cryptographic primitive for privacy-preserving computation, yet bootstrapping remains the primary bottleneck for its practical deployment. For the CKKS scheme, the dominant cost of bootstrapping arises from the homomorphic evaluation of the Discrete Fourier Transform (DFT) and its inverse. Existing approaches realize these operations as matrix-vector products, thereby relying heavily on a large number of homomorphic rotations, a type of key-switching operation. Despite substantial efforts to reduce the rotation count, these transforms remain fundamentally rotation-heavy -- requiring $O(r \cdot N^{1/2r})$ rotations per ciphertext at the cost of $r$ multiplicative levels, where $N$ is the ring degree -- and still account for a major portion of the overall bootstrapping latency. In this paper, we resolve this dependency in a batched manner, yielding a novel batch bootstrapping algorithm. We propose \emph{MRFHE}, an FHE scheme over a mixed-radix cyclotomic ring, which inherently decomposes the DFT into two layers -- a radix-$2$ DFT and a radix-$3$ DFT. This structure allows the homomorphic linear transformations during bootstrapping to be realized as two smaller, independent DFT evaluations. By batching ciphertexts, each smaller DFT can be reduced to a batch matrix multiplication over cleartexts, requiring only $O(1)$ key-switching operations per ciphertext and admitting efficient acceleration by highly optimized libraries such as BLAS and FLINT. We implement MRFHE on top of the Lattigo library, demonstrating significant efficiency gains in batch bootstrapping and general ciphertext operations.