The GHS Attack in odd Characteristic

Claus Diem

March 24, 2003

Abstract

The GHS attack is originally an approach to attack the discretelogarithm problem (DLP) in the group of rational points of an elliptic curve over a non-prime finite field of characteristic 2. It is a method to transform the original DLP into DLPs in class groups of specific curves of higher genera over smaller fields.

In this article we give a generalization of the attack to degree 0 class groups of (hyper-)elliptic curves over non-prime fields of arbitrary characteristic. We solve the problem under which conditions the kernel of the “transformation homomorphism” (GHS-conorm-norm homomorphism) is small. We then analyze the resulting curves for the case that the characteristic is odd.

2000 Mathematics Subject Classification Primary 94A60, 11T71. Secondary 11Y99, 14H30.

1 Introduction

The discrete-logarithm problem (DLP) in the group of rational points of an elliptic curve over a finite field and more generally in the degree 0 divisor class group of a (hyper-)elliptic curve over a finite field is a well-studied cryptographic primitive for public-key cryptosystems. The security of this primitive relies on the difficulty of solving the DLP.

In [8], a new approach to attack the DLP in the group of rational points of elliptic curves over non-prime finite fields of characteristic 2 was introduced. Following [16], we call this approach the GHS attack.

The GHS attack is a method to transform the DLP in the group of rational points of an elliptic curve over a non-prime field into DLPs in class groups of specific curves of higher genera over smaller fields. The hope is that if the genus of a resulting curve is not “too large” and one finds “nice” explicit equations, it might be possible to solve the DLP via index calculus methods.

The curves of higher genera over smaller fields were originally discovered as smooth, projective curves which are birational to components of intersections of Weil restrictions of an affine part of the elliptic curve with certain hyperplanes. Then function field theory was applied to study the resulting curves; see [8, 3.2-3.4], expecially [8, Theorem 12]. In this article, our starting point is a generalization of the function field theoretic approach developed in [8]. (The role of Weil restrictions in the GHS attack is discussed in an appendix. There one also finds a discussion how the GHS attack fits into Frey’s “Weil descent” idea.)

Notations and terminology

The terminology follows [13] and [21]. By a function field, we mean a finitely generated field extension F |k of transcendence degree 1. If k is a perfect field (e.g. a finite field), the function field F |k is called regular if k is algebraically closed in F; cf. [13, VIII, 4].

We make the following convention: If K|k is a finite extension of fields, we denote function fields/curves over K with a prime and those over k without a prime. This philosophy is not consistent with the notations in [8]. For example, the meaning of F and F′ is interchanged.

Outline of the GHS attack for (hyper-)elliptic curves in arbitrary characteristic

We give a brief description of a generalization of the original GHS attack from elliptic curves to (hyper-)elliptic curves and from characteristic 2 to arbitrary characteristic in the function field-theoretic setting. We will refer to this generalization also as GHS attack.

Let p be a prime, q a power of p, n > 1 an odd natural number.^{1} Let H′ be a (hyper-)elliptic curve over 𝔽_{q^{n}}. Let an explicit (hyper-)elliptic equation of an affine part of H′ be fixed. The fixed equation of H′ induces an explicit description of Cl^{0}(H′), the degree 0 divisor class group of H′ (see for example [17]), and with respect to this description, we consider the DLP in Cl^{0}(H′).

Assume that – with the possible exception of vulnerability to the GHS attack which we will study – H′ would be regarded as “cryptographically suitable”. For the present article it is most important that #Cl^{0}(H′) should be prime up to a small cofactor, and the large prime factor of #Cl^{0}(H′) should be ≥ 2^{160}. In order to guarantee that the known index calculus attacks are not more efficient than generic attacks, the genus of H′ should be at most 3; cf. [2], [7]. ^{2}

1In [8], it is shown that in characteristic 2 the GHS attack can also be applied to certain elliptic curves if n is even. In this article, we concentrate on the case that n is odd. The case that p is odd and n = 2 is discussed in [22].

Let 𝔽_{q^{n}}(H′) be the function field of H′. Then Cl^{0}(𝔽_{q^{n}}(H′)) = Cl^{0}(H′). Let the extension F′|K(H′) be defined as in (2), and let us assume for simplicity that F′|K is regular; see also Lemma 1. Then there exists a regular function field F |𝔽_{q} such that 𝔽_{q^{n}}F = F′; see Proposition 3.

Consider the following homomorphism of groups.

N_{F′|F} ∘ Con_{F′|𝔽_{q^{n}}(H′)} : Cl^{0}(𝔽_{q^{n}}(H′)) ⟶ Cl^{0}(F)  (1)

Here, Con_{F′|𝔽_{q^{n}}(H′)} is the conorm homomorphism, and N_{F′|F} is the norm homomorphism. We call homomorphism (1) the GHS-conorm-norm homomorphism.

Via this homomorphism, one wishes to transform the DLP in Cl^{0}(𝔽_{q^{n}}(H′)) into the DLP in Cl^{0}(F). In order that this is possible, it is necessary that the large subgroup of prime order is preserved, i.e. that the kernel of (1) and the large subgroup of prime order have trivial intersection. We will give a condition which is both necessary as well as sufficient in order that this is the case; see Proposition 5 and Theorem 1.

The goal of the attack is now to find a “nice” explicit (for example hyperelliptic) equation of F, represent Cl^{0}(F) with the help of this equation and then try to break instances of the DLP in Cl^{0}(K(H′)) by transforming them with (1) into instances of the DLP in Cl^{0}(F) and then solving them with index calculus methods; cf. [2], [7].

Besides finding “nice” equations for F, it is of greatest importance that #Cl^{0}(F) ≈ q^{g(F)} is not too large (g(F) = genus of F). For example, if q^{g(F)} ≥ 2^{1024}, by the current state of the art of index calculus, it is impossible to solve the resulting DLP in Cl^{0}(F).

The attack was previously analyzed in detail for elliptic curves and p = 2; see [8], [16], [12], [14]. Similar results to the ones in [8] can be found in [5] for certain hyperelliptic curves – again for p = 2.

In this article, we prove in particular (see Section 6):

Let p be odd. Then:

• If n is prime, n ≥ 11, and H′ = E′ is an elliptic curve such that q^{n} ≥ 2^{160}, then #Cl^{0}(F) ≈ q^{g(F)} ≥ 2^{5000}.

• For n = 5, 7 there exist examples of elliptic curves E′ for which the genus of F is 5 respectively 7. These examples are optimal in the sense that the genus of F is smallest possible under the condition that the large subgroup prime order of E′(K) ≃ Cl^{0}(E′) is preserved under (1).

2Furthermore, #Cl^{0}(H′) should not equal p (cf. [19], [20]), and the (multiplicative)

order of p modulo the large prime factor of #Cl^{0}(H′) should be so large that the attacks via the Weil- and the Tate-pairing (cf. [15], [4]) are infeasible.

In the first case, the size of Cl^{0}(F) is so large that the attack fails unless a substantial improvement on the solution of the DLP in class groups of high-genus curves / function fields is made or some very special properties of the function field F can be exploited. In the second case, the attack might be successful.

The rest of the article is organized as follows: In the next section, we prove the existence of the function field F, in Section 3, we prove under which conditions the kernel of the GHS-conorm-norm homomorphism is small. We then turn to the case that the characteristic is odd. After having given some background information on Kummer theory of function fields, we analyze the genera of the resulting function fields, first for general odd extension degree in Section 5, and then for prime extension degree in Section 6. In Section 7, we show how for certain important examples explicit defining equations for F can be derived. In the last section, we draw conclusions, and in an appendix we discuss the relation between the GHS attack and Frey’s “Weil descent” idea.

2 The GHS attack in arbitrary characteristic

We begin by showing that the necessary constructions for the attack can be carried out independently of the characteristic provided that the extension degree n is odd.

We first fix some notation that we will use throughout the article.

Let K|k be a non-trivial extension of finite fields of odd degree n. Let \overline{K} denote a fixed algebraic closure of K. Let H′ be a (hyper-)elliptic curve over K, i.e. a smooth geometrically irreducible curve of genus g ≥ 1 over K such that there exists a non-constant morphism of degree 2 from the curve to the projective line.

Let K(H′) be the function field of H′ and fix some embedding K(x) ↪ K(H′) such that the extension K(H′)|K(x) has degree 2 (for g ≥ 2, K(H′) contains a unique rational subfield of index 2, and the embedding K(x) ↪ K(H′) is unique up to an automorphism of K(x) ).

Fix a separable closure K(x)^{sep} of K(x) (containing K(H′) and \overline{K}(x)). In the following, we will entirely work within this closure. If K̃|K is some algebraic extension (inside \overline{K}), we denote the composite K̃K(H′) (inside K(x)^{sep}) by K̃(H′).

We denote the Frobenius automorphism of K|k by σ_{K|k}. By setting σ_{K|k}(x) := x, σ_{K|k} extends to an automorphism of K(x)|k(x), also denoted by σ_{K|k}. We extend σ_{K|k} to some automorphism σ̂_{K|k} of K(x)^{sep} and let σ_{K|k}^{i}(K(H′)) be the image of K(H′) under σ̂_{K|k} ^{i}. (As K(H′)|K(x) is Galois, this is independent of the chosen extension of σ_{K|k}.)

Let

F′ := K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{n−1}(K(H′)).  (2)

This is the Galois closure of K(H′) over k(x) (inside k(x)^{sep}); cf. [21, A.11.]. Let m, \overline{m} ∈ ℕ be defined by

[F′ : K(x)] = 2^{m} , [\overline{K}F′ : \overline{K}(x)] = 2\overline{m}.  (3)

Lemma 1 Either F′|K is regular or F′ is regular over the unique quadratic extension of K.

Proof Let K̃ be the algebraic closure of K in F′. Then Gal(K̃|K) ≃ Gal(K̃(x)|K(x)). This group is on the one hand cyclic and on the other hand a quotient of Gal(F′|K(x)). Now Gal(F′|K(x)) is isomorphic to (ℤ/2ℤ)^{m}, and thus its only cyclic quotients are the trivial group and the cyclic group of order 2. □

Under our assumption that n is odd, we have the following lemma:

Lemma 2 The Frobenius σ_{K|k} on K(x) extends to an automorphism of F′|k(x) of order n, and two such extensions are conjugate to each other in Gal(F′|k(x)).

Proof By Galois theory, we have a short exact sequence

1 ⟶ Gal(F′|K(x)) ⟶ Gal(F′|k(x)) ⟶ Gal(K(x)|k(x)) ⟶ 1,

where Gal(K(x)|k(x)) ≃ Gal(K|k). The order of Gal(F′|K(x)), 2^{m}, is prime to n, since by assumption n is odd. By two well-known group-theoretic theorems by Zassenhaus (which are rather elementary in the special case we are considering), the sequence splits and two sections are conjugate to each other; see [11, I, 18.1,18.2]. The statement of the lemma is a reformulation of this fact. □

Now let us fix an extension σ̃_{K|k} of σ_{K|k} as in the lemma, and let F := F^{′⟨σ̃_{K|k}⟩} be the fixed field under σ̃_{K|k}. Then [F′ : F] = n, F′ = KF and F ∩ K = k.

If F′|K is regular, it follows that F |k is regular. If F′|K(x) is not regular, let λ|k be the unique quadratic extension. Then by Lemma 1, F′|Kλ is regular, and F |λ is regular.

[figure: F′; F; K(H′); K(x); k(x)]

Proposition 3 Assume that F′|K is regular. Then there exists a subextension F |k(x) of F′|k(x) such that F |k is regular and KF = F′. Further, any two such extensions F |k(x) are isomorphic.

If F′|K is not regular, let λ|k be the unique quadratic extension. Then F′|λK is regular and there exists a subextension F |λ(x) of F′|λ(x) such that F′|λ is regular and λK F = KF = F′. Again, any two such extensions are isomorphic.

Proof We have to show that any extension F_{1}|k(x) or F_{1}|λ(x) as in the proposition is isomorphic to the extension F |k(x) or F |λ(x) constructed above. Assume that F′|K is regular (the other case is proved analogously). Let F_{1}|k(x) be a subextension of F′|k(x) such that F_{1}|k is regular and KF_{1} = F′. The fact that F_{1}|k is regular is equivalent to F_{1} ∩ \overline{k}(x) = k(x). In particular we have F_{1} ∩ K(x) = k(x). This means that the restriction homomorphism Gal(F′|F_{1}) ⟶ Gal(K(x)|k(x)) is an isomorphism; see [13, VI, Theorem 1.12]. Thus F′|F and F′|F_{1} are cyclic extensions of order n, and there exists a generating element in the Galois groups of F′|F_{1} which restrict to σ_{K|k} ∈ Gal(K(x)|k(x)). By Lemma 2, this generating element of Gal(F′|F_{1}) is conjugate to the above chosen extension σ̃_{K|k} of σ_{K|k}. This implies that F |k(x) and F_{1}|k(x) are isomorphic field extensions. □

Remark If n is not odd but n = m, Lemma 2 and thus Proposition 3 still hold. This follows from the fact that in this case F′ ≃ K(H′) ⊗_{K(x)} σ_{K|k}(K(x)) ⊗_{K(x)} ⋯ ⊗_{K(H′)} σ_{K|k}^{n−1}(K(H′)).

3 The kernel of the GHS-conorm-norm homomorphism

We keep the notations of the last section. For instance, K|k is an extension of finite fields of arbitrary characteristic of odd degree n. Again, we work entirely within a fixed separable closure of K(x).

We first want to state a necessary condition in order that – in cryptographically relevant situations – the kernel of (1) does not contains the large subgroup of prime order.

The idea is as follows: Assume that K(H′)|k(x) is Galois. Then by construction, F′ = K(H′), thus KF = K(H′). In cryptographically relevant situations, it follows that the large subgroup of prime order is contained in the kernel of (1).

Lemma 4 Let μ be an intermediate field of K|k. The following statements are equivalent:

1. K(H′) = σ_{K|μ}(K(H′)) (where σ_{K|μ} = σ_{K|k}^{[μ:k]} is the Frobenius of K|μ)

2. K(H′)|μ(x) is Galois

3. There exists an extension M|μ(x) of degree 2 such that M|μ is regular and KM = K(H′).

Proof As the Galois closure of K(H′)|μ(x) is K(H′)σ_{K|μ}(K(H′)) ⋯ σ_{K|μ}^{[K:μ]−1}(K(H′)), the equivalence of the first two points is obvious.

It is also obvious that the third condition implies the first two.

So let K(H′)|μ(x) be Galois. By Proposition 3 applied to K|μ instead of K|k, we see that there exists an extension M|μ(x) such that M|μ is regular and KM = K(H′). By construction M|μ(x) has degree 2. □

Remark If n is even, the first two points are also equivalent, and the third implies these two points.

Let μ be an intermediate field of K|k such that μ ⊊ K, assume that the conditions of the lemma are satisfied, and let M|μ(x) be as in the lemma. We claim that (1) factors through the norm homomorphism from Cl^{0}(K(H′)) to Cl^{0}(M).

Let F′_{0} be the Galois closure of M|k(x). By the argumentation following Lemma 2 applied to μ|k, M|k(x) and F′_{0}, there exists an extension F_{0}|k(x) with μF_{0} = F′_{0} and F_{0} ∩ μ = k. As in the last section, let λ be the unique extension of k of degree 2. Then depending on whether F′|K is regular or F′|λK is regular, F_{0}|k is regular or F_{0}|λ is regular. Further F′ = KF′_{0} = KF_{0}, and thus by Proposition 3 F_{0}|k(x) is isomorphic to F |k(x). (In particular, F is contained in the Galois extension F′_{0}|k(x).) We thus obtain the following diagram.

[figure: F′ = KF_{0}; F′_{0} = μF_{0}; K(H′) = KM; M; F_{0}, F]

This induces the commutative diagram

\xymatrix{Cl^{0}(F′) \ar[d] & Cl^{0}(K(H′)) \ar[d] \ar[l] \\ Cl^{0}(μF_{0}) \ar[d] & Cl^{0}(M) \ar[l] \\ Cl^{0}(F).}

(Here the left-arrows are conorm homomorphisms and the down-arrows are norm homomorphisms.) It follows that (1) factors through norm_{K(H′)|M} : Cl^{0}(K(H′)) ⟶ Cl^{0}(M).

Proposition 5 Let μ be an intermediate field of K|k and assume that K(H′)|μ(x) is Galois. Then there exists a regular function field M|μ with KM = K(H′) such that (1) factors through N_{K(H′)|M} : Cl^{0}(K(H′)) ⟶ Cl^{0}(M).

Cryptological application Assume that the curve H′ is cryptographically suitable – i.e. in particular the genus of H′ is small (≤ 3) and the order of Cl^{0}(K(H′)) is prime up to a small cofactor – and that a field μ ⊊ K as in the proposition exists. Then the proposition implies that the kernel of (1) contains the large subgroup of prime order, and thus the GHS attack fails. This follows from the theorem of Hasse-Weil; cf. [21, V.2.1.].

The following theorem can be viewed as a converse to the last proposition.

Theorem 1 Let K|k, H′, F and F′ be as in Proposition 3. Assume that for no intermediate field μ of K|k such that μ ⊊ K, K(H′)|μ(x) is Galois. Then the kernel of (1) contains only elements of order a 2-power. ^{3} Proof In fact, we will prove that the kernel of (1) is annihilated by multiplication with 2^{m−1}, i.e. that every element of the kernel has an order dividing 2^{m−1}.

3After having finished the preparation of the manuscript, we were informed that in the context of [8], F. Hess obtained a similar result.

We first fix a notation: If α : A_{1} ↪ A_{2} is a homomorphism of function fields, we denote the conorm from Cl^{0}(A_{1}) to Cl^{0}(A_{2}) with respect to α by \underline{α}.

Let ι : K(H′) ↪ F′ be the inclusion. As in Section 2, let σ̃_{K|k} be a fixed extension of σ_{K|k} to F′|k(x) and let F = F^{′⟨σ̃_{K|k}⟩}.

Then by definition, Con_{F′|K(H′)} = \underline{ι}, and

Con_{F′|F} ∘ N_{F′|F} ∘ Con_{F′|K(H′)} = ∑_{i=0}^{n−1} \underline{σ̃_{K|k}}^{i} ∘ \underline{ι} : Cl^{0}(K(H′)) ⟶ Cl^{0}(F′).

As the conorm homomorphism Con_{F′|F} is injective (see [21, III.6.3. (f)]), the kernel of N_{F′|F} ∘ Con_{F′|K(H′)} : Cl^{0}(K(H′)) ⟶ Cl^{0}(F), i.e. the kernel of (1), equals the kernel of

∑_{i=0}^{n−1} \underline{σ̃_{K|k}}^{i} ∘ \underline{ι} : Cl^{0}(K(H′)) ⟶ Cl^{0}(F′).

We want to study the kernel of this homomorphism.

Let \overline{σ_{K|k}^{i}} : K(H′) ⟶ σ_{K|k}^{i}(K(H′)) be the restriction of σ̃_{K|k}^{i} to K(H′). Let ι_{i} : σ_{K|k}^{i}(K(H′)) ↪ F′ be the inclusions. Then ∑_{i=0}^{n−1} \underline{σ̃_{K|k}}^{i} ∘ \underline{ι} =

∑_{i=0}^{n−1} \underline{ι_{i}} ∘ \underline{\overline{σ_{K|k}^{i}}}.

The conorm homomorphisms

\underline{ι_{i}} : Cl^{0}(σ_{K|k}^{i}(K(H′))) ⟶ Cl^{0}(F′)

induce a homomorphism

⊕_{i} \underline{ι_{i}} : ⨁_{i=0}^{n−1} Cl^{0}(σ_{K|k}^{i}(K(H′))) ⟶ Cl^{0}(F′),

and the conorm homomorphisms

\underline{\overline{σ_{K|k}^{i}}} : Cl^{0}(K(H′)) ⟶ Cl^{0}(σ_{K|k}^{i}(K(H′)))

induce a homomorphism

(\underline{\overline{σ_{K|k}^{i}}})_{i} : Cl^{0}(K(H′)) ⟶ ∏_{i=0}^{n−1} Cl^{0}(σ_{K|k}^{i}(K(H′))) = ⨁_{i=0}^{n−1} Cl^{0}(σ_{K|k}^{i}(K(H′))).

Combining these two homomorphisms, we obtain:

∑_{i=0}^{n−1} \underline{σ̃_{K|k}}^{i} ∘ \underline{ι} = ∑_{i=0}^{n−1} \underline{ι_{i}} ∘ \underline{\overline{σ_{K|k}^{i}}} = (⊕_{i} \underline{ι_{i}}) ∘ (\underline{\overline{σ_{K|k}^{i}}})_{i} : Cl^{0}(K(H′)) ⟶ Cl^{0}(F′)

The homomorphism (\underline{\overline{σ_{K|k}^{i}}})_{i} is obviously injective, and we will prove now that the exponent of the kernel of ⊕_{i} \underline{ι_{i}} divides 2^{m−1}.

The norm homomorphisms N_{i} := N_{F′|σ_{K|k}^{i}(K(H′))} : Cl^{0}(F′) ⟶ Cl^{0}(σ_{K|k}^{i}(K(H′)))

induce a homomorphism

(N_{i})_{i} : Cl^{0}(F′) ⟶ ∏_{i=0}^{n−1} Cl^{0}(σ_{K|k}^{i}(K(H′))) = ⨁_{i=0}^{n−1} Cl^{0}(σ_{K|k}^{i}(K(H′)))

We claim that (N_{i})_{i} ∘ (⊕_{i} \underline{ι_{i}}) = 2^{m−1}. This implies in particular that the exponent of the kernel of ⊕_{i} \underline{ι_{i}} divides 2^{m−1}.

The claim follows from the following two claims:

• For i = 0, …, n − 1, N_{F′|σ_{K|k}^{i}(K(H′))} ∘ Con_{F′|σ_{K|k}^{i}(K(H′))} : Cl^{0}(σ_{K|k}^{i}(K(H′))) ⟶ Cl^{0}(σ_{K|k}^{i}(K(H′))) is multiplication by 2^{m−1}.

• For i, j = 0, …, n − 1, i ≠ j, N_{F′|σ_{K|k}^{j}(K(H′))} ∘ Con_{F′|σ_{K|k}^{i}(K(H′))} :

Cl^{0}(σ_{K|k}^{i}(K(H′))) ⟶ Cl^{0}(σ_{K|k}^{j}(K(H′))) is trivial. The first claim is standard, we prove the second.

By assumption and Lemma 4, for no i = 1, …, n−1, K(H′) = σ_{K|k}^{i}(K(H′)). This means that for no i, j = 0, …, n − 1 with i ≠ j, σ_{K|k}^{i}(K(H′)) = σ_{K|k}^{j}(K(H′)).

Let i ≠ j ∈ {0, …, n − 1}, let L′ := σ_{K|k}^{i}(K(H′)) σ_{K|k}^{j}(K(H′)). Then L′|K(x) is an extension of degree 4, and F′|L′ is an extension of degree 2^{m−2}.

[figure: F′; L′; σ_{K|k}^{i}(K(H′)); σ_{K|k}^{j}(K(H′)); K(x)]

We have

N_{F′|σ_{K|k}^{j}(K(H′))} ∘ Con_{F′|σ_{K|k}^{i}(K(H′))} =
N_{L′|σ_{K|k}^{j}(K(H′))} ∘ N_{F′|L′} ∘ Con_{F′|L′} ∘ Con_{L′|σ_{K|k}^{i}(K(H′))} =
N_{L′|σ_{K|k}^{j}(K(H′))} ∘ [2^{m−2}] ∘ Con_{L′|σ_{K|k}^{i}(K(H′))},

where [2^{m−2}] denotes multiplication by 2^{m−2}. It thus suffices to prove that N_{L′|σ_{K|k}^{j}(K(H′))}∘Con_{L′|σ_{K|k}^{i}(K(H′))} = 0. By the following lemma, N_{L′|σ_{K|k}^{j}(K(H′))}∘ Con_{L′|σ_{K|k}^{i}(K(H′))} = Con_{σ_{K|k}^{j}(K(H′))|K(x)} ∘ N_{σ_{K|k}^{i}(K(H′))|K(x)}, and this is equal

to 0 as Cl^{0}(K(x)) = 0. □

Lemma 6 Let A be a function field over a field K, let B|A and C|A be finite Galois extensions, let BC be a composite of B and C over A such that inside BC, B ∩ C = A. Then

N_{BC|C} ∘ Con_{BC|B} = Con_{C|A} ∘ N_{B|A} : Cl^{0}(B|K) ⟶ Cl^{0}(C|K).

Proof The statement follows from the corresponding statement on the level of divisors:

N_{BC|C} ∘ Con_{BC|B} = Con_{C|A} ∘ N_{B|A} : Div(B|K) ⟶ Div(C|K)

This statement can be proven as follows:

On the level of divisors, the conorm homomorphism is injective. It thus suffices to check that Con_{BC|C}∘N_{BC|C}∘Con_{BC|B} = Con_{BC|C}∘Con_{C|A}∘N_{B|A} : Div(B|K) ⟶ Div(C|K).

We denote the conorm on the level of divisors with respect to a homomorphism of function fields α : A_{1} ⟶ A_{2} also by α. If τ ∈ Gal(BC|C), we denote its restriction to B by \overline{τ}, and we denote the inclusion B ↪ BC by ι. By assumption on the composite BC|A, Gal(BC|C) ⟶ Gal(B|A), τ ↦ \overline{τ} is an isomorphism (see [13, VI, Theorem 1.12]) and τι = ι\overline{τ} : B ⟶ BC.

Now, for D ∈ Div(B|K), Con_{BC|C} ∘ N_{BC|C} ∘ Con_{BC|B}(D) = ∑_{τ∈Gal(BC|C)} τ(ι(D)) = ι(∑_{\overline{τ}∈Gal(B|A)} \overline{τ}(D)) = Con_{BC|B}∘Con_{B|A}∘N_{B|A}(D) = Con_{BC|A} ∘ N_{B|A}(D) = Con_{BC|C} ∘ Con_{C|A} ∘ N_{B|A}(D). □

Remark The theorem is also valid for n = [K : k] even, provided that the field F as in Proposition 3 exists.

Corollary 7 Let n be prime and assume that K(H′) ⊊ F′. Then the kernel of (1) contains only elements of order a 2-power.

4 Composites of (hyper-)elliptic function fields

For the rest of the article, we restrict ourselves to the case that the characteristic is odd.

The main goal is now to calculate the genus of F′ = K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{n−1}(K(H′)) or – what is the same – the genus of \overline{K}F′|\overline{K} and furthermore to check whether F′|K is regular.

In [8], Artin-Schreier Theory was used to study the extension F′|K(x). Since we work in odd characteristic, we wish to substitute this by Kummer Theory.

We first give an exposition to the results we need and come back to the GHS attack in the following section.

Let Λ be a field with char(Λ) ≠ 2, let Λ^{sep} be a fixed separable closure, and let μ_{2} ⊆ Λ^{∗} be the subgroup consisting of 1 and -1.

We have a pairing

Gal(Λ^{sep}|Λ) × Λ^{∗} ⟶ μ_{2}
(σ, u) ↦ \frac{σ(ν)}{ν} where ν^{2} = u, ν ∈ Λ^{sep}.

Let U be a finite subgroup of Λ^{∗}/Λ^{∗2}. Let Λ[\sqrt[2]{U}] be the subfield of \sqrt[2]{Λ} generated over Λ by the square roots of the preimages of the elements of U in Λ^{∗}.

Then the above pairing induces a non-degenerate pairing

⟨·, ·⟩ : Gal(Λ[\sqrt[2]{U}]|Λ) × U ⟶ μ_{2}  (4)

of finite abelian groups of exponent 2.

We can regard U as an 𝔽_{2}-vector space. Since the pairing is nondegenerate,

[Λ[\sqrt[2]{U}] : Λ] = 2^{dim_{𝔽_{2}}(U)}.  (5)

The non-degeneracy of the pairing also implies:

Lemma 8 The assignment V ↦ Λ[\sqrt[2]{V}] gives bijection between the subvector spaces of U and the subextensions of Λ[\sqrt[2]{U}]|Λ.

Now let K be a perfect field with char(K) ≠ 2. Fix an algebraic closure \overline{K} and a separable closure K(x)^{sep} containing \overline{K}(x). All the following extensions of K(x) should be regarded inside K(x)^{sep}. We now apply the above statements to the case that Λ = K(x).

We fix the following notation: If h ∈ K(x)^{∗}, its image in K(x)^{∗}/K(x)^{∗2} is denoted by \underline{h}.

Let f_{1}, …, f_{n} ∈ K(x)^{∗}, let L_{i}|k(x) be the extension given by y_{i}^{2} = f_{i}(x) inside K(x)^{sep}. Let L be the composite of the L_{i} inside K(x)^{sep}.

Let U be the 𝔽_{2}-vector space generated by the \underline{f_{i}} ∈ K(x)^{∗}/K(x)^{∗2}. Let \overline{U} be the image of U inside \overline{K}(x)^{∗}/\overline{K}(x)^{∗2}. Then L = K(x)[\sqrt[2]{U}], \overline{K}L = \overline{K}(x)[\sqrt[2]{\overline{U}}].

Lemma 9 L|K is regular iff U ⟶ \overline{U} is an isomorphism.

Proof L|K is regular iff [L : K(x)] = [\overline{K}L : \overline{K}(x)]. By (5) this is equivalent to U ˜ ⟶ \overline{U}. □

Especially:

Lemma 10 Let all f_{i} be monic, i.e. the leading coefficient is 1. Then L|K is regular.

Proof Under this condition, all elements of U are images of monic rational functions. Now, if a monic rational function of K is a square in \overline{K}(x), it is also a square in K(x). (As \overline{K}|K is separable.) □

We want to study the ramification of L|K(x) in terms of the ramification of L_{i}|K(x).

Lemma 11 L|K(x) is ramified at a place 𝔭 of K(x)|K iff there exists an i such that L_{i}|K(x) is ramified. If this is the case, the ramification index of 𝔭 in L|K(x) is 2.

Proof This is a special case of Abhyankar’s Lemma; see [18, Lemma (2.14)] or [21, Proposition III.8.9]. ^{4} □

Let κ be the algebraic closure of K in L. We now want to calculate the genus of the function field L|κ. Since the genus is invariant under extension of the constant field, we can instead calculate the genus of \overline{K}L|\overline{K}.

Let r be the number of places of \overline{K}(x)|\overline{K} which ramify in at least one of the \overline{K}L_{i}|\overline{K}(x). By the above lemma this is equal to the number of ramified places of \overline{K}L|\overline{K}(x). Let

\overline{m} := dim_{𝔽_{2}}(\overline{U}).  (6)

Then by (5) [\overline{K}L : \overline{K}(x)] = 2\overline{m}, and by the Hurwitz genus formula (see [21, III.5.6])

\begin{matrix}g(L|κ) = g(\overline{K}L|\overline{K}) = 2\overline{m}(0 − 1) + \frac{1}{2}r(2 − 1)\frac{2\overline{m}}{2} + 1 \\ = −2\overline{m} + r2^{\overline{m}−2} + 1 = 2^{\overline{m}−2}(r − 4) + 1. \end{matrix}  (7)

If \overline{m} ≥ 3, g(L|κ) = g(\overline{K}L|\overline{K}) is odd. In particular:

4We would like to stress that the lemma is only valid because we assumed that char(K) ≠ 2. In particular, it cannot be applied to study the GHS attack in characteristic 2.

Lemma 12 If \overline{m} ≥ 3, L|κ is not a rational function field.

Applying this result to subextensions of \overline{K}L|\overline{K}(x) – which by Lemma 8 all have the form \overline{K}(x)[\sqrt[2]{\overline{V}}] for some vector subspace \overline{V} of \overline{U} –, we obtain: If \overline{m} ≥ 4, \overline{K}L|\overline{K}(x) does not contain a rational subfield of index 2. This implies:

Lemma 13 If \overline{m} ≥ 4, L|K(x) does not contain a rational subfield of index 2.

Proof Let M|K(x) be a subfield of index 2. Then either \overline{K}L|\overline{K}M is an extension of degree 2 or it is trivial. In both cases, g(\overline{K}M|\overline{K}) ≥ 1. □

We will need the following explicit description of K(x)^{∗}/K^{∗2}.

Let P be the set of monic irreducible polynomials over K. Unique factorization in the ring K[x] induces an isomorphism

\begin{matrix}K^{∗} ⊕ ⨁_{p∈P} ℤ ˜ ⟶ K(x)^{∗}, \\ (c, (f_{p})_{p∈P}) ↦ c ∏_{p∈P} p^{f_{p}}. \end{matrix}

Thus

K^{∗}/K^{∗2} ⊕ ⨁_{p∈P} 𝔽_{2} ˜ ⟶ K(x)^{∗}/K(x)^{∗2} .  (8)

Note that if K is finite (and as always char(K) is odd), K^{∗}/K^{∗2} ≃ 𝔽_{2}.

5 Analysis of the GHS attack in odd characteristic

We now apply the above results to the special case of the GHS attack in odd characteristic with respect to an odd extension degree n.

Let k be a finite field of odd characteristic, K|k an extension of odd degree n. Let H′ be a (hyper-)elliptic curve of genus g, and let K(H′)|K(x) be an extension of degree 2.

As in Section 2, let F′ be the Galois closure of K(H′)|k(x) inside K(x)^{sep}. In order for the attack to be successful we assume (see Proposition 5):

For no intermediate field μ of K|k with μ ⊊ K, K(H′)|μ(x) is Galois. The extension K(H′)|K(x) is given by a Weierstraß-equation of the form

y^{2} = c f(x),

where f is a monic square-free polynomial of degree 2g + 1 or 2g + 2 and c ∈ K^{∗}. By Kummer Theory we can change c by multiplication with an element of K^{∗}^{2}. Since K^{∗}/K^{∗}^{2} ≃ 𝔽_{2} ≃ k^{∗}/k^{∗}^{2}, we can choose c ∈ k^{∗} and we do so.

Now F′ is generated over K(x) by y_{0}, …, y_{n−1} where y_{i} satisfies

y_{i}^{2} = c σ_{K|k}^{i}(f)(x).

Thus F′ = K(x)[\sqrt[2]{U}] where U ⊆ K(x)^{∗}/K(x)^{∗2} is the vector subspace generated by the images \underline{σ_{K|k}^{i}(f)} of σ_{K|k}^{i}(f) in K(x)^{∗}/K(x)^{∗2}. Let \overline{U} be the

image of U in \overline{K}(x)^{∗}/\overline{K}(x)^{∗2}. Then by (5), the numbers m and \overline{m} defined in (3) can be expressed as follows:

m = dim_{𝔽_{2}}(U) , \overline{m} = dim_{𝔽_{2}}(\overline{U}).  (9)

Lemma 10 and Proposition 3 imply:

Proposition 14 If c = 1, F′|K is regular, and so is F |k.

We fix the following notations: Let σ_{k} ∈ Gal(\overline{K}|k) ≃ Gal(\overline{K}(x)|k(x)) be the Frobenius automorphism relative to k. Analogously to σ_{K|k}^{i}(K(H′)) we define σ_{k}^{i}(\overline{K}(H′)). Then σ_{k}^{i}(\overline{K}(H′)) equals the composite \overline{K} σ_{K|k}^{i}(K(H′)). Moreover, \overline{K}F′ = \overline{K}(H′) σ_{k}(\overline{K}(H′)) ⋯ σ_{k}^{n−1}(\overline{K}(H′)).

We ask at which places \overline{K}F′|\overline{K}(x) is ramified, i.e. by Lemma 11 which places of \overline{K}(x)|\overline{K} ramify in at least one of the extensions σ_{k}^{i}(\overline{K}(H′))|\overline{K}(x).

We identify the places of \overline{K}(x)|\overline{K} with \overline{P} ∪ \{∞\}, where \overline{P} is the set of monic linear polynomials over \overline{K}. The Frobenius σ_{k} operates on the places, and this operation corresponds to the operation on \overline{P} ∪ \{∞\} induced by the operation on \overline{K}(x) (where σ_{k}(∞) = ∞).

The extension \overline{K}(H′)|\overline{K}(x) is ramified at some place p ∈ P iff p divides f. (Note our assumption that f be square free.) It is ramified at ∞ iff the deg(f) = 2g + 1. Let R be the set of ramified places of \overline{K}(H′)|\overline{K}(x), i.e. #R = 2g + 2. Then σ_{k}^{i}(\overline{K}(H′))|\overline{K}(x) is ramified exactly at σ_{k}^{i}(R), and \overline{K}F′|\overline{K}(x) is ramified exactly at ⋃_{i=0}^{n−1} σ_{k}^{i}(R). Let r := # ⋃_{i=0}^{n−1} σ_{k}^{i}(R) be the number of ramified places of \overline{K}F′|\overline{K}(x).

By (7) we obtain

g(F) = g(F′) = 2^{\overline{m}−2}(r − 4) + 1.  (10)

The number \overline{m} is obviously bounded from above by n. Further, r ≤ n·#R = n(2g + 2). Thus

g(F) ≤ 2^{n−2}((2g + 2)n − 4) + 1 = 2^{n−1}((g + 1)n − 2) + 1.  (11)

We are searching for a lower bound for g(F).

As in the last section, if h ∈ K(x)^{∗}, we denote its image in K(x)^{∗}/K(x)^{∗2} by \underline{h}. If h ∈ \overline{K}(x)^{∗}, we denote its image in \overline{K}(x)^{∗}/\overline{K}(x)^{∗2} by \overline{\underline{h}}.

Since \overline{U} is \overline{m}-dimensional, there exist i_{l}, l = 1, …, \overline{m} such that \overline{\underline{σ_{K|k}^{i_{l}}(f)}}

form a basis for \overline{U}. This means in particular that ⋃_{i=0}^{n−1} σ_{k}^{i}(R) = ⋃\overline{m} ; l=1 σ_{k}^{i_{l}}(R), and we have r = # ⋃\overline{m} ; l=1 σ_{k}^{i_{l}}(R) ≤ \overline{m} · #R = \overline{m}(2g + 2). This implies

\overline{m} ≥ ⌈\frac{r}{2g + 2}⌉.  (12)

Here, for x ∈ ℚ, ⌈x⌉ denotes the smallest integer greater or equal x.

We now want to bound r from below by a function depending only on n. We use the fact that by assumption for no intermediate field μ of K|k with μ ⊊ K, Gal(K(H′))|μ(x)) is Galois.

The group Gal(\overline{K}|k) operates on ⋃_{i=0}^{n−1} σ_{k}^{i}(R). Let Gal(\overline{K}|Δ) be the kernel of the homomorphism Gal(\overline{K}|k) ⟶ Aut(⋃_{i=0}^{n−1} σ_{k}^{i}(R)).

Lemma 15 K ⊆ Δ.

Proof We show K = K ∩ Δ. We have Gal(\overline{K}|K ∩ Δ) = ⟨Gal(\overline{K}|K) ∪ Gal(\overline{K}|Δ)⟩. The polynomial c f is fixed by both of these groups, thus it is fixed by Gal(\overline{K}|K ∩ Δ). It follows that c f ∈ K ∩ Δ, and this implies that K(H′)|K ∩ Δ(x) is Galois. It follows from the assumption that K = K ∩ Δ.

□

By definition of Δ, we have an injective homomorphism

Gal(Δ|k) ↪ Aut( ⋃_{i=0}^{n−1} σ_{k}^{i}(R)).  (13)

Let δ := [Δ : k], let δ = ∏_{p prime} p^{δ_{p}} be the prime decomposition of δ. By (13) we know that the cyclic group of order δ can be embedded in the symmetric group on r elements. This implies

r ≥ ∑_{p,δ_{p}≠0} p^{δ_{p}}.  (14)

Let n = ∏_{p prime} p^{n_{p}} be the prime decomposition of n. By the above lemma, n|δ, thus for all primes p, n_{p} ≤ δ_{p}. With (14), we obtain

r ≥ ∑_{p,n_{p}≠0} p^{n_{p}}.  (15)

Inserting (12) and (15) into the right-hand side of (10), we obtain

g(F) ≥ 2^{⌈^{\frac{∑_{p,np≠0} p^{np}}{2g+2}} ⌉−2}( ∑_{p,n_{p}≠0} p^{n_{p}} − 4) + 1  (16)

Combining everything we obtain the following theorem.

Theorem 2 Let K|k be an extension of finite fields of odd characteristic and odd degree n = ∏_{p prime} p^{n_{p}}. Let H′ be a (hyper-)elliptic curve over K of genus g. Choose some extension K(H′)|K(x) of degree 2, given by an equation of the form y^{2} = c f(x) where f is monic and c ∈ K^{∗}.

Then via the GHS attack one obtains a function field F, regular over k or its unique quadratic extension, an extension KF |K(H′) of degree 2^{m} for some m ≤ n, and a homomorphism from Cl^{0}(K(H′)) to Cl^{0}(F) with the following properties:

• If c = 1, F |k is regular.

• g(F) ≤ 2^{n−1}((g + 1)n − 2) + 1.

• If there exists some field μ with k ⊆ μ ⊊ K such that K(H′)|μ(x) is Galois, there exists a regular function field M|μ with KM = K(H′) such that the homomorphism factors through N_{K(H′)|M} : Cl^{0}(K(H′)) ⟶ Cl^{0}(M). ^{5}

• If there does not exist such a μ, the kernel of the homomorphism contains only elements of order a 2-power and

g(F) ≥ 2^{⌈^{\frac{∑_{p,np≠0} p^{np}}{2g+2}} ⌉−2}( ∑_{p,n_{p}≠0} p^{n_{p}} − 4) + 1.

Proof The existence of F and the homomorphism was already shown in Section 2. The first point is Proposition 14, the second is (11), the third is Proposition 5, the fourth is (16). □

Further, by Lemma 13:

Proposition 16 Let \overline{m} be defined as in (9). If \overline{m} ≥ 4, F′|K(x) does not contain a rational subfield of index 2.

Note that this is a major difference between the GHS attack in odd characteristic and in characteristic 2. Indeed, according to [8], if H′ is an elliptic curve and K has characteristic 2, one can always choose an extension K(H′)|K(x) such that F′|K(x) has a rational subfield of index 2.

6 Analysis for prime extension degree

Now let n be an odd prime. We will analyze the attack in more detail in this case and outline some possible applications as well as limitations of the attack.

5In cryptological applications, this means that the large subgroup of prime order of Cl^{0}(K(H′)) is not preserved under the homomorphism.

Let the notations be as above and let n be prime. We still assume that K(H′)|k(x) is not Galois, i.e. that K(H′) ⊊ F′, for otherwise the attack fails.

Note that by (16),

g(F) ≥ 2^{⌈ \frac{n}{2g+2} ⌉−2}(n − 4) + 1.  (17)

We want to give a new bound for g(F) from below.

The operation of Gal(K|k) ≃ Gal(K(x)|k(x)) on K(x)^{∗} restricts to an operation on the subgroup ⟨K^{∗} ∪ K(x)^{∗2}⟩, and we obtain an operation on K(x)^{∗}/⟨K ∪ K(x)^{∗2}⟩. This group is included in \overline{K}(x)^{∗}/\overline{K}(x)^{∗2}, and \overline{U} is a subgroup of K(x)^{∗}/⟨K ∪K(x)^{∗2}⟩. The operation of Gal(K|k) induces a nontrivial operation of Gal(K|k) on \overline{U} which gives rise to a non-trivial operation of the group ring 𝔽_{2}[Gal(K|k)] on \overline{U}. By construction, \overline{U} is the image of \overline{\underline{f}} ∈ \overline{K}(x)^{∗}/\overline{K}(x)^{∗2} under the operation of 𝔽_{2}[Gal(K|k)]. As 𝔽_{2}[Gal(K|k)] ≃ 𝔽_{2}[ℤ/nℤ], \overline{U} is a cyclic 𝔽_{2}[ℤ/nℤ]-module with a non-trivial operation by ℤ/nℤ.

Definition For some natural number n, let φ_{2}(n) be the multiplicative order of 2 modulo n, i.e. φ_{2}(n) = [𝔽_{2}[ζ_{n}] : 𝔽_{2}].

Lemma 17 Let n be an odd prime number. Let V be a cyclic 𝔽_{2}[ℤ/nℤ]- module. Then

dim_{𝔽_{2}}(V) = κ φ_{2}(n) or dim_{𝔽_{2}}(V) = 1 + κ φ_{2}(n)

for some κ = 0, …, \frac{n−1}{φ_{2}(n)}. If the operation by ℤ/nℤ is non-trivial, then κ ≥ 1.

Proof Let V = 𝔽_{2}[ℤ/nℤ] v for some v ∈ V, and let Ann(v) ⊲ 𝔽_{2}[ℤ/nℤ] be the annihilator of v. Then as 𝔽_{2}[ℤ/nℤ]-module, V is isomorphic to 𝔽_{2}[ℤ/nℤ]/Ann(v).

On the other hand, we have canonical isomorphisms 𝔽_{2}[ℤ/nℤ] ≃ 𝔽_{2}[x]/(x^{n}− 1) ≃ 𝔽_{2} ⊕ 𝔽_{2}[x]/(x^{n−1} + ⋯ + x + 1) of rings, and the ring 𝔽_{2}[x]/(x^{n−1} + ⋯ + x + 1) is (non-canonically) isomorphic to 𝔽_{2}[ζ_{n}]^{\frac{n−1}{φ_{2}(n)}} . This implies the result on the dimension of V. □

We obtain:

\overline{m} = κ φ_{2}(n) or \overline{m} = 1 + κ φ_{2}(n)  (18)

for some κ = 1, …, \frac{n−1}{φ_{2}(n)}.

Remark Note the similarity of this result with the one obtained in [16] (our \overline{m} corresponds to m in [16]). However, there is an important difference.

In odd characteristic we have the additional bound \overline{m} ≥ ⌈\frac{n}{2g+2}⌉ (see (12) and note that r ≥ n as n is prime).

Equations (10) and (18) imply (as r ≥ n):

Proposition 18 Let n be prime. Then additionally to the bound (17), we have the following bound for the genus of F.

g(F) ≥ 2^{φ_{2}(n)−2}(n − 4) + 1

We now want to outline explicit examples of applications of the attack for n = 5, 7 and elliptic curves H′ = E′. Then we will show that for cryptographically suitable elliptic curves and prime extension degree n ≥ 11, log_{2}((#k)^{g(F)}) ≥ 5000.

In order to be able to describe the vector space \overline{U} explicitly we make the following definition.

Let S be the set of monic linear polynomials of \overline{K} which divide at least one of the σ_{K|k}^{i}(f). If we identify the places of \overline{K}(x)|\overline{K} with \overline{P} ∪ \{∞\} where \overline{P} is the set of monic linear polynomials of \overline{K}, S = ⋃_{i=0}^{n−1} σ_{k}^{i}(R)\\{∞\} where – as in the last section – R is the set of ramified places of \overline{K}(H′)|\overline{K}(x).

By (8), \overline{U} is included in 𝔽_{2}^{S}. Here, if (e_{s})_{s∈S} denotes the standard basis of 𝔽_{2}^{S}, e_{s} corresponds to \overline{\underline{s}} ∈ \overline{U}.

6.1 n = 5 ^{6}

If H′ = E′ is an elliptic curve, by (17), the genus of F is bounded from below by 2, and by Proposition 18, it is bounded from below by 5. We will now give examples of elliptic curves for which F |k is regular and the genus of F is indeed 5.

Let p be a prime and q a power of p. Let k = 𝔽_{q}, K = 𝔽_{q^{5}}. Let a ∈ K\k, let

f(x) = (x − a)(x − a^{q})(x − a^{q^{2}})(x − a^{q^{3}}) ∈ K(x).

Let E′ be the elliptic curve over K given by y^{2} = f(x). Let K(E′)|K(x) be the extension given by this equation.

Since f is monic, F |k is regular; see Theorem 2. We want to calculate \overline{m} and then g(F).

We have S = {x − a, x − a^{q}, x − a^{q^{2}}, x − a^{q^{2}}, x − a^{q^{3}}, x − a^{q^{4}}}, r = 5. We regard the image of \overline{U} under the inclusion into 𝔽_{2}^{S}. We enumerate the

elements of S by x−a ↔ 1, …, x−a^{q^{4}} ↔ 5 and identify 𝔽_{2}^{S} with 𝔽_{2}^{5}. Then \overline{\underline{f}}

6Results similar to the ones for n = 5 or n = 7 can be obtained for n = 3. In this case, there exist elliptic curves E′ over K such that g(F) = 3 and F |k is regular and even hyperelliptic. Since there is little hope that in the foreseeable future the DLP in class groups of genus 3 hyperelliptic curves can be more efficiently attacked via index calculus methods than with generic attacks, we omit the details.

corresponds to the vector ( \begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 0 \end{matrix} ), and \underline{\overline{σ_{K|k}(f)}}, \underline{\overline{σ_{K|k}^{2}(f)}}, \underline{\overline{σ_{K|k}^{3}(f)}}, \underline{\overline{σ_{K|k}^{4}(f)}}

correspond to the vectors ( \begin{matrix}0 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix} ) , ( \begin{matrix}1 \\ 0 \\ 1 \\ 1 \\ 1 \end{matrix} ) , ( \begin{matrix}1 \\ 1 \\ 0 \\ 1 \\ 1 \end{matrix} ) , ( \begin{matrix}1 \\ 1 \\ 1 \\ 0 \\ 1 \end{matrix} ). Thus \overline{m} =

dim_{𝔽_{2}}(\overline{U}) equals the rank of the matrix

( \begin{matrix}1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \end{matrix} )

which is 4. With (10) we conclude: F |k is regular and g(F) = 2^{4−2}(5 − 4) + 1 = 5.

Note that this means that up to small subgroups E′(𝔽_{q}) and Cl^{0}(F) are isomorphic.

6.2 n = 7

We want to give elliptic curves for which F is regular and g(F) = 7. Let q be as above, k = 𝔽_{q}, K = 𝔽_{q^{7}}. Let a ∈ K\k, let

f(x) = (x − a)(x − a^{q})(x − a^{q^{2}})(x − a^{q^{4}}) ∈ K(x).

Let E′ be the elliptic curve over K given by y^{2} = f(x). Let K(E′)|K(x) be the extension given by this equation. Again F |k is regular.

Then S = {x − a, x − a^{q}, …, x − a^{q^{6}}}, r = 7. As above we identify 𝔽_{2}^{S} with 𝔽_{2}^{7}.

Now \overline{\underline{f}} corresponds to the vector ( \begin{matrix}1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix} ), \overline{m} equals the rank of the matrix

( \begin{matrix}1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix} ) .

The first three columns are linearly independent, and the sum of the first, the second and the fourth equals zero. This relation is preserved under shifting. Thus the fourth up to the seventh vectors are linearly dependent on the first three. So the rank of the matrix is 3.

We conclude again with (10): F |k is regular and g(F) = 2^{3−2}(7−4)+1 = 7. Again up to small subgroups, E′(K) and Cl^{0}(F) are isomorphic.

Remark The example was constructed in the following way: x^{7} − 1 splits over 𝔽_{2} into (x + 1)(x^{3} + x^{2} + 1)(x^{3} + x + 1). Let s be the cyclic shifting in 𝔽_{2}^{7}. Then application of (s + 1)(s^{3} + s^{2} + 1) = (s^{4} + s^{2} + s + 1) to the first vector of the standard basis yields the vector corresponding to \overline{\underline{f}}. It follows that s^{3} + s + 1 applied to this vector is trivial and \overline{U} is 3-dimensional.

6.3 n ≥ 11

Let n ≥ 11 be a prime. We want to give explicit lower bounds on q^{g(F)} ≈ #Cl^{0}(F) for elliptic curves H′ = E′.

Let q be a power of a prime, k = 𝔽_{q}, K = 𝔽_{q^{n}}. Let H′ = E′ be an elliptic curve over K. Let c := log_{2}(q^{n}), thus log_{2}(q) = \frac{c}{n}.

Since n ≥ 11 > 8, (17) implies

g(F) > 2^{⌈ \frac{n}{4} ⌉−2}(n − 4) > 2^{⌈ \frac{n}{4} ⌉−2} \frac{1}{2}n = 2^{⌈ \frac{n}{4} ⌉−3} n.

Together with the definition of c, we obtain

log_{2}(q^{g(F)}) = \frac{g(F) c}{n} > 2^{⌈ \frac{n}{4} ⌉−3} c.

It follows that if n ≥ 29, then

log_{2}(q^{g(F)}) > 32.

We now use Proposition 18 to obtain lower bounds on log_{2}(q^{g(F)}) = \frac{g(F) c}{n} for n = 11, 13, 17, 19, 23.

\begin{aligned}n & φ_{2}(n) & g(F) & log_{2}(q^{g(F)}) \\ 11 & 10 & ≥ 2^{10−2}(11 − 4) + 1 = 1793 & ≥ 163 c \\ 13 & 12 & ≥ 2^{12−2}(13 − 4) + 1 = 9217 & ≥ 709 c \\ 17 & 8 & ≥ 2^{8−2}(17 − 4) + 1 = 833 & ≥ 49 c \\ 19 & 18 & ≥ 2^{18−2}(19 − 4) + 1 = 983041 & ≥ 51739 c \\ 23 & 11 & ≥ 2^{11−2}(23 − 4) + 1 = 9729 & ≥ 423 c \end{aligned}

We thus obtain the following result:

Proposition 19 Let K|k be an extension of finite fields of prime degree n ≥ 11, let H′ = E′ be an elliptic curve. Then log_{2}((#k)^{g(F)}) ≥ 32 log_{2}(#K). In particular, if E′(K) has cryptographically relevant size, i.e. log_{2}(#K) ≥ 160, then log_{2}((#k)^{g(F)}) > 5000.

7 Explicit equations

In this section, we continue the discussion of the examples of the last section for n = 5 and n = 7. We show how one can derive explicit equations of the resulting fields F.

We keep the notations of the previous sections. We start off more generally with n some odd integer.

7.1 Four lemmata

The following four lemmata will be used to calculate explicit equations of the fields F. The proofs of the first two of them are also valid in characteristic 2.

Lemma 20 The inclusions σ_{K|k}^{i}(K(H′)) ⟶ F′ induce an isomorphism

F′ ≃ K(H′) ⊗_{K(x)} σ_{K|k}(K(H′)) ⊗_{K(x)} ⋯ ⊗_{K(x)} σ_{K|k}^{m−1}(K(H′)).

Proof If m = n, the statement is obvious, so we assume that m < n.

Let i_{0} be the largest integer such that [K(H′) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)) : K(x)] = 2^{i_{0}}. We claim that K(H′) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)) = F′. This implies that i_{0} = m, and the statement of the lemma follows.

By definition of i_{0}, σ_{K|k}^{i_{0}}(K(H′)) ⊆ K(H′) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)). It follows that K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{i_{0}}(K(H′)) = K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)). Now we proceed by induction: Assume that for some j with i_{0} ≤ j < n − 1, σ_{K|k}^{j} ⊆ K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)). Then σ_{K|k}^{j+1}(K(H′)) ⊆ σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{i_{0}}(K(H′)) ⊆ K(H′) ⋯ σ_{K|k}^{i_{0}}(K(H′)) = K(H′) σ_{K|k}(K(H′)) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)).

It follows that K(H′) ⋯ σ_{K|k}^{i_{0}−1}(K(H′)) = F′. □

Let g(x, y) ∈ K(x)[y] be a defining polynomial for K(H′) over K(x). For i = 0, …, m, choose a root y_{i} of σ_{K|k}^{i}(g)(x, y) in σ_{K|k}^{i}(K(H′)).

Recall that Gal(K|k) operates by taking preimages and conjugation on Gal(F′|K(x)).

Lemma 21 If all elements of Gal(F′|K(x)) have norm 1 under the operation of Gal(K|k), there exists an extension σ̃_{K|k} of σ_{K|k} to F′|k(x) of order n which operates in the following way:

σ̃_{K|k} : y_{0} ↦ y_{1}, y_{1} ↦ y_{2}, …, y_{m−1} ↦ y_{m}.

Proof Let σ̃_{K|k} be an extension of σ_{K|k} to F′|k(x) of order n.

Applying Lemma 20 to σ_{K|k}(K(H′)) instead of K(H′), we see that F′ ≃ σ_{K}(K(H′)) ⊗_{K(x)} ⋯ ⊗_{K(x)} σ_{K|k}^{m}(K(H′)). This implies that there exists an α ∈ Gal(F′|K(x)) such that α ∘ σ̃_{K|k} operates as described in the statement of the lemma. Now α ∘ σ̃_{K|k} has order n as α has – by assumption – norm 1. Thus α σ̃_{K|k} is an extension of σ_{K|k} of order n which operates on the y_{i} as stated in the lemma. □

Lemma 22 Assume that \overline{m} = m = φ_{2}(n). Then there is no proper subfield of F |k(x).

Proof Lemma 17 implies that there is no proper subspace of U which is invariant under the operation of Gal(K|k). This implies that there is no proper subextension of F′|K(x) which is invariant under the operation by Gal(K|k), and it follows that there is no proper subfield of F |k(x). □

The condition of the Lemma is in particular fulfilled in the examples for n = 5 and n = 7 in the last section. When searching for “nice” equations for F, we have to cope with this unpleasant fact.

The Galois group Gal(K|k) operates on Gal(F′|K(x)) as well as on U. Moreover, via the non-degenerate pairing (4) Gal(F′|K(x)) is naturally isomorphic to the dual space of U. The following lemma shows that under this isomorphism the induced operation of Gal(K|k) on the dual space of U is the same as the operation on Gal(F′|K(x)).

Lemma 23 Under the pairing (4) we have:

For α ∈ Gal(F′|K(x)), u ∈ U and σ ∈ Gal(K|k), ⟨σ(α), u⟩ = ⟨α, σ^{−1}(u)⟩.

Proof Let α ∈ Gal(F′|K(x)), u ∈ U, σ ∈ Gal(K|k), and let ν ∈ F′ such that ν^{2} = u. Then ⟨σ(α), u⟩ = \frac{σασ^{−1}(ν)}{ν} = σ(\frac{α(σ^{−1}(ν))}{σ^{−1}(ν)}) = \frac{α(σ^{−1}(ν))}{σ^{−1}(ν)} = ⟨α, σ^{−1}(u)⟩.

□

Let us assume – as is the case in the examples for n = 5 and n = 7 in the last section – that the constant c in the defining equation y^{2} = cf of K(H′)|K(x) is equal to 1. Then U ≃ \overline{U}, m = \overline{m}, and F |k is regular; cf. Proposition 14. From the preceding lemma it follows in particular:

Let n be prime and assume that m = κφ_{2}(n) for some κ = 1, … \frac{n−1}{φ_{2}(n)} (instead of m = 1 + κφ_{2}(n)); cf. (18). Then all elements u ∈ U satisfy u + σ_{K|k}(u) + ⋯ + σ_{K|k}^{n−1}(u) = 0, and thus all elements α ∈ Gal(F′|K(x)) satisfy α σ_{K|k}(α) ⋯ σ_{K|k}^{n−1}(α) = id, i.e. they have norm 1.

The assumption m = κφ_{2}(n) holds in particular for the examples for n = 5 and n = 7. We can thus use Lemma 21 to extend σ_{K|k} to F′|k(x).

7.2 n = 5

We continue with the example in Subsection 6.1.

For i = 0, 1, 2, 3, let y_{i} be a root of the equation y^{2} = σ_{K|k}^{i}(f) in F′. Let

y_{4} := y_{0} y_{1} y_{2} y_{3}/[(x − a)(x − a^{q})(x − a^{q^{2}})(x − a^{q^{3}})^{2}].

Then y_{4} is a root of the equation y^{2} = σ_{K|k}^{4}(f). Let

z := y_{0} + y_{1} + y_{2} + y_{3} + y_{4}.

As m = 4 = φ_{2}(5), all elements of Gal(F′|K(x)) have norm 1, and thus there exists an extension σ̃_{K|k} of σ_{K|K} to F′|k(x) which operates by

y_{0} ↦ y_{1}, y_{1} ↦ y_{2}, y_{2} ↦ y_{3}, y_{3} ↦ y_{4}.

We fix this extension and obtain a subfield F of F′ as in Proposition 3. It follows that z is invariant under Gal(F′|F) ≃ Gal(K|k), thus z lies in F. We claim that it is a primitive element of F |k(x).

By Lemma 22, we only have to show that z does not lie in k(x). Assume that z ∈ k(x). Then in particular, it is fixed by the automorphism α of F′|K(x) given by y_{0} ↦ −y_{0}, y_{1} ↦ y_{1}, y_{2} ↦ y_{2}, y_{3} ↦ y_{3}. We obtain that z = α(z) = −y_{0}+y_{1}+y_{2}+y_{3}−y_{4}. It follows that y_{0}+y_{4} = 0, a contradiction.

For j = (j_{0}, j_{1}, j_{2}, j_{3}) ∈ 𝔽_{2}^{{0,1,2,3}}, let

z_{j} := (−1)^{j_{0}}y_{0} + (−1)^{j_{1}}y_{1} + (−1)^{j_{2}}y_{2} + (−1)^{j_{3}}y_{3} + (−1)^{j_{0}+j_{1}+j_{2}+j_{3}}y_{4}.

Then z_{(0,0,0,0)} = z, and the z_{j} are the Galois conjugates of z under the operation of Gal(F′|K(x)).

The z_{i} are the images of z under all inclusions of F into F′ fixing K(x). It follows that the minimal polynomial of z in F |k(x) is

h := ∏_{j∈𝔽_{2}^{{0,1,2,3}}}(T − z_{j}) ∈ k(x)[T].

All y_{i} are contained in the Galois closure of K[x] in F′, and so is z. It follows that h is contained in K[x, T], thus it is contained in k[x, T].

The polynomial h is a defining polynomial for F |k(x). It has degree 16 in T, and its degree in x is bounded by 32.

Note that we have chosen a particular extension of σ_{K|k} to F′|k(x), thus by construction h is the defining polynomial for a particular extension F |k(x) such that F |k is regular and KF = F′. However, by Proposition 3 these extensions are all isomorphic, thus h defines all these extensions.

7.3 n = 7

Let us now continue the example in Subsection 6.2.

For i = 0, 1, 2, let y_{i} be a root of the equation y^{2} = σ_{K|k}^{i}(f) in F′. Let

y_{3} := y_{0} y_{1}/[(x − a^{q})(x − a^{q^{2}})]
y_{4} := y_{1} y_{2}/[(x − a^{q^{2}})(x − a^{q^{3}})]
y_{5} := y_{2} y_{3}/[(x − a^{q^{3}})(x − a^{q^{4}})]
y_{6} := y_{3} y_{4}/[(x − a^{q^{4}})(x − a^{q^{5}})].

Then for all i = 1, …, 6, y_{i} is a root of the equation y^{2} = σ_{K|k}^{i}(f). Let

z := y_{0} + y_{1} + y_{2} + y_{3} + y_{4} + y_{5} + y_{6}.

As m = 3 = φ_{2}(7), all elements of Gal(F′|K(x)) have norm 1, and thus there exists an extension σ̃_{K|k} of σ_{K|k} to F′|k(x) which operates by

y_{0} ↦ y_{1}, y_{1} ↦ y_{2}, y_{2} ↦ y_{3}.

We fix this extension and obtain a subfield F of F′ as in Proposition 3. By construction, z is invariant under the operation of σ̃_{K|k}, thus it lies in F. We claim that it is a primitive element of F |k(x), and again by Lemma 22 we only have to show that it does not lie in k(x).

Assume that z ∈ k(x). Then in particular, it is fixed by the automorphism α of F′|K(x) given by y_{0} ↦ −y_{0}, y_{1} ↦ −y_{1}, y_{2} ↦ −y_{2}. We have z = α(z) = −y_{0}−y_{1}−y_{2}+y_{3}+y_{4}−y_{5}+y_{6}. It follows that y_{0}+y_{1}+y_{2}+y_{5} = 0. Applying the automorphism of F′|K(x) given by y_{0} ↦ −y_{0}, y_{1} ↦ y_{1}, y_{2} ↦ y_{2} to this equation, we obtain −y_{0} +y_{1} +y_{2} −y_{5} = 0. It follows that y_{1} +y_{2} = 0, a contradiction.

For j = (j_{0}, j_{1}, j_{2}) ∈ 𝔽_{2}^{{0,1,2}}, let

j_{3} := j_{0} + j_{1}
j_{4} := j_{1} + j_{2}
j_{5} := j_{2} + j_{3} = j_{0} + j_{1} + j_{2}
j_{6} := j_{3} + j_{4} = j_{0} + j_{1} + j_{1} + j_{2} = j_{0} + j_{2}

Let

z_{j} := ∑_{i=0}^{6}(−1)^{j_{i}}y_{i}.

Then z_{(0,0,0)} = z, and the z_{j} are the Galois conjugates of z under the operation of Gal(F′|K(x)).

Analogous to the previous case, the minimal polynomial of z in F |k(x) is

h := ∏_{j∈𝔽_{2}^{{0,1,2}}}(T − z_{j}) ∈ k(x)[T].

Again this is contained in k[x, T]. The polynomial h is a defining polynomial for F |k(x) as well as the other extensions F_{1}|k(x) such that F_{1}|k is regular and KF_{1} = F′. It is a polynomial of degree 8 in T, and its degree in x is bounded by 16.

We finish with an explicit calculation based on these results. ^{7} Let p := 10000019, this is a prime such that p^{7} has 163 bit, let a ∈ 𝔽_{p^{7}} be

a root of the following irreducible polynomial in the polynomial ring 𝔽_{p}[A].

A^{7}+5581056A^{6}+1071250A^{5}+7891954A^{4}+3686323A^{3}+1634662A^{2}+5314472A+6311551

Let E′ be the elliptic curve over 𝔽_{p^{7}} given by

y^{2} = (x − a)(x − a^{p})(x − a^{p^{2}})(x − a^{p^{4}}).

The order of E′(𝔽_{p^{7}}) is 4 · l where l is prime and

l = 2500033250189525600163640252013683579685963948773.

One checks that [𝔽_{p}[ζ_{l}] : 𝔽_{p}], i.e. the multiplicative order of p modulo l, is ≥ 10 000, thus the DLP in E′(𝔽_{p^{7}}) is resistant against the attacks based on the Weil- and the Tate-Pairing; cf. [15], [4]. This means that up to now the elliptic curve E′ would have been regarded as cryptographically suitable.

7The following explicit example was calculated using the MAGMA computer algebra package.

Via the approach presented above one finds the following defining polynomial for F.

T^{8} + (9999991x^{4} + 703275x^{3} + 1430019x^{2} + 1502111x + 6267729) T^{6}+ (9999907x^{6} + 4219650x^{5} + 4300171x^{4} + 4915913x^{3}+ 3056838x^{2} + 7690930x + 4968619) T^{5}+ (9999809x^{8} + 549106x^{7} + 50570x^{6} + 6963813x^{5} + 631870x^{4}+ 2499584x^{3} + 7550175x^{2} + 7984600x + 8893034) T^{4}+ (9999795x^{10} + 4065481x^{9} + 5800988x^{8} + 8738342x^{7} + 5465058x^{6} + 1967241x^{5}+ 2095794x^{4} + 4444654x^{3} + 8381656x^{2} + 2592793x + 8848697) T^{3}+ (9999879x^{12} + 549106x^{11} + 8650912x^{10} + 1059594x^{9} + 9156513x^{8}+ 9340731x^{7} + 7885968x^{6} + 6953996x^{5} + 5734556x^{4}+ 4113592x^{3} + 2896371x^{2} + 9062942x + 3377385) T^{2}+ (9999971x^{14} + 4219650x^{13} + 7180437x^{12} + 8192553x^{11} + 6767478x^{10}+ 4323463x^{9} + 3837644x^{8} + 4788445x^{7} + 3851x^{6} + 4376874x^{5}+ 1282375x^{4} + 5472015x^{3} + 6147853x^{2} + 4182920x + 4970743) T + 10000012x^{16} + 703275x^{15} + 7150095x^{14} + 2321271x^{13} + 9233281x^{12} +2141319x^{11} + 5465933x^{10} + 1278572x^{9} + 3721128x^{8} + 1041848x^{7}+ 191179x^{6} + 8523379x^{5} + 9649232x^{4} + 2099202x^{3} + 5892994x^{2}+ 9327110x + 3852461

One can check that F has genus 7 and that l divides the order of Cl^{0}(F).

Moreover, F has at least two Weierstrass places of degree 1. One of these places is given by the simultaneous vanishing of x+7735061 and T +3901461, the other by the simultaneous vanishing of x + 8799748 and T + 1933887. The first pole number is 7 in both cases.

The reader should be warned however that in a similar manner one can also give examples such that F does not have any Weierstrass place of degree 1.

8 Conclusions

We showed that in principle the GHS attack can be generalized from elliptic curves over finite non-prime fields of characteristic 2 to (hyper-)elliptic curves over finite non-prime fields of arbitrary characteristic – provided that the extension degree in consideration is odd. We then analyzed the genera of the resulting curves for the case that the characteristic is odd.

For elliptic curves and applications of the GHS attack with respect to prime extension degree n we showed: For n ≥ 11, the size of Cl^{0}(F) is so large that the attack fails unless there is a breakthrough in the solution of the DLP in class groups of high genus curves.

However for n = 5 and n = 7, there exist elliptic curves such that the genus of F is 5 respectively 7. For these examples, explicit equations of the resulting fields F can be derived. These results are optimal in the sense that the degree 0 class group of F is then up to small subgroups isomorphic to the group of rational points on the elliptic curve. It would now be an interesting task to try to break the DLP in the class groups of the resulting fields F using index calculus methods. However, before one can do so, the known index calculus attacks first have to generalized from hyperelliptic to more general curves to cope with the fact that the explicit equations we derived are not hyperelliptic.

Finally, we would like to stress that it might be possible to apply other methods than the GHS attack to transform the original DLP into potentially easier DLPs in class-groups of curves of higher genera over smaller fields. In particular for elliptic curves E′, just as in even characteristic, it might be possible to use the “extended GHS attack”; see [6]. Here, one first applies an isogeny and then uses the GHS attack for the isogenous curve.

A The GHS attack and the Weil restriction ^{8}

The GHS attack can be viewed as a special case of Frey’s “Weil descent” idea; cf. [3]. This idea is based on the idea of finding “nice” smooth, projective, irreducible k-curves X which are (over k) birational to curves on the “Weil restriction” W/k of H′ with respect to K|k and then trying to transform the DLP from Cl^{0}(H′) into a DLP in Cl^{0}(X). More concretely, if E′ = H′ is an elliptic curve, the original idea was to transform the DLP in E′(K) into the DLP in W (k) (by the definition of W, E′(K) ≃ W (k)), and from there to Jac(X)(k) ≃ Cl^{0}(X) by pull-back.

Originally, the consideration of the function field F (in characteristic 2) was motivated by the fact that it is the function field of a curve on the Weil restriction W/k. In this appendix, we make the relation between Frey’s “Weil descent” idea and the GHS attack a little bit more explicit (and thereby try to point out a common inaccuracy concerning the GHS attack).

Let us first recall the definition of the Weil restriction.

Let S′ ⟶ S be a finite, flat morphism of locally noetherian schemes, let Y′ be a (quasi)-projective S′-scheme.

It is well known that there exists a (quasi)-projective S-scheme W = Res_{S}^{S′}(Y′), called the Weil restriction of Y′ with respect to S′ ⟶ S, with the following universal property (for a proof see [1, 7.6]):

There is a S′-morphism w : W ×_{S} S′ ⟶ Y′ such that: For all Sschemes X and all K-morphisms c : X ×_{S} S′ ⟶ Y′, there exists a unique S-morphism b : X ⟶ W such that c = w ∘ (b ×_{S} id_{S′}). (Conversely, any b : X ⟶ W defines in a unique way a c : X ×_{S} S′ ⟶ Y′. In fact, set c := w ∘ (b ×_{S} id_{S′}).)

8In this appendix, we use the theory of arithmetic algebraic geometry as in [10].

As usual, W and w are unique up to a unique isomorphism. (The Weil restriction is usually defined as a representing object of the contravariant functor Hom_{S′}(− ⊗_{S} S′, Y′) from the category of S-schemes to the category of sets; cf. [1, 7.6]. The above mentioned universal property is an easy reformulation of this definition.)

Additionally, if S′ ⟶ S corresponds to an extension of fields K|k and Y′ is a K-variety, the Weil restriction W is a k-variety. Moreover, if Y′ is geometrically reduced or geometrically irreducible or smooth, so is W, and if Y′ is a abelian K-variety, (e.g. an elliptic curve), W is an abelian k-variety.

If S′ and S are connected and S′ ⟶ S is Galois (in the sense of [9, V]), then W ×_{S} S′ is naturally isomorphic to ∏_{σ∈Aut(S′⟶S)} σ(Y′), and under this isomorphism, b ×_{S} id_{S′} : X ×_{S} S′ ⟶ Y′ is given by (σ(c))_{σ∈Aut(S′⟶S)}. Here, σ(Y′) is Y′ regarded as a S′ scheme via the structure morphism

Y′ ⟶ S′ ⟶^{σ} S′.

We keep the notations of the article. We do not make an assumption on the characteristic of k, and we do not assume that n = [K : k] is odd. However, we assume that as in Proposition 3, a function field F |k which is linearly disjoint from K|k and satisfies K ⊗_{k} F ≃ KF = F′ exists. ^{9}

Let W := Res_{k}^{K}(H′) be the Weil restriction of H′ with respect to K|k. Under the bijection between isomorphism classes of function fields and

isomorphism classes of normal, complete (projective), irreducible curves the field F corresponds to a normal (smooth, non-singular), projective, irreducible k-curve X.

As K ⊗_{k} F ≃ KF, the extension KF |K(H′) induces a covering (i.e. a finite morphism) c : X_{K} = X ⊗_{k} K ⟶ H′, and by the universal property of W this covering corresponds to a non-constant k-morphism from X to W.

We now describe this morphism more concretely. The extension K(H′)|K(x) corresponds to a covering H′ ⟶ ℙ_{K}^{1}. Let Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) be the Weil restriction of H′ with respect to ℙ_{K}^{1} ⟶ ℙ_{k}^{1}. This is a K-curve which is (in general) reducible. ^{10} By the universal property of W = Res_{k}^{K}(H′), the universal morphism Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) ⊗_{k} K ≃ Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) ×_{ℙ_{k}^{1}} ℙ_{K}^{1} ⟶ H′ cor-

responds to a morphism Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) ⟶ Res_{k}^{K}(H′).

By the universal property of Res_{k}^{K}(ℙ_{K}^{1}), the identity id : ℙ_{K}^{1} ⟶ ℙ_{K}^{1} corresponds to a morphism ℙ_{k}^{1} ⟶ Res_{k}^{K}(ℙ_{K}^{1}) which is a closed immersion (see [1, 7.6, p. 197]), and Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) is naturally isomorphic to Res_{k}^{K}(H′)×_{Res_{k}^{K}(ℙ_{K}^{1})}

9For linear disjointness see [13, VIII, §3]. Note that if A is a field, B|A is an algebraic extension of fields and C|A is any extensions of fields, then the question whether B|A and C|A are linearly disjoint (in some common overfield) is equivalent to whether B ⊗_{A} C is a field. In particular it is independent of the chosen common overfield of B and C.

10Let H′ be an elliptic K-curve as in [8] (denoted there by E). Then in the situation of [8], the affine curve curve 𝒞 studied in [8] is an affine open part of Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′).

ℙ_{k}^{1}. The above morphism Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) ⟶ Res_{k}^{K}(H′) is induced by the mor-

phism ℙ_{k}^{1} ⟶ Res_{k}^{K}(ℙ_{K}^{1}) via base-change, and as “closed immersion” is stable under base-change, it it is also a closed immersion.

Now, the covering c : X_{K} ⟶ H′ induces a morphism X ⟶ Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′),

and the morphism X ⟶ Res_{k}^{K}(H′) factors through this morphism. ^{11} The following argument shows that X is birational to its image in Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′). We only have to check this after base change. After base change K|k,

the morphism X ⟶ Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) is given by

(σ_{K|k}^{i}(c))_{i=0}^{n−1} : X_{K} ⟶ H′ ×_{ℙ_{K}^{1}} σ_{K|k}(H′) ×_{ℙ_{K}^{1}} ⋯ ×_{ℙ_{K}^{1}} σ_{K|k}^{n−1}(H′).

(Where σ_{K|k} : Spec(K) ⟶ Spec(K) is the automorphism corresponding to σ_{K|k} : K ⟶ K.)

On the total quotient rings, this morphism induces a homomorphism

K(H′) ⊗_{K(x)} K(σ_{K|k}(H′)) ⊗_{K(x)} ⋯ ⊗_{K(x)} K(σ_{K|k}^{n−1}(H′)) ⟶ F′.

By the very definition of F′, this homomorphism is surjective, and it follows that X_{K} is birational to its image, i.e. it is the normalization of its image.

It follows also that X is the normalization of its image on W. Furthermore, one can show that – in the case that H′ is an elliptic curve – the GHS-conorm-norm homomorphism is the same homomorphism as the one suggested by Frey (see above).

Not only the field F corresponds to a curve on the Weil restriction – whenever one is given a function field A|k, linearly disjoint to K|k, and a finite extension K ⊗_{k} A ≃ KA|K(H′), one obtains a smooth, projective, irreducible k-curve X with a covering X_{K} ⟶ H′. This induces a nonconstant k-morphism X ⟶ W.

On the other hand, let X be a smooth, projective, irreducible k-curve with a k-morphism onto a k-curve on W and assume that X_{K} is also irreducible. Then the morphism X ⟶ W induces a covering X_{K} ⟶ H′, and this induces an extension K(X_{K})|K(H′) of function fields. If we set A := k(X), we obtain a function field A|k, linearly disjoint to K|k, and an extension K ⊗_{k} A ≃ KA|K(H′).

11Although it is stated correctly in [8] that the curve Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) is (in general) reducible, some authors seem to confuse Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) and its components. See for example the introductions to [6], [12], [16].

In particular, the proof of the existence of the function field F (our notation) given in [5, 4.2 and 4.5] is not correct as the author confuses (in [5, 4.2]) the curve Res_{ℙ_{k}^{1}}^{ℙ_{K}^{1}}(H′) (our notation) with its components.

Moreover, one can show that if H′ is an elliptic curve, just like in the GHS attack, the homomorphism N_{K(X_{K})|k(X)} ∘ Con_{K(X_{K})|K(H′)} : H′(K) ≃ Cl^{0}(K(H′)) ⟶ Cl^{0}(k(X)) is the same homomorphism as the one suggested by Frey.

We thus obtain a possible reinterpretation of Frey’s “Weil descent” idea in terms of covering theory of curves.

It is an interesting task to find other methods than the GHS attack for constructing suitable regular function fields A|k with extensions KA|K(H′), or – what amounts to the same – to find suitable geometrically irreducible kcurves on the Weil restriction of H′ with respect to K|k. But this is beyond the scope of this article.

Acknowledgments

It is a pleasure for me to thank G. Frey for introducing me to the subject and for fruitful discussions. I thank F. Hess for a discussion concerning Lemma 2.

The results in this article are based on results of my doctoral thesis. The thesis was supported by the Friedrich-Naumann-Stiftung, the Deutsche Forschungsgemeinschaft DFG and the Volkswagen Stiftung.

References

[1] S. Bosch, W. Lütkebohmert, and W. Raynaud. Néron Models. Springer-Verlag, Berlin, 1980.

[2] A. Enge and P. Gaudry. A general framework for subexponential discrete logarithm algorithms. Acta. Arith., 102:83–103, 2002.

[3] G. Frey. How to disguise an elliptic curve (Weil descent). Talk at the 2nd Elliptic Curve Cryptography Workshop (ECC), 1998.

[4] G. Frey and H.-G. Rück. A remark concerning m-divisibility and the discrete logarithm problem in divisor class groups. Math. Comp., 62:865–874, 1994.

[5] S. Galbraith. Weil Descent Of Jacobians. In D. Augot and C. Carlet, editors, Electronic Notes in Discrete Mathematics, volume 6. Elsevier Science Publishers, 2001.

[6] S. Galbraith, F. Hess, and N. Smart. Extending the GHS Weil-Descent Attack. In Eurocrypt 2002, LNCS 2332, pages 29–44. Springer-Verlag, New York and Berlin, 2002.

[7] P. Gaudry. An algorithm for solving the discrete log problem on hyperelliptic curves. In Advances in Cryptology, Eurocrypt 2000, LNCS 1807, pages 19–34, New York and Berlin, 2000. Springer-Verlag.

[8] P. Gaudry, F. Hess, and N. Smart. Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptology, 15, 2002.

[9] A. Grothendieck. Séminaire de Geometrie Algebrique 1960-61: Revêtements Etales et Groupe Fondamentale (SGA I). Institut des Hautes Etudes Scientifiques, 1961.

[10] R. Hartshorne. Algebraic Geometry. Springer-Verlag, New York, 1977.

[11] B. Huppert. Endliche Gruppen. Springer-Verlag, Berlin, 1967.

[12] M. Jacobson, A. Menezes, and A. Stein. Solving Elliptic Curve Discrete Logarithm Problems Using Weil Descent. J. Ramanujan Math. Soc., 16, 2001.

[13] S. Lang. Algebra (Third Edition). Addison-Wesley Publishing Company, 1993.

[14] M. Maurer, A. Menezes, and E. Teske. Analysis of the GHS Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree. LMS Journal of Computation and Mathematics, 5:127–174, 2002.

[15] A. Menezes, T. Okomoto, and S. Vanstone. Reducing elliptic curve logarithms to logarithms in finite fields. IEEE Transactions on Information Theory, 39:1639–1646, 1993.

[16] A. Menezes and M. Qu. Analysis of the Weil Descent Attack of Gaudry, Hess and Smart. In Topics in Cryptology - CT-RSA 2001, LNCS 2020, pages 308–318. Springer-Verlag, 2001.

[17] S. Paulus and H.-G. Rück. Real and Imaginary Quadratic Representations of Hyperelliptic Function Fields. Math. Comp., 227:1233–1241, 1999.

[18] H. Popp. Fundamentalgruppen algebraischer Mannigfaltigkeiten. Springer-Verlag, Berlin, 1970.

[19] H.-G. Rück. On the discrete logarithm in the divisor class group of curves. Math. Comp., 68:805–806, 1999.

[20] I. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Math. Comp., 67:353– 356, 1998.

[21] H. Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, Berlin, 1993.

[22] Thériault. Weil-Descent Attack for Kummer Extensions. forthcomming.