Paper 2020/1397

NTT Multiplication for NTT-unfriendly Rings

Chi-Ming Marvin Chung, Vincent Hwang, Matthias J. Kannwischer, Gregor Seiler, Cheng-Jhih Shih, and Bo-Yin Yang

Abstract

In this paper, we show how multiplication for polynomial rings used in the NIST PQC finalists Saber and NTRU can be efficiently implemented using the Number-theoretic transform (NTT). We obtain superior performance compared to the previous state of the art implementations using Toom–Cook multiplication on both NIST’s primary software optimization targets AVX2 and Cortex-M4. Interestingly, these two platforms require different approaches: On the Cortex-M4, we use 32-bit NTT-based polynomial multiplication, while on Intel we use two 16-bit NTT-based polynomial multiplications and combine the products using the Chinese Remainder Theorem (CRT). For Saber, the performance gain is particularly pronounced. On Cortex-M4, the Saber NTT-based matrix-vector multiplication is 61% faster than the Toom-Cook multiplication resulting in 22% fewer cycles for Saber encapsulation. For NTRU, the speed-up is less impressive, but still NTT-based multiplication performs better than Toom–Cook for all parameter sets on Cortex-M4. The NTT-based polynomial multiplication for NTRU-HRSS is 10% faster than Toom–Cook which results in a 6% cost reduction for encapsulation. On AVX2, we obtain speed-ups for three out of four NTRU parameter sets. As a further illustration, we also include code for AVX2 and Cortex-M4 for the Chinese Association for Cryptologic Research competition award winner LAC (also a NIST round 2 candidate) which outperforms existing code.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2021
Keywords
Polynomial MultiplicationNTT MultiplicationSaberNTRUCortexM4AVX2
Contact author(s)
marvin852316497 @ gmail com
vincentvbh7 @ gmail com
cs861324 @ gmail com
by @ crypto tw
matthias @ kannwischer eu
gseiler @ inf ethz ch
History
2021-01-14: revised
2020-11-10: received
See all versions
Short URL
https://ia.cr/2020/1397
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1397,
      author = {Chi-Ming Marvin Chung and Vincent Hwang and Matthias J.  Kannwischer and Gregor Seiler and Cheng-Jhih Shih and Bo-Yin Yang},
      title = {NTT Multiplication for NTT-unfriendly Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1397},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1397}},
      url = {https://eprint.iacr.org/2020/1397}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.