Weil Descent Page
This page is devoted to the new technique of Weil descent
as described in the papers:
 A cryptographic application of Weil descent,
by S.D. Galbraith and N.P. Smart.
Proceedings Cryptography and Coding, Springer LNCS 1746, pp 191200. (1999)

Constructive and Destructive Facets of Weil Descent on Elliptic Curves
,
by P. Gaudry, F. Hess and N.P. Smart.

Two topics in hyperelliptic cryptography
by F. Hess, G. Seroussi and N.P. Smart.

Analysis of the Weil Descent Attack of Gaudry, Hess and Smart
by A. Menezes and M. Qu.

How secure are elliptic curves over composite extension fields?
by N.P. Smart.

Solving Elliptic Curve Discrete Logarithm Problems Using Weil Descent
by M. Jacobson, A. Menezes and A. Stein

Limitations of constructive Weil descent by S.D. Galbraith.

Weil descent of Jacobians by S.D. Galbraith.

Extending the GHS Weil Descent Attack
by S.D. Galbraith, F. Hess and N.P. Smart.
 Analysis of the GHS Weil descent attack on the ECDLP
over characteristic two finite fields of composite degree
by M. Maurer, A. Menezes and E. Teske.
Weil descent is a technique in the area of elliptic curve cryptography.
Elliptic curve cryptography is a public key technique which allows
for the use of cryptography in applications which are constrained by
bandwidth, CPU time or memory.
This not only includes small devices but also large overworked servers
trying to deal with heavy traffic loads generated by ecommerce applications.
The main paper by Gaudry, Hess and Smart (GHS) can be summarized
by the following:
Let E denote an elliptic curve over a field, K, of q^n elements where
q is a power of two.
Then there exists a hyperelliptic curve, H, of genus
2^{m1} or 2^{m1}1
defined over the field, k, of q elements such that there is a computable
group homomorphism
E(K) > Jac_H(k)
The number m is a "magic number" which controls how hard or easy it is
to use this approach. See the above paper for a more detailed description.
This is ofcourse all a bit mathematical and hence we explain this in more
down to earth terms below.
There are essentially two ways to interpret this result, one
constructively and one destructively.
Destructive Implications
One can map the discrete logarithm problem from the elliptic curve
over to the hyperelliptic curve.
Hence if the genus is about the size of n and this is not too large
then this can give reduced security.
Solution
One should always use either a field with a prime number of elements
or use a field of the form 2^p, where p is a prime.
In other words you should deploy systems which are standards
compliant. Following the standards layed down by
SECG is probably the best approach.
After all these standards have been developed by the worlds leading
experts in the area of the elliptic curve cryptography.
Koblitz Curves
It should be noted that over any field Koblitz curves are resistent to
the above attack (since for Koblitz curves the number m will always
be equal to one) as it is described in the GHS work.
Recent work of Frey and his students has extended the GHS work to
Koblitz curves.
Hence, Koblitz curves also only be used over fields of the form
2^p, where p is a prime.
Constructive Implications
The work also allows us to construct hyperelliptic curves of
small genus with known group order.
Hence one can now deploy hyperelliptic cryptosystems.
For example consider the field of 2^131 elements defined by the
polynomial
t^131 + t^8 + t^3+t^2 + 1=0.
Over this field we define the hyperelliptic curve of genus two
Y^2 + H(X) Y = F(X)
where
H(X) = 
531DF454AD40EFDC0D6CAE356D574810F X^2 

+ 3561FA9336C3CA3F080AB1FEE1F789636 X 

+ 2D82C28316120279E55BF01B0AD476DC5, 
and
F(X) = 
138BE9EF56BA5C72A8CE09AA4C3590B9 X^5
+ DB308DD57C16D90670C4A311DB298F43 X^4


+ 4FEB32114979B67F1CF2D5B73B57ABCAE X^3
+ 63A3FD1EB41F004DD75D7E1E485C07AA4 X^2


+ 5593CEF38C79C53D1B7A7B81AAF39E4D0 X
+ 57D20BB08FC9578EB750D98A07C6D94AB.

This curve has group order
7410693711188236507108543040556026102606669553107633893031957930119262165819774
which is two times a prime.
Weil Descent Program
A KASH
program is now available which given an elliptic curve
with various points on it will not only produce the associated
hyperelliptic curve but will also map the point over to the
Jacobian of the hyperelliptic curve.
The code is here.
There is a special version of KASH to use with this program:
ftp://ftp.math.tuberlin.de/pub/algebra/Kant/Kash/kash22.wd.sol2.tgz.
This new version of KASH means that one can map places of the various
function fields around much faster.
Alas this only works on Solaris machines at the moment.
Other users will need to use the standard slower version of KASH.
To switch this option on change the sixth line of weilres.g
from
KashVersionIsWD := false;
to
KashVersionIsWD := true;
To see how to use this function see the following
excerpt from the code:
AlffWeilRestriction := function(arg)
#
# Given an elliptic function field E: y^2 + xy + x^3 + ax^2 + b
# n and and optionally some places of degree one, return the
# hyperelliptic curve in the Weil restriction and the image of
# the given places.
#
# Calling is AlffWeilRestriction(E, n [, p1, p2, p3, ... , reduce] ).
#
# Returns F or [ F, D1, D2, D3, ... ] such that e.g. if (p2p3) = m*(p1p3)
# then (D1D3) = m*(D2D3). The pi may not be over x=0 or x=infty, which
# makes a translation of the origin necessary.
#
# reduce is true or false. If it is false no reduction is done at the
# end and results (especially point mapping) are obtained faster but also
# "uglier".
#
# Program contains some special assumptions making the trafos easier,
# they may fail. Should be no problem in general.
#
Note the code is completely unsupported and may not work on some
installations of KASH.
Hopefully one day we will convert it to work with Magma.
Other Resources
A number of other people are working on this topic:
Nigel Smart