Hierarchical NTT architectures on FPGA

Fully Homomorphic Encryption (FHE) represents a paradigm shift in cryptography,enabling computations directly on encrypted data while preserving privacy. However,the computational complexity inherent in FHE operations, particularly polynomialmultiplications, presents a significant barrier to practical adoption. This thesisfocuses on addressing these challenges by developing high-performance, hardwareacceleratedarchitectures for FHE, with a particular emphasis on the optimizationof negacyclic Number Theoretic Transform (NTT) operations.The key contribution of this work is the introduction of a high speed, throughputoptimized,hierarchical 7-step NTT algorithm tailored for FPGA implementation.This approach builds on the negacyclic NTT method to enhance computational efficiencyby leveraging hierarchical partitioning of polynomial operations. Comparedto conventional 4-step NTT designs, the proposed architecture achieves superior scalabilityand resource efficiency, supporting polynomial sizes ranging from 210 to 216.By utilizing a modular and pipelined hardware architecture, the design overcomesmemory access bottlenecks, achieving significant improvement in NTT throughputcompared to state-of-the-art software implementations.The hierarchical design employs advanced techniques, including column independenceand unrolled NTT stages, to maximize throughput while minimizing latency.Additionally, the modular reduction operations utilize Word-Level Montgomery(WLM) methods, enabling compatibility with varying security levels andFHE parameters. The results highlight the practicality of negacyclic NTT-based hiiverarchical designs in high-throughput cryptographic applications, facilitating securedata processing in domains such as privacy-preserving machine learning, encrypteddatabase queries, and secure cloud computing.Our proposed design achieves significant performance improvements over state-ofthe-art implementations for NTT operations, with up to 8.14× speed-up in averagelatency and 4.01× better Area-Time-Product (ATP) for high-performance FPGAs.Compared to leading solutions, our seven-step architecture demonstrates superiorthroughput and scalability across various ring dimensions (n=210 to n=216), offeringup to 7.96× lower latency while maintaining resource efficiency. Furthermore,our design supports runtime-configurable parameters, making it a practical solution.