Cryptography Reference
In-Depth Information
Chapter 13
Hyperelliptic Curves
Given an algebraic curve, we can form its
Jacobian
, namely the group of
divisors of degree 0 modulo principal divisors. As we saw in Corollary 11.4,
the Jacobian of an elliptic curve gives the same group as the elliptic curve.
However, for other curves, we get something new. In this chapter, we discuss
hyperelliptic curves, for which the theory can be carried out rather explicitly.
In [62], Koblitz suggested using hyperelliptic curves to build cryptosystems.
Of course, whenever we have a group, we can build cryptosystems whose
security depends on the di
culty of solving the discrete logarithm problem
in the group. But computations in the group, for example adding elements,
need to be fast if the cryptosystem is to have practical value. In Section
13.3, we discuss Cantor's algorithm, which allows us to compute in Jacobians
of hyperelliptic curves. In Section 13.4, we show how a form of the index
calculus can be used to attack the discrete logarithm for these Jacobians. It
turns out that this attack is effective when the genus (an invariant attached
to the curve; see Theorem 11.15) is large. Therefore, it appears that the best
curves for cryptography have genus 2. For much more on hyperelliptic curves,
see [27], for example.
13.1 Basic Definitions
Let
K
be a field. Throughout Sections 13.1, 13.2, and 13.3, we assume that
K
is algebraically closed, so that all points we consider have coordinates in
K
.
Let
g ≥
1 be an integer and let
h
(
x
)and
f
(
x
) be polynomials with coecients
in
K
such that deg
f
=2
g
+1 and deg
h ≤ g
. Also, assume that
f
is monic
(that is, the coecient of
x
2
g
+1
is 1). The curve
C
given by the equation
C
:
y
2
+
h
(
x
)
y
=
f
(
x
)
(13.1)
is called a
hyperelliptic curve
of genus
g
if it is nonsingular for all
x, y ∈
K
. This means that no point (
x, y
) on the curve, with
x, y ∈ K
,satisfies
2
y
+
h
(
x
)=0=
f
(
x
)
− yh
(
x
). When
g
= 1, we obtain an elliptic curve in
Search WWH ::
Custom Search