Paper 2023/686

Efficient Accelerator for NTT-based Polynomial Multiplication

Raziyeh Salarifard, Shahid Beheshti University
Hadi Soleimany, Shahid Beheshti University
Abstract

The Number Theoretic Transform (NTT) is used to efficiently execute polynomial multiplication. It has become an important part of lattice-based post-quantum methods and the subsequent generation of standard cryptographic systems. However, implementing post-quantum schemes is challenging since they rely on intricate structures. This paper demonstrates how to develop a high-speed NTT multiplier highly optimized for FPGAs with few logical resources. We describe a novel architecture for NTT that leverages unique precomputation. Our method efficiently maps these specific pre-computed values into the built-in Block RAMs (BRAMs), which greatly reduces the area and time required for implementation when compared to previous works. We have chosen Kyber parameters to implement the proposed architectures. Compared to the most well-known approach for implementing Kyber’s polynomial multiplication using NTT, the time is reduced by 31%, and AT (area × time) is improved by 25% as a result of the pre computation we suggest in this study. It is worth mentioning that we obtained these improvements while our method does not require DSP.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. Journal of Cryptographic Engineering
DOI
10.1007/s13389-024-00357-1
Keywords
Post quantum cryptographyCrystals-KyberNumber Theoretic Transformpolynomial multiplication
Contact author(s)
r_salarifard @ sbu ac ir
h_soleimany @ sbu ac ir
History
2024-08-13: revised
2023-05-15: received
See all versions
Short URL
https://ia.cr/2023/686
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/686,
      author = {Raziyeh Salarifard and Hadi Soleimany},
      title = {Efficient Accelerator for {NTT}-based Polynomial Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/686},
      year = {2023},
      doi = {10.1007/s13389-024-00357-1},
      url = {https://eprint.iacr.org/2023/686}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.