Paper 2017/121

Twisted $\mu_4$-normal form for elliptic curves

David Kohel

Abstract

We introduce the twisted $\mu_4$-normal form for elliptic curves, deriving in particular addition algorithms with complexity $9M + 2S$ and doubling algorithms with complexity $2M + 5S + 2m$ over a binary field. Every ordinary elliptic curve over a finite field of characteristic 2 is isomorphic to one in this family. This improvement to the addition algorithm is comparable to the $7M + 2S$ achieved for the $\mu_4$-normal form, and replaces the previously best known complexity of $13M + 3S$ on López-Dahab models applicable to these twisted curves. The derived doubling algorithm is essentially optimal, without any assumption of special cases. We show moreover that the Montgomery scalar multiplication with point recovery carries over to the twisted models, giving symmetric scalar multiplication adapted to protect against side channel attacks, with a cost of $4M + 4S + 1m_t + 2m_c$ per bit. In characteristic different from 2, we establish a linear isomorphism with the twisted Edwards model. This work, in complement to the introduction of $\mu_4$-normal form, fills the lacuna in the body of work on efficient arithmetic on elliptic curves over binary fields, explained by this common framework for elliptic curves if $\mu_4$-normal form in any characteristic. The improvements are analogous to those which the Edwards and twisted Edwards models achieved for elliptic curves over finite fields of odd characteristic and extend $\mu_4$-normal form to cover the binary NIST curves.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
elliptic curve cryptographybinary curves
Contact author(s)
David Kohel @ univ-amu fr
History
2017-02-16: received
Short URL
https://ia.cr/2017/121
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/121,
      author = {David Kohel},
      title = {Twisted $\mu_4$-normal form for elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2017/121},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/121}},
      url = {https://eprint.iacr.org/2017/121}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.