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
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
NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME
Download
Esra_Yeniaras_Tez.pdf
Date
2022-1-21
Author
Yeniaras, Esra
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
533
views
475
downloads
Cite This
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’s three 3-way split method, Toom-Cook-like formulas, and other recent algorithms. We realize that there are not any 4-way or 5-way split multiplication algorithms in characteristic three fields unlike the binary (characteristic two) fields which have various 4, 5, or more split versions. We then propose three different 4-way split polynomial multiplication algorithms which are derived by using the interpolation technique in F_9. Furthermore, we propose a new 5-way split polynomial multiplication algorithm and then compare the arithmetic complexities and the implementation results for all of the aforementioned 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 F_9 and a 26.8% reduction for multiplication over F_3 for the input size 1280. Moreover, the new 4-way and 5-way algorithms yield faster implementation results compared to the current state-of-the-art methods. We apply the proposed methods to NTRU Prime protocol, a key encapsulation mechanism, submitted to NIST PQC Standardization Process by Bernstein et al., which executes characteristic three polynomial multiplication in its decapsulation stage. We implement the new methods in C and 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.
Subject Keywords
Efficient polynomial multiplication, Characteristic three fields, Karatsuba, Interpolation, Post-quantum cryptography, Lattice-based cryptography, Key encapsulation mechanism, NTRU Prime
URI
https://hdl.handle.net/11511/95245
Collections
Graduate School of Applied Mathematics, Thesis
Suggestions
OpenMETU
Core
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...
Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation
Yeniaras, Esra; Cenk, Murat (2022-01-01)
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 ...
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Ali, Shoukat; Cenk, Murat (2016-12-02)
We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
HYBRID ANALYSIS OF TMVP FOR MODULAR POLYNOMIAL MULTIPLICATION IN CRYPTOGRAPHY
Efe, Giray; Cenk, Murat; Department of Cryptography (2022-3-07)
Polynomial multiplication on the quotient ring Z[x]/<x^n+-1> is one of the most fundamental, general-purpose operations frequently used in cryptographic algorithms. Therefore, a possible improvement over a multiplication algorithm directly affects the performance of algorithms used in a cryptographic application. Well-known multiplication algorithms such as Schoolbook, Karatsuba, and Toom-Cook are dominant choices against NTT in small and ordinary input sizes. On the other hand, how these approaches are imp...
New Efficient Algorithms for Multiplication Over Fields of Characteristic Three
Cenk, Murat; Hasan, M. Anwar (2018-03-01)
In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by where nae1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in . Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over and . The final proposal is a new 3-way polynomial...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
E. Yeniaras, “NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME,” Ph.D. - Doctoral Program, Middle East Technical University, 2022.