Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT

  • Neng Zhang Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
  • Bohan Yang Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
  • Chen Chen Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
  • Shouyi Yin Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
  • Shaojun Wei Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
  • Leibo Liu Institute of Microelectronics, Tsinghua University, Beijing, 100084, China
Keywords: NewHope, FPGA, post-quantum cryptography, ring learning with errors, number theoretic transform

Abstract

NewHope-NIST is a promising ring learning with errors (RLWE)-based postquantum cryptography (PQC) for key encapsulation mechanisms. The performance on the field-programmable gate array (FPGA) affects the applicability of NewHope-NIST. In RLWE-based PQC algorithms, the number theoretic transform (NTT) is one of the most time-consuming operations. In this paper, low-complexity NTT and inverse NTT (INTT) are used to implement highly efficient NewHope-NIST on FPGA. First, both the pre-processing of NTT and the post-processing of INTT are merged into the fast Fourier transform (FFT) algorithm, which reduces N and 2N modular multiplications for N-point NTT and INTT, respectively. Second, a compact butterfly unit and an efficient modular reduction on the modulus 12289 are proposed for the low-complexity NTT/INTT architecture, which achieves an improvement of approximately 3× in the area time product (ATP) compared with the results of the state-of-the-art designs. Finally, a highly efficient architecture with doubled bandwidth and timing hiding for NewHope-NIST is presented. The implementation results on an FPGA show that our design is at least 2.5× faster and has 4.9× smaller ATP compared with the results of the state-of-the-art designs of NewHope-NIST on similar platforms.

Published
2020-03-02
How to Cite
Zhang, N., Yang, B., Chen, C., Yin, S., Wei, S., & Liu, L. (2020). Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(2), 49-72. https://doi.org/10.13154/tches.v2020.i2.49-72
Section
Articles