Efficient implementation of karatsuba algorithm based three-operand multiplication over binary extension field

Chiou Yng Lee, Chia Chen Fan, Jiafeng Xie*, Shyan-Ming Yuan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Three-operation multiplication (TOM) over binary extension field is frequently encountered in cryptosystems such as elliptic curve cryptography. Though digit-serial polynomial basis multipliers are usually preferred for the realization of TOM due to their efficient tradeoff in implementation complexity, the Karatsuba algorithm (KA)-based strategy is rarely employed to reduce the complexity further. Based on this reason, in this paper, we derive a novel low-complexity implementation of TOM based on a new KA-based digit-serial multiplier. The proposed TOM is obtained through two novel coherent interdependent efforts: 1) mapping an efficient KA-based algorithm into a novel digit-serial multiplier and 2) obtaining a new TOM structure through the novel derivation of the TOM algorithm. From the estimated results, it is shown that the proposed structure has significant lower area-time-complexities when compared with the existing competing TOMs. The proposed TOM is highly regular with low-complexity, and hence can be employed in many cryptographic applications.

Original languageEnglish
Article number8400526
Pages (from-to)38234-38242
Number of pages9
JournalIEEE Access
Volume6
DOIs
StatePublished - 29 Jun 2018

Keywords

  • Digit-level serial-in parallel-out (DL-SIPO) multiplier
  • Karatsuba-algorithm (KA) decomposition
  • low-complexity
  • three-operand multiplication (TOM)

Fingerprint Dive into the research topics of 'Efficient implementation of karatsuba algorithm based three-operand multiplication over binary extension field'. Together they form a unique fingerprint.

Cite this