International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
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
Download:
DOI: 10.13154/tches.v2020.i2.49-72
URL: https://tches.iacr.org/index.php/TCHES/article/view/8544
Search ePrint
Search Google
Presentation: Slides
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.
Video from TCHES 2020
BibTeX
@article{tches-2020-30154,
  title={Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 2},
  pages={49-72},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8544},
  doi={10.13154/tches.v2020.i2.49-72},
  author={Neng Zhang and Bohan Yang and Chen Chen and Shouyi Yin and Shaojun Wei and Leibo Liu},
  year=2020
}