Efficient subquadratic space complexity binary polynomial multipliers based on block recombination

Download

index.pdf

Date

2014-09-01

Author

Cenk, Murat
Negre, Christophe

Metadata

Show full item record

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

Item Usage Stats

235
views

0
downloads

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 multipliers.

Subject Keywords

Block recombination, Binary field, Subquadratic space complexity, Two-way, three-way and four-way split formula, Binary polynomial multiplication

URI

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

Journal

IEEE Transactions on Computers

DOI

https://doi.org/10.1109/tc.2013.105

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

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...
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 ...
Modular exponentiation methods in cryptography Yünüak, Hasan Bartu; Cenk, Murat; Department of Cryptography (2017) Modular exponentiation has an important role in many cryptographic algorithms. These exponentiation methods differ in the bases used and their representations, the repeating aspect, and for which algorithms they are used for: fixed or variable base. Our research aims to compare the efficiencies and implementation timings for some selected algorithms. Also, we look at the options for using a dedicated cubing algorithm, and compare them with the current algorithms.
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 and Toeplitz Matrix Vector Products Cenk, Murat; Hasan, M. Anwar (2013-07-01) In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that a...

Citation Formats

M. Cenk and C. Negre, “Efficient subquadratic space complexity binary polynomial multipliers based on block recombination,” IEEE Transactions on Computers, pp. 2273–2287, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31923.