Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
276
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.