Proteus: A Pipelined NTT Architecture Generator

• Published in: IEEE transactions on very large scale integration (VLSI) systems 2024-07, Vol.32 (7), p.1228-1238
• Main Authors: Hirner, Florian, Mert, Ahmet Can, Roy, Sujoy Sinha
• Format: Article
• Language: English
• Subjects: Commutators; Computer architecture; Configuration management; Costs; Cryptography; Delays; Fully homomorphic encryption (FHE); Hardware; Homomorphic encryption; number theoretic transform (NTT); Optimization; parametric; pipelined; Polynomials; Quantum cryptography; zero-knowledge proof (ZKP)
• ISSN: 1063-8210; 1557-9999
• DOI: 10.1109/TVLSI.2024.3377366

Number theoretic transform (NTT) is a fundamental building block in emerging cryptographic constructions such as fully homomorphic encryption (FHE), post-quantum cryptography (PQC), and zero-knowledge proof (ZKP). In this work, we introduce Proteus, an open-source parametric hardware to generate pipelined architectures for the NTT. For a given parameter set including the polynomial degree and size of the coefficient modulus, Proteus can generate Radix-2 NTT architectures using single-path delay feedback (SDF) and multipath delay commutator (MDC) approaches. We also present a detailed analysis of NTT implementation approaches and use several optimizations to achieve the best NTT configuration. Our evaluations demonstrate performance gain up to 1.8 \times compared to SDF and MDC-based NTT implementations in the literature. Our SDF and MDC architectures use 1.75 \times and 6.5 \times less DSPs, and 3 \times and 10.5 \times less BRAMs, respectively, compared to state-of-the-art SDF and MDC-based NTT implementations.