TY - GEN

T1 - Faster repeated doublings on binary elliptic curves

AU - Doche, Christophe

AU - Sutantyo, Daniel

PY - 2014

Y1 - 2014

N2 - The use of precomputed data to speed up a cryptographic protocol is commonplace. For instance, the owner of a public point P on an elliptic curve can precompute various points of the form [2k]P and transmit them together with P. One inconvenience of this approach though may be the amount of information that needs to be exchanged. In the situation where the bandwidth of the transmissions is limited, this idea can become impractical. Instead, we introduce a new scheme that needs only one extra bit of information in order to efficiently and fully determine a point of the form [2k]P on a binary elliptic curve. It relies on the x-doubling operation, which allows to compute the point [2k]P at a lower cost than with regular doublings. As we trade off regular doublings for -doublings, we use multi-scalar multiplication techniques, such as the Joint Sparse Form or interleaving with NAFs. This idea gives rise to several methods, which are faster than Montgomery's method in characteristic . A software implementation shows that our method called induces a speed-up between 4 and 18 % for finite fields double-struck F2d with d between 233 and 571. We also generalize to characteristic the scheme of Dahmen et al. in order to precompute all odd points [3]P, [5]P,..., [2t-1]P in affine coordinates at the cost of a single inversion and some extra field multiplications. We use this scheme with -doublings as well as with the window NAF method in López-Dahab coordinates.

AB - The use of precomputed data to speed up a cryptographic protocol is commonplace. For instance, the owner of a public point P on an elliptic curve can precompute various points of the form [2k]P and transmit them together with P. One inconvenience of this approach though may be the amount of information that needs to be exchanged. In the situation where the bandwidth of the transmissions is limited, this idea can become impractical. Instead, we introduce a new scheme that needs only one extra bit of information in order to efficiently and fully determine a point of the form [2k]P on a binary elliptic curve. It relies on the x-doubling operation, which allows to compute the point [2k]P at a lower cost than with regular doublings. As we trade off regular doublings for -doublings, we use multi-scalar multiplication techniques, such as the Joint Sparse Form or interleaving with NAFs. This idea gives rise to several methods, which are faster than Montgomery's method in characteristic . A software implementation shows that our method called induces a speed-up between 4 and 18 % for finite fields double-struck F2d with d between 233 and 571. We also generalize to characteristic the scheme of Dahmen et al. in order to precompute all odd points [3]P, [5]P,..., [2t-1]P in affine coordinates at the cost of a single inversion and some extra field multiplications. We use this scheme with -doublings as well as with the window NAF method in López-Dahab coordinates.

UR - http://www.scopus.com/inward/record.url?scp=84902603150&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-43414-7_23

DO - 10.1007/978-3-662-43414-7_23

M3 - Conference proceeding contribution

SN - 9783662434130

VL - 8282 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 456

EP - 470

BT - Selected Areas in Cryptography, SAC 2013 - 20th International Conference, Revised Selected Papers

A2 - Lange, Tanja

A2 - Lauter, Kristin

A2 - Lisoněk, Petr

PB - Springer, Springer Nature

CY - Heidelberg

ER -