Karatsuba-like formulae and their associated techniques

CENK M.

JOURNAL OF CRYPTOGRAPHIC ENGINEERING, vol.8, no.3, pp.259-269, 2018 (ESCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 8 Issue: 3
  • Publication Date: 2018
  • Doi Number: 10.1007/s13389-017-0155-8
  • Journal Name: JOURNAL OF CRYPTOGRAPHIC ENGINEERING
  • Journal Indexes: Emerging Sources Citation Index (ESCI), Scopus
  • Page Numbers: pp.259-269
  • Keywords: Polynomial multiplication, Karatsuba algorithm, Cryptographic computation, Chinese remainder theorem, EFFICIENT MULTIPLICATION, 5-TERM, 6-TERM
  • Middle East Technical University Affiliated: Yes

Abstract

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.