Weil Descent Page

This page is devoted to the new technique of Weil descent as described in the papers: 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 e-commerce 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^{m-1} or 2^{m-1}-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.tu-berlin.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 (p2-p3) = m*(p1-p3) 
#  then (D1-D3) = m*(D2-D3).  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