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
HYBRID ANALYSIS OF TMVP FOR MODULAR POLYNOMIAL MULTIPLICATION IN CRYPTOGRAPHY
Download
giray_efe_msc_thesis_v2.0.pdf
Date
2022-3-07
Author
Efe, Giray
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
469
views
92
downloads
Cite This
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 implemented under the quotient ring of polynomials, Z[x]/<x^n+-1>, matters. Instead of applying the reduction procedure as the final stage, using Toeplitz Matrix Product (i.e., TMVP) is a clever way to realize the modular multiplication more efficiently. Furthermore, the hybrid use of these algorithms yields more efficient results than the static choice of any single algorithm. For this purpose, we derive and analyze various constructions of multiplication and share the best possible sequences under different circumstances, and show that TMVP is a decent choice instead of classical modular polynomial multiplication approaches in cryptographic applications.
Subject Keywords
Cryptography, Modular Polynomial Multiplication, Hybrid Multiplication,TMVP, 2-way Split Multiplication, 3-way Split Multiplication, Karatsuba Multiplication, Toom-Cook Multiplication, Arithmetic Complexity Analysis, Delay Complexity Analysis, Cost Metrics, Hybrid Cost Calculation, Most Efficient Hybrid Cost Results
URI
https://hdl.handle.net/11511/96309
Collections
Graduate School of Applied Mathematics, Thesis
Suggestions
OpenMETU
Core
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...
Some new results on binary polynomial multiplication
Cenk, Murat (2015-11-01)
This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein's 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein's 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials ...
On the computation of generalized division polynomials
Küçüksakallı, Ömer (2015-01-01)
We give an algorithm to compute the generalized division polynomials for elliptic curves with complex multiplication. These polynomials can be used to generate the ray class fields of imaginary quadratic fields over the Hilbert class field with no restriction on the conductor.
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 three-way split formulas for binary polynomial multiplication
Cenk, Murat; Hasan, M. Anwar (2011-08-12)
In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
G. Efe, “HYBRID ANALYSIS OF TMVP FOR MODULAR POLYNOMIAL MULTIPLICATION IN CRYPTOGRAPHY,” M.S. - Master of Science, Middle East Technical University, 2022.