Twisted Hessian curves

Template:Short description In mathematics, twisted Hessian curves are a generalization of Hessian curves; they were introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations (see the last sections), it is close in speed to Edwards curves. Twisted Hessian curves were introduced by Bernstein, Lange, and Kohel.

Definition

A Twisted Hessian curve of equation $10x^3+y^3+1=15xy$

Let Template:Mvar be a field. The twisted Hessian form in affine coordinates is given by:

$a\cdot x^3+y^3+1=d\cdot x\cdot y$

and in projective coordinates by

$a\cdot X^3+Y^3+Z^3=d\cdot X\cdot Y\cdot Z,$

where Template:Math and Template:Math and Template:Math. These curves are birationally equivalent to Hessian curves, and Hessian curves are just the special case of twisted Hessian curves in which Template:Math.

Considering the equation Template:Math, note that, if Template:Mvar has a cube root in Template:Mvar, then there exists a unique Template:Mvar such that Template:Mvar; otherwise, it is necessary to consider an extension field of Template:Mvar, such as Template:Math. Then, since Template:Math, defining Template:Math, the following equation is needed (in Hessian form) to do the transformation:

$t^3+y^3+1=d\cdot x\cdot y$.

This means that twisted Hessian curves are birationally equivalent to elliptic curves in Weierstrass form.

Group law

It is interesting to analyze the group law of the elliptic curve, defining the addition and doubling formulas (because the simple power analysis and differential power analysis attacks are based on the running time of these operations). 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 explicit formulas for the group law depend on the curve shape.

Let Template:Math be a point; its inverse is then Template:Math in the plane. In projective coordinates, let Template:Math be a point; then Template:Math is its inverse. Furthermore, the neutral element in affine plane is Template:Math, and in projective coordinates it is Template:Math.

In some applications of elliptic curves for cryptography and integer factorization, it is necessary to compute scalar multiples of Template:Mvar, say Template:Math for some integer Template:Mvar, and they are based on the double-and-add method, so the addition and doubling formulas are needed. Using affine coordinates, the addition and doubling formulas for this elliptic curve are as follows.

Addition formulas

Let Template:Math and Template:Math; then, Template:Math, where

$x_3=\frac{x_1-y_1^2\cdot x_2\cdot y_2}{a\cdot x_1\cdot y_1\cdot x_2^2-y_2}$

$y_3=\frac{y_1\cdot y_2^2-a\cdot x_1^2\cdot x_2}{a\cdot x_1\cdot y_1\cdot x_2^2-y_2}$

Doubling formulas

Let Template:Math; then Template:Math, where

$x_1=\frac{x-y^3\cdot x}{a\cdot y\cdot x^3-y}$

$y_1=\frac{y^3-a\cdot x^3}{a\cdot y\cdot x^3-y}$

Algorithms and examples

Here some efficient algorithms of the addition and doubling law are given; they can be important in cryptographic computations, and the projective coordinates are used to this purpose.

Addition

$A=X_1\cdot Z_2$

$B=Z_1\cdot Z_2$

$C=Y_1{X}_2$

$D=Y_1\cdot Y_2$

$E=Z_1\cdot Y_2$

$F=a\cdot X_1\cdot X_2$

$X_3=A\cdot B-C\cdot D$

$Y_3=D\cdot E-F\cdot A$

$Z_3=F\cdot C-B\cdot E$

The cost of this algorithm is 12 multiplications, one multiplication by a constant, and 3 additions.

Example:

Let Template:Math and Template:Math be points over a twisted Hessian curve with Template:Math. Then Template:Math is given by:

$A=-1;B=-1;C=-1;D=-1;E=1;F=2;$

$x_3=0$

$y_3=-3$

$z_3=-3$

That is, Template:Math.

Doubling

$D=X_1^3$

$E=Y_1^3$

$F=Z_1^3$

$G=a\cdot D$

$X_3=X_1\cdot (E-F)$

$Y_3=Z_1\cdot (G-E)$

$Z_3=Y_1\cdot (F-G)$

The cost of this algorithm is 3 multiplications, one multiplication by a constant, 3 additions, and 3 cubings. This is the best result obtained for this curve.

Example:

Let Template:Math be a point over the curve defined by Template:Math as above; then, Template:Math is given by:

$D=1;E=-1;F=1;G=-4;$

$x_3=-2$

$y_3=-3$

$z_3=-5$

That is, Template:Math.

See also

• Table of costs of operations in elliptic curves

External links

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

References

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