Weil Descent is a technique that can be applied to cryptosystem attacks amongst other things. The general idea is as follows. If C is a curve defined over field L and K is a subfield of L, the group of points of the Jacobian of C, Jac(C), over L is isomorphic to the group of points of a higher-dimensional abelian variety, the Weil restriction of Jac(C), over K. If a curve D over K can be found along with an algebraic homomorphism defined over K from Jac(D) to this Weil restriction, it is usually possible to transfer problems about Jac(C)(L) (like discrete log problems) to Jac(D)(K). D will have larger genus than C, but we have descended to a smaller field. The advantage is that techniques like Index calculus, where the time complexity depends more strongly on the field size than the genus, can now be applied.
An important special case is where C is an ordinary elliptic curve over a finite field of characteristic 2. In this case, Artin-Schreier theory gives a very concrete algorithm for computing a suitable D. This is the GHS attack (see [Gau00] or the chapter by F. Heß in [Bla05]). There is a corresponding function WeilDescent in the Elliptic Curve chapter that works with curves rather than function fields.
The functions below implement the GHS Weil Descent in a more general characteristic p setting.
The main function. E must be an "Artin-Schreier" function field over finite field K, an extension of k, of the following form. If p is the characteristic of K, then the base field of E is a rational function field K(x) and E.1, the generator of E over K(x) has minimal polynomial of the form yp - y = c/x + a + b * x for a, b, c ∈K. These parameters must satisfy b, c != 0 and at least one of the following conditionsThen, if E1 is the Galois closure of the separable field extension E/k and [K:k]=n, there is an extension of the Frobenius generator of G(K/k) to an automorphism of E1 which fixes x and is also of order n. If F is the fixed field of this extension, then it has exact constant field k and so it is the function field of a (geometrically irreducible) curve over k. This is the WeilDescent curve. It's algebraic function field F is the first return value.
- i) TraceK/k(b) != 0
- ii) TraceK/k(c) != 0
- iii) TraceK/Fp(a) = 0
Note that when p=2, E is the function field of an ordinary elliptic curve in characteristic 2 (multiply the defining equation by x2 and take xy as the new y variable) and conversely, any such elliptic curve can be put into this form in multiple ways.
The second return value is a map from the divisors of E to the divisors of F which represents the homomorphism Jac(Curve(E))(K) -> Jac(Curve(F))(k). This map, however does not attempt any divisor reduction. For the characteristic 2 WeilDescent function on elliptic curves mentioned in the introduction, if F is hyperelliptic, the divisor map returned is the actual homomorphism from the elliptic curve (with function field E) to the Jacobian of the hyperelliptic curve with function field F. This may be more convenient for the user.
There are functions below that may be called to return the genus and other attributes of F before actually going through with its construction.
One important special case, worth noting here, is that when p = 2 and b or c is in k, then the degree of F is also 2 and so the descent curve is a hyperelliptic curve.
A convenience function to generate the function field which is an extension of K(x) by the (irreducible) polynomial yp - y - c/x - a - bx where K is a finite field which is the parent of a, b, c and p is the characteristic of K.
With E and k as in the main WeilDescent function, returns the degree of the descended function field F over its rational base field k(x). The computation only involves the Frobenius action on a, b, c and the descent isn't actually performed.
With E and k as in the main WeilDescent function, returns the genus of the descended function field F over its rational base field k(x). The computation only involves the Frobenius action on a, b, c and the descent isn't actually performed.
This is a simple convenience function, useful for generating elements of K on which the Frobenius has a given minimal polynomial when considered as an Fp-linear map (see the example below).The argument b should be an element of a ring R, f a polynomial over ring R0, which is naturally a subring of R and F a map from R to itself.
If f = a0 + a1x + ... then the function returns f(F)(b) which is a0 + a1F(b) + a2F(F(b)) + ... .
> SetSeed(1);
> k<u> := GF(2^5);
> K<w> := GF(2^155);
> Embed(k, K);
> k2<t> := PolynomialRing(GF(2));
> h := (t^31-1) div (t^5 + t^2 + 1);
> frob := map< K -> K | x :-> x^#k >;
> b := MultiplyFrobenius(K.1,h,frob);
> E := ArtinSchreierExtension(K!1, K!0, b);
> WeilDescentGenus(E, k);
31
> WeilDescentDegree(E,k);
2
> C,div_map := WeilDescent(E, k);
> C;
Algebraic function field defined over Univariate rational function field over
GF(2^5) by
y^2 + u*y + u^18/($.1^32 + u^29*$.1^16 + u^14*$.1^8 + u^2*$.1^4 + $.1^2 +
u^9*$.1 + u^5)
> // get the image of the place representing a K-rational point
> pl := Zeroes(E!(BaseField(E).1)-w)[1];
> D := div_map(pl);
> Degree(D); //31*32
992
> k := GF(3);
> K<w> := GF(3,4);
> a := w+1;
> c := w;
> b := c^3+c;
> E := ArtinSchreierExtension(c, a, b);
> WeilDescentDegree(E,k);
27
> WeilDescentGenus(E,k);
78
> C := WeilDescent(E, k);
> C;
Algebraic function field defined over Univariate rational function field over
GF(3) by
y^27 + 2*y^9 + y^3 + 2*y + (2*$.1^18 + 2*$.1^12 + 2*$.1^9 + 2)/($.1^9 + $.1^3 +
1)