Hyperelliptic curve cryptography
Encyclopedia
Hyperelliptic curve cryptography is similar to elliptic curve cryptography
(ECC) insofar as the Jacobian
of a hyperelliptic curve is an Abelian group
on which to do arithmetic, just as we use the group of points on an elliptic curve in ECC.
of genus
over a field 
is given by the equation 
where 
is a polynomial of degree not larger than 
and 
is a monic polynomial of degree 
. From this definition it follows that elliptic curves are hyperelliptic curves of genus 1. In hyperelliptic curve cryptography 
is often a finite field
. The Jacobian of
, denoted 
, is a quotient group
, thus the elements of the Jacobian are not points, they are equivalence classes of divisors
of degree 0 under the relation of linear equivalence
. This agrees with the elliptic curve case, because it can be shown that the Jacobian of an elliptic curve is isomorphic with the group of points on the elliptic curve. The use of hyperelliptic curves in cryptography came about in 1989 from Neal Koblitz
. Although introduced only 3 years after ECC, not many cryptosystems implement hyperelliptic curves because the implementation of the arithmetic isn't as efficient as with cryptosystems based on elliptic curves or factoring (RSA). The efficiency of implementing the arithmetic depends on the underlying finite field
, in practice it turns out that finite fields of characteristic
2 are a good choice for hardware implementations while software is usually faster in odd characteristic.
The Jacobian on a hyperelliptic curve is an Abelian group and as such it can serve as group for the discrete logarithm problem
(DLP). In short, suppose we have an Abelian group
and 
an element of 
, the DLP on 
entails finding the integer 
given two elements of 
, namely 
and 
. The first type of group used was the multiplicative group of a finite field, later also Jacobians of (hyper)elliptic curves were used. If the hyperelliptic curve is chosen with care, then Pollard's rho method
is the most efficient way to solve DLP. This means that, if the Jacobian has
elements, that the running time is exponential in 
. This makes is possible to use Jacobians of a fairly small order
, thus making the system more efficient. But if the hyperelliptic curve is chosen poorly, the DLP will become quite easy to solve. In this case there are known attacks which are more efficient than generic discrete logarithm solvers or even subexponential. Hence these hyperelliptic curves must be avoided. Considering various attacks on DLP, it is possible to list the features of hyperelliptic curves that should be avoided.
and Pollard's rho method
can be used to attack the DLP in the Jacobian of hyperelliptic curves. The Pohlig-Hellman attack reduces the difficulty of the DLP by looking at the order of the group we are working with. Suppose the group
that is used has 
elements, where 
is the prime factorization of 
. Pohlig-Hellman reduces the DLP in 
to DLPs in subgroups of order 
for 
. So for 
the largest prime divisor of 
, the DLP in 
is just as hard to solve as the DLP in the subgroup of order 
. Therefore we would like to choose 
such that the largest prime divisor 
of 
is almost equal to 
itself. Requiring 
usually suffices.
The index calculus algorithm is another algorithm that can be used to solve DLP under some circumstances. For Jacobians of (hyper)elliptic curves there exists an index calculus attack on DLP. If the genus of the curve becomes too high, the attack will be more efficient than Pollard's rho. Today it is known that even a genus of
cannot assure security. Hence we are left with elliptic curves and hyperelliptic curves of genus 2.
Another restriction on the hyperelliptic curves we can use comes from the Menezes-Okamoto-Vanstone-attack / Frey-Rück-attack. The first, often called MOV for short, was developed in 1993, the second came about in 1994. Consider a (hyper)elliptic curve
over a finite field 
where 
is the power of a prime number. Suppose the Jacobian of the curve has 
elements and 
is the largest prime divisor of 
. For 
the smallest positive integer such that 
there exists a computable injective
group homomorphism
from the subgroup of
of order 
to 
. If 
is small, we can solve DLP in 
by using the index calculus attack in 
. For arbitrary curves 
is very large (around the size of 
); so even though the index calculus attack is quite fast for multiplicative groups of finite fields this attack is not a threat for most curves. The injective function used in this attack is a pairing and there are some applications in cryptography that make use of them. In such applications it is important to balance the hardness of the DLP in 
and 
; depending on the security level values of 
between 6 and 12 are useful.
The subgroup of
is a torus
. There exists some independent usage in torus based cryptography.
We also have a problem, if
, the largest prime divisor of the order of the Jacobian, is equal to the characteristic of 
By a different injective map we could then consider the DLP in the additive group 
instead of DLP on the Jacobian. However, DLP in this additive group is trivial to solve, as can easily be seen. So also these curves, called anomalous curves, are not to be used in DLP.
of genus 
over the field 
where 
is the power of a prime number and define 
as 
but now over the field 
. It can be shown that the order of the Jacobian of 
lies in the interval 
, called the Hasse-Weil interval. But there is more, we can compute the order using the zeta-function on hyperelliptic curves. Let 
be the number of points on 
. Then we define the zeta-function of 
as 
. For this zeta-function it can be shown that 
where 
is a polynomial of degree 
with coefficients in 
. Furthermore 
factors as 
where 
for all 
. Here 
denotes the complex conjugate
of
. Finally we have that the order of 
equals 
. Hence orders of Jacobians can be found by computing the roots of 
.
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...
(ECC) insofar as the Jacobian
Imaginary hyperelliptic curve
A hyperelliptic curve is a particular kind of algebraic curve.There exist hyperelliptic curves of every genus g \geq 1. If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curve. Hence we can see hyperelliptic curves as generalizations of elliptic curves...
of a hyperelliptic curve is an Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
on which to do arithmetic, just as we use the group of points on an elliptic curve in ECC.
Definition
An (imaginary) hyperelliptic curveImaginary hyperelliptic curve
A hyperelliptic curve is a particular kind of algebraic curve.There exist hyperelliptic curves of every genus g \geq 1. If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curve. Hence we can see hyperelliptic curves as generalizations of elliptic curves...
of genus
Genus (mathematics)
In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
over a field is given by the equation where is a polynomial of degree not larger than and is a monic polynomial of degree . From this definition it follows that elliptic curves are hyperelliptic curves of genus 1. In hyperelliptic curve cryptography is often a finite fieldFinite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
. The Jacobian of
, denoted , is a quotient groupQuotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...
, thus the elements of the Jacobian are not points, they are equivalence classes of divisors
Imaginary hyperelliptic curve
A hyperelliptic curve is a particular kind of algebraic curve.There exist hyperelliptic curves of every genus g \geq 1. If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curve. Hence we can see hyperelliptic curves as generalizations of elliptic curves...
of degree 0 under the relation of linear equivalence
Linear system of divisors
In algebraic geometry, a linear system of divisors is an algebraic generalization of the geometric notion of a family of curves; the dimension of the linear system corresponds to the number of parameters of the family....
. This agrees with the elliptic curve case, because it can be shown that the Jacobian of an elliptic curve is isomorphic with the group of points on the elliptic curve. The use of hyperelliptic curves in cryptography came about in 1989 from Neal Koblitz
Neal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...
. Although introduced only 3 years after ECC, not many cryptosystems implement hyperelliptic curves because the implementation of the arithmetic isn't as efficient as with cryptosystems based on elliptic curves or factoring (RSA). The efficiency of implementing the arithmetic depends on the underlying finite field
, in practice it turns out that finite fields of characteristicCharacteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
2 are a good choice for hardware implementations while software is usually faster in odd characteristic.
The Jacobian on a hyperelliptic curve is an Abelian group and as such it can serve as group for the discrete logarithm problem
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
(DLP). In short, suppose we have an Abelian group
and an element of , the DLP on entails finding the integer given two elements of , namely and . The first type of group used was the multiplicative group of a finite field, later also Jacobians of (hyper)elliptic curves were used. If the hyperelliptic curve is chosen with care, then Pollard's rho methodPollard's rho algorithm
Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.-Core ideas:...
is the most efficient way to solve DLP. This means that, if the Jacobian has
elements, that the running time is exponential in . This makes is possible to use Jacobians of a fairly small orderOrder (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
, thus making the system more efficient. But if the hyperelliptic curve is chosen poorly, the DLP will become quite easy to solve. In this case there are known attacks which are more efficient than generic discrete logarithm solvers or even subexponential. Hence these hyperelliptic curves must be avoided. Considering various attacks on DLP, it is possible to list the features of hyperelliptic curves that should be avoided.
Attacks against the DLP
All generic attacks on the discrete logarithm problem in finite abelian groups such as the Pohlig-Hellman algorithmPohlig-Hellman algorithm
In number theory, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer....
and Pollard's rho method
Pollard's rho algorithm for logarithms
Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....
can be used to attack the DLP in the Jacobian of hyperelliptic curves. The Pohlig-Hellman attack reduces the difficulty of the DLP by looking at the order of the group we are working with. Suppose the group
that is used has elements, where is the prime factorization of . Pohlig-Hellman reduces the DLP in to DLPs in subgroups of order for . So for the largest prime divisor of , the DLP in is just as hard to solve as the DLP in the subgroup of order . Therefore we would like to choose such that the largest prime divisor of is almost equal to itself. Requiring usually suffices.The index calculus algorithm is another algorithm that can be used to solve DLP under some circumstances. For Jacobians of (hyper)elliptic curves there exists an index calculus attack on DLP. If the genus of the curve becomes too high, the attack will be more efficient than Pollard's rho. Today it is known that even a genus of
cannot assure security. Hence we are left with elliptic curves and hyperelliptic curves of genus 2.Another restriction on the hyperelliptic curves we can use comes from the Menezes-Okamoto-Vanstone-attack / Frey-Rück-attack. The first, often called MOV for short, was developed in 1993, the second came about in 1994. Consider a (hyper)elliptic curve
over a finite field where is the power of a prime number. Suppose the Jacobian of the curve has elements and is the largest prime divisor of . For the smallest positive integer such that there exists a computable injectiveInjective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
group homomorphism
Group homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...
from the subgroup of
of order to . If is small, we can solve DLP in by using the index calculus attack in . For arbitrary curves is very large (around the size of ); so even though the index calculus attack is quite fast for multiplicative groups of finite fields this attack is not a threat for most curves. The injective function used in this attack is a pairing and there are some applications in cryptography that make use of them. In such applications it is important to balance the hardness of the DLP in and ; depending on the security level values of between 6 and 12 are useful.The subgroup of
is a torusTorus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
. There exists some independent usage in torus based cryptography.
We also have a problem, if
, the largest prime divisor of the order of the Jacobian, is equal to the characteristic of By a different injective map we could then consider the DLP in the additive group instead of DLP on the Jacobian. However, DLP in this additive group is trivial to solve, as can easily be seen. So also these curves, called anomalous curves, are not to be used in DLP.Order of the Jacobian
Hence, in order to choose a good curve and a good underlying finite field, it is important to know the order of the Jacobian. Consider a hyperelliptic curve of genus over the field where is the power of a prime number and define as but now over the field . It can be shown that the order of the Jacobian of lies in the interval , called the Hasse-Weil interval. But there is more, we can compute the order using the zeta-function on hyperelliptic curves. Let be the number of points on . Then we define the zeta-function of as . For this zeta-function it can be shown that where is a polynomial of degree with coefficients in . Furthermore factors as where for all . Here denotes the complex conjugateComplex conjugate
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...
of
. Finally we have that the order of equals . Hence orders of Jacobians can be found by computing the roots of .External links
- Colm Ó hÉigeartaigh Implementation of some hyperelliptic curves algorithms using MIRACLMIRACL (software)MIRACL is an arbitrary-precision arithmetic software package developed by Shamus Software. It is often used in encryption and number theory programs. The source code of this library is publicly available and it can be used for free for educational and non-commercial use...