Discrete Applied Mathematics 128 (2003) 165180

www.elsevier.com/locate/dam
Weil descent of Jacobians

Steven D. Galbraith
Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, UK
Received 20 February 2001; received in revised form 29 May 2001; accepted 8 April 2002
Abstract
The technique of Weil restriction of scalars has signicant implications for elliptic curve
cryptography. In this paper we apply these ideas to the case of the discrete logarithm problem
in the Jacobian of a curve of genus greater than one over a nite eld F
q
n where n 1.
? 2003 Elsevier Science B.V. All rights reserved.
1. Introduction
The idea of using Weil restriction of scalars as a means to solve the elliptic curve
discrete logarithm problem was suggested by Frey [5] and then developed further in
[7,9].
In this paper we consider the Jacobian of a genus q 1 curve C over a nite eld
F
q
n where q is a prime or a power of a prime and where n 1. The discrete logarithm
problem is as follows: Suppose there is a divisor D
1
in the divisor class group of C
over F
q
n which has (large) prime order L, then given any other divisor D
2
in the group
generated by D
1
the problem is to nd an integer z such that D
2
= zD
1
.
As in the case of elliptic curves, one can consider the Weil restriction of the
q-dimensional Abelian variety Jac(C) with respect to the Galois extension F
q
n }F
q
and
obtain an Abelian variety A of dimension nq over F
q
. One then searches for a curve C
lying on A in such a way that one can pull the divisors D
1
and D
2
back to Jac(C)(F
q
)
and then solve the discrete logarithm problem there using one of the available algo-
rithms (see [1,4,8]) for solving such problems on high genus curves.

This research was supported by the NRW-Initiative f ur Wissenschaft und Wirtschaft Innovationscluster
f ur Neue Medien and cv cryptovision gmbh (Gelsenkirchen).
E-mail address: [email protected] (S.D. Galbraith).
0166-218X/03/$ - see front matter ? 2003 Elsevier Science B.V. All rights reserved.
PII: S0166- 218X( 02) 00443- 2
166 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
Before giving esh to this skeleton, we discuss the practical situation we have in
mind.
2. The cryptographic application
The most relevant cases of Jacobians of curves for cryptography are when C is a
hyperelliptic curve of genus 2 or 3 or possibly 4. For these cases there are few ecient
methods to construct cryptographically suitable curves with known group order. One
commonly used method to construct curves with known group order is to use subeld
curves, i.e., curves C dened over a small eld F
q
but considered as a group over
some larger extension eld F
q
! (the group order can be deduced from the characteristic
polynomial of the Frobenius map).
This strategy rst appeared in Koblitz [11]. His examples involve curves C}F
2
and
the group used for cryptography is Jac(C)(F
2
! ) for some prime number !. In practice,
we have q = 2, 3 and ! roughly in the range 70 ! 100. We emphasise that, in
practice, it is always the case that the extension degree is prime, since, otherwise, it
is not possible to obtain a group order which has very large prime factor.
One advantage of using subeld curves is that the action of the Frobenius endomor-
phism can be used to accelerate the arithmetic on these curves [11,10]. However, this
Frobenius action also makes the Pollard methods more eective as one can consider
random walks on equivalence classes as in [3]. Therefore, there is slightly less security
than was rst imagined from using these curves. Another drawback is that there are
very few curves available when one restricts to curves over F
2
.
To obtain a larger number of examples and to reduce the eectiveness of the Pollard
methods one might prefer to choose the original curve C over a slightly larger extension
F
2
n and consider the group as Jac(C)(F
2
n! ) for some prime number !. For curves of
genus 2 or 3 we then take 2 6n 65 and correspondingly 12 ! 50 so that we have
qn! 200.
It is exactly the case outlined in the previous paragraph which will be the main
focus of this paper. We will consider the Weil restriction of Jac(C)(F
2
n! ) with respect
to the extension F
q
n! }F
q
! to obtain an Abelian variety of dimension nq over F
q
! . We
show that Weil descent can give a feasible attack in this situation.
In this case, the curve C is dened over the larger eld with respect to the ex-
tension F
q
n }F
q
. This means that, from the point of view of Weil descent, the curve
is not a subeld curve. As emphasised above, Weil descent is rarely interesting for
subeld curves as the corresponding eld extensions always have fairly large prime
degree. Of course, the techniques are also applicable in the case where the curve C
is actually dened over the full eld F
2
n! , though this case is not so prominent in the
applications.
This paper is primarily concerned with the elds of characteristic two as they are the
most important in practice. The odd characteristic case is discussed in
Section 7.
It is not very easy to express the complexity of Weil descent in a meaningful sense
(i.e., one which can be used to determine the security of a discrete logarithm problem).
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 167
Part of the problem is a lack of experience with solving discrete logarithms on high
genus curves (although see [4,8,12]). Examples 2 and 3 (Sections 4.7 and 4.8) show
that there are cases of curves of genus 3 over certain eld extensions for which the
discrete logarithm problem is signicantly easier to solve than had been previously
thought (although still exponential complexity).
To completely avoid the threat of Weil descent one may use curves over prime
elds F

(where is prime). Curves over elds of the form F

2
! where ! is prime (and
thus ! 40) will, in general, be resistant to the Weil descent attack. In particular, the
curves in Koblitz [11] seem to resist our methods.
Of course there is a constructive aspect to this work as in [9] (i.e., giving a
method to construct Abelian varieties or Jacobians with known group order). This is
not as interesting as the elliptic curve case where the SchoofAtkinElkies algorithm
is available. Also, the Abelian varieties arising will be very special (see [6] for a
discussion of the elliptic curve case).
3. The algebraic approach
The approach given by Gaudry, Hess and Smart in [9] used only algebraic techniques
(function elds and norm maps) and was extremely successful. We will mimic that
approach in this paper. First, we explain the algebraic approach in geometric terms.
Let K =F
q
n , k =F
q
(where q is a power of any prime), let C be a curve of genus
q over K and suppose we have a discrete logarithm problem D
2
= zD
1
in the divisor
class group Pic
0
K
(C) of the curve. We identify the divisor class group Pic
0
K
(C) with the
K-valued points of the Jacobian Jac(C). A prime divisor on C over K corresponds to
a place of the function eld K(C) and so we can manipulate divisors by manipulating
places of the eld.
The starting point of the approach of [9] is to construct a certain function eld F
over the eld K. This is an algebraic eld extension of K(C) constructed specically
so that there is a Galois action which allow us to view F as having constant eld k.
In [9] this is motivated by taking a curve C which lies on the Weil restriction of E}K
and dening F = K(C).
In this paper we mimic the construction of F given in [9] (see Section 4.2). At
rst sight there seems to no longer be any geometry in the picture since we have
not written down any equations for the Weil restriction of the Abelian variety Jac(C).
However, given the function eld F over K there exists some curve C which (except for
some special cases) may be dened over K and is such that F = K(C). The inclusion
K(C) K(C) induces a rational map [ : C C of curves over K and this then
induces a map of Abelian varieties Jac(C) Jac(C) over K.
The next step of [9] is to pull back the discrete logarithm problem to C. This is
done using the conorm (see Stichtenoth [14, Denition III.1.8]). The geometric picture
behind the denition of the conorm is simply that, under the map [: C C, a place
of C is pulled back to a divisor of places on C counted with a multiplicity which
corresponds to the ramication. A principal divisor ([) on C is pulled back to the
principal divisor ([ [).
168 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
We can therefore transfer the discrete logarithm problem from Jac(C)(K) to
Jac(C)(K). Now, by the construction of F = K(C) it follows (at least, except for
some special cases) that C can be dened over k. There is the inclusion Jac(C)(k)
Jac(C)(K) and it remains to pull the discrete logarithm problem back along this
map. The obvious method to achieve this is to take a trace map DPic
0
K
(C)

oGal(K}k)
D
o
Pic
0
k
(C). The norm map of [9] is precisely this trace converted to the
function eld notation. The image of a principal divisor ([) is simply the principal
divisor (

o
[
o
).
It is possible that some of these maps can be degenerate on certain divisors. However,
this will happen with low probability in the general case.
4. A specic class of curves
The Weil descent strategy outlined in the previous section applies in a very general
way. The key step is the construction of the function eld F. In this section we discuss
a special class of curves C over elds of characteristic two, analogous to the elliptic
curves considered in [9], for which we have a construction for the function eld F.
We can then prove some strong results about the curves C which arise. In particular, it
is possible to bound the genus of the curves C and to prove that they are hyperelliptic.
4.1. The curves
We let k =F
q
be a nite eld of characteristic two (i.e., q =2
t
) and let K =F
q
n be
the Galois extension of k of degree n. A general hyperelliptic curve of genus q over
a characteristic two eld K is given by an equation of the form ,
2
+ h(x), = [(x)
where deg(h(x)) 6q + 1 and deg([(x)) 62q + 2.
In this section we consider the most commonly appearing special case, namely C
given by an equation ,
2
+ x, = [(x) where [(x) = x
2q+1
+ a
2q
x
2q
+ a
1
x + a
0
is a
monic polynomial of degree 2q + 1 over K. Up to a change of variable (dened over
K) this case includes all curves with deg(h(x)) =1. The case deg(h(x)) =0 is handled
with the same ease. Cases where deg(h(x)) 1 can often be handled by these methods
(see Examples 4 and 5), but our theoretical results do not cope with this case.
Note that there will be further conditions imposed on C below and so not all curves
can be handled using the method of this section.
4.2. Weil restriction
Let C be a curve over K = F
q
n of genus q with generic point (x, ,). The Weil
restriction of C with respect to the Galois extension K}k =F
q
n }F
q
is the variety whose
generic point is

jGal(K}k)
(x
j
, ,
j
). In our case, we let o be a generator for Gal(K}k)
and write (x
i
, w
i
) for the point (x
o
i
, ,
o
i
). Each such point satises the equation w
2
i
+
x
i
w
i
= [
o
i
(x
i
).
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 169
The principle adopted in [7,9] of taking a product over P
1
of Galois twists of curves
(equivalently, imposing that the function x is Galois invariant) gives rise to a function
eld F = K(x, w
0
, w
1
, . . . , w
n1
) dened by the equations
w
2
0
+ xw
0
= [(x)
w
2
1
+ xw
1
= [
o
(x)
.
.
.
.
.
.
.
.
.
w
2
n1
+ xw
n1
= [
o
n1
(x).
This is analogous to the variety D of [9, Section 3.1].
The rst equation implies that K(C) is a subeld of F. Indeed, F may be consid-
ered as an algebraic extension of K(C) obtained by taking a sequence of quadratic
extensions.
4.3. ArtinSchreier extensions
We now study the results of [9] in the context of our more general extension of
function elds. We dene the magic number m to be such that 2
m
= [F : K(x)]. In
general, we have m = n.
To generalise the expression of m in terms of the dimension of a simple vector space
as in [9] requires some care as the equations under consideration have more terms on
the right-hand side.
We now mimic the changes of variable used in [9] so that we can study the function
eld F by means of the theory of ArtinSchreier extensions. We make the change of
variable s
i
= (w
i
+

a
0
o
i
)x
1
for i = 0, 1, . . . , n 1 to obtain the set of equations
s
2
i
+ s
i
= x
2q1
+ a
o
i
2q
x
2q2
+ + a
o
i
2
+ (a
o
i
1
+

a
0
o
i
)x
1
, (1)
where i = 0, 1, . . . , n 1. We then dene t
i
= s
i
+ s
0
for i = 1, . . . , n 1 to obtain the
set of equations
t
2
i
+ t
i
= (a
2q
+ a
o
i
2q
)x
2q2
+ + (a
1
+

a
0
+ a
o
i
1
+

a
0
o
i
)x
1
, (2)
where i = 1, . . . , n 1. Clearly, F = K(x, s
0
, . . . , s
n1
) = K(x, s
0
, t
1
, . . . , t
n1
).
At rst our ArtinSchreier extensions (2) seem much more complicated than those
in [9], and it seems unlikely that we can obtain equations of the form
t
2
i
+ t
i
=
i
+ o
i
x
1
or t
2
i
+ t
i
=
i
+ o
i
x.
The crucial property of the above two equations is linearity in x
1
or x and we will
call them Type A and Type B, respectively. However, recall that ArtinSchreier
extensions are only dened up to terms of the form :
2
+ : and so one can easily
eliminate any even-degree terms from the right-hand side. Also recall that odd-degree
terms (e.g., the term x
2q1
) will possibly have been removed by subtraction using the
rst equation.
Nevertheless, there are curves C for which this process does not give a non-trivial
linear equation and the results of this section do not apply in those cases. We give a
170 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
few examples to illustrate which curves can be tackled with this approach and which
cannot. In all these examples we let c
i
lie in k, while elements 0 K are chosen such
that 0
o
i
= 0 for all 1 i n where o generates Gal(K}k) (in particular, if 0 does not
lie in any proper subeld of K then this property will hold). We rst list some curves
for which a Type A or B equation always arises
,
2
+ x, = x
2q+1
+ + c
3
x
3
+ c
2
x
2
+ c
1
x + 0,
,
2
+ x, = x
2q+1
+ + c
3
x
3
+ c
2
x
2
+ 0x + c
1
,
,
2
+ x, = x
2q+1
+ + 0x
3
+ c
3
x
2
+ c
2
x + c
1
,
,
2
+ x, = x
2q+1
+ + 0

x
3
+ c
1
x
2
+ 0x + 0
2
.
Here the terms in the all have coecients dened over the small eld k. On the
other hand, curves of the form ,
2
+ x, = x
2q+1
+ 0x
2
+ c
1
x + c
2
or ,
2
+ x, = x
2q+1
+
0
2
x
4
+ 0x
3
+ c
1
x
2
+ c
2
x + c
3
are not amenable to our methods.
4.4. Hyperellipticity and genus formulae
We now restrict to the case where Eqs. (2) can be massaged so that they are of
Type A or B (i.e., are linear in either x or x
1
).
In both cases, the method and result of [9, Lemma 7] of applies verbatim where
: = x
1
if we have a Type A curve and : = x if the curve is of Type B. It follows
that there is a function c (which is a linear combination of the functions t
i
over K)
such that : = (c) where is a polynomial over K of the form z
1
+

m1
)=0
z
)
c
2
)
. It
also follows that z
0
and z
m1
are both non-zero.
We write L = K(c). This rational function eld is a subeld of F. Furthermore, F
is obtained from L by adjoining the function s
0
given by the quadratic equation (1).
The following result is therefore immediate:
Proposition 1. The function eld F is hyperelliptic.
We now want to estimate the genus of the function eld F. The following result is
a generalisation of [9, Lemma 9]. We will give a dierent proof to the one given in
[9]. Our proof is rather elementary but it has the mild disadvantage of only providing
an upper bound on the genus.
Proposition 2. Let F be the function eld over K as above and suppose we are in
the Type A or B case. Then the genus of the hyperelliptic function eld F is less
than or equal to q2
m1
, where q is the genus of the original curve C.
Proof. In Type A case we have x
1
=(c) while in the Type B case we have x=(c)
where (c) has degree 2
m1
. Starting from the i = 0 equation in (1) we will exhibit
a particular hyperelliptic equation for the function eld F over L.
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 171
In the Type A case dene w = (c)
q
s
0
and obtain (writing a

1
= (a
1
+

a
0
) which
in the Type A case is non-zero)
w
2
+ (c)
q
w = (c) + a
2q
(c)
2
+ a
2
(c)
2q
+ a

1
(c)
2q+1
. (3)
In Type B case we dene w = (c)s
0
and obtain
w
2
+ (c)w = (c)
2q+1
+ a
2q
(c)
2q
+ + a

1
(c). (4)
To show that the curve ,
2
+ h(c), = [(c) has genus 6q2
m1
we will show that
deg(h(c)) 6q2
m1
and deg([(c)) 6q2
m
+ 1. For the two Eqs. (3) and (4) we have
h(c) = (c)
q
or h(c) = (c) and so the condition on the degree of h(c) is satised.
However, the condition on [ is initially violated since (c)
2q+1
has terms of degree
q2
m
+ 2
m1
, q2
m
+ 2
m2
, . . . , q2
m
+ 2. Note that the powers of c appearing in the term
(c)
2q
have degree at most q2
m
which is no problem.
It remains to perform an inductive sequence of changes of variable to remove the
terms of degree more than q2
m
+1. Set t
1
=w and suppose that our equation is of the
form
t
2
i
+ h(c)t
i
= [(c),
where the leading term of [(c) is :c
q2
m
+2
mi
and where the only terms in [(c) of
degree greater than q2
m
+ 1 have degrees of the form q2
m
+ 2
k
(with k 6(m i)).
Dene t
i+1
= t
i
+

:c
q2
m1
+2
mi1
. Then we have
t
2
i+1
+ h(c)t
i+1
= [(c) + :c
q2
m
+2
mi
+ h(c)

:c
q2
m1
+2
mi1
. (5)
It remains to show that the high degree terms in the right-hand side have degree
q2
m
+2
k
with k 6(mi). In the Type B case this is immediate since deg(h(c)) 62
m1
and so no new terms of high degree have appeared. In the Type A case observe
that h(c) = h
0
c
q2
m1
+ h
1
c
q2
m1
2
m2
+ and so h(c)c
q2
m1
+2
mi1
= h
0
c
q2
m
+2
mi1
+
h
1
c
q2
m
+2
mi1
2
m2
+ and since i 1 the second term above has degree 6q2
m
+1.
Hence, our new equation does satisfy the inductive hypothesis.
Eventually, we obtain an equation for the function eld F of the form t
2
m
+h(c)t
m
=
[(c) where deg([(c)) 6q2
m
+1. Of course, it is possible that the equation be singular
or that deg([(c)) q2
m
+ 1 in which case the genus is smaller than our bound. But
in the case when the equation is non-singular and deg([(c)) = q2
m
+ 1 then one can
show that the hyperelliptic curve has genus q2
m1
and that there is only one point at
innity.
4.5. Finding the curve C over k
The function eld F is dened over K. We can take the xed eld F

of F with
respect to the Galois action as in [9] to obtain a function eld corresponding to a curve
C

over k. In general, we have K(C

)

= F =K(C) and thus have obtained an equation
for C which is dened over k. Note that there is the possibility that K(C

) is a proper
subeld of F which could mean that the Weil descent strategy has failed. This special
situation is excluded in [9] by the condition () (see [9, Section 1]).
172 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
The curve C can be constructed explicitly using the method of [9, Lemma 13] which
is as follows: Let j K be such that Tr
K}k
(j) = 1 and dene
X = Tr
K}k
(jz
0
c) and Y

= Tr
K}k
(jw
0
).
Then X = z
0
c + z

for some z

K and Y

= w
0
+ r(c) for some polynomial r over
K. It follows that k(X) is a subeld of L which is xed by the Galois action and that
K(X)=L. It also follows that k(X, Y

) is a subeld of F, [k(X, Y

) : k(X)] =n and that

K(X, Y

) = F which shows that the functions X and Y

are the functions we require.

An equation relating X and Y

may be easily obtained from the earlier equations. To

get an equation of small degree it will be necessary to perform a change of variable
in Y

analogous to those used in the proof of Proposition 2. This process is illustrated

in the examples given below.
Finally, one must consider the norm maps which enable the pulling-back of the
discrete logarithm problem. This stage proceeds exactly as in [9].
In cases where the curve C has more than one point at innity, the base point for
the divisor representation on C can be chosen arbitrarily. This is because we are only
concerned with divisor classes.
4.6. Example one
We consider the curve C : ,
2
+ x, = x
5
+ x
4
+ 0
2
x
2
+ 0x + 1 over K = F
2
2 = F
2
[0]
where 0
2
+ 0 + 1 = 0. This curve has characteristic polynomial of Frobenius equal to
P(1) = 1
4
+ 1
3
+ 41 + 16 and #Jac(C)(F
2
122 ) = 2 11 28549 L where L is a 225 bit
prime.
We perform the Weil descent of Jac(C) with respect to the extension F
2
2 }F
2
(note
that the curve is not a subeld curve with respect to this extension). We can worry
about the divisors over F
2
122 in the nal stage, but the job of nding C can be performed
completely over F
2
2 . We rst obtain the pair of equations (where s
i
= (w
i
+ 1)x
1
)
s
2
0
+ s
0
= x
3
+ x
2
+ 0
2
+ 0
2
x
1
, (6)
s
2
1
+ s
1
= x
3
+ x
2
+ 0 + 0x
1
(7)
and we see that m = 2. Setting t = s
0
+ s
1
and subtracting we get
t
2
+ t = 1 + x
1
(8)
and so the curve is of Type A. This immediately gives the rational function eld
L = K(t) with x = (t
2
+ t + 1)
1
.
As an aside we note that it is crucial that Eq. (8) only contains a term x
1
. For
instance, if Eq. (8) was t
2
+t =1 +x
1
+x
2
then we could eliminate all the x terms
and we would nd that we have m = 1 and that the function eld F is isomorphic to
the function eld of the original curve C. Of course, t
2
+ t = 1 + x
2
would be ne
as modifying the equation by x
1
+x
2
gives an acceptable form. On the other hand,
if Eq. (8) was t
2
+ t = x + 1 + x
1
then it would no longer be true that x lies in the
rational eld generated by t.
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 173
Continuing with the example, we obtain an equation for F over K by combining
these equations, i.e.,
s
2
0
+ s
0
= (t
2
+ t + 1)
3
+ (t
2
+ t + 1)
2
+ 0
2
+ 0
2
(t
2
+ t + 1).
To obtain a model for C over F
2
we follow the method of Section 4.5 with c=t, z
0
=1
and j =0. We nd that Tr
F
4
}F
2
(jz
0
c) =0t +0
2
t =t. To compute Y

=Tr
F
4
}F
2
(jw
0
) we
note that w
i
= xs
i
+ 1 and so Y

= x(0s
0
+ 0
2
s
1
) + (0 + 0
2
) = x(0
2
t + s
0
) + 1.
We nd the equation
(Y

)
2
+ xY

= x
5
+ x
4
+ x
2
(0t
2
+ 0
2
t + 0
2
) + 0x + 1.
To get this in terms of a polynomial in t we multiply by x
6
and nd (x
3
Y

)
2
+
x
2
(x
3
Y

) = t
12
+ t
10
+ t
9
+ t
8
+ t
6
+ t
5
+ t
2
. The degree of the right-hand side now
appears to be too large. We therefore perform the change of variable Y = x
3
Y

+ t
6
to obtain
Y
2
+ (t
4
+ t
2
+ 1)Y = t
9
+ t
5
+ t
2
which is a genus 4 curve over F
2
.
We can now pull divisors on Jac(C)(F
2
122 ) back to divisors on Jac(C)(F
2
61 ) using
the conorm and norm maps.
The solution of the discrete logarithm problem in Jac(C) can be found using a
version of Gaudrys algorithm [8]. It was shown in [9] that for curves of genus 4 this
algorithm does run slightly faster than the Pollard method on an elliptic curve and
so we are sure that we have transformed the discrete logarithm problem from Jac(C)
to an easier problem (though still exponential time). In this case (as with the other
examples in this paper), the use of the Frobenius endomorphism gives a very important
improvement to the running time of Gaudrys algorithm (see [3,8]).
4.7. Example two
We now consider a Type B example. Consider the genus 3 curve over F
2
2
C : ,
2
+ x, = x
7
+ x
5
+ 0x
3
+ 1,
which has characteristic polynomial of Frobenius equal to 1
6
1
5
41
3
161 + 64.
We nd that #Jac(C)(F
2
58 ) = 2
2
11 L where L is a 169 bit prime. We can perform
Weil descent of Jac(C) with respect to the extension F
2
2 }F
2
as outlined above.
We rst obtain the equations
w
2
0
+ xw
0
= x
7
+ x
5
+ 0x
3
+ 1,
w
2
1
+ xw
1
= x
7
+ x
5
+ 0
2
x
3
+ 1.
We then perform the usual changes of variable to get s
2
0
+s
0
=x
5
+x
3
+0x +x
1
and
t
2
+ t = x which shows that we have a Type B curve. We have m = n = 2 for this
example.
The function eld F =F
2
2 (x, w
0
, w
1
) =F
2
2 (s
0
, t) is thus a hyperelliptic function eld
over the rational function eld L = F
2
2 (t).
174 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
To obtain a model over F
2
we write Y

= x(s
0
+ 0
2
t) + 1. From this we obtain the
equation
(Y

)
2
+ xY

= x
7
+ x
5
+ 0x
3
+ (0t
2
+ 0
2
t)x
2
+ 1.
Expanding out the terms and setting Y = Y

+ t
7
gives
C: Y
2
+ (t
2
+ t)Y = t
13
+ t
11
+ t
9
+ t
8
+ t
6
+ t
3
+ 1
which is a genus 6 curve over F
2
and one can check that #Jac(C)(F
2
29 ) =2
2
11 L as
expected.
Once again, one can pull a discrete logarithm problem from Jac(C)(F
2
58 ) to Jac(C)
(F
2
29 ) using conorms and norms and then solve the discrete logarithm problem in the
genus 6 Jacobian.
4.8. Example three
Let F
2
3 = F
2
(0) where 0
3
+ 0 + 1 = 0. Consider the curve
C : ,
2
+ x, = x
7
+ x
4
+ 0x
3
+ 1
of genus 3. The characteristic polynomial of Frobenius for this curve is P(1) = 1
6

1
5
+ 41
4
+ 321
2
641 + 512. Thus, #Jac(C)(F
2
323 ) = 2
2
11
2
796813 L where L is
a 179 bit prime.
Performing the method as described gives s
2
0
+s
0
=x
5
+x
2
+0x +x
1
and similarly
for s
1
and s
2
. We get t
2
1
+ t
1
= 0
4
x and t
2
2
+ t
2
= 0
2
x and m = 3.
Put c=t
2
+0
6
t
1
. Then c
2
+c=0t
1
from which we obtain t
1
=0
6
c
2
+0
6
c, t
2
=0
5
c
2
+0
4
c
and x = 0c
4
+ 0
4
c
2
+ 0
2
c. It follows that K(c) = K(x, t
1
, t
2
).
To get functions over F
2
we nd X = 0
2
c and Y

= x(s
0
+ t
1
+ t
2
) + 1. We obtain
(Y

)
2
+ xY

= X
28
+ X
26
+ X
25
+ + 1. Putting Y = Y

+ X
14
+ X
13
gives
C: Y
2
+ (X
4
+ X
2
+ X)Y = X
25
+ X
24
+ X
21
+ X
19
+ X
11
+X
9
+ X
7
+ X
4
+ 1
which is a non-singular hyperelliptic curve of genus 12 as expected.
One can compute the characteristic polynomial of Frobenius for this curve and see
that it is P(1
3
)(1
6
1
5
41 + 8).
Once again we can transfer discrete logarithms from the Jacobian of the genus 3
curve over F
2
69 to the Jacobian of the genus 12 curve over F
2
23 . Since the Pollard
methods on the original curve will take time O(q
9}2
) (where q = 2
23
) we expect the
solution of the discrete logarithm problem on genus 12 curve to be rather easy compared
with the original problem.
5. More general algebraic approach
The above strategy, which is generalised from the method of [9], seems to be very
eective. However, there are many curves for which the method does not seem to
apply: we may have diculties when deg(h(x)) 1, the magic number m may be too
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 175
small or the t
i
equations may not reduce to a simple enough form to have a Type A
or B curve (and thus to be able to deduce hyperellipticity).
On the other hand, we stress that the philosophy of the method does not depend on
these details and, in principle, any discrete logarithm problem on any curve over any
extension of elds can be approached using these techniques. To illustrate this point
we now give some examples which are not covered by the results of Section 4.
5.1. Example four
This example concerns the case where deg(h(x)) 1. Let F
2
2 =F
2
(0) and consider
the curve C : ,
2
+ x(x + 1), = x
5
+ 0x
2
+ 1 which has P(1) = 1
4
1
2
+ 16.
Performing Weil descent in the usual manner results in the two equations
,
2
0
+ x(x + 1),
0
= x
5
+ 0x
2
+ 1,
,
2
1
+ x(x + 1),
1
= x
5
+ 0
2
x
2
+ 1.
Dene t

=,
0
+,
1
to get (t

)
2
+x(x +1)t

=x
2
. Thus, t =x
1
t

satises t
2
+(x +1)t =1
and so we have x = (t
2
+ t + 1)}t and the function eld F
2
2 (x, ,
0
, ,
1
) = F
2
2 (t, ,
0
).
To get an equation over F
2
we dene Y

= Tr
F
4
}F
2
(0,
0
) = ,
0
+ 0
2
xt. We therefore
obtain the equation (Y

)
2
+(t
2
+1)(t
2
+t +1)}t
2
Y

=(t +1)
3
(t
7
+t
7
+t
5
+t
4
+1)}t
5
.
Setting Y = t
3
Y

}(t + 1) yields
C: Y
2
+ (t
4
+ t)Y = t
9
+ t
5
+ t
2
+ t
which is a genus 4 curve having characteristic polynomial of Frobenius equal to P(1
2
).
This example shows that there are cases when deg(h(x)) 1 which still yield a nice
hyperelliptic curve.
5.2. Example ve
In this case, we consider what happens when deg(h(x)) 1 and when h(x) is dened
over K rather than k. Consider the genus two curve over F
2
2 given by
C : ,
2
+ (x
2
+ 0), = x
5
+ 0x.
The usual Weil descent construction gives two equations
w
2
0
+ (x
2
+ 0)w
0
= x
5
+ 0x,
w
2
1
+ (x
2
+ 0
2
)w
1
= x
5
+ 0
2
x.
Writing t = w
0
+ w
1
gives
t
2
+ (x
2
+ 0)t + w
1
= x.
Therefore, we can write w
1
= t
2
+ (x
2
+ 0) + x and insert into the second equation to
obtain
C: t
4
+ (x
4
+ x
2
)t
2
+ (x
4
+ x
2
+ 1)t + x
5
+ x
3
+ x
2
= 0
which is a genus 7 curve over F
2
with singular points only at innity.
176 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
We see that this curve does not satisfy the theoretical results of the previous section.
Nevertheless, it is possible to transfer a discrete logarithm problem in Jac(C)(F
2
2! ) to
a discrete logarithm problem in Jac(C)(F
2
! ). It is not clear how eciently the discrete
logarithm problem can be solved on Jac(C) in practice, but in theory (using methods
like those of [8]) one can achieve a complexity which is better than the Pollard methods
on Jac(C).
Another approach for performing Weil descent would be to use a more geometric
strategy. We briey discuss this approach below.
6. The geometric approach
As we noted in the previous sections, the algebraic approach is very successful.
However, there are cases to which it does not seem to apply. One could attempt a
more geometric approach following the methods of [7]. The basic idea of this approach
is to represent Jac(C) as an ane variety, take Weil restriction of scalars explicitly to
get an ane part of A, nd a curve C on A, pull back the discrete logarithm problem
from A to Jac(C) and then solve it as before.
The representation of Jac(C) as an ane variety uses a technique going back to
Mumford which was explicitly described by Spallek [13]. To be precise we recall
the Cantor representation of a reduced divisor of degree q on C. A generic divisor
on C has degree q and is represented as a pair of polynomials (u(x), t(x)) where
u(x)=x
q
+u
q1
x
q1
+ +u
0
and t(x)=t
q1
x
q1
+ +t
0
. The points (x
0
, ,
0
) in the
support correspond to those values of x
0
which satisfy u(x
0
)=0 and where ,
0
=t(x
0
). It
follows from the equation ,
2
+h(x),=[(x) that we have u(x)|(t(x)
2
+h(x)t(x)[(x)).
This means that the divisor corresponding to (u, t) may be represented as the element
(u
0
, u
1
, . . . , u
q1
, t
0
, . . . , t
q1
) in 2q-dimensional ane space. The Jacobian is then the
set of points for which the equation (t(x)
2
+h(x)t(x)[(x)) 0 (mod u(x)) is satised.
This is of course only generic (it misses the so-called theta divisor which is a ag
variety of dimension q 1). If given target divisors do not have the full degree q then
they can be easily modied by adding a small multiple of the base point.
Once an ane equation for A is obtained it remains to nd a suitable ane curve C
on A and to pull back the discrete logarithm problem to a divisor on C. To achieve this
seems to require considerable computer algebra computations. This leads to a situation
where the security of the original discrete logarithm problem is now related to the
diculty of solving some non-linear multivariate equations. These calculations seem
to be dicult to perform in practice, but we do not know if they are as dicult as
solving discrete logarithm problems. We give an example.
6.1. Example six
Consider genus 2 curve
C : ,
2
+ x, = x
5
+ 0x
2
+ 1
over F
2
2 = F
2
[0] where 0
2
+ 0 + 1 = 0.
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 177
Note that this curve is actually isomorphic to one dened over F
2
under the map
(x, ,) (X, Y + :X) where :
2
+ : + 0 = 0 (so : F
2
4 ). Thus, the curve C can be
called a quartic twist of the genus 2 curve C

: Y
2
+ XY = X
5
+ 1 over F
2
.
We will perform a Weil descent of Jac(C) with respect to the extension F
2
2 }F
2
.
Using the algebraic approach developed above one nds oneself in a degenerate case
(in fact, the function eld F contains a proper constant eld extension and so the curve
C cannot be dened over F
2
).
Taking the geometric approach, we rst construct a model for Jac(C) in terms of
the generic polynomials x
2
+ u
1
x + u
0
and t
1
x + t
0
. The hyperelliptic involution on
C corresponds to the involution t
1
t
1
+ 1 on this model. We aim to preserve this
involution.
One obtains the equations
0 = u
0
u
3
1
+ u
0
t
2
1
+ u
0
t
1
+ 0u
0
+ t
2
0
+ 1,
0 = u
2
0
+ u
0
u
2
1
+ u
4
1
+ u
1
t
2
1
+ u
1
t
1
+ 0u
1
+ t
0
for Jac(C) as a two-dimensional variety in four-dimensional ane space.
One can then perform a Weil descent on this in the usual manner by writing u
0
=
u
0, 1
+ u
0, 2
0 etc. One obtains a four-dimensional variety in eight-dimensional ane
space.
Two of these equations have the form t
0, i
=
i
(u
0, 1
, u
0, 2
, u
1, 1
, u
1, 2
, t
1, 1
, t
1, 2
) and so
these two variables are immediately eliminated to obtain a two-dimensional variety in
six-dimensional ane space.
We want to intersect this variety with hypersurfaces. The rst choice is to set u
1, 1
=
u
1, 2
=0 since these variables appear to the highest degree. This is interpreted as setting
u
1
= 0 or, in other words, restricting the curve to lie on the divisors of the form
2(x
1
, ,
1
) 2P

(this will not be a problem since we are interested in divisors of odd

order). One obtains the equations
0 = u
4
0, 1
+ u
0, 1
t
2
1, 1
+ u
0, 1
t
1, 1
+ u
0, 1
t
2
1, 2
+ u
0, 2
t
2
1, 2
+ u
0, 2
t
1, 2
+ u
0, 2
+ 1,
0 = u
0, 1
t
2
1, 2
+ u
0, 1
t
1, 2
+ u
0, 1
+ u
4
0, 2
+ u
0, 2
t
2
1, 1
+ u
0, 2
t
1, 1
+ u
0, 2
t
1, 2
+ u
0, 2
.
We now intersect with the hypersurface u
0, 1
=0 to obtain a very simple pair of equa-
tions. Writing x for u
0, 2
, , for t
1, 1
(recall that the hyperelliptic involution is t
1, 1

t
1, 1
+ 1) and w for t
1, 2
we have
x = (w
2
+ w + 1)
1
,
,
2
+ , = x
3
+ w + 1.
From this we obtain genus 4 curve (writing Y = (w
2
+ w + 1)
2
,)
C: Y
2
+ (w
4
+ w
2
+ 1)Y = w
9
+ w
8
+ w
5
+ w
4
+ w
2
.
The hyperelliptic involution on C is inherited from that on the original curve C.
It remains to transfer instances of the discrete logarithm problem on Jac(C) to Jac(C).
This is not at all easy and so we give some discussion.
178 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
Consider a point (w, Y) of C. By substituting back into the formulae above one sees
that this point corresponds to the point
(u
0, 1
, u
0, 2
, u
1, 1
, u
1, 2
, t
0, 1
, t
0, 2
, t
1, 1
, t
1, 2
) = (0, :
1
, 0, 0, :
2
, :
2
, Y:
2
, w), (9)
where :=w
2
+w+1. As an example, the point (0, 1) C(F
2
) corresponds to the divisor
(x
2
+0, x+0
2
) on C(F
2
2 ). One can see from Eq. (9) that the process is undened when
w satises w
2
+w+1=0. This is a reection of the fact that the group homomorphism
from Jac(C)(F
2
m) Jac(C)(F
2
2m) is only dened when m is odd.
To pull back a target divisor D
1
in Jac(C) we aim to nd k reduced divisor classes
B
i
in Jac(C) coming from divisor classes (w
i
, Y
i
) () in Jac(C) such that B
1
+B
2
+
+B
k
=D
1
in Jac(C). Ideally, we would take k =q=4; however, these points will be
Galois conjugates over an extension of degree k and our mappings may not be dened
when the eld extension is not coprime to n. Therefore, we should take k = 5 in our
example, though k = 3 would span a set of divisors of density 1}q.
The easiest way to nd this seems to be to split it into halves. In the case k =3, we
must solve (B
1
+ B
2
) =(B
3
D
1
) using the fact that inverses in the additive group
can be easily understood. To do this we need some kind of addition formulae rather
than the addition algorithm for divisors. Such a mechanism was provided by Spallek
[13] in the case of genus 2 and, as we may assume that our initial points are generic,
the numerous special cases do not arise.
Given the resulting expressions in terms of the variables w
i
and Y
i
we hope to
be able to nd a solution dened over the ground eld. Experiments using Magma
indicate that solving these sorts of equations using Groebner basis techniques requires
signicant computing resources. We have not been able to pull back a target divisor
for this example.
7. Characteristic greater than two
One can also consider Jacobians of curves over elds of characteristic 2. Even
for elliptic curves the techniques are not very well developed in the odd characteristic
case, though see Diem [2]. In general, we cannot apply the theory of ArtinSchreier
extensions. Nevertheless, in some cases the Weil descent strategy can be performed.
7.1. Example seven
Let 0 be a generator of F

19
2
which satises 0
2
0 + 2 = 0 (we use Magma for
computations and so will represent eld elements in terms of powers of the generator)
and consider the genus 2 curve C : ,
2
= x
5
+ x + 0.
Performing Weil descent as usual gives the two equations
w
2
0
= x
5
+ x + 0,
w
2
1
= x
5
+ x + 0
19
.
Subtracting these two equations gives the conic w
2
1
= w
2
0
+ 0
150
whose solutions are
parameterised as w
1
=0
75
(s
2
+1)}(s
2
1) and w
0
=20
75
s}(s
2
1). It therefore follows
S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180 179
that the function eld F = F
19
2 (x, s) contains the function eld F
19
2 (x, w
0
, w
1
). Indeed,
s = (w
0
+ w
1
+ 0
75
)}(w
0
+ w
1
0
75
) and so F = F
19
2 (x, s)

= F
19
2 (x, w
0
, w
1
).
One can compute the equation
C: x
5
(s
4
2s
2
+ 1) + x(s
4
2s
2
+ 1) + 0
181
s
4
+ 0
24
s
2
+ 0
181
= 0 (10)
for the curve corresponding to the eld F.
It remains to construct a model for C over F
19
. This is done by rst calculating
the action of Gal(F
19
2 }F
19
) = o on s by using the fact that o : w
0
w
1
. One gets
o(s) =

1(s

1)
2
}(s
2
+1) =

1(s

1)}(s

1) (the choice of sign in the

depends on the selection of

1; a coherent choice is o(s)=(0
270
s +1)}(s +0
270
))
and one can verify that o
2
(s) = s.
It is necessary to nd a function Y which is Galois invariant and is such that
F
19
2 (x, Y)

= F
19
2 (x, s). This can be done by writing Y =(s +b)}(cs +d) with unknowns
b, c, dF
19
2 and solving for Y
o
= Y. One solution is
Y =
s + 0
333
0
233
s + 3
.
It is then clear that F
19
2 (x, Y)

= F
19
2 (x, s). Substituting into Eq. (10) yields the curve
(x
5
+ x + 9)(Y
4
+ 4Y
2
+ 4) + Y
3
2Y = 0
over F
19
. Magma calculates that this curve has genus 8. The ideal genus for a curve
arising from a degree two Weil descent of a genus 2 curve would be 4. It is not clear
if it is easier to solve the discrete logarithm problem on this genus 8 curve than on
the original genus 2 curve.
8. Conclusions
We have shown that the Weil descent strategy does extend to the higher dimensional
situation. For a large class of curves over certain nite elds we obtain a reduction
of the discrete logarithm problem to a computationally easier problem. Nevertheless,
there are many cases of curves and elds for which these techniques do not seem to
apply.
Acknowledgements
I thank Florian Hess and Claus Diem for discussions on this topic, and the anony-
mous referees for helpful comments.
References
[1] L. Adleman, J. De Marrais, M.-D. Huang, A subexponential algorithm for discrete logarithms over
the rational subgroup of the Jacobians of large genus hyperelliptic curves over nite elds, in: L.M.
Adleman, M-D. Huang (Eds.), ANTS-I, Vol. 877, Springer, Berlin, 1994, pp. 2840.
180 S.D. Galbraith / Discrete Applied Mathematics 128 (2003) 165180
[2] C. Diem, The GHS attack in odd characteristic, preprint 2001, available from
http://www.exp-math.uni-essen.de/diem/.
[3] I. Duursma, P. Gaudry, F. Morain, Speeding up the discrete log computation on curves with
automorphisms, in: Lam et al. (Eds.), ASIACRYPT 99, Lecture Notes in Computer Science, Vol. 1716,
Springer, Berlin, 1999, pp. 103121.
[4] R. Flassenberg, S. Paulus, Sieving in function elds, Exp. Math. 8 (4) (1997) 339349.
[5] G. Frey, How to disguise an elliptic curve, Talk at ECC 98, Waterloo, 1998,
http://cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.html.
[6] S.D. Galbraith, Limitations of constructive Weil descent, in: K. Alster, et al. (Eds.), Public-Key
Cryptography and Computational Number Theory, Walter de Gruyter, Berlin, 2001, pp. 5970.
[7] S.D. Galbraith, N.P. Smart, A cryptographic application of Weil descent, in: M. Walker (Ed.), Codes
and Cryptography Cirencester, Lecture Notes in Computer Science, Vol. 1746, Springer, Berlin, 1999,
pp. 191200.
[8] P. Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, in: B. Preneel
(Ed.), EUROCRYPT 2000, Lecture Notes in Computer Science, Vol. 1807, 2000, pp. 1934.
[9] P. Gaudry, F. Hess, N.P. Smart, Constructive and destructive facets of Weil descent on elliptic curves,
J. Cryptology 15 (1) (2002) 1946.
[10] C. G unther, T. Lange, A. Stein, Speeding up the arithmetic on Koblitz curves of genus two, in: D.
Stinson, et al., (Eds.), SAC 2001, Lecture Notes in Computer Science, Vol. 2012, Springer, Berlin,
2001, pp. 106117.
[11] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (3) (1989) 139150.
[12] N.P. Smart, How secure are elliptic curves over composite extension elds? in: B. Ptzmann (Ed.),
EUROCRYPT 2001, Lecture Notes in Computer Science, Vol. 2045, Springer, Berlin, 2001, pp. 3039.
[13] A.-M. Spallek, Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen, Ph.D.
Thesis, IEM Essen, 1994.
[14] H. Stichtenoth, Algebraic Function Fields and Codes, Springer Universitext, Berlin, 1993.