Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation

Yeniaras, Esra
Cenk, Murat
Efficient computation of polynomial multiplication over characteristic three fields is required for post-quantum cryptographic applications which gain importance upon the recent advances in quantum computers. In this paper, we propose three new polynomial multiplication algorithms over F-3 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 F-3[x] including the Karatsuba 2-way and 3-way split formulas along with the latest 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 F-9, the finite field with nine elements. Moreover, we propose a 5-way split multiplication algorithm and then compare the efficiencies of these algorithms altogether. Even though there exist 4-way or 5-way split multiplication algorithms in characteristic two (binary) fields, there has not been any such algorithms developed for characteristic three fields before this paper. We apply the proposed algorithms to the NTRU Prime protocol, a post-quantum key encapsulation mechanism, submitted to the MST PQC Competition by Bernstein et al., performing polynomial multiplication over 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.


Yeniaras, Esra; Cenk, Murat; Department of Cryptography (2022-1-21)
Some of the post-quantum cryptographic protocols require polynomial multiplication in characteristic three fields, thus the efficiency of such multiplication algorithms gain more importance recently. In this thesis, we propose four new polynomial multiplication algorithms in characteristic three fields and we show that they are more efficient than the current state-of-the-art methods. We first analyze the well-known algorithms such as the schoolbook method, Karatsuba 2-way and 3-way split methods, Bernstein...
Improved Polynomial Multiplication Algorithms over Characteristic Three Fields and Applications to NTRU Prime
Yeniaras, Esra; Cenk, Murat (2022-01-01)
© 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 ver...
Efficient multiplications in F(5)5n and F(7)7n
Cenk, Murat; Özbudak, Ferruh (2011-08-15)
Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F(5)5n and F(7)7n are obtained with 10 multiplications in F(5)n for F(5)5n and 15 multiplications in F(7)n for F(7)7n improving the results in Cenk and Ozbudak (2008) [4], Cenk et al. (2009) [5], Lee et al...
Efficient subquadratic space complexity binary polynomial multipliers based on block recombination
Cenk, Murat; Negre, Christophe (2014-09-01)
Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper we consider two, three and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two, three and four-way split mult...
Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields
Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2010-09-24)
In this paper, we give faster versions of Montgomery modular multiplication algorithm without pre-computational phase for GF(p) and GF(2 m ) which can be considered as a generalization of [3], [4] and [5]. We propose sets of moduli different than [3], [4] and [5] which can be used in PKC applications. We show that one can obtain efficient Montgomery modular multiplication architecture in view of the number of AND gates and XOR gates by choosing proposed sets of moduli. We eliminate precomputational phase wi...
Citation Formats
E. Yeniaras and M. Cenk, “Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation,” JOURNAL OF CRYPTOGRAPHIC ENGINEERING, pp. 0–0, 2022, Accessed: 00, 2022. [Online]. Available: