Table of costs of operations in elliptic curves

Last updated December 14, 2020

Elliptic curve cryptography is a popular form of public key encryption that is based on the mathematical theory of elliptic curves. Points on an elliptic curve can be added and form a group under this addition operation. This article describes the computational costs for this group addition and certain related operations that are used in elliptic curve cryptography algorithms.

Abbreviations for the operations

The next section presents a table of all the time-costs of some of the possible operations in elliptic curves. The columns of the table are labelled by various computational operations. The rows of the table are for different models of elliptic curves. These are the operations considered :

DBL - Doubling
ADD - Addition
mADD - Mixed addition: addition of an input that has been scaled to have Z-coordinate 1.
mDBL - Mixed doubling: doubling of an input that has been scaled to have Z coordinate 1.
TPL - Tripling.
DBL+ADD - Combined double and add step

To see how adding (ADD) and doubling (DBL) points on elliptic curves are defined, see The group law. The importance of doubling to speed scaler multiplication is discussed after the table. For information about other possible operations on elliptic curves see http://hyperelliptic.org/EFD/g1p/index.html.

Tabulation

Under different assumptions on the multiplication, addition, inversion for the elements in some fixed field, the time-cost of these operations varies. In this table it is assumed that:

I = 100M, S = 1M, *param = 0M, add = 0M, *const = 0M

This means that 100 multiplications (M) are required to invert (I) an element; one multiplication is required to compute the square (S) of an element; no multiplication is needed to multiply an element by a parameter (*param), by a constant (*const), or to add two elements.

For more information about other results obtained with different assumptions, see http://hyperelliptic.org/EFD/g1p/index.html

Curve shape, representation	DBL	ADD	mADD	mDBL	TPL	DBL+ADD
Short Weierstrass projective	11	14	11	8
Short Weierstrass projective with a4=-1	11	14	11	8
Short Weierstrass projective with a4=-3	10	14	11	8
Short Weierstrass Relative Jacobian^[1]	10	11	(7)	(7)		18
Tripling-oriented Doche–Icart–Kohel curve	9	17	11	6	12
Hessian curve extended	9	12	11	9
Hessian curve projective	8	12	10	6	14
Jacobi quartic XYZ	8	13	11	5
Jacobi quartic doubling-oriented XYZ	8	13	11	5
Twisted Hessian curve projective	8	12	12	8	14
Doubling-oriented Doche–Icart–Kohel curve	7	17	12	6
Jacobi intersection projective	7	14	12	6	14
Jacobi intersection extended	7	12	11	7	16
Twisted Edwards projective	7	11	10	6
Twisted Edwards Inverted	7	10	9	6
Twisted Edwards Extended	8	9	8	7
Edwards projective	7	11	9	6	13
Jacobi quartic doubling-oriented XXYZZ	7	11	9	6	14
Jacobi quartic XXYZZ	7	11	9	6	14
Jacobi quartic XXYZZR	7	10	9	7	15
Edwards curve inverted	7	10	9	6
Montgomery curve	4			3

Importance of doubling

In some applications of elliptic curve cryptography and the elliptic curve method of factorization (ECM) it is necessary to consider the scalar multiplication [n]P. One way to do this is to compute successively:

P,\quad [2]P=P+P,\quad [3]P=[2]P+P,\dots ,[n]P=[n-1]P+P

But it is faster to use double-and-add method, e.g. [5]P = [2]([2]P) + P. In general to compute [k]P, write

$k=\sum _{i\leq l}k_{i}2^{i}$

with k_i in {0,1} and $l=[log_{2}k]$ , k_l = 1, then:

$[2](....([2]([2]([2]([2]([2]P+[k_{(l-1)}]P)+[k_{(l-2)}]P)+[k_{(l-3)}]P)+\dots )\dots +[k_{1}]P)+[k_{0}]P=[2^{l}]P+[k_{(l-1)}2^{l-1}]P+\dots +[k_{1}2]P+[k_{0}]P$ .

Note that, this simple algorithm takes at most 2l steps and each step consists of a doubling and (if k_i≠ 0) adding two points. So, this is one of the reasons why addition and doubling formulas are defined. Furthermore, this method is applicable to any group and if the group law is written multiplicatively, the double-and-add algorithm is instead called square-and-multiply algorithm.

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

In the mathematics of the real numbers, the logarithm log_ba is a number x such that b^x = a, for given numbers a and b. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_ba is an integer k such that b^k = a. In number theory, the more commonly used term is index: we can write x = ind_ra (mod m) for r^x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography.

Hyperelliptic curve cryptography is similar to elliptic curve cryptography (ECC) insofar as the Jacobian of a hyperelliptic curve is an abelian group in which to do arithmetic, just as we use the group of points on an elliptic curve in ECC.

In mathematics, a polynomial basis is a basis of a polynomial ring, viewed as a vector space over the field of coefficients, or as a free module over the ring of coefficients. The most common polynomial basis is the monomial basis consisting of all monomials. Other useful polynomial bases are the Bernstein basis and the various sequences of orthogonal polynomials.

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in $where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.$

In geometry, the Hessian curve is a plane curve similar to folium of Descartes. It is named after the German mathematician Otto Hesse. This curve was suggested for application in elliptic curve cryptography, because arithmetic in this curve representation is faster and needs less memory than arithmetic in standard Weierstrass form.

In 1998 Gerhard Frey firstly proposed using trace zero varieties for cryptographic purpose. These varieties are subgroups of the divisor class group on a low genus hyperelliptic curve defined over a finite field. These groups can be used to establish asymmetric cryptography using the discrete logarithm problem as cryptographic primitive.

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication. While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group $, of elliptic curves over a finite field, where q = p k and p is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p -adic methods exist.$

In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptography were developed by Daniel J. Bernstein and Tanja Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form.

In mathematics, the Jacobi curve is a representation of an elliptic curve different from the usual one. Sometimes it is used in cryptography instead of the Weierstrass form because it can provide a defence against simple and differential power analysis style (SPA) attacks; it is possible, indeed, to use the general addition formula also for doubling a point on an elliptic curve of this form: in this way the two operations become indistinguishable from some side-channel information. The Jacobi curve offers also faster arithmetic compared to the Weierstrass curve.

In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations, it is close in speed to Edwards curves.

In mathematics, the doubling-oriented Doche–Icart–Kohel curve is a form in which an elliptic curve can be written. It is a special case of Weierstrass form and it is also important in elliptic-curve cryptography because the doubling speeds up considerably. It has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in Efficient Scalar Multiplication by Isogeny Decompositions.

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve. At certain conditions some operations, as adding, doubling or tripling points, are faster to compute using this form. The Tripling oriented Doche–Icart–Kohel curve, often called with the abbreviation 3DIK has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in

In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein, Birkner, Joye, Lange and Peters in 2008. The curve set is named after mathematician Harold M. Edwards. Elliptic curves are important in public key cryptography and twisted Edwards curves are at the heart of an electronic signature scheme called EdDSA that offers high performance while avoiding security problems that have surfaced in other digital signature schemes.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC) as a means of producing a one-way function. The literature presents this operation as scalar multiplication, as written in Hessian form of an elliptic curve. A widespread name for this operation is also elliptic curve point multiplication, but this can convey the wrong impression of being a multiplication between two points.

In cryptography, FourQ is an elliptic curve developed by Microsoft Research. It is designed for key agreements schemes and digital signatures (Schnorr), and offers about 128 bits of security. It is equipped with a reference implementation made by the authors of the original paper. The open source implementation is called FourQlib and runs on Windows and Linux and is available for x86, x64, and ARM. It is licensed under MIT License and the source code is available on GitHub.

References

↑ Fay, Björn (2014-12-20). "Double-and-Add with Relative Jacobian Coordinates". Cryptology ePrint Archive.

http://hyperelliptic.org/EFD/g1p/index.html

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Fay, Björn (2014-12-20). "Double-and-Add with Relative Jacobian Coordinates". Cryptology ePrint Archive.

[1]