Hyperelliptic curve

A hyperelliptic curve is an algebraic variety , that is, a set of points from a body that satisfy a polynomial equation and some constraints.

They are constructed similarly to elliptic curves . In contrast to these, hyperelliptic curves do not yet play a major role in cryptography , but they are increasing. Their properties have not yet been researched extensively enough to be able to estimate their increased usability for cryptography. In addition, the calculation in hyperelliptic curves is more complicated than in elliptic curves, so that their current practical application does not yet appear useful.

The hyperelliptic curve

{\ displaystyle y ^ {2} = x (x + 1) (x-3) (x + 2) (x-2)}

definition

A hyperelliptic curve is the solution of a polynomial

{\ displaystyle y ^ {2} = f (x)}

,

where is a polynomial of degree with different roots in pairs. In the case of similarly constructed elliptical curves, however, is . ${\ displaystyle f (x)}$ ${\ displaystyle n> 4}$ ${\ displaystyle n}$ ${\ displaystyle n = 3}$

Gender is determined by the degree of the polynomial for or has the gender . It follows that gender is (the case corresponds to elliptic curves). The case is called an imaginary hyperelliptic curve, the case a real hyperelliptic curve. Often they are defined for odd degrees because the neighboring even case can be reduced to the case . ${\ displaystyle g}$ ${\ displaystyle n = 2g + 1}$ ${\ displaystyle n = 2g + 2}$ ${\ displaystyle g}$ ${\ displaystyle g> 1}$ ${\ displaystyle g = 1}$ ${\ displaystyle 2g + 1}$ ${\ displaystyle 2g + 2}$ ${\ displaystyle n}$ ${\ displaystyle n + 1}$ ${\ displaystyle n}$

In this form, the curve has a singular point at infinity, which is avoided by transitioning to a non-singular model in birational geometry.

In addition to considering real and complex numbers, they are also considered over finite fields and rational numbers within the framework of number theory. Since the gender is greater than 1, they only have a finite number of points above the rational numbers ( Mordell's conjecture / von Faltings' theorem).

The function body of a hyperelliptic curve (the body of the hyperelliptic functions) is a quadratic extension of the body of the rational functions.

Hyperelliptic curves over a finite body

A slightly different definition is used here. Elliptic curves are also considered as curves of gender g = 1, which is otherwise not common.

Let (where a prime power) be a finite field and be the algebraic closure of . A hyperelliptic curve with gender over is an equation of shape ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle q}$ ${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle C}$ ${\ displaystyle g}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle (g \ geq 1)}$

{\ displaystyle C}

: in .

{\ displaystyle y ^ {2} + h (x) y = f (x)}

{\ displaystyle \ mathbb {F} _ {q} [x, y]}

Also, there is no solution to the equations ${\ displaystyle (x, y) \ in {\ overline {\ mathbb {F}}} _ {q} \ times {\ overline {\ mathbb {F}}} _ {q}}$

{\ displaystyle y ^ {2} + h (x) y = f (x)}

,

{\ displaystyle 2y + h (x) = 0}

( partial derivative according to ),

{\ displaystyle y}

{\ displaystyle h '(x) y-f' (x) = 0}

(partial derivative according to )

{\ displaystyle x}

fulfilled (that is, only non-singular solutions are considered).

In addition, hyperelliptic curves are divided into two models:

Imaginary model : is normalized and of degree and degree at most ${\ displaystyle f}$ ${\ displaystyle 2g + 1}$ ${\ displaystyle h (u)}$ ${\ displaystyle g}$

Real model : or is normalized and of degree . If is odd, then is normalized and of degree . If is even, then either is of degree less than or equal to or of degree and the leading coefficient of is of the form for one . ${\ displaystyle h = 0}$ ${\ displaystyle h}$ ${\ displaystyle g + 1}$ ${\ displaystyle q}$ ${\ displaystyle f}$ ${\ displaystyle 2g + 2}$ ${\ displaystyle q}$ ${\ displaystyle f}$ ${\ displaystyle 2g + 1}$ ${\ displaystyle 2g + 2}$ ${\ displaystyle f}$ ${\ displaystyle x ^ {2} + x}$ ${\ displaystyle x \ in \ mathbb {F} _ {q} \ setminus \ {0 \}}$

A hyperelliptic involution of a point is defined as Points that are invariant are called Weierstrass points. ${\ displaystyle P = (x, y)}$ ${\ displaystyle -P = (x, -yh (x))}$

Construction of a group on hyperelliptic curves

Preliminary remarks

Interesting in cryptography are the point sets that satisfy the equation and at the same time are in a finite field (and meet the constraints of the definition). In order to use the curve in the sense of cryptography , an algebraic structure , i.e. a rule to be able to calculate on these points, must be defined - in this case it is a group . In addition, the algebraic structure must be such that it can be used to calculate efficiently, but under certain precautions the reversal of arithmetic operations can only be carried out very inefficiently, but again with the knowledge of certain additional information (so-called keys) Trapdoor one-way functions must be possible). It does this via the generally difficult problem of computing the discrete logarithm in the group. A group element and (the group is written here as a multiplicative) are given. Then the attacker's problem is to find (the “logarithm”). ${\ displaystyle g}$ ${\ displaystyle g ^ {a}}$ ${\ displaystyle a}$

Differentiation from elliptical curves

In contrast to elliptical curves , which allow a direct construction of a group on its points (tangent-secant construction), this is not possible with a hyperelliptic curve, since, for example, a straight line here has more than three intersection points (each counted with multiplicity and the Point at infinity is also taken into account) with the curve. Formal sums of points, so-called divisors, are defined here . The equivalence class of the group of divisors (to be defined below) of degree 0 modulo of the main divisors is called the Jacobian of the hyperelliptic curve. A group with the desired properties can then be defined on the Jacobian .

Basic definitions / notes

Points in projective space

As noted in the first definition, points on curve C are either pairs of numbers that satisfy the curve's equation or the point at infinity. In contrast, the pairs of numbers that satisfy the equation are also called finite points. The point at infinity is introduced as the curve is interpreted in projective space . It is a trick to compensate for the later-to-be-defined multiplicities of intersections of points on the curve with rational functions that intersect the curve. This will be detailed later in the article.

Heuristic / Idea for Construction

With reference to the last subsection, the idea of the construction will be briefly presented heuristically. This also makes the idea of the trick just mentioned become clear. A finite point P on curve C is to be assigned a number (order) that also depends on a rational function that intersects the curve in P. The order then indicates the multiplicity in which the rational function intersects curve C. Geometrically, a section of the multiplicity 1 would be the “classic” section, that is, where the functions (curve and rational function) do not “nestle” together; Multiplicity 2 would be a tangential cut, etc. The rational function might cut the curve at other points. A multiplicity can then be assigned to these. The others get the multiplicity 0. The point at infinity then gets the multiplicity that corresponds to the sum of the multiplicities of the finite points. This means that the total is equal to 0 (poles like here at infinity have a negative sign and an amount corresponding to the pole order). The rational function thus intersects the straight line at infinity (see projective geometry ) in precisely this multiplicity. The formal sum of these points is called the divisor . The set of divisors, the sum of the multiples (including the point at infinity) equals 0, is a subgroup of the total set of divisors (with a suitably definable link) and is denoted by. The subgroup of main divisors, to which a rational function can be assigned according to the above construction (divisor of a rational function on the Riemann surface of the hyperelliptic curve), is . On the equivalence class (called the Jacobi variety of C), a link can now be defined, which enables addition on the hyperelliptic curve. ${\ displaystyle \ mathbb {D} ^ {0}}$ ${\ displaystyle \ mathbb {P}}$ ${\ displaystyle \ mathbb {D} ^ {0} / \ mathbb {P}}$

literature

Cohen, Henry and Frey, Gerhard: Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall, Taylor & Francis Group 2006
Koblitz, Neal: Algebraic Aspects of Cryptography, Algorithms an Computation in Mathematics, Springer 1997

Web links

Menezes, An elementary introduction to hyperelliptic curves , University of Waterloo (pdf)
Hyperelliptic Curve, Mathworld

Individual evidence

^ Hyper-elliptic curve, Encyclopedia of Mathematics, Springer
↑ Sylvain Duquesne, Tanja Lange, Arithmetic of hyperelliptic curves, Chapter 14 in Cohen, Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall, Taylor & Francis Group 2006, pp. 303ff

[1] Hyper-elliptic curve, Encyclopedia of Mathematics, Springer

[2] Sylvain Duquesne, Tanja Lange, Arithmetic of hyperelliptic curves, Chapter 14 in Cohen, Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall, Taylor & Francis Group 2006, pp. 303ff