Paper 2020/1336

Faster Characteristic Three Polynomial Multiplication and Its Application to NTRU Prime Decapsulation

Esra Yeniaras and Murat Cenk


Efficient computation of polynomial multiplication for characteristic three fields, $\mathbb{F}_{3^{n}}$ for $n\geq1$, is an important attribute for many cryptographic protocols. In this paper, we propose three new polynomial multiplication algorithms over $\mathbb{F}_{3}[x]$ and show that they are more efficient than the current state-of-the-art algorithms. We first examine through the well-known multiplication algorithms in $\mathbb{F}_{3}[x]$ including Karatsuba-2-way and 3-way split formulas along with the recent enhancements. Then, we propose a new 4-way split polynomial multiplication algorithm and an improved version of it which are both derived by using interpolation in $\mathbb{F}_{9}$. Moreover, we propose a 5-way split multiplication algorithm, and then compare the efficiencies of these algorithms altogether. We apply the proposed algorithms to the NTRU Prime protocol, a post-quantum key encapsulation mechanism (KEM), submitted to the NIST PQC Competition by Bernstein et al., performing polynomial multiplication in characteristic three fields in its decapsulation phase. We observe that the new hybrid algorithms provide a $12.9\%$ reduction in the arithmetic complexity. Furthermore, we implement these new hybrid methods on Intel (R) Core (TM) i7-9750H architecture using C and obtain a $37.3\%$ reduction in the implementation cycle count.

Available format(s)
Publication info
Preprint. MINOR revision.
Polynomial multiplicationKaratsubaCharacteristic three fieldsKey encapsulationNTRU PrimeLattice-based cryptographyPost-quantum cryptography
Contact author(s)
yeniaras esra @ metu edu tr
mcenk @ metu edu tr
2020-10-26: received
Short URL
Creative Commons Attribution


      author = {Esra Yeniaras and Murat Cenk},
      title = {Faster Characteristic Three Polynomial Multiplication and Its Application to NTRU Prime Decapsulation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1336},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.