Open main menu

Tripling-oriented Doche–Icart–Kohel curve

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve. At certain conditions some operations, as adding, doubling or tripling points, are faster to compute using this form. The Tripling oriented Doche–Icart–Kohel curve, often called with the abbreviation 3DIK has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in [1]

Contents

DefinitionEdit

 
A tripling-oriented Doche–Icart–Kohel curve of equation  

Let   be a field of characteristic different form 2 and 3.

An elliptic curve in tripling oriented Doche–Icart–Kohel form is defined by the equation:

 

with  .

A general point P on   has affine coordinates  . The "point at infinity" represents the neutral element for the group law and it is written in projective coordinates as O = (0:1:0). The negation of a point P = (xy) with respect to this neutral element is −P = (x, −y).

The group lawEdit

Consider an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form in affine coordinates:

 

As in other forms of elliptic curves, it is possible to define some "operations" between points, such as adding points, or doubling (See also The group law). In the following sections formulas to add, negate and doubling points are given. The addition and doubling formulas are often used for other operations: given a point P on an elliptic curve it is possible to compute [n]P, where n is an integer, using addition and doubling; computing multiples of points is important in elliptic curve cryptography and in Lenstra elliptic curve factorization.

AdditionEdit

Given   and   on  , the point   has coordinates:

 

DoublingEdit

Given a point   on  , the point   has coordinates:

 

NegationEdit

Given a point   on  , its negation with respect to the neutral element   is  .

There are also other formulas given in [2] for Tripling-oriented Doche–Icart–Kohel curves for fast tripling operation and mixed-addition.

New Jacobian coordinatesEdit

For computing on these curves points are usually represented in new Jacobian coordinates (Jn):

a point in the new Jacobian coordinates is of the form  ; moreover:

 

for any  .

This means, for example, that the point   and the point   (for  ) are actually the same.

So, an affine point   on   is written in the new Jacobian coordinates as  , where   and  ; in this way, the equation for   becomes:

 

The term   of a point on the curve makes the mixed addition (that is the addition between two points in different systems of coordinates) more efficient.

The neutral element in new Jacobian coordinates is  .

Algorithms and examplesEdit

AdditionEdit

The following algorithm represents the sum of two points   and   on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. The result is a point  . It is assumed that   and that  . The cost of this implementation is 7M + 4S + 1*a3 + 10add + 3*2 + 1*4, where M indicates the multiplications, S the squarings, a3 indicates the multiplication by the constant a3, add represents the number of additions required.

 

 

 

 

 

 

 

 

 

 

 

 

 

ExampleEdit

Let   and   affine points on the elliptic curve over  :

 .

Then:

 

 

 

 

 

 

 

 

 

 

 

 

 

Notice that in this case  . The resulting point is  , that in affine coordinates is  .

DoublingEdit

The following algorithm represents the doubling of a point   on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. It is assumed that  ,  . The cost of this implementation is 2M + 7S + 1*a2 + 1*a3 + 12add + 2*2 + 1*3 + 1*8; here M represents the multiplications, S the squarings, a2 and a3 indicates the multiplications by the constants a2 and a3 respectively, and add indicates the additions.

 

 

 

 

 

 

 

 

 

 

ExampleEdit

Let   be a point on  .

Then:

 

 

 

 

 

 

 

 

 

 

Notice that here the point is in affine coordinates, so  . The resulting point is  , that in affine coordinates is  .

Equivalence with Weierstrass formEdit

Any elliptic curve is birationally equivalent to another written in the Weierstrass form.

The following twisted tripling-oriented Doche-Icart-Kohel curve:

 

can be transformed into the Weierstrass form by the map:

 

In this way   becomes:

 .

Conversely, given an elliptic curve in the Weierstrass form:

 ,

it is possible to find the "corresponding" Tripling-oriented Doche–Icart–Kohel curve, using the following relation:

 

where a is a root of the polynomial

 

where

 

is the j-invariant of the elliptic curve  .

Notice that in this case the map given is not only a birational equivalence, but an isomorphism between curves.

Internal linkEdit

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

NotesEdit

  1. ^ Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions
  2. ^ Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions, pag 198-199

External linksEdit

ReferencesEdit

  • Christophe Doche; Thomas Icart & David R. Kohel (2006). Efficient Scalar Multiplication by Isogeny Decompositions (PDF). appeared at PKC 2006, part of LNCS (Lecture Series in Computer Science) volume number 3958. Springer Verlag. pp. 285–352.
  • Daniel J. Bernstein, Tanja Lange (2007). Analysis and optimization of elliptic-curve single-scalar multiplication (PDF). appeared in G.L. Mullen, D. Panario, I.E. Shparlinski (eds.), Finite Fields and Applications (Proceedings 8th International Conference, Fq8, Melbourne, Australia, July 9–13, 2007). Mathematics Subject Classification.
  • D.J.Bernstein, P.Birkner, T.Lange, and C.Peters (2007). Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication (PDF). appeared in K. Srinathan, C. Pandu Rangan, M. Yung (Eds.), Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (Indocrypt 2007) 9–13 December 2007, Chennai, India. Springer.CS1 maint: Multiple names: authors list (link)
  • http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html