Reducing the Complexity of Normal Basis Multiplication

Omer Egecioglu; Cetin Kaya Koc

Paper 2014/687

Reducing the Complexity of Normal Basis Multiplication

Omer Egecioglu and Cetin Kaya Koc

Abstract

In this paper we introduce a new transformation method and a multiplication algorithm for multiplying the elements of the field GF$(2^k)$ expressed in a normal basis. The number of XOR gates for the proposed multiplication algorithm is fewer than that of the optimal normal basis multiplication, not taking into account the cost of forward and backward transformations. The algorithm is more suitable for applications in which tens or hundreds of field multiplications are performed before needing to transform the results back.

Note: Accepted to WAIFI 2014.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Finite fields characteristic 2 normal basis optimal normal basis
Contact author(s): koc @ cs ucsb edu
History: 2014-09-04: received
Short URL: https://ia.cr/2014/687
License: CC BY

BibTeX

@misc{cryptoeprint:2014/687,
      author = {Omer Egecioglu and Cetin Kaya Koc},
      title = {Reducing the Complexity of Normal Basis Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/687},
      year = {2014},
      url = {https://eprint.iacr.org/2014/687}
}