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

Jeremy Maitin-Shepard 1, *
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. WCC2015 - 9th International Workshop on Coding and Cryptography 2015, Apr 2015, Paris, France. 2016, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01275712
Contributeur : Jean-Pierre Tillich <>
Soumis le : jeudi 18 février 2016 - 09:16:52
Dernière modification le : jeudi 18 février 2016 - 15:43:15
Document(s) archivé(s) le : jeudi 19 mai 2016 - 10:30:42

Fichier

wcc15-mo2-3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01275712, version 1

Collections

Citation

Jeremy Maitin-Shepard. Optimal software-implemented Itoh–Tsujii inversion for F 2 m. Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. WCC2015 - 9th International Workshop on Coding and Cryptography 2015, Apr 2015, Paris, France. 2016, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015. 〈hal-01275712〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

61