In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the Twisted Hessian curve represents a generalization of Hessian curve

Hessian 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...

s; it was introduced in elliptic curve cryptography

Elliptic curve cryptography

Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

 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 curve

Edwards curve

In mathematics, an Edwards curve is a new representation of elliptic curves, discovered by Harold M. Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography...

s.

Definition

Let be a field

Field (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

. According to twisted Hessian curves were introduced by Bernstein

Daniel J. Bernstein

Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...

, Lange,
and Kohel.

The twisted Hessian form in affine coordinates

Affine space

In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...

is given by:



and in projective coordinates

Projective space

In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....

:



where and and in

Note that these curves are birationally equivalent

Birational geometry

In mathematics, birational geometry is a part of the subject of algebraic geometry, that deals with the geometry of an algebraic variety that is dependent only on its function field. In the case of dimension two, the birational geometry of algebraic surfaces was largely worked out by the Italian...

 to Hessian curves.

The Hessian curve is just a special case of Twisted Hessian curve, with a=1.

Considering the equation , note that:

if a has a cube root in , there exists a unique b such that .Otherwise, it is necessary to consider an extension field

Field extension

In abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties...

 of (e.g., ). Then, since , defining , the following equation is needed (in Hessian form) to do the transformation:

.

This means that Twisted Hessian curves are birationally equivalent to elliptic curve in Weierstrass form

Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

.

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). 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 be a point, then its inverse is in the plane.
In projective coordinates, let be one point, then is the inverse of P.

Furthermore, the neutral element (in affine plane) is: and in projective coordinates: .

In some application of elliptic curve cryptography

Elliptic curve cryptography

Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

 and the ellitpic curve method of factorization (ECM

Lenstra elliptic curve factorization

The Lenstra elliptic curve factorization or the elliptic curve factorization method 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...

) it is necessary to compute the scalar multiplications of P, say [n]P for some integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 n, and they are based on double-and-add method

Exponentiation by squaring

Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...

; so the addition and dobling formulas are needed.

The addition and doubling formulas for this elliptic curve

Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

 can be defined, using the affine coordinates to simplify the notation:

Addition formulas:

Let and then, is given by the following equations:





Doubling formulas:

Let then is given by the following equations:

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

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

Example:

let and be points over a twisted Hessian curve with a=2 and d=-2.Then is given by:



That is, .

Doubling

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

Example:

let be a point over the curve defined by a=2 and d=-2 as above, then is given by:




That is .

Internal Link

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

Table of costs of operations in elliptic curves

This table relates to the computational cost for certain operations used in elliptic curve cryptography, used in practice for strong cryptographic security of a public key system. The columns of the table are labelled by various computational steps...