Hessian form of an elliptic curve

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 is important for application in elliptic curve cryptography, because we can get a 33% performance improvement as compared to the best reported methods and requires much less memory.

Definition

File:Hessian curve.jpg

An Hessian curve of equation $x^{3}+y^{3}+1=0.3xy$

Let $K$ be a field and let E denote an elliptic curve in Weierstrass form over $K$. Then the following curve can be obtained:

$Y^{2}+(a_{1}*X+a_{3})*Y=X^{3}$

where the curve has discriminant $\Delta =(a_{3}(a_{1}^{3}-27a_{3}))=a_{3}^{3}\delta ,$

and (0,0) has order 3. Before proving this, note that if the characteristic of $K$, say q, is 2 modulo 3, then the curve has 3 points of order 3; and if q is 1 modulo 3, there are 8 points of order 3.

To prove that $P=(0,0)$ has order 3, it is suffiecient to show: $[3]*P=\theta$ if and only if $[2]*P=-P$.

(i) Compute $-P$: if $Y^{2}+h(X)*Y=X^{3}$ is the given curve and $P_{1}=(x_{1},y_{1})$ the point, then $-P=(x_{1},h(x_{1})-y_{1})$. So, in this case, since $P=(0,0)$, then $-P=(0,a_{3})$.

(ii) Compute $[2]*P$: it can be done using the tangent and chord method, that is, first contstruct the line through the general point $P_{1}=(x_{1},y_{1})$ and find the other intersection points (at most 2) with the curve. Then, by the group law, these three points sum up to zero. In this case, since the multiplicity of $P=(0,0)$ is two, there will only be one more point and $[2]P_{1}+P_{2}=\theta$, that is, $[2]P_{1}=-P_{2}$.

Let $y=l*x+m$ for m non-zero be a general line through the point $P_{1}$. Now, to find the points of intersection between the curve and the line, replace every $y$ by $y=l*x+m$ in the curve:

$(l*x+m)^{2}+(a_{1}*x+a_{3})*(l*x+m)=x^{3}$ iff $x^{3}-(l^{2}+a_{1}l)*x^{2}-(2*l*m+a_{1}*l+a_{3}*l)*x-m^{2}-a_{3}m=0$

The roots of this equation are the x-coordinates of $P_{1}$ and $P_{2}=(x_{2},y_{2})$, so:

$(x-x_{1})^{2}*(x-x_{2})=x^{3}-(2*x_{1}+x23)*x^{2}+g(x)=x^{3}-(l^{2}+a_{1}*l)*x^{2}+g'(x)$

Then comparing the coefficients:

$x_{2}=l^{2}+a_{1}*l-2*x_{1}$ and $y_{2}=l*x_{2}+y_{1}-l*x_{1}$ ($y_{2}=l*x_{2}+m$ and $m=y_{1}-l*x_{1}$).

Note that $x_{1},y_{1}$ are known and by the implicit function theorem $l=-{\frac {\frac {\partial f}{\partial x}}{\frac {\partial f}{\partial y}}}$ (which is the slope of the line $y=l*x+m$). Then, $[2]P_{1}=-P_{2}$ and [2]P would be known. This is a general method to compute $[2]P$.

So applying it to P=(0,0):

since $l={\frac {3*x^{2}-a_{1}*y}{2*y+a_{1}*x+a_{3}}}=0$ (note $a_{3}$ cannot be zero, otherwise the denominator would vanish at $P$ and the curve would be singular),

then $[2]*P=-P_{2}=(l^{2}+a_{1}*l-2*x_{1},h(x_{1})-l*x_{3}+y_{1}-l*x_{1})=(0,a_{3})$ where $h(x)=a_{1}x+a_{3}$

Thus, $[2]*P=(0,a_{3})=-P$, that is, $[3]*P=\theta$ and (0,0) has order 3 over $Y^{2}+(a_{1}*X+a_{3})*Y=X^{3}$.

Now, to obtain the Hessian curve, it is necessary to do the following transformation:

First let $\mu$ denote a root of the polynomial T³ − δT² +  δ²T/3 + a₃$\delta$² = 0.

where $\mu$ is determined from the formula:

$\mu$=1/3((-27a₃$\delta$²)1/3+$\delta$)

Note that if $K$ has characteristic q ≡ 2 (mod 3), then every element of $K$ has a unique cube root; otherwise, it is necessary to consider an extension field of K.

Now by defining the following value $D={\frac {3*(\mu -\delta )}{\mu }}$ another curve, C, is obtained, that is birationally equivalent to E:

$C$ : $x^{3}+y^{3}+z^{3}=Dxyz$

which is called cubic Hessian form (in projective coordinates)

$C$ : $x^{3}+y^{3}+1=Dxy$

in the affine plane ( satisfying $x={\frac {X}{Z}}$ and $y={\frac {Y}{Z}}$ ).

Furthermore, D³≠1 (otherwise, the curve would be singular)

Since the Weierstrass form is the most known elliptic curve (in books), it is interesting to note that the Hessian curve given by the last equation is birationally equivalent to the Weierstrass equation:

$v^{2}=u^{3}-27D(D^{3}+8)u+54(D^{6}-20D^{3}-8),\,$

under the transformations:

$(x,y)=(\eta (u+9D^{2})-1+\eta (3D^{3}-Dx-12))\,$

and

$(u,v)=(-9D^{2}+\varepsilon x,3\varepsilon (y-1))\,$

where:

$\eta$=[6(D³-1)(v+9D³-3Du-36)]/[(x+9D²)3+(3Dd-Dx-12)3]

$\epsilon$=[12(D³-1)]/[Dx+y+1]

Group law

It is interesting to analyze the group law of the elliptic curve, defining the addition and doubling formulas (because the SPA and DPA attacks are based on the running time of these operations). Furthermore, in this case, we only need to use the same procedure to compute the addition, doubling or subtraction of points to get efficient results, as said above. In general, the group law is defined in the following way: if three points lies in the same line then they sum up to zero. So, by this property, the group laws are different for every curve.

In this case, the correct way is to use the Cauchy-Desboves´ formulas, obtaining the point at infinity $\theta$ = ( 1 : -1: 0), that is, the neutral element (the inverse of $\theta$ is $\theta$ again). Let P=(x₁,y₁) be a point on the curve. The line $y=-x+(x_{1}+y_{1})$ contains the point $P$ and the point at infinity $\theta$. Therefore, -P is the third point of the intersection of this line with the curve. Intersecting the elliptic curve with the line, the following condition is obtained $x_{2}-(x_{1}+y_{1})*x+x_{1}*y_{1}=\theta$

Since $x_{1}+y_{1}+D$ is non zero (because $D^{3}$ is distinct to 1), the x-coordinate of $-P$ is $y_{1}$ and the y-coordinate of $-P$ is $x_{1}$ , i.e. , $-P=(y_{1},x_{1})$ or in projective coordinates $-P=(Y_{1}:X_{1}:Z_{1})$ .

In some application of elliptic curve cryptography (e.g. ECM) it is necessary to compute the scalar multiplications of P, say [n]P for some n integer, and they are based on the double-and-add method; these operations need the addition and dobling formulas.

Doubling

Now, if $P=(X_{1}:Y_{1}:Z_{1})$ is a point on the elliptic curve, it is possible to define a "doubling" operation using Cauchy-Desboves´ formulae:

$2*P=(Y_{1}*(X_{1}^{3}-Z_{1}^{3}):X_{1}*(Z_{1}^{3}-Y_{1}^{3}):Z_{1}*(Y_{1}^{3}-X_{1}^{3}))$

Addition

In the same way, for two different points, say $P=(X_{1}:Y_{1}:Z_{1})$ and $Q=(X_{2}:Y_{2}:Z_{2})$, it is possible to define the addition formula. Let $R$ denote the sum of these points, $R=P+Q$, then its coordinates are given by:

$R=(Y_{1}*X_{2}*Z_{2}-Y_{2}*X_{1}*Z_{1}:X_{1}*Y_{2}*Z_{2}-X_{2}*Y_{1}*Z_{1}:Z_{1}*X_{2}*Y_{2}-Z_{2}*X_{1}*Y_{1})$

Algorithms and examples

There is one algorithm that can be used to add two different points or to double; it is given by Joye and Quisquarte . Then, the following result gives the possibility the obtain the doubling operation by the addition:

Proposition.Let P=(X,Y,Z) be a point on a Hessian elliptic curve E(K).Then: 2(X:Y:Z) = (Z:X:Y) + (Y:Z:X) (2). Furthermore, we have (Z:X:Y)≠(Y:Z:X).

Finally, contrary to other parameterizations, there is no subtraction to compute the negation of a point. Hence, this addition algorithm can also be used for subtracting two points P= ( X1:Y1:Z1) and Q= ( X2:Y2:Z2) on an Hessian elliptic curve:

( X₁:Y₁:Z₁) - ( X₂:Y₂:Z₂) = ( X₁:Y₁:Z₁) + (Y₂:X₂:Z₂) (3)

To sum up, by adapting the order of the inputs according to equation (2) or (3), the addition algorithm presented above can be used indifferently for: Adding 2 (diff.) points, Doubling a point and Subtracting 2 points with only 12 multiplications and 7 auxiliary variables including the 3 result variables. These results represent the fastest known method for implementing the elliptic curve scalar multiplication towards resistance against side-channel attacks; since now the Edwards curves with a=-1 are faster (8 multiplications).

However, for some algorithms protection againts side-channel attacks is not neccesary. So, for these doublings can be faster. Since there are many algorithms, only the best for the addition and doubling formulas is given here, with one example for each one:

Addition

Let P₁=(X₁:Y₁:Z₁) and P₂=(X₂:Y₂:Z₂) be two points distinct to $\theta$. Assuming that Z₁=Z₂=1 then the algorithm is given by:

A = X₁*Y₂

B = Y₁*X₂

X₃ = B*Y₁-Y₂*A

Y₃ = X₁*A-B*X₂

Z₃ = Y₂*X₂-X₁*Y₁

The cost needed is 8 multiplications and 3 additions readdition cost of 7 multiplications and 3 additions, depending on the first point.

Example

Given the following points in the curve for d=-1 P₁=(1:0:-1) and P₂=(0:-1:1), then if P₃=P₁+P₂ we have:

X₃=0-1=-1

Y₃=-1-0=-1

Z₃=0-0=0

Then: P₃=(-1:-1:0)

Doubling

Let P = (X₁ : Y₁ : Z₁) be a point, then the doubling formula is given by:

• A = X₁²
• B = Y₁²
• D = A + B
• G = (X₁ + Y₁)² − D
• X₃ = (2Y₁ − G) × (X₁ + A + 1)
• Y₃ = (G − 2X₁) × (Y₁ + B + 1)
• Z₃ = (X₁ − Y₁) × (G + 2D)

The cost of this algorithm is three multiplications + three squarings + 11 additions + 3×2.

Example

If $P=(-1:-1:1)$ is a point over the Hessian curve with parameter d=-1, then the coordinates of $2P=(X:Y:Z)$ are given by:

X=(2.(-1)-2)(-1+1+1)=-4

Y=(-4-2.(-1))((-1)+1+1)=-2

Z=(-1-(-1))((-4)+2.2)=0

That is, $2P=(-4:-2:0)$

Extended coordinates

There is another coordinates system with which an Hessian curve can be represented; these new coordinates are called extended coordinates. They can speed up the addition and doubling. To have more information about operations with the extended coordinates see:

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

$x$ and $y$ are represented by $X,Y,Z,XX,YY,ZZ,XY,YZ,XZ$ satisfying the following equations:

$x=X/Z$

$y=Y/Z$

$XX=X*X$

$YY=Y*Y$

$ZZ=Z*Z$

$XY=2*X*Y$

$YZ=2*Y*Z$

$XZ=2*X*Z$

Internal link

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

Twisted Hessian curves

External link

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

References

• Otto Hesse (1844), "Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln", Journal für die reine und angewandte Mathematik, 10, pp. 68–96
• Marc Joye, Jean-Jacques Quisquarter (2001). Hessian Elliptic Curves and Side-Channel Attacks. Springer-Verlag Berlin Heidelberg 2001. ISBN 978-3-540-42521-2.
• N. P. Smart (2001). The Hessian form of an Elliptic Curve. Springer-Verlag Berlin Heidelberg 2001. ISBN 978-3-540-42521-2.