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 54 articles )
Showing results 1 to 20 of 54.
Sorted by year (- Semmouni, Meryem Cherkaoui; Nitaj, Abderrahmane; Belkasmi, Mostafa: Bitcoin security with a twisted Edwards curve (2022)
- Taleb, Abdul Rahman; Vergnaud, Damien: Speeding-up verification of digital signatures (2021)
- Fouotsa, Emmanuel; Diao, Oumar: Complete addition formulas on the level four theta model of elliptic curves (2020)
- Boudabra, Maher; Nitaj, Abderrahmane: A new public key cryptosystem based on Edwards curves (2019)
- Karati, Sabyasachi; Sarkar, Palash: Connecting Legendre with Kummer and Edwards (2019)
- Fan, Xinxin; Otemissov, Adilet; Sica, Francesco; Sidorenko, Andrey: Multiple point compression on elliptic curves (2017)
- Fouotsa, Emmanuel; Diao, Oumar: A theta model for elliptic curves (2017)
- Gallin, Gabriel; Celik, Turku Ozlum; Tisserand, Arnaud: Architecture level optimizations for Kummer based HECC on FPGAs (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)
- Grebnev, S. V.: Optimizing memory cost of multi-scalar multiplication (2016)
- Heer, Henriette; Mcguire, Gary; Robinson, Oisín: JKL-ECM: an implementation of ECM using Hessian curves (2016)
- Rezaeian Farashahi, Reza; Hosseini, Seyed Gholamhossein: Differential addition on binary elliptic 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)
- Dygin, D. M.; Grebnev, S. V.: Efficient implementation of the GOST R 34.10 digital signature scheme using modern approaches to elliptic curve scalar multiplication (2013)
Further publications can be found at: http://www.hyperelliptic.org/EFD/bib.html