Faster Repeated Doublings on Binary Elliptic Curves
| Autor: | Christophe Doche, Daniel Sutantyo |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | Selected Areas in Cryptography--SAC 2013 ISBN: 9783662434130 Selected Areas in Cryptography |
| DOI: | 10.1007/978-3-662-43414-7_23 |
| Popis: | 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 18i¾?% 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 Lopez---Dahab coordinates. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|