Edwards curve

In mathematics an Edwards curve is a new form of elliptic curve, recently discovered by mathematician Harold M. Edwards. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Its applications to cryptography were developed by Bernstein and Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form.

Definition

File:Edwards curve.jpg

An Edwards curve of equation $x^{2}+y^{2}=1-300x^{2}y^{2}$

The equation of an Edwards curve is:

$x^{2}+y^{2}=1+dx^{2}y^{2}\,$

for some scalar d ≠ {0, 1}. An elliptic curve in Edwards form over a field K has parameters c, d, and coordinates x, y satisfying the following equations:

$x^{2}+y^{2}=c^{2}(1+dx^{2}y^{2})\,$

where c, d ∈ K with cd(1 − c⁴ d) ≠ 0.

Every Edwards curve is birationally equivalent to an elliptic curve in Weierstrass form. If K is finite then a sizeable fraction of all elliptic curves over K can be written as Edwards curves. Often elliptic curves in Edwards form are defined having c=1, without loss of generality. In the following sections, it is assumed that c=1.

The group law

(See also Weierstrass curve group law)

It is possible to do some operations on the points on any elliptic curve, such as adding two or more points and doubling or tripling one. Usually, given two points P and Q on an elliptic curve, the point R = P + Q is the third point of intersection between the curve and the line that passes trough P and Q; but in the case of Edwards curve this is not true: indeed the curve expressed in Edwards form has degree 4, so drawing a line one gets not 3 but 4 intersection points. In this case, the addition law cannot be explained so easily geometrically. For more information see http://eprint.iacr.org/2009/155

Edwards addition law

It is possible to add points on an elliptic curve, and, in this way, obtain another point that belongs to the curve as well.

To understand better the concept of "addition" between points on a curve, a nice example is given by the circle:

take the circle of radius 1

$x^{2}+y^{2}=1$

and consider two points P₁=(x₁,y₁), P₂=(x₂,y₂) on it. Let α₁ and α₂ be the angles such that:

P₁=(x₁,y₁)=(sinα₁, cosα₁),

P₂=(x₂,y₂)=(sinα₂, cosα₂).

The sum of P₁ and P₂ is, thus, given by the sum of "their angles". That is, the point P₃=P₁+P₂ is a point on the circle with coordinates (x₃,y₃), where:

x₃ = sin(α₁+α₂) = sinα₁cosα₂+sinα₂cosα₁ = x₁y₂+x₂y₁

y₃ = cos(α₁+α₂) = cosα₁cosα₂-sinα₁sinα₂ = y₁y₂-x₁x₂.

In this way, the addition formula for points on the circle of radius 1 is:

$(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})$.

When two points (x₁, y₁) and (x₂, y₂) on an Edwards curve are added, the result is another point which has coordinates:

$(x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)\,$

The neutral element of this addition is (0, 1). The inverse of any point (x₁y₁) is (−x₁y₁). The point (0, −1) has order 2: this means that the sum of this point to itself gives the "zero element" that is the neutral element of the group law, i.e. 2(0, −1) = (0, 1).

If d is not a square in K, then there are no exceptional points: the denominators 1 + dx₁x₂y₁y₂ and 1 − dx₁x₂y₁y₂ are always nonzero. Therefore, the Edwards addition law is complete when d is not a square in K. This means that the formulas work for all pairs of input points on the edward curve with no exceptions for doubling, no exception for the neutral element, no exception for negatives, etc. In other words, it is defined for all pairs of input points on the Edwards curve over K and the result gives the sum of the input points.

If d is a square in K, then the same operation can have exceptional points, i.e there can be pairs (x₁, y₁) and (x₂, y₂) where 1 + dx₁x₂y₁y₂ = 0 or 1 − dx₁x₂y₁y₂ = 0.

One of the attractive feature of the Edwards Addition law is that it is strongly unified i.e it can also be used to double a point, simplifying protection against side-channel attack. The addition formula above is faster than other unified formulas and has the strong property of completeness

Example of addition law :

Let's consider the elliptic curve in the Edwards form with d=2

$x^{2}+y^{2}=1+2x^{2}y^{2}$

and the point $P_{1}=(1,0)$ on it. It is possible to prove that the sum of P₁ with the neutral element (0,1) gives again P₁. Indeed, using the formula given above, the coordinates of the point given by this sum are:

$x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=1$

$y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=0$

Projective homogeneous coordinates

In the context of cryptography, homogeneous coordinates are used to prevent field inversions that appear in the affine formula. To avoid inversions in the original Edwards addition formulas, the curve equation can be written in projective coordinates as:

$(X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$.

A projective point (X₁ : Y₁ : Z₁) corresponds to the affine point (X₁/Z₁, Y₁/Z₁) on the Edwards curve.

The identity element is represented by (0 : 1 : 1). The inverse of (X₁ : Y₁ : Z₁) is (−X₁ : Y₁ : Z₁).

The addition formula in projective homogeneous coordinates is given by:

(X₃ : Y₃ : Z₃) = (X₁ : Y₁ : Z₁) + (X₂ : Y₂ : Z₂)

where

X₃ = Z₁Z₂(X₁Y₁ − Y₁X₂)(X₁Y₁Z_{²2 + Z1²X2Y2)}

Y₃ = Z₁Z₂(X₁X₂ + Y₁Y₂)(X₁Y₁Z₂² − Z₁²X₂Y₂)

Z₃ = kZ₁²Z₂²(X₁X₂ + Y₁Y₂)(X₁Y₂ − Y₁X₂) with k = 1/c.

Algorithm

Using the following algorithm, X₃, Y₃, Z₃ can be written as: X₃→ GJ , Y₃→ HK, Z₃→ kJK.d

where: A→ X₁Z₂,

B→ Y₁Z₂,

C→ Z₁X₂,

D→ Z₁Y₂,

E→ AB,

F→ CD,

G→ E+F,

H→ E-F,

J→ (A-C)(B+D)-H,

K→ (A+D)(B+C)-G

Doubling

Doubling can be performed with exactly the same formula as addition. Doubling refers to the case in which the inputs (x₁, y₁) and (x₂, y₂) are known to be equal. Since (x₁, y₁) is on the Edwards curve, one can substitute the coefficient by (x₁² + y₁² − 1)/x₁²y₁² as follows:

${\begin{aligned}2(x_{1},y_{1})&=(x_{1},y_{1})+(x_{1},y_{1})\\[6pt]2(x_{1},y_{1})&=\left({\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}\right)\\[6pt]&=\left({\frac {2x_{1}y_{1}}{x_{1}^{2}+y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{2-x_{1}^{2}y_{1}^{2}}}\right)\end{aligned}}$

This reduces the degree of the denominator from 4 to 2 which is reflected in faster doublings. A general addition in Edwards coordinates takes 10M + 1S + 1C + 1D + 7a and doubling costs 3M + 4S + 3C + 6a where M is field multiplications, S is field squarings, D is the cost of multiplying by a selectable curve parameter and a is field addition.

Example of doubling

As in the previous example for the addition law, let's consider the Edwards curve with d=2:

$x^{2}+y^{2}=1+2x^{2}y^{2}$

and the point P₁=(1,0). The coordinates of the point 2P₁ are:

$x_{3}={\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}}=0$

$y_{3}={\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}=-1$

The point obtained from doubling P₁ is thus P₃=(0,-1).

Mixed Addition

Mixed addition is the case when Z₂ is known to be 1. In such a case A=Z₁.Z₂ can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a

Algorithm

A= Z₁.Z₂

B= Z_I²

C=X₁.X₂

E=d.C.D

F=B-E

G=B+E

X₃= Z₁.F((X_I+Y₁).(X₂+Y₂)-C-D)

Y₃= Z₁.G.(D-C)

Z₃=C.F.G

Tripling

Tripling can be done by first doubling the point and then adding the result to itself. By applying the curve equation as in doubling, we obtain

$3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,$

There are two sets of formulas for this operation in standard Edwards coordinates. The first one costs 9M + 4S while the second needs 7M + 7S. If the S/M ratio is very small, specifically below 2/3, then the second set is better while for larger ratios the first one is to be preferred. Using the addition and doubling formulas (as mentioned above) the point (X₁ : Y₁ : Z₁) is symbolically computed as 3(X₁ : Y₁ : Z₁) and compared with (X₃ : Y₃ : Z₃)

Example of tripling

Giving the Edwards curve with d=2, and the point P₁=(1,0), the point 3P₁ has coordinates:

$x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=1$

$y_{3}={\frac {(x_{1}^{2}+y_{1}^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0$

So, 3P₁=(1,0)=P₁. This result can also be found considering the doubling example: 2P₁=(0,1), so 3P₁ = 2P₁ + P₁ = (0,1) + P₁ = P₁, because (0,1) is the neutral element.

Algorithm

A=X₁²

B=Y₁²

C=(2Z₁)²

D=A+B

E=D²

F=2D.(A-B)

G=E-B.C

H=E-A.C

I=F+H

J=F-G

X₃=G.J.X1

Y₃=H.I.Y1

Z₃=I.J.Z1

This formula costs 9M + 4S

Extended Coordinates for Edward Curves

There is another coordinates system with which an Edwards curve can be represented; these new coordinates are called extended coordinates. They are used to obtain fast computations in certain cases. For more information about the time-cost required in the operations with these coordinates see: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Inverted Edwards coordinates

Bernstein and Lange introduced an even faster coordinate system for elliptic curves called the Inverted Edward coordinates in which the coordinates (X : Y : Z) satisfy the curve (X² + Y²)Z² = (dZ⁴ + X²Y²) and corresponds to the affine point (Z/X, Z/Y) on the Edwards curve x² + y² = 1 + dx²y² with XYZ ≠ 0.

Inverted Edwards coordinates, unlike standard Edwards coordinates, do not have complete addition formulas: some points, such as the neutral element, must be handled separately. But the addition formulas still have the advantage of strong unification: they can be used without change to double a point.

For more information about operations with these coordinates see http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

See also

• Twisted Edwards curve

For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curves.

References

• Daniel Bernstein, T.Lange (2007), Faster Addition and Doubling on Elliptic curves (PDF)
• Edwards, Harold M. (4/9/2007), "A normal form for elliptic curves", Bulletin of the American Mathematical Society, 44, Providence, R.I.: American Mathematical Society: 393–422, ISSN 0002-9904, retrieved 2010/01/29 {{citation}}: Check date values in: |accessdate= and |date= (help)
• Faster Group Operations on Elliptic curves, H. Hisil, K. K. Wong, G. Carter, E. Dawson
• D.J.Bernstein, P.Birkner. T. Lange, C.Peters, Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication (PDF){{citation}}: CS1 maint: multiple names: authors list (link)
• Washington, Lawrence C. (2008), Elliptic Curves: Number Theory and Cryptography, Discrete Mathematics and its Applications (2nd ed.), Chapman & Hall/CRC, ISBN 978-1-4200-7146-7
• Daniel J. Bernstein, T. Lange, " Inverted Edwards coordinates" (PDF)

External link

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-edwards.html