Implementation of Number Theoretic Transform Unit for Polynomial Multiplication of Lattice-based Cryptography

In the post-quantum Internet of Things (loT) era, the use of anti-quantum cryptographic algorithms in a large number of terminals can effectively resist potential quantum computing attacks. The lattice-based cryptography has the characteristics of resisting quantum computing attacks, and will be an alternative to the traditional public-key cryptographic algorithm that is widely deployed now. However, the relatively large time complexity of the algorithm itself will bring considerable computational overhead to the edge computing chip in the IoT terminal. Polynomial multiplication is the most computationally intensive operation in lattice-based cryptographic algorithms, and the research on fast calculation of polynomial multiplication is of great significance. Using fast number theory transformations to speed up polynomial multiplication is a common method. This paper proposes a hardware implementation of a fast number theory transformation. We used multiple arithmetic units in the design to achieve parallel calculations, and implemented it on ASIC. The performance evaluation results show that our implementation performance is greatly improved compared to other implementation, and it can be deployed in edge computing chips to increase computing speed.