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

Date

2022-01-01

Author

Yeniaras, Esra
Cenk, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

197
views

0
downloads

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.

Subject Keywords

Characteristic three fields, Karatsuba, Key encapsulation, Lattice-based cryptography, NTRU Prime, Polynomial multiplication, Post-quantum cryptography, DISCRETE LOGARITHMS, ALGORITHMS, FORMULAS, FIELDS

URI

https://hdl.handle.net/11511/95275

Journal

JOURNAL OF CRYPTOGRAPHIC ENGINEERING

DOI

https://doi.org/10.1007/s13389-021-00282-7

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME 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) 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 fast...
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...
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...
On multiplication in finite fields Cenk, Murat; Özbudak, Ferruh (2010-04-01) We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite ...

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: https://hdl.handle.net/11511/95275.