×

Faster repeated doublings on binary elliptic curves. (English) Zbl 1362.94028

Lange, Tanja (ed.) et al., Selected areas in cryptography – SAC 2013. 20th international conference, Burnaby, BC, Canada, August 14–16, 2013. Revised selected papers. Berlin: Springer (ISBN 978-3-662-43413-0/pbk; 978-3-662-43414-7/ebook). Lecture Notes in Computer Science 8282, 456-470 (2014).
Summary: 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 \([2^k]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 \([2^k]P\) on a binary elliptic curve. It relies on the \(x-doubling\) operation, which allows to compute the point \([2^k]P\) at a lower cost than with \(k\) regular doublings. As we trade off regular doublings for \(x\)-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 \(2\). A software implementation shows that our method called \(\text{x-JSF}_2\) induces a speed-up between 4 and 18 % for finite fields \({\mathbb {F}}_{2^d}\) with \(d\) between \(233\) and \(571\). We also generalize to characteristic \(2\) the scheme of Dahmen et al. in order to precompute all odd points [3]\(P\), [5]\(P, \dots, [2t - 1]P\) in affine coordinates at the cost of a single inversion and some extra field multiplications. We use this scheme with \(x\)-doublings as well as with the window NAF method in López-Dahab coordinates.
For the entire collection see [Zbl 1321.94008].

MSC:

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry

Software:

gmp; EFD; NTL
PDFBibTeX XMLCite
Full Text: DOI