SANTA: A Spatial Accelerator Design for Efficient Number Theoretic Transform (NTT) on Heterogeneous System-on-Chips

Recent developments in lattice-based post-quantum cryptographic (PQC) algorithms are drawing attention to their implementation on low-power edge devices. Number theoretic transform (NTT) is the core mathematical operation of the lattice-based PQC algorithm. Hence, a power-efficient NTT accelerator is the fundamental building block of edge device-friendly PQC implementation. This paper presents SANTA, the world's first accelerator for NTT computation on AMD's Versal ® Adaptive System on Chip (ASoC), an edge-application-oriented spatial computation system. We leverage ASoC's single instruction multiple data (SIMD) feature in our proposed accelerator design by vectorizing the NTT computation to achieve speed gain. We further accelerate the NTT computation by utilizing the two-dimensional spatial computing architecture of the ASoC platform to distribute the workload for parallel processing. We also evaluate the runtime and power consumption of our proposed NTT accelerator on AMD's Versal VCK190 evaluation board. Our results show that edge deployable spatial accelerators can significantly improve performance over traditional CPUs. For 4096-point NTT, SANTA demonstrates 2.8× speed gain over the state-of-the-art CPU implementation. We have published this work's open-source codes at https://github.com/SPIRE-GMU/ACAP_NTT.