HF-NTT: Hazard-Free Dataflow Accelerator for Number Theoretic Transform
<|reference_start|>HF-NTT: Hazard-Free Dataflow Accelerator for Number Theoretic Transform: Polynomial multiplication is one of the fundamental operations in many applications, such as fully homomorphic encryption (FHE). However, the computational inefficiency stemming from polynomials with many large-bit coefficients poses a significant challenge for the practical implementation of FHE. The Number Theoretic Transform (NTT) has proven an effective tool in enhancing polynomial multiplication, but a fast and adaptable method for generating NTT accelerators is lacking. In this paper, we introduce HF-NTT, a novel NTT accelerator. HF-NTT efficiently handles polynomials of varying degrees and moduli, allowing for a balance between performance and hardware resources by adjusting the number of Processing Elements (PEs). Meanwhile, we introduce a data movement strategy that eliminates the need for bit-reversal operations, resolves different hazards, and reduces the clock cycles. Furthermore, Our accelerator includes a hardware-friendly modular multiplication design and a configurable PE capable of adapting its data path, resulting in a universal architecture. We synthesized and implemented prototype using Vivado 2022.2, and evaluated it on the Xilinx Virtex-7 FPGA platform. The results demonstrate significant improvements in Area-Time-Product (ATP) and processing speed for different polynomial degrees. In scenarios involving multi-modulus polynomial multiplication, our prototype consistently outperforms other designs in both ATP and latency metrics.<|reference_end|>
@article{meng2024hf-ntt:,
    title={HF-NTT: Hazard-Free Dataflow Accelerator for Number Theoretic Transform},
    author={Xiangchen Meng, Zijun Jiang, Yangdi Lyu},
    journal={arXiv preprint arXiv:2410.04805},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04805},
    primaryClass={cs.AR cs.CR}
}