Tripling-oriented Doche–Icart–Kohel curve

Last updated

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography [ when? ]; 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

Definition

A tripling-oriented Doche-Icart-Kohel curve of equation
y
2
=
x
3
-
3
x
2
-
6
x
-
3
{\displaystyle y^{2}=x^{3}-3x^{2}-6x-3} Tripling oriented.svg
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 = (x, y) with respect to this neutral element is P = (x, y).

The group law

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.

Addition

Given and on , the point has coordinates:

Doubling

Given a point on , the point has coordinates:

Negation

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 coordinates

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 examples

Addition

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.

Example

Let and affine points on the elliptic curve over :

.

Then:

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

Doubling

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.

Example

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 form

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.

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

Notes

  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, page 198-199

Related Research Articles

Elliptic curve Algebraic 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 defined over a field K and describes points in K2, the Cartesian product of K with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which, after a linear change of variables, consists of solutions (x,y) for:

In the mathematical field of complex analysis, elliptic functions are a special kind of meromorphic functions, that satisfy two periodicity conditions. They are named elliptic functions because they come from elliptic integrals. Originally those integrals occurred at the calculation of the arc length of an ellipse.

Ellipsoid Quadric surface that looks like a deformed sphere

An ellipsoid is a surface that may be obtained from a sphere by deforming it by means of directional scalings, or more generally, of an affine transformation.

Legendre function

In physical science and mathematics, the Legendre functionsPλ, Qλ and associated Legendre functionsPμ
λ
, Qμ
λ
, and Legendre functions of the second kind, Qn, are all solutions of Legendre's differential equation. The Legendre polynomials and the associated Legendre polynomials are also solutions of the differential equation in special cases, which, by virtue of being polynomials, have a large number of additional properties, mathematical structure, and applications. For these polynomial solutions, see the separate Wikipedia articles.

In mathematics, the Carlson symmetric forms of elliptic integrals are a small canonical set of elliptic integrals to which all others may be reduced. They are a modern alternative to the Legendre forms. The Legendre forms may be expressed in terms of the Carlson forms and vice versa.

Weierstrass elliptic function Class of mathematical functions

In mathematics, the Weierstrass elliptic functions are elliptic functions that take a particularly simple form. They are named for Karl Weierstrass. This class of functions are also referred to as ℘-functions and they are usually denoted by the symbol ℘, a uniquely fancy script p. They play an important role in the theory of elliptic functions. A ℘-function together with its derivative can be used to parameterize elliptic curves and they generate the field of elliptic functions with respect to a given period lattice.

<i>j</i>-invariant

In mathematics, Felix Klein's j-invariant or j function, regarded as a function of a complex variable τ, is a modular function of weight zero for SL(2, Z) defined on the upper half-plane of complex numbers. It is the unique such function which is holomorphic away from a simple pole at the cusp such that

In mathematics, complex multiplication (CM) is the theory of elliptic curves E that have an endomorphism ring larger than the integers; and also the theory in higher dimensions of abelian varieties A having enough endomorphisms in a certain precise sense. Put another way, it contains the theory of elliptic functions with extra symmetries, such as are visible when the period lattice is the Gaussian integer lattice or Eisenstein integer lattice.

In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.

In functional analysis, a branch of mathematics, it is sometimes possible to generalize the notion of the determinant of a square matrix of finite order to the infinite-dimensional case of a linear operator S mapping a function space V to itself. The corresponding quantity det(S) is called the functional determinant of S.

In physics and mathematics, the solid harmonics are solutions of the Laplace equation in spherical polar coordinates, assumed to be (smooth) functions . There are two kinds: the regular solid harmonics, which are well-defined at the origin and the irregular solid harmonics, which are singular at the origin. Both sets of functions play an important role in potential theory, and are obtained by rescaling spherical harmonics appropriately:

In mathematics, every analytic function can be used for defining a matrix function that maps square matrices with complex entries to square matrices of the same size.

In mathematics, the Jacobi curve is a representation of an elliptic curve different from the usual one defined by the Weierstrass equation. Sometimes it is used in cryptography instead of the Weierstrass form because it can provide a defence against simple and differential power analysis style (SPA) attacks; it is possible, indeed, to use the general addition formula also for doubling a point on an elliptic curve of this form: in this way the two operations become indistinguishable from some side-channel information. The Jacobi curve also offers faster arithmetic compared to the Weierstrass curve.

In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations, it is close in speed to Edwards curves.

Doubling-oriented Doche–Icart–Kohel curve

In mathematics, the doubling-oriented Doche–Icart–Kohel curve is a form in which an elliptic curve can be written. It is a special case of Weierstrass form and it is also important in elliptic-curve cryptography because the doubling speeds up considerably. It has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in Efficient Scalar Multiplication by Isogeny Decompositions.

Twisted Edwards curve

In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein, Birkner, Joye, Lange and Peters in 2008. The curve set is named after mathematician Harold M. Edwards. Elliptic curves are important in public key cryptography and twisted Edwards curves are at the heart of an electronic signature scheme called EdDSA that offers high performance while avoiding security problems that have surfaced in other digital signature schemes.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

In mathematics, the method of steepest descent or saddle-point method is an extension of Laplace's method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point, in roughly the direction of steepest descent or stationary phase. The saddle-point approximation is used with integrals in the complex plane, whereas Laplace’s method is used with real integrals.

Modular lambda function

In mathematics, the modular lambda function λ(τ) is a highly symmetric holomorphic function on the complex upper half-plane. It is invariant under the fractional linear action of the congruence group Γ(2), and generates the function field of the corresponding quotient, i.e., it is a Hauptmodul for the modular curve X(2). Over any point τ, its value can be described as a cross ratio of the branch points of a ramified double cover of the projective line by the elliptic curve , where the map is defined as the quotient by the [−1] involution.

Confocal conic sections

In geometry, two conic sections are called confocal, if they have the same foci. Because ellipses and hyperbolas possess two foci, there are confocal ellipses, confocal hyperbolas and confocal mixtures of ellipses and hyperbolas. In the mixture of confocal ellipses and hyperbolas, any ellipse intersects any hyperbola orthogonally. Parabolas possess only one focus, so, by convention, confocal parabolas have the same focus and the same axis of symmetry. Consequently, any point not on the axis of symmetry lies on two confocal parabolas which intersect orthogonally.

References