Faster repeated doublings on binary elliptic curves

Christophe Doche*, Daniel Sutantyo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

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.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography, SAC 2013 - 20th International Conference, Revised Selected Papers
EditorsTanja Lange, Kristin Lauter, Petr Lisoněk
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages456-470
Number of pages15
Volume8282 LNCS
ISBN (Print)9783662434130
DOIs
Publication statusPublished - 2014
Event20th International Conference on Selected Areas in Cryptography, SAC 2013 - Burnaby, BC, Canada
Duration: 14 Aug 201316 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8282 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other20th International Conference on Selected Areas in Cryptography, SAC 2013
CountryCanada
CityBurnaby, BC
Period14/08/1316/08/13

Fingerprint Dive into the research topics of 'Faster repeated doublings on binary elliptic curves'. Together they form a unique fingerprint.

Cite this