A Depth-First Iterative Number-Theoretic Transform Architecture for CKKS Bootstrapping on FPGA

Despite the potential of fully homomorphic encryption as a solution to privacy-preserving calculations, it faces limitations in practical deployment, especially in Cheon-Kim-Kim-Song (CKKS) bootstrapping, where large-scale polynomial computations require a lot of computing resources. Conventional number-theoretic transform (NTT) implementations often encounter high memory usage, limited local data, and less scalable hardware, especially in multi-prime scenarios. We propose a depth-first search (DFS) strategy for NTT computation and a DFS-based mixed-radix for performing CKKS bootstrapping. This proposed design combines local buffer reuse with a modular, stack-based control scheme, which reduces unnecessary memory access and prevents redundant hardware replication among primes, achieving a high area-time efficiency. On Xilinx Artix UltraScale FPGA, this design executes a complete 54-prime, 2¹⁷-point NTT in 3.33 milliseconds, relying less on logic and BRAM than similar solutions and yielding better area-time-product and scalability compared to the latest state-of-the-art designs.