Optimizing Systolic Array-Based NTT Accelerators

Lattice-based Post-quantum cryptography and Homomorphic Encryption schemes have become the key methodologies for today’s and the future’s secure world. This comes at the cost of a vastly increased computational load due to the multiplication of wide-integer coefficient polynomials. NIST recommends Number Theoretic Transform (NTT) as an efficient remedy. Nevertheless, NTT strongly requires acceleration for large numbers of coefficients. This paper explores the use of systolic arrays as NTT accelerators and finds an optimal hardware architecture configuration across problem sizes. Design-space exploration is performed, resulting in a new design configuration for an efficient two-dimensional NTT accelerator without losing the ability to execute other workloads. Our finding indicates that for 22 nm technology, an optimal systolic array accelerator requires an area of 53.04 mm2. The accelerator can efficiently execute and apply NTT on a polynomial with 4096 32-bit integer coefficients requiring 3296 cycles, and 1794.92 nJ.