New Efficient Characteristic Three Polynomial Multiplication Algorithms and Their Applications to NTRU Prime

In this talk, I will introduce four new polynomial multiplication algorithms in characteristic three fields and show that they are more efficient than the current state-of-the-art methods. We show that the new 4-way and 5-way split algorithms provide a 48.6% reduction in the arithmetic complexity for multiplication over F9 and a 26.8% reduction for multiplication over F3 for the input size 1280. We apply the proposed methods to NTRU Prime decapsulation, submitted to NIST PQC Standardization Process by Bernstein et al. and by implementing in C we observe a 26.85% speedup for stnrup653 and a 35.52% speedup for sntrup761 in the characteristic three polynomial multiplication step of the NTRU Prime decapsulation.

This talk is based on joint work with Murat Cenk, appearing at the Journal of Cryptographic Engineering and presented at SECITC’21.

Suggested readings: ia.cr/2020/1336, doi:10.1007/s13389-021-00282-7, github.com/cryptoarith