Paper 2015/028

Optimal software-implemented Itoh--Tsujii inversion for GF($2^m$)

Jeremy Maitin-Shepard

Abstract

Field inversion in GF($2^m$) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. Itoh--Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations, but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh--Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on 8 binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
finite fieldsinversionnumber theory
Contact author(s)
jeremy @ jeremyms com
History
2015-01-14: received
Short URL
https://ia.cr/2015/028
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/028,
      author = {Jeremy Maitin-Shepard},
      title = {Optimal software-implemented Itoh--Tsujii inversion for GF($2^m$)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/028},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/028}},
      url = {https://eprint.iacr.org/2015/028}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.