Akademik Veri Yönetim Sistemi
14th International Conference on Innovative Security Solutions for Information Technology and Communications, SecITC 2021, Virtual, Online, 25 - 26 Kasım 2021, cilt.13195 LNCS, ss.125-144
© 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.