Karatsuba-like formulae and their associated techniques

Date

2018-09-01

Author

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

186
views

0
downloads

Efficient polynomial multiplication formulae are required for cryptographic computation. From elliptic curve cryptography to homomorphic encryption, many cryptographic systems need efficient multiplication formulae. The most widely used multiplication formulae for cryptographic systems are the Karatsuba-like polynomial multiplication formulae. In this paper, these formulae and Montgomery's work yielding more efficient such formulae are introduced. Moreover, recent efforts to improve these results are discussed by presenting associated techniques. The state of art for this area is also discussed.

Subject Keywords

Polynomial multiplication, Karatsuba algorithm, Cryptographic computation, Chinese remainder theorem

URI

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

Journal

JOURNAL OF CRYPTOGRAPHIC ENGINEERING

DOI

https://doi.org/10.1007/s13389-017-0155-8

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18 Cenk, Murat; Özbudak, Ferruh (2008-06-14) Using a method based on Chinese Remainder Theorem for polynomial multiplication and suitable reductions, we obtain an efficient multiplication method for finite fields of characteristic 3. Large finite fields of characteristic 3 are important for pairing based cryptography [3]. For 5 <= l <= 18, we show that our method gives canonical multiplication formulae over F-3lm for any m >= 1 with the best multiplicative complexity improving the bounds in [6]. We give explicit formula in the case F-36.97.
An improved algorithm for iterative matrix-vector multiplications over finite fields Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat (2018-11-09) Cryptographic computations such as factoring integers and computing discrete logarithms over finite fields require solving a large system of linear equations. When dealing with such systems iterative approaches such as Wiedemann or Lanczos are used. Both methods are based on the computation of a Krylov subspace in which the computational cost is often dominated by successive matrix-vector products. We introduce a new algorithm for computing iterative matrix-vector multiplications over finite fields. The pro...
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...
On the arithmetic complexity of Strassen-like matrix multiplications Cenk, Murat (2017-05-01) The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Stras...
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...

Citation Formats

M. Cenk, “Karatsuba-like formulae and their associated techniques,” JOURNAL OF CRYPTOGRAPHIC ENGINEERING, pp. 259–269, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30812.