HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Optimal software-implemented Itoh–Tsujii inversion for F 2 m

Abstract : Field inversion in F2m dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. [7, 6, 2] Itoh–Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations [19, 14, 2], 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01275712
Contributor : Jean-Pierre Tillich Connect in order to contact the contributor
Submitted on : Thursday, February 18, 2016 - 9:16:52 AM
Last modification on : Friday, June 28, 2019 - 3:01:15 PM
Long-term archiving on: : Thursday, May 19, 2016 - 10:30:42 AM

File

wcc15-mo2-3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01275712, version 1

Collections

Citation

Jeremy Maitin-Shepard. Optimal software-implemented Itoh–Tsujii inversion for F 2 m. WCC2015 - 9th International Workshop on Coding and Cryptography 2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01275712⟩

Share

Metrics

Record views

32

Files downloads

78