EFD
Explicit-Formulas Database: Analysis and optimization of elliptic-curve single-scalar multiplication. The authors study the elliptic-curve single-scalar multiplication over finite fields, i.e. given a finite field k (the ground field), an elliptic curve E (with small parameters), an integer n (the scalar) and a point P∈E(k), they identify today’s fastest methods to compute the point nP on E. Due to the well-known cryptographic applications, tables and figures are given for 160, 256 and 512-bit scalars, expressing the necessary number of multiplications per bit as a function of the I/M ratio, i.e. the number of multiplications needed to provide an inversion in the ground field. In order to do this, the authors first consider the problem of adding two points (or doubling a point). They look at twelve different coordinate systems: Projective, Jacobian (these two systems are also considered in the particular, faster, case a 4 =-3), Doubling (resp. Tripling)-oriented Doche/Icart/Kohel, Montgomery, Jacobi intersections, Jacobi quartics, Hessian, Edwards and inverted Edwards. For each system, the relation with the classical Weierstrass model and the corresponding (affine) coordinates is given. Note that certain systems do not provide a model for every elliptic curve. Since the precomputation of some little multiples 2P,3P,5P,7P,⋯,mP is necessary, they look for the optimal odd m (always less than 31), constructing for each m,n an “addition-subtraction” chain, that allows a fast computation of nP. In order to do this, they combine “windows” techniques, and average over many random scalars of given size to get the best choice. Finally, the authors consider four cases, allowing zero, one, two or three inversions in the ground field (typically, an inversion is needed when one wants to give the affine coordinates of a point). Then they compare their respective performances when the ratio I/M varies. All the results are summarized in three tables, and the fastest ones in three figures, giving a clear account of what is known about this problem nowadays. Note also that all these results are updated at the address http://hyperelliptic.org/EFD.
Keywords for this software
References in zbMATH (referenced in 34 articles )
Showing results 1 to 20 of 34.
Sorted by year (- Fan, Xinxin; Otemissov, Adilet; Sica, Francesco; Sidorenko, Andrey: Multiple point compression on elliptic curves (2017)
- Hisil, Huseyin; Costello, Craig: Jacobian coordinates on genus 2 curves (2017)
- Bos, Joppe W.; Costello, Craig; Hisil, Huseyin; Lauter, Kristin: Fast cryptography in genus 2 (2016)
- Heer, Henriette; Mcguire, Gary; Robinson, Oisín: JKL-ECM: an implementation of ECM using Hessian curves (2016)
- Bauer, Aurélie; Jaulmes, Eliane; Prouff, Emmanuel; Reinhard, Jean-René; Wild, Justine: Horizontal collision correlation attack on elliptic curves (2015)
- Budhathoki, Parshuram; Steinwandt, Rainer: Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves (2015)
- Diao, Oumar; Fouotsa, Emmanuel: Arithmetic of the level four theta model of elliptic curves (2015)
- Robert, Jean-Marc: Parallelized software implementation of elliptic curve scalar multiplication (2015)
- Doche, Christophe; Sutantyo, Daniel: Faster repeated doublings on binary elliptic curves (2014)
- Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane: ECM using Edwards curves (2013)
- Feng, Rongquan; Nie, Menglong; Wu, Hongfeng: Twisted Jacobi intersections curves (2013)
- Costello, Craig; Lauter, Kristin: Group law computations on Jacobians of hyperelliptic curves (2012)
- Farashahi, Reza Rezaeian; Moody, Dustin; Wu, Hongfeng: Isomorphism classes of Edwards curves over finite fields (2012)
- Arène, Christophe; Lange, Tanja; Naehrig, Michael; Ritzenthaler, Christophe: Faster computation of the Tate pairing (2011)
- Bernstein, Daniel J.; Lange, Tanja: A complete set of addition laws for incomplete Edwards curves (2011)
- Castryck, Wouter; Vercauteren, Frederik: Toric forms of elliptic curves and their arithmetic (2011)
- Galbraith, Steven D.; Lin, Xibin; Scott, Michael: Endomorphisms for faster elliptic curve cryptography on a large class of curves (2011)
- Gu, Haihua; Gu, Dawu; Xie, Wenlu: Efficient pairing computation on elliptic curves in Hessian form (2011)
- Moody, Dustin: Using $5$-isogenies to quintuple points on elliptic curves (2011)
- Moody, Dustin; Wu, Hongfeng: Families of elliptic curves with rational 3-torsion (2011)
Further publications can be found at: http://www.hyperelliptic.org/EFD/bib.html