SpringerLink
Log in

Optimal software-implemented Itoh–Tsujii inversion for \(\mathbb {F}_{2^{m}}\)

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Field inversion in \(\mathbb {F}_{2^{m}}\) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves (Brown et al. in: Submission to NIST, 2008; Brown in: IACR Cryptology ePrint Archive 2008:12, 2008; Aranha et al. in: Cryptology ePrint Archive, Report 2014/486, 2014) Itoh–Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations (Taverne et al. in: CHES 2011, 2011; Oliveira et al. in: J Cryptogr Eng 4(1):3–17, 2014; Aranha et al. in: Cryptology ePrint Archive, Report 2014/486, 2014), 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 eight 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. As we are primarily concerned with elliptic curve cryptography, binary field sizes of interest range from about \(m = 127\) to about \(m = 571\).

  2. It is straightforward to verify that this equivalence relation respects all search operations.

  3. Concretely, we do not expand a state during the search if we have already expanded an equivalent state.

References

  1. Ahmadi O., Hankerson D., Rodrıguez-Henrıquez F.: Parallel formulations of scalar multiplication on Koblitz curves. J. Univ. Comput. Sci. 14(3), 481–504 (2008).

  2. Aranha D.F., López J., Hankerson D.: Efficient software implementation of binary field arithmetic using vector instruction sets. In: Progress in Cryptology—LATINCRYPT 2010, pp. 144–161. Springer, Berlin (2010).

  3. Aranha D.F., Fouque P.A., Qian C., Tibouchi M., Zapalowicz J.C.: Binary elligator squared. Cryptology ePrint Archive, Report 2014/486. http://eprint.iacr.org/ (2014).

  4. Bahig H.M.: Improved generation of minimal addition chains. Computing 78(2), 161–172 (2006).

  5. Bluhm M., Gueron S.: Fast software implementation of binary elliptic curve cryptography. IACR Cryptology ePrint Archive 2013, 741 (2013).

  6. Bos J.W., Kleinjung T., Niederhagen R., Schwabe P.: Ecc2k-130 on cell cpus. In: Progress in Cryptology—AFRICACRYPT 2010, pp. 225–242. Springer, Berlin (2010).

  7. Brown D.R.L.: The encrypted elliptic curve hash. IACR Cryptology ePrint Archive 2008, 12 (2008).

  8. Brown D.R.L., Antipa A., Campagna M., Struik R.: ECOH: the elliptic curve only hash. Submission to NIST (2008).

  9. Certicom Research: SEC 2: Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography. http://www.secg.org/download/aid-386/sec2_final.pdf, version 1.0 (2000).

  10. Fong K., Hankerson D., López J., Menezes A.: Field inversion and point halving revisited. IEEE Trans. Comput. 53(8), 1047–1059 (2004).

  11. Guajardo J., Paar C.: Itoh-Tsujii inversion in standard basis and its application in cryptography and codes. Des. Codes Cryptogr. 25(2), 207–216 (2002).

  12. Hankerson D., Vanstone S., Menezes A.J.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004).

  13. Itoh T., Tsujii S.: A fast algorithm for computing multiplicative inverses in GF(\(2^m\)) using normal bases. Inf. Comput. 78(3), 171–177 (1988).

  14. Järvinen K.U.: On repeated squarings in binary fields. In: Selected Areas in Cryptography, pp. 331–349. Springer, Berlin (2009).

  15. Maitin-Shepard J.: C++ Elliptic Curve Multiset Hash library. http://jeremyms.com/ecmh (2015).

  16. National Institute of Standards and Technology: FIPS 186-4: Digital Signature Standard (DSS), Federal Information Processing Standard (FIPS), publication 186-4. Tech. rep., Department of Commerce, Gaithersburg, MD, USA. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf (2013).

  17. Oliveira T., López J., Aranha D.F., Rodríguez-Henríquez F.: Two is the fastest prime: lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014).

  18. Paoloni G.: How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures. Tech. Rep. (2010).

  19. Rebeiro C., Mukhopadhyay D.: High speed compact elliptic curve cryptoprocessor for FPGA platforms. In: Progress in Cryptology—INDOCRYPT 2008, pp. 376–388. Springer, Berlin (2008).

  20. Russell S., Norvig P.: Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Prentice Hall, Upper Saddle River (2010).

  21. Shacham H., Boneh D.: Improving SSL handshake performance via batching. In: Topics in Cryptology CT-RSA 2001, pp. 28–43. Springer, Berlin (2001).

  22. Taverne J., Faz-Hernández A., Aranha D.F., Rodríguez-Henríquez F., Hankerson D., López J.: Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication. In: Cryptographic Hardware and Embedded Systems—CHES 2011, pp. 108–123. Springer, Heidelberg (2011).

  23. Thurber E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28(4), 1247–1263 (1999).

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, USA

    Jeremy Maitin-Shepard

Authors
  1. Jeremy Maitin-Shepard
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremy Maitin-Shepard.

Additional information

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Maitin-Shepard, J. Optimal software-implemented Itoh–Tsujii inversion for \(\mathbb {F}_{2^{m}}\) . Des. Codes Cryptogr. 82, 301–318 (2017). https://doi.org/10.1007/s10623-016-0260-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-016-0260-1

Keywords

Mathematics Subject Classification

Search

Navigation