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 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.^[1]

Definition

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

Let $K$ be a field and consider an elliptic curve $E$ in the following special case of Weierstrass form over $K$ :

Y^{2}+a_{1}XY+a_{3}Y=X^{3}

where the curve has discriminant

\Delta =a_{3}^{3}\left(a_{1}^{3}-27a_{3}\right)=a_{3}^{3}\delta .

Then the point $P = (0, 0)$ has order 3. To see this note that the tangent to $E$ at $P$ is the line $Y = 0$ which intersects $E$ with multiplicity 3 at $P$ . Conversely, given a point $P$ of order 3 on an elliptic curve $E$ both defined over a field $K$ one can put the curve into Weierstrass form with $P = (0, 0)$ so that the tangent at $P$ is the line $Y = 0$ . Then the equation of the curve is

Y^{2}+a_{1}XY+a_{3}Y=X^{3},\qquad a_{1},a_{3}\in K.

Now, to obtain the Hessian curve, first let $μ$ denote a root of the polynomial

T^{3}-\delta T^{2}+{\tfrac {1}{3}}\delta ^{2}T+a_{3}\delta ^{2}=0.

Then

\mu ={\tfrac {1}{3}}\left(\delta -a_{1}\delta ^{\frac {2}{3}}\right).

Note that if $K$ has a finite field of order $q\equiv 2$ (mod 3), then every element of $K$ has a unique cube root; in general, $μ$ lies in an extension field of $K$ .

Now the curve, $C$ , defined below is birationally equivalent to $E$ :

C:x^{3}+y^{3}+z^{3}=Dxyz,\qquad D={\frac {3(\mu -\delta )}{\mu }}

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^{3}\neq 1$ (otherwise, the curve would be singular).

Starting from the Hessian curve, a birationally equivalent Weierstrass equation is given by

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

under the transformations:

{\begin{aligned}(x,y)&=\left(\eta \left(u+9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)\\(u,v)&=\left(-9D^{2}+\varepsilon x,3\varepsilon (y-1)\right)\end{aligned}}

where:

\eta ={\frac {6(D^{3}-1)(v+9D^{3}-3Du-36)}{(u+9D^{2})^{3}+(3Dd-Du-12)^{3}}},\qquad \varepsilon ={\frac {12(D^{3}-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 lie 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 $θ = (1 : -1 : 0)$ , that is, the neutral element (the inverse of $θ$ is $θ$ again). Let $P = (x 1, y 1)$ be a point on the curve. The line $y = - x + (x 1 + y 1)$ contains $P$ and $θ$ . 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 $D 3 \neq 1$ we have $x 1 + y 1 + D \neq 0$ , 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 and the elliptic curve method of factorization (ECM) it is necessary to compute the scalar multiplications of $P$ , say $[n] P$ for some integer $n$ , and they are based on the double-and-add method; these operations need the addition and dobling formulas.

Doubling: It is possible to define a "doubling" operation using Cauchy-Desboves´ formulae:

{\begin{aligned}2P&=2(X_{1}:Y_{1}:Z_{1})\\&=\left(Y_{1}\left(X_{1}^{3}-Z_{1}^{3}\right):X_{1}\left(Z_{1}^{3}-Y_{1}^{3}\right):Z_{1}\left(Y_{1}^{3}-X_{1}^{3}\right)\right)\end{aligned}}

Addition: Similarly given two different points it is possible to define the addition formula:

{\begin{aligned}P+Q&=(X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})\\&=\left(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}\right)\end{aligned}}

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 Quisquater. 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)

. Furthermore, we have

(Z : X : Y) \neq (Y : Z : X)

.

Finally, the negation of a point is simply a permutation in the coordinates which means that for subtraction we have:

(X_{1}:Y_{1}:Z_{1})-(X_{2}:Y_{2}:Z_{2})=(X_{1}:Y_{1}:Z_{1})+(Y_{2}:X_{2}:Z_{2}).

To sum up, using the addition algorithm presented above can be used indifferently for: Adding two distinct points, doubling a point and subtracting two points with only 12 multiplications and 7 auxiliary variables including the 3 result variables. Before the invention of Edwards curves, these results represent the fastest known method for implementing the elliptic curve scalar multiplication towards resistance against side-channel attacks.

For some algorithms protection against side-channel attacks is not necessary. So, for these doublings can be faster. Since there are many algorithms, only the best for the addition and doubling formulas is given here:

Addition

Let $P 1 = (X 1 : Y 1 : Z 1)$ and $P 2 = (X 2 : Y 2 : Z 2)$ be two points distinct to $θ$ . Assuming $Z 1 = Z 2 = 1$ then the algorithm is given by:

{\begin{aligned}X_{3}&=BY_{1}-Y_{2}A\\Y_{3}&=X_{1}A-BX_{2}\\Z_{3}&=Y_{2}X_{2}-X_{1}Y_{1}\end{aligned}}

where

A=X_{1}Y_{2},\qquad B=Y_{1}X_{2}.

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

Doubling

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

{\begin{aligned}X_{3}&=(2Y_{1}-G)(X_{1}+A+1)\\Y_{3}&=(G-2X_{1})(Y_{1}+B+1)\\Z_{3}&=(X_{1}-Y_{1})(G+2D)\end{aligned}}

where:

A=X_{1}^{2},\quad B=Y_{1}^{2},\quad D=A+B,\quad G=(X_{1}+Y_{1})^{2}-D.

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

Example

Let $E$ be the Hessian curve with parameter $d = -1$ . In this curve we have:

(1:0:-1)+(0:-1:1)=(X:Y:Z),\quad {\begin{cases}X=0-1=-1\\Y=-1-0=-1\\Z=0-0=0\end{cases}}\quad \to \quad (-1:-1:0)

2(-1:-1:1)=(X:Y:Z),\quad {\begin{cases}X=(2(-1)-2)(-1+1+1)=-4\\Y=(-4-2(-1))((-1)+1+1)=-2\\Z=(-1-(-1))((-4)+2(2))=0\end{cases}}\quad \to \quad 4:-2:0).

Extended coordinates

There is another coordinates system with which a 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\cdot X$

$YY=Y\cdot Y$

$ZZ=Z\cdot Z$

$XY=2\cdot X\cdot Y$

$YZ=2\cdot Y\cdot Z$

$XZ=2\cdot X\cdot Z$

External links

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

Notes

^ Cauchy-Desbove's Formulae: Hessian-elliptic Curves and Side-Channel Attacks, Marc Joye and Jean-Jacques Quisquarter

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 Quisquater (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.

[1] Cauchy-Desbove's Formulae: Hessian-elliptic Curves and Side-Channel Attacks, Marc Joye and Jean-Jacques Quisquarter

[1]