Cryptology ePrint Archive: Report 2017/121
Twisted $\mu_4$-normal form for elliptic curves
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.
Category / Keywords: public-key cryptography / elliptic curve cryptography, binary curves
Original Publication (in the same form): IACR-EUROCRYPT-2017
Date: received 13 Feb 2017, last revised 13 Feb 2017
Contact author: David Kohel at univ-amu fr
Available format(s): PDF | BibTeX Citation
Version: 20170216:215645 (All versions of this report)
Short URL: ia.cr/2017/121
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]