|
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.
WeilDescent(E,k) : FldFun, FldFin -> FldFunG, Map
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 conditions
- i) TraceK/k(b) != 0
- ii) TraceK/k(c) != 0
- iii) TraceK/Fp(a) = 0
Then, 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.
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)) + ... .
We demonstrate with an example of descent over a degree 31 extension
in characteristic 2, which results in a genus 31 hyperelliptic function
field, and a small characteristic 3 example.
> 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)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|