Improved Polynomial Multiplication Algorithms over Characteristic Three Fields and Applications to NTRU Prime

Yeniaras E., CENK M.

14th International Conference on Innovative Security Solutions for Information Technology and Communications, SecITC 2021, Virtual, Online, 25 - 26 November 2021, vol.13195 LNCS, pp.125-144 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 13195 LNCS
  • Doi Number: 10.1007/978-3-031-17510-7_9
  • City: Virtual, Online
  • Page Numbers: pp.125-144
  • Keywords: Characteristic three fields, Efficient polynomial multiplication, Interpolation, Karatsuba, Key encapsulation, Lattice-based cryptography, NTRU prime, Post-quantum cryptography
  • Middle East Technical University Affiliated: Yes


© 2022, Springer Nature Switzerland AG.This paper introduces a new polynomial multiplication algorithm which decreases the arithmetic complexity and another modified algorithm that speeds up the implementation run-time over the characteristic three fields. We first introduce a new polynomial multiplication algorithm using a 4-way split approach and observe that its asymptotic arithmetic complexity is better than Bernstein’s 3-way method for characteristic three fields. We then define an unbalanced split version a 5-way split method which is faster than Bernstein’s 3-way method in terms of implementation speed. We observe that, compared to the most recent methods, for the input size 1280, the new 4-way method together with the unbalanced 5-way split one provide a 48.6 % decrease in arithmetic complexity for polynomial multiplication over F9 and a 26.8 % decrease for polynomial multiplication over F3 respectively. Moreover, from the implementation perspective, the unbalanced 5-way algorithm yields faster polynomial multiplication results. For application purposes, we pick the quantum-resistant key encapsulation protocol NTRU Prime, proposed by Bernstein et al., since it executes a characteristic three polynomial multiplication in the decapsulation stage. Implementing the proposed algorithms combining with the other known methods in C, on an Intel (R) Core (TM) i7-10510U architecture, we observe a 29.85 % speedup for sntrup653 and a 35.52 % speedup for sntrup761.