Paper 2015/028 Original: eprint.iacr.org/2015/028 ↗
Optimal software-implemented Itoh--Tsujii inversion for GF($2^m$)
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.
- History
- 2015-01-14: last updated
- 2015-01-14: published
- Short URL
- https://ia.cr/2015/028
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2015/028}
}