ńņš. 6 |

to be small. What remains is then a complexity of O(q g+1 ).

This idea of reducing the factor basis has been pushed further by ThĀ“riault

e

[325]: by considering some of the elements as ālarge primes,ā the complexity

4

can be reduced to O(q 2ā’ 2g+1 ). The practical use of this last version is still to

be studied.

VII.7. PRACTICAL CONSIDERATIONS 149

In the following table, we compare the complexities of these two variants

to the complexity of Pollard rho algorithm, which has a complexity in the

square root of the group size, namely O(q g/2 ).

g 1 2 3 4 5 6 7 8

1/2 3/2 2 5/2 3 7/2

q4

rho q q q q q q q

q q 4/3 q 3/2 q 8/5 q 5/3 q 12/7 q 7/4 q 16/9

Index

ThĀ“riault q 2/3 q 6/5 q 10/7 q 14/9 q 18/11 q 22/13 q 26/15 q 30/17

e

We conclude that for genus 4 curves, the index-calculus method provides

a faster attack than the generic Pollard rho algorithm, and using ThĀ“riaultā™s

e

method, even genus 3 curves seem to be subject to the attack.

VII.7. Practical Considerations

We mention a few improvements that do not change the complexity but

that can make big diļ¬erences in a practical implementation. First of all it is

important that the basic arithmetic be as fast as possible. Once the Jacobian

group law, the polynomial factorization and the arithmetic in Z/N Z have

been optimized, here are some more tricks.

ā¢ A hyperelliptic curve always comes with its hyperelliptic involution

which can be computed almost for free. As a consequence, there is no

need to store both a divisor and its opposite in the factor basis: if the

opposite occurs in the smooth divisor, just put a ā’1 instead of a 1 in the

matrix. More generally, if the curve has other cheap automorphisms

(for instance if this is a Koblitz curve), then only one element in each

orbit needs to be stored in F.

ā¢ The search for relations is trivially parallelized by taking a diļ¬erent

random walk on each processor.

ā¢ As said above, testing if a divisor is smooth does not require the full

factorization of the a-polynomial. In fact, in principle, a squarefreeness

test has to be run before going to the Distinct-Degree-Factorization

step. But in our case, this additionnal test is not necessary: non-

squarefree polynomials are rare and saving this computation more than

compensates the loss of these potentially smooth divisors.

ā¢ In the case of the reduced basis (when the genus is very small), we

can choose to keep in the basis the elements with small abscissa. Then

a reduced divisor of degree g can be written on this basis only if its

degree g ā’ 1 coeļ¬cient is small. Indeed, the divisor is smooth if and

only if its a-polynomial splits completely and all its roots are small,

and the degree g ā’ 1 coeļ¬cient is the sum of the roots. This criterion

is much faster than the Distinct Degree Factorization algorithm and

enables one to eliminate most of the non-smooth divisors.

ā¢ If the group law is more costly than the smoothness test, it can be

sped-up as follows: between each step of the classical random walk, we

150 VII. HYPERELLIPTIC CURVES

introduce small steps where we add an element of the factor basis to

the current element. We continue the small steps until a smooth divisor

is found. Then we can write a relation in the matrix. The drawback is

that there is one more term in the matrix corresponding to the multiple

of the element that we added. On the other hand, most of the time is

spent in small steps in which we add a weight one divisor. Therefore

the group law is much faster.

ā¢ The implementation of a fast sparse linear algebra algorithm is not a

simple task. Our case is diļ¬erent from the integer factorization case,

where the matrix is deļ¬ned over F2 . Here, the base ring is not that

small and most of the tricks do not apply. If parallelization is not nec-

essary, then Lanczosā™s algorithm is probably the best choice. Otherwise

the Block-Wiedemann algorithm can give better results (see [328] for

recent experiments).

ā¢ If the genus is large, so that the optimal B is not one, a precise non-

asymptotical analysis must be done to ļ¬nd the best value for B. This

was done in [181].

CHAPTER VIII

Weil Descent Attacks

F. Hess

Weil descent attacks provide means of attacking the DLP for elliptic

curves, or for more general algebraic curves such as hyperelliptic curves, when

they are used over ļ¬nite extension ļ¬elds, i.e., non-prime ļ¬elds.

The application of the original basic idea, the Weil restriction of scalars for

elliptic curves, to cryptography and the ECDLP was ļ¬rst suggested in [124].

An important step forward was made in [145] using explicit covering tech-

niques, relating the ECDLP to a potentially easier HCDLP. Since then, vari-

ations, generalizations and ramiļ¬cations of the employed methodology have

been investigated in some detail.

The aim of this chapter is to explain the basic ideas, to summarize the

main results about Weil descent attacks for elliptic curves and to discuss the

relevance to ECC.

VIII.1. Introduction ā” the Weil Descent Methodology

Throughout this chapter we let K/k denote an extension of ļ¬nite ļ¬elds

of degree n. The characteristic and cardinality of k are p and q = pr , respec-

tively.

VIII.1.1. Curves in the Weil Restriction. Let E be an elliptic curve

over K. The initial motivation for the Weil descent attacks came from the

consideration of the Weil restriction ResK/k (E) of E with respect to K/k,

suggested by Frey [124].

The Weil restriction ResK/k (E) is an abelian variety of dimension n deļ¬ned

over k, as opposed to E, which is an abelian variety of dimension one over

K. The group ResK/k (E)(k) of k-rational points of ResK/k (E) is isomorphic

to the group E(K) of K-rational points of E and thus contains an equivalent

version of any DLP in E(K). Given E and K/k and the deļ¬ning equations,

the group law of ResK/k (E) and the isomorphism of the point groups can be

computed without much diļ¬culty. We do not need the details here and refer

to [124], [137], [145] instead.

The main idea now is the following. An algebraic curve C 0 and a map

C 0 ā’ ResK/k (E) deļ¬ned over k lead to a map Ļ : Jac(C 0 ) ā’ ResK/k (E), due

to the functorial property of Jac(C 0 ). If we take such a curve C 0 , we may

be able to lift a given DLP from ResK/k (E)(k) to Jac(C 0 )(k). The DLP in

151

152 VIII. WEIL DESCENT ATTACKS

Jac(C 0 )(k) can then be attacked, possibly more eļ¬ciently, by index-calculus

methods on C 0 (k) than by the Pollard methods on E(K), the main point

being that C 0 is deļ¬ned over the small ļ¬eld k.

In order to ļ¬nd C 0 one can intersect ResK/k (E) with suitable hyperplanes,

and we remark that there is a fairly natural choice of such a hyperplane.

It is then a priori not clear whether the DLP can be lifted to Jac(C 0 )(k);

however some evidence is given by the fact that ResK/k (E) is simple in many

interesting cases [105]. Another quite diļ¬cult problem is how to actually lift

the DLP to Jac(C 0 )(k) using explicit equations. We refer to [137] for a more

detailed discussion.

VIII.1.2. Covering Techniques. Covering techniques boil down to a re-

formulation of the method of the previous section at the level of curves,

their function ļ¬elds and Galois theory. Curves are basically one-dimensional

objects as opposed to the above Weil restriction and Jacobians, and their

function ļ¬elds can furthermore be viewed as āequationlessā substitutes. This

leads to a much easier and algorithmically accessible treatment of the pre-

vious section and was ļ¬rst applied by Gaudry, Hess and Smart in [145], an

approach which is now referred to as the GHS attack.

We consider the following general situation. Let E denote an elliptic

function ļ¬eld over K and C a ļ¬nite extension ļ¬eld of E such that there is

a ļ¬eld automorphism Ļ which extends the Frobenius automorphism of K/k

and has order n on C. We say that Ļ is a Frobenius automorphism of C

with respect to K/k and denote the ļ¬xed ļ¬eld of Ļ by C 0 . The extension

C/C 0 has degree n and the exact constant ļ¬eld of C 0 is k. Choosing suitable

deļ¬ning equations we can regard E, C and C 0 as the function ļ¬elds of curves

E, C and C 0 , respectively, where E is an elliptic curve, E and C are deļ¬ned

over K and C 0 is deļ¬ned over k. We denote the divisor class groups of

E, C and C 0 by Pic0 (E), Pic0 (C) and Pic0 (C 0 ) so that E(K) ā¼ Pic0 (E)

=

K K k K

ā¼ Pic0 (C 0 ). The conorm and norm maps of function ļ¬eld

0

and Jac(C )(k) = k

extensions yield homomorphisms ConC/E : Pic0 (E) ā’ Pic0 (C) and NC/C 0 :

K K

PicK (C) ā’ Pick (C ). Figure VIII.1 contains a graphical presentation of the

0 0 0

situation.

Pic0 (C)

C K

Con N

Pic0 (E) Pic0 (C 0 )

C0

E K k

Figure VIII.1. Diagram of function ļ¬elds and divisor class groups

The composition of NC/C 0 , ConC/E and the isomorphism between Pic0 (E)

k

and E(K) is a homomorphism from E(K) to Pic0 (C 0 ) which we denote by Ļ.

k

VIII.2. THE GHS ATTACK 153

Using Ļ, a discrete logarithm problem Q = Ī»P in E(K) is mapped to the dis-

crete logarithm problem Ļ(Q) = Ī»Ļ(P ) in Pic0 (C 0 ), where it can be attacked

k

possibly more eļ¬ciently than in E(K), since it is deļ¬ned over the small ļ¬eld

k and index-calculus methods can be applied. Of course, P and Q should

not be in the kernel of Ļ. The index-calculus methods depend exponentially

or subexponentially on the genus g of C 0 ; see Chapter VII, [92], [117] and

[169]. There are thus three main questions.

1. How can such C and Ļ be constructed?

2. Does Ļ preserve the DLP?

3. Is the genus of C 0 small enough?

The construction of such a C and Ļ can be achieved quite generally us-

ing techniques from Galois theory. For example, one determines a suitable

rational subļ¬eld K(x) of E and deļ¬nes C to be the splitting ļ¬eld of E over

k(x). A suļ¬cient condition for the existence of a suitable Ļ is then that n is

coprime to the index [C : K(x)]. For the sake of eļ¬ciency and explicitness,

Artinā“Schreier and Kummer extensions are the most prominent constructions

used.

The question of whether Ļ preserves the DLP can be answered aļ¬rma-

tively in most cases of interest [104], [168].

Finally, the genus can be explicitly determined or estimated for the em-

ployed Artinā“Schreier and Kummer extensions, given E and n. As it turns

out, the genus is in general exponential in n, and it is smaller only in excep-

tional cases. This is the reason why the Weil descent methodology does not

apply to general or randomly chosen elliptic curves when n is large.

These issues are discussed in detail in the following sections.

VIII.1.3. Remarks. The approaches of Subsections VIII.1.1 and VIII.1.2

are jointly carried out in [145]. For a further discussion of the equivalence of

these two approaches see [103, Chapter 3] and the appendix of [104].

The term āWeil descentā is actually used with a diļ¬erent meaning in

mathematics than we do here and in cryptography. There a āWeil descent

argumentā refers to a special proof technique about the ļ¬eld of deļ¬nition

of a variety, introduced by A. Weil in [347], while here we loosely mean the

transition of an elliptic curve to its Weil restriction and further considerations

by which we hope to solve a DLP more quickly.

VIII.2. The GHS Attack

VIII.2.1. The Reduction. The most important case for practical applica-

tions are elliptic curves in characteristic two. In this section we describe the

reduction of a DLP on such an elliptic curve over K to the divisor class group

of a curve deļ¬ned over k.

We start with an ordinary elliptic curve

Ea,b : Y 2 + XY = X 3 + aX 2 + b (VIII.1)

154 VIII. WEIL DESCENT ATTACKS

with a, b ā K, b = 0. Every isomorphism class of ordinary elliptic curves over

K has a unique representative of the form (VIII.1) under the requirement

that a ā {0, Ļ} where Ļ ā F2u with u = 2v2 (nr) is a ļ¬xed element such

that TrF2u /F2 (Ļ) = 1. In the following we only consider these unique elliptic

curves with a ā {0, Ļ}.

Applying the transformations Y = y/Ė + b1/2 , X = 1/Ė, multiplying by

x x

Ć—

x , substituting x = x/Ī³ for some Ī³ ā K and writing Ī± = a, Ī² = b1/2 /Ī³ we

2

Ė Ė

obtain the Artinā“Schreier equation

y 2 + y = Ī³/x + Ī± + Ī²x. (VIII.2)

On the other hand, reversing the transformations, we can return to equa-

tion (VIII.1) from equation (VIII.2) for any Ī³, Ī² ā K Ć— . This shows that the

function ļ¬eld E = K(Ea,b ) of Ea,b contains and is in fact generated by two

functions x, y satisfying the relation (VIII.2), that is, E = K(x, y). Note that

the transformation backwards is described by the map (Ī³, Ī²) ā’ b = (Ī³Ī²)2

and a = Ī±.

The function ļ¬eld E = K(x, y) is a Galois extension of the rational func-

tion ļ¬eld K(x) of degree two. Furthermore, K(x) is a Galois extension of

k(x) of degree n and the Galois group is generated by the Frobenius auto-

morphism Ļ of K(x) with respect to K/k satisfying Ļ(x) = x. We deļ¬ne the

function ļ¬eld C = CĪ³,Ī±,Ī² to be the splitting ļ¬eld of the extension E/k(x).

Before we state the main theorem about CĪ³,Ī±,Ī² we need some further

m

notation. For z ā K let mz (t) = i=0 Ī»i t ā F2 [t] with Ī»m = 1 be the

i

unique polynomial of minimal degree such that m Ī»i Ļ i (z) = 0. We deļ¬ne

i=0

mĪ³,Ī² = lcm{mĪ³ , mĪ² }.

Recall that if we have a Frobenius automorphism on CĪ³,Ī±,Ī² with respect

to K/k, we take C 0 = CĪ³,Ī±,Ī² to be its ļ¬xed ļ¬eld.

0

Theorem VIII.1. The Frobenius automorphism Ļ of K(x) with respect to

K/k satisfying Ļ(x) = x extends to a Frobenius automorphism of C with

respect to K/k if and only if at least one of the conditions

TrK/F2 (Ī±) = 0, TrK/k (Ī³) = 0 or TrK/k (Ī²) = 0

holds. In this case, we have:

(i) If k(Ī³, Ī²) = K, then

ker(Ļ) ā E(K)[2deg(mĪ³,Ī² )ā’1 ].

(ii) The genus of C 0 satisļ¬es

gC 0 = 2deg(mĪ³,Ī² ) ā’ 2deg(mĪ³,Ī² )ā’deg(mĪ³ ) ā’ 2deg(mĪ³,Ī² )ā’deg(mĪ² ) + 1.

(iii) There is a rational subļ¬eld of C 0 of index min{2deg(mĪ³ ) , 2deg(mĪ² ) }.

(iv) If Ī³ ā k or Ī² ā k, then C 0 is hyperelliptic.

For the proof of Theorem VIII.1 see [145], [168] and Section VIII.2.6.

The following corollary is an immediate consequence of Theorem VIII.1 and

VIII.2. THE GHS ATTACK 155

the fact that mĪ² is not divisible by tā’1 if and only if the given trace condition

holds. A proof is given in [168].

Corollary VIII.2. If Ī³ ā k, then

2deg(mĪ³,Ī² )ā’1 ā’ 1 if TrK/Fqu (Ī²) = 0 where u = 2v2 (n) ,

gC 0 =

2deg(mĪ³,Ī² )ā’1 otherwise.

Similarly with Ī³ and Ī² exchanged.

The construction of C 0 and the computation of images under Ļ can be

made explicit using Artinā“Schreier extensions and the operation of Ļ on C; see

[145], [168] and [165]. This leads to algorithms which are at most polynomial

in gC 0 . Various implementations of this construction are available in the

computer algebra systems Kash and Magma [46], [193], [229].

If the condition of Theorem VIII.1(i) is satisļ¬ed, we see that any large

prime factor of E(K) and hence the DLP in E(K) is preserved under Ļ. Since

there is some freedom in choosing Ī³ and Ī², this can also be achieved if E

is actually deļ¬ned over a subļ¬eld of K. We also remark that there is an

explicit formula for the L-polynomial (or zeta function) of C 0 in terms of the

L-polynomials (or zeta functions) of E and further related elliptic curves; see

[165], [168] and Section VIII.5.3.

The main points of interest are the possible degrees m = deg(mĪ³,Ī² ) and

the relationship to Ī³ and Ī². The eļ¬ciency or feasibility of the attack crucially

depends on this m, and it is therefore sometimes referred to as the āmagicā

number m. Its properties are discussed in Section VIII.2.4.

We conclude this section with some examples.

Example 1: Let k = F2 and K = F2127 = k[w] with w127 + w + 1 = 0.

Consider the elliptic curve

E : Y 2 + XY = X 3 + w2 .

We can choose Ī³ = 1, Ī± = 0 and Ī² = w. Then mĪ³ (t) = t + 1 and mĪ² (t) =

t7 + t + 1 since Ī² 128 + Ī² 2 + Ī² = 0. It follows that mĪ³,Ī² (t) = t8 + t7 + t2 + 1.

All conditions of Theorem VIII.1 are fulļ¬lled. We conclude that C 0 is a

hyperelliptic function ļ¬eld over k of genus 127. Using the programs mentioned

above we compute a representing curve

C 0 : y 2 + (x127 + x64 + 1)y = x255 + x192 + x128 .

A diļ¬erent model is given by C 0 : y 2 + (x128 + x64 + x)y = (x128 + x64 + x).

Example 2: Let k = F25 = F2 [u] and K = F2155 = F2 [w] with u5 + u2 + 1 = 0

and w155 + w62 + 1 = 0. Consider the elliptic curve

E : Y 2 + XY = X 3 + Ī“

156 VIII. WEIL DESCENT ATTACKS

with

w140 + w134 + w133 + w132 + w130 + w129 + w128 + w127 + w117 +

w113 + w111 + w110 + w102 + w97 + w96 + w78 + w74 + w72 +

Ī“ = 70

w + w63 + w49 + w48 + w47 + w41 + w39 + w36 + w35 + w34 +

w32 + w24 + w17 + w10 + w9 + w8 + w5 .

Similarly to the previous example we can choose Ī³ = 1, Ī± = 0 and Ī² = Ī“ 1/2 .

Then mĪ³ (t) = t + 1 and mĪ² (t) = t15 + t11 + t10 + t9 + t8 + t7 + t5 + t3 + t2 + t + 1.

It follows that mĪ³,Ī² (t) = mĪ³ (t)mĪ² (t). All conditions of Theorem VIII.1 are

fulļ¬lled and we conclude that C 0 is a hyperelliptic function ļ¬eld over k of

genus 32767.

Example 3: In Example 2 we can also choose

w140 + w132 + w128 + w125 + w101 + w94 +

Ī³=

w78 + w70 + w64 + w63 + w47 + w39 + w35 ,

Ī± = 0 and Ī² = Ī“ 1/2 /Ī³. Then mĪ³,Ī² (t) = mĪ³ (t) = mĪ² (t) = t5 + t2 + 1.

All conditions of Theorem VIII.1 are fulļ¬lled and we conclude that C 0 is a

function ļ¬eld over k of genus 31. Using the programs mentioned above we

compute a representing curve

y 32 + u22 y 16 + u3 y 8 + u9 y 4 + u13 y 2 + u24 y + (u24 x24 + u9 x16

C:

0

= 0.

+u25 x12 + u30 x10 + u3 x9 + u26 x7 + u23 x6 + u15 x4 + u30 )/x8

The last two examples show that the choice of Ī³ and Ī² can make a very

signiļ¬cant diļ¬erence for the size of the resulting genus.

VIII.2.2. The Asymptotic Attack. Let us assume that Ī³ ā k. According

to Theorem VIII.1(iv) and Corollary VIII.2, the resulting function ļ¬eld C 0 is

hyperelliptic and has genus bounded by 2nā’1 ā’ 1 or 2nā’1 since mĪ³,Ī² (t) divides

tn ā’ 1, and this holds independently of q. Combining this with the theorem

of Gaudry, Theorem VII.10, and the improvements of Harley for very small

genera we obtain the following, slightly improved main result of [145].

Theorem VIII.3. Let E : Y 2 + XY = X 3 + Ī±X 2 + Ī² denote an elliptic curve

over K = Fqn such that

n is odd or TrK/F2 (Ī±) = 0 or TrK/k (Ī²) = 0.

Let #E(K) = h, where is a large prime. One can solve the discrete log-

arithm problem in the -cyclic subgroup of E(K) in time O(q 2 ) where the

complexity estimate holds for a ļ¬xed value of n ā„ 4 as q tends to inļ¬nity.

The complexity estimate is in fact always slightly better than O(q 2 ). This

time has to be compared with the running time of the Pollard methods on

E(K), which are O(q n/2 ). It follows that the DLP can be solved (much) faster

using the GHS attack when n ā„ 4 is ļ¬xed and q tends to inļ¬nity. By the

VIII.2. THE GHS ATTACK 157

recent results of ThĀ“riault [325] improving index-calculus for hyperelliptic

e

curves further we ļ¬nd that the DLP on C 0 can be solved in time O(q 10/7 ) and

O(q 14/9 ) if the genus is 3 or 4, respectively. Since 10/7 < 3/2 < 14/9, this

means that the DLP on E can also be solved asymptotically faster using the

GHS attack when n = 3 and TrK/k (Ī²) = 0, using Corollary VIII.2.

It is now natural to ask, at what sizes of q does the crossover point lie.

A computer experiment comparing the Pollard times against index-calculus

times for n = 4 has been carried out in [145]. The index-calculus method

proves to be faster by a factor of about 0.7 for an 84-bit elliptic curve. Since

the crossover point is already reached for such small ļ¬eld sizes, it can be

concluded that for n = 4 the DLP is solved faster using the GHS attack also

in practical instances and not only asymptotically. The crossover point for

larger values of n however will be much higher (see for example [311]).

VIII.2.3. Special Attacks. The previous section applies uniformly to all

elliptic curves when n is small and q large enough, so that gC 0 is relatively

small. But it could also apply for cases where n is large and deg(mĪ³,Ī² ) happens

to be suļ¬ciently small. More generally, we could allow arbitrary Ī³ ā K,

resulting in non-hyperelliptic curves C 0 , and consider only those cases where

gC 0 is suļ¬ciently small. Moreover, the running time of the algorithm behind

Theorem VIII.3 depends exponentially on gC 0 , since low genus index-calculus

methods are used. But there are also high genus index-calculus methods

available, see [92], [117] and [169], whose asymptotic running time depends

1/2+o(1)

subexponentially on gC 0 and is roughly of the form q gC 0 . In Example 1

we have gC 0 = n, and for such cases with large n the high genus index-calculus

attack would be much more eļ¬cient than the Pollard methods on the original

elliptic curve.

In the following sections we investigate for which special values of n

and which special families of elliptic curves an index-calculus attack can be

mounted which is (possibly) faster than the Pollard methods. A summary

of the results of practical interest also using the methods of Section VIII.3 is

given in Section VIII.4.

VIII.2.4. Analysis of Possible Genera and Number of Curves. Pos-

sible genera of C 0 and the number of corresponding elliptic curves have been

investigated in detail in [233], [241] for the case Ī³ ā k. We give here a more

general and simpliļ¬ed discussion allowing for arbitrary Ī³ ā K.

We ļ¬rst analyse the various possibilities for mĪ² (t) and Ī² in more detail.

It is helpful to introduce the following standard technique from linear algebra

(see also [134] and [241]). We deļ¬ne a multiplication of polynomials h(t) =

d d

i=0 Ī»i t ā k[t] and ļ¬nite ļ¬eld elements z ā K by h(t)z =

i i

i=0 Ī»i Ļ (z). This

makes the additive group of K into a so-called k[t]-module. The polynomials

mĪ² (t) are then by deļ¬nition polynomials in F2 [t] of smallest degree such that

mĪ² (t)Ī² = 0.

158 VIII. WEIL DESCENT ATTACKS

Let w ā K be a normal basis element for K/k. The theorem of the

normal basis is equivalent to the statement that K is a cyclic (or āone-

dimensionalā) k[t]-module with annihilator tn ā’ 1, that is, K = {h(t)w :

h(t) ā k[t] and deg(h(t)) < n} ā¼ k[t]/(tn ā’ 1) is generated by one element.

=

We deļ¬ne Bm(t) = {Ī³ ā K : mĪ³ (t) = m(t)} for m(t) ā k[t] and let Ī¦(m(t))

be the number of polynomials of degree less than n in k[t] coprime to m(t).

These observations and deļ¬nitions give the following theorem.

Theorem VIII.4. For every Ī² ā K it holds that mĪ² (t) is a divisor of tn ā’ 1

in F2 [t]. Conversely, let m(t) be a divisor of tn ā’ 1 in F2 [t]. Then

Bm(t) = {h(t)Ī³0 : h ā k[t], deg(h) < deg(m) and gcd{h, m} = 1}

with Ī³0 = ((tn ā’ 1)/m(t))w and

s

(q ji di ā’ q (ji ā’1)di ),

#Bm(t) = Ī¦(m(t)) =

i=0

where m(t) = s fiji is the factorization of m(t) into irreducible polynomials

i=0

fi ā F2 [t] with deg(fi ) = di .

We remark that the situation is completely analogous to the possibly more

familiar case of ļ¬nite cyclic groups. Consider an additive cyclic group G with

generator g of order M . Replace K by G, w by g, k[t] by Z, tn ā’ 1 by M and

k[t]/(tn ā’ 1) by Z/(M ) and let m be a divisor of M . The analogous version of

Theorem VIII.4 then tells us, for example, that the elements Ī³ ā G of precise

order mĪ³ = m are given in the form hĪ³0 with 0 ā¤ h < m, gcd{h, m} = 1 and

Ī³0 = (M/m)g.

Using Theorem VIII.4, all possible mĪ² (t), the corresponding Ī² and their

cardinalities can be easily computed. Combining the various possibilities for

mĪ³ (t) and mĪ² (t) yields all possible mĪ³,Ī² (t) and genera gC 0 . But we also

require that k(Ī³, Ī²) = K, so not all combinations do actually occur. We

can obtain sharp lower bounds for gC 0 as follows. Let n1 = [k(Ī³) : k] and

n2 = [k(Ī²) : k]. Then n = lcm{n1 , n2 }. Furthermore, mĪ³ (t) divides tn1 ā’ 1

but does not divide ts ā’ 1 for any proper divisor s of n1 , and analogously

for mĪ² (t). Enumerating the smallest possibilities for mĪ³ (t) and mĪ² (t) for all

n1 , n2 then yields sharp lower bounds.

The following theorem contains some statistics about the possible genera.

Theorem VIII.5. Assume that the trace condition of Theorem VIII.1 and

k(Ī³, Ī²) = K holds. Then n ā¤ gC 0 ā¤ 2n ā’ 1 and gC 0 ā„ 65535 for all primes

100 ā¤ n ā¤ 1000 except gC 0 = 127 for n = 127 and gC 0 = 32767 for n = 151.

The lower bound is attained if and only if

n ā {1, 2, 3, 4, 7, 15, 21, 31, 63, 93, 105, 127, 217, 255, 381, 465, 511, 889}.

Among these, the values n ā {1, 2, 3, 4, 7, 15, 31, 63, 127, 255, 511} yield an

(elliptic or) hyperelliptic function ļ¬eld C 0 .

VIII.2. THE GHS ATTACK 159

The proof of Theorem VIII.5 follows the above observations and requires

explicit calculations using a computer. We remark that n ā¤ gC 0 ā¤ 2n for 43

odd and even values of n ā {1, . . . , 1000}.

Theorem VIII.5 basically means that the GHS attack in even characteristic

fails for large prime values of n since it does not appear that the DLP can be

solved more easily in a curve of genus ā„ 65535, albeit deļ¬ned over k instead

of K. On the other hand, composite values of n and in particular the special

values given in the list appear susceptible. Note that the extension degree 155

of Example 3 is not shown in Theorem VIII.5; however, n = 31 is a factor of

155 which was indeed used to construct a curve of genus 31.

Let us now look at the proportion of elliptic curves which yield a small

gC 0 when n is large. In view of the running time for high genus index-calculus

methods, a rough estimation of possibly interesting genera is gC 0 ā¤ n2 . The

following lemma contains a crude upper bound for the proportion of possibly

susceptible elliptic curves.

Lemma VIII.6. Let Ļ ā„ 1. The probability that a C 0 associated to a ran-

dom elliptic curve Ea,b has a genus at most nĻ is bounded by approximately

22Ļ log2 (n)+2 q 2Ļ log2 (n) /q n .

Proof. It is not diļ¬cult to see that 2mā’d1 + 2mā’d2 ā¤ 2mā’1 + 2 under the

side conditions 1 ā¤ d1 , d2 ā¤ m, d1 + d2 ā„ m. Thus with d1 = deg(mĪ³ ),

d2 = deg(mĪ² ) and Theorem VIII.1(ii) it follows that n2 ā„ gC 0 ā„ 2mā’1 ā’ 1

and m ā¤ log2 (nĻ + 1) + 1. Now there are at most 2m+1 polynomials over F2

of degree ā¤ m, so there are at most 22m+2 pairs (mĪ³ , mĪ² ) such that mĪ³,Ī² =

lcm{mĪ³ , mĪ² } has degree ā¤ m. Consequently there are at most 22m+2 q 2m pairs

(Ī³, Ī²) and thus elements b = (Ī³Ī²)2 . The total number of b is q n , so the result

follows with m ā Ļ log2 (n).

As a result we see that the probability of obtaining a relatively small genus

for a random elliptic curve quickly becomes negligible as n increases.

The following results are additions to Theorem VIII.4 and can be found

in [241].

Lemma VIII.7. Let n be an odd prime. The polynomial tn ā’ 1 factors over

F2 as tn ā’ 1 = (t ā’ 1)Ļn (t) = (t ā’ 1)h1 (t) Ā· Ā· Ā· hs (t), where Ļn (t) denotes the

nth cyclotomic polynomial and the hi (t) are distinct polynomials of a degree

d. Furthermore, d is the order of 2 in (Z/nZ)Ć— and d ā„ log2 (n + 1).

Corollary VIII.8. Let Ī“ ā {0, 1}. For any Ī² ā K, the degree of mĪ² (t) is

of the form deg(mĪ² (t)) = id + Ī“, and there are s (q d ā’ 1)i (q ā’ 1)Ī“ diļ¬erent

i

Ī² ā K such that deg(mĪ² (t)) = id + Ī“.

The corollary follows immediately from Theorem VIII.4 and Lemma VIII.7.

VIII.2.5. Further Analysis and the Decompositions b = Ī³Ī². In the

following let m1 (t), m2 (t) ā F2 [t] denote divisors of tn ā’ 1 such that if ts ā’ 1

160 VIII. WEIL DESCENT ATTACKS

is divisible by m1 (t) and by m2 (t), then s is divisible by n. In other words,

we require K = k(Ī³, Ī²) for every Ī³ ā Bm1 (t) and Ī² ā Bm2 (t) . We abbreviate

this condition on m1 and m2 by the predicate P (m1 , m2 ) and deļ¬ne

Bm1 (t),m2 (t) = {Ī³Ī² : Ī³ ā Bm1 (t) , Ī² ā Bm2 (t) }.

We remark that Bm1 (t),m2 (t) is invariant under the 2-power Frobenius auto-

morphism. To distinguish cases we deļ¬ne the predicate

T (m1 (t), m2 (t)) = (vtā’1 (m1 (t)) = 2v2 (n) or vtā’1 (m2 (t)) = 2v2 (n) ).

Then, let

{Ea,b : a ā {0, Ļ}, b ā Bm1 (t),m2 (t) } if T (m1 (t), m2 (t)),

Sm1 (t),m2 (t) =

{E0,b : b ā Bm1 (t),m2 (t) } otherwise.

Observe that T (m1 (t), m2 (t)) holds true precisely when TrK/k (Ī³) = 0 or

TrK/k (Ī²) = 0. Thus by Theorem VIII.1 and since P (m1 , m2 ) is assumed

to hold true, the set Sm1 (t),m2 (t) contains elliptic curves for which the GHS

reduction applies when using the corresponding Ī³, Ī±, Ī². Letting mĪ³,Ī² (t) =

lcm{m1 (t), m2 (t)} and m = deg(mĪ³,Ī² (t)), the resulting genus satisļ¬es gC 0 =

2m ā’ 2mā’deg(m1 (t)) ā’ 2mā’deg(m2 (t)) + 1.

We say that an elliptic curve Ea,b is susceptible to the GHS attack if

Ea,b ā Sm1 (t),m2 (t) for some āsuitableā choices of m1 (t), m2 (t). Here āsuitableā

means that m1 (t), m2 (t) are such that we expect that the DLP can be solved

more easily in Pick (C 0 ) than by the Pollard methods in Ea,b (K). With regard

to Section VIII.2.3, the main questions then are how to ļ¬nd such suitable

choices of m1 (t), m2 (t), how to determine the cardinality of Sm1 (t),m2 (t) and

how to develop an eļ¬cient algorithm which checks whether Ea,b ā Sm1 (t),m2 (t)

and computes the corresponding decomposition b = Ī³Ī² for Ī³, Ī² ā K with

mĪ³ = m1 and mĪ² = m2 . The following lemma answers these questions in the

case of a composite n.

Lemma VIII.9. Let n = n1 n2 , K1 = Fqn1 and b ā K. Let f1 = tn1 ā’ 1 and

f2 = (t ā’ 1)(tn ā’ 1)/(tn1 ā’ 1).

(i) The following conditions are equivalent.

1. TrK/K1 (b) = 0.

2. There exist Ī³1 , Ī³2 ā K Ć— with

Ī³1 Ī³2 = b, Ī³1 ā K1 and TrK/K1 (Ī³2 ) ā k Ć— .

3. There exist Ī³1 , Ī³2 ā K Ć— with

Ī³1 Ī³2 = b, mĪ³1 dividing f1 , mĪ³2 dividing f2 and vtā’1 (mĪ³2 ) = vtā’1 (f2 ).

(ii) If TrK/K1 (b) = 0, then Ī³1 = TrK/K1 (b) and Ī³2 = b/Ī³1 satisfy conditions

2 and 3 of (i). For any two decompositions b = Ī³1 Ī³2 = Ī³1 Ī³2 as in (i) it

ĖĖ

Ć—

holds that Ī³1 /Ī³1 ā k .

Ė

VIII.2. THE GHS ATTACK 161

(iii) Let m1 divide f1 and m2 divide f2 such that vtā’1 (m2 ) = vtā’1 (f2 ). Then

#Bm1 ,m2 = Ī¦(m1 )Ī¦(m2 )/(q ā’ 1).

(iv) (GHS conditions). In the case of (ii):

1. k(b) = k(Ī³1 , Ī³2 ),

2. TrK/k (Ī³2 ) = 0 if and only if n1 is odd,

3. TrK/k (Ī³1 ) = 0 if and only if vtā’1 (mb ) = 2v2 (n) and n/n1 is odd.

Proof.

(i)

1 ā’ 2. Deļ¬ne Ī³1 = TrK/K1 (b) and Ī³2 = b/Ī³1 , observing Ī³1 = 0 by as-

sumption. Then TrK/K1 (Ī³2 ) = TrK/K1 (b)/Ī³1 = 1, which proves

the ļ¬rst implication.

2 ā’ 3. If Ī³1 ā K1 , then (tn1 ā’ 1)Ī³1 = 0 and hence mĪ³1 divides f1 . Also,

TrK/K1 (Ī³2 ) = ((tn ā’ 1)/(tn1 ā’ 1))Ī³2 = 0 and (t ā’ 1)TrK/K1 (Ī³2 ) = 0

since TrK/K1 (Ī³2 ) ā k Ć— . This implies vtā’1 (mĪ³2 ) = vtā’1 (f2 ) and

mĪ³2 divides f2 , and the second implication follows.

3 ā’ 1. Since mĪ³1 divides f1 we have Ī³1 ā K1 . The conditions vtā’1 (mĪ³2 ) =

vtā’1 (f2 ) and m2 divides f2 imply that

TrK/K1 (Ī³2 ) = ((tn ā’ 1)/(tn1 ā’ 1))Ī³2 = 0.

Also Ī³1 = 0 by assumption, so that TrK/K1 (b) = Ī³1 TrK/K1 (Ī³2 ) =

0. This proves the third implication.

(ii) The ļ¬rst part follows from the proof of (i). Let b = Ī³1 Ī²1 = Ī³2 Ī²2 be the

two decompositions where Ī³i ā K1 and Āµi = TrK/K1 (Ī²i ) ā k Ć— by (i).

Then Ī³1 Āµ1 = TrK/K1 (b) = Ī³2 Āµ2 = 0. Thus Ī³1 /Ī³2 ā k Ć— .

(iii) Using Theorem VIII.4 and observing Ī³1 Ī³2 = (Ī»Ī³1 )(Ī»ā’1 Ī³2 ) for Ī» ā k Ć— ,

it follows that #Bm1 ,m2 ā¤ Ī¦(m1 )Ī¦(m2 )/(q ā’ 1). Because of (ii) this is

in fact an equality.

(iv)

1. k(b) ā k(Ī³1 , Ī³2 ) is clear since b = Ī³1 Ī³2 . On the other hand, Ī³2 =

TrK/K1 (b) ā k(b), hence Ī³1 = b/Ī³2 ā k(b) and k(Ī³1 , Ī³2 ) ā k(b)

follows.

2. Writing Ī» = TrK/K1 (Ī³2 ) we have TrK/k (Ī³2 ) = TrK1 /k (Ī») = n1 Ī»

since Ī» ā k Ć— .

3. We have that TrK/k (Ī³1 ) = 0 is equivalent to vtā’1 (mĪ³1 ) = 2v2 (n) .

Also, we have mĪ³1 divides mb since Ī³1 = ((tn ā’ 1)/(tn1 ā’ 1))b and

vtā’1 (mĪ³1 ) = vtā’1 (mb ) if and only if n/n1 is odd. This implies the

statement.

162 VIII. WEIL DESCENT ATTACKS

Corollary VIII.10. Assume that n1 is odd. Then

ļ£± ļ£¼

ļ£± ļ£¼ ļ£“ ļ£“

m1 divides f1 ,

ļ£“ ļ£“

a ā {0, Ļ},

ļ£² ļ£½ ļ£² ļ£½

m2 divides f2 ,

Ea,b : TrK/K1 (b) = 0, = Sm1 ,m2 : ,

ļ£³ ļ£¾ ļ£“ ļ£“

vtā’1 (m2 ) = 2v2 (n) ,

ļ£“ ļ£“

ļ£³ ļ£¾

k(b) = K

P (m1 , m2 )

where the union is disjoint.

Example 4: Consider n = 6, n1 = 3 and n2 = 2. Using Corollary VIII.10

we see that every elliptic curve over Fq6 with TrFq6 /Fq3 (b) = 0 leads to a

genus gC 0 ā {8, 9, 11, 12, 14}.

We now focus on the case where n is an odd prime. We can then use

Lemma VIII.7 and Corollary VIII.8. Over F2 we have the factorization into

irreducible polynomials tn + 1 = (t ā’ 1)h1 Ā· Ā· Ā· hs and deg(hi ) = d such that

n = sd + 1. In this situation the ļ¬rst non-trivial m = deg(mĪ³,Ī² ) satisļ¬es d ā¤

m ā¤ d + 1 corresponding to mĪ³,Ī² = hi or mĪ³,Ī² = (t ā’ 1)hi by Theorem VIII.4

and equation (VIII.5), observing that (t ā’ 1) | hi . After that we already have

m ā„ 2d which is too big in most instances. The case m = d is (only) obtained

when Ī³, Ī² ā Bhi (t) and TrK/F2 (Ī±) = 0. The conditions of Theorem VIII.1 are

fulļ¬lled so the GHS reduction does work and the resulting genus is gC 0 =

2d ā’ 1. The case m = d + 1 leads to the smallest genera when Ī³ ā Btā’1 and

Ī² ā Bhi (t) āŖ B(tā’1)hi (t) , which is a disjoint union. Since TrK/k (Ī³) = nĪ³ = 0

the conditions of Theorem VIII.1 are fulļ¬lled for every Ī± ā {0, Ļ}, and the

genus gC 0 is 2d ā’ 1 if Ī² ā Bhi (t) and 2d if Ī² ā B(tā’1)hi (t) .

The transformation between (VIII.2) and (VIII.1) is described by b =

(Ī³Ī²)2 and a = Ī±. The map (Ī³, Ī²) ā’ (Ī³Ī²)2 is not injective, so several tuples

(Ī³, Ī²) will lead to the same elliptic curve. It is (q ā’ 1) ā’ 1 when restricted

to Btā’1 Ć— Bhi or Btā’1 Ć— B(tā’1)hi , and at least 2(q ā’ 1) ā’ 1 when restricted to

Bhi Ć— Bhi . Namely, the tuples (Ī»Ī³, Ī»ā’1 Ī²) for Ī» ā k Ć— and also (Ī², Ī³) in the

latter case are mapped to the same b as (Ī³, Ī²). Heuristically we expect that

the ļ¬bres are not much bigger than 2(qā’1) in this case if #(Bhi Ć—Bhi ) is small

in comparison with #K. Now clearly Btā’1,hi = Bhi and Btā’1,(tā’1)hi = B(tā’1)hi ,

so these sets are disjoint for all i and we obtain # āŖi Btā’1,hi = s(q d ā’ 1) and

# āŖi Btā’1,(tā’1)hi = s(q ā’ 1)(q d ā’ 1). Furthermore, we expect that #Bhi ,hi ā

min{q n , (q d ā’ 1)2 /(2(q ā’ 1))} and that # āŖi Bhi ,hi ā min{q n , s(q d ā’ 1)2 /(2(q ā’

1))}.

A summary is given in Table VIII.1. Note that the elliptic curves from

SmĪ³ ,mĪ² of the last two rows lead to hyperelliptic function ļ¬elds C 0 and that the

cardinality ā is only heuristically expected (Lemma VIII.11 provides proven

bounds in special cases).

If hi is of a trinomial form, we have the following precise statement.

VIII.2. THE GHS ATTACK 163

Table VIII.1. Cardinalities of SmĪ³ ,mĪ² for n Odd Prime

ā #SmĪ³ ,mĪ²

mĪ³ mĪ² Ī± gC 0

min{q n , sq 2dā’1 /2}ā

2d ā’ 1

hi hi 0

tā’1 2d ā’ 1 2sq d

hi 0, Ļ

tā’1 (t ā’ 1)hi 2d 2sq d+1

0, Ļ

Lemma VIII.11. Assume h = tr1 + tr2 + 1 with r1 > r2 > 0, gcd{r2 , n} = 1

and mb | h. Then there are no or precisely 2(q ā’ 1) pairs (Ī³, Ī²) ā K 2 such

that b = Ī³Ī² and mĪ³ = mĪ² = h.

Proof. Assume that b = Ī³Ī² and mĪ³ = mĪ² = h. Then Ī³ = 0 and Ī² = 0

since b = 0, and consequently

r1 ā’1 r2 ā’1

Ī³q + Ī³q + 1 = 0,

q r1 ā’1 q r2 ā’1 q r1 ā’q r2 q r1 ā’1

b +b Ī³ +Ī³ = 0.

r2 ā’1

Deļ¬ne Ļ = Ī³ q . The ļ¬rst equation implies

r1 ā’1

Ī³q = Ļ + 1, (VIII.3)

r1 ā’q r2

Ī³q = (Ļ + 1)/Ļ.

r1 ā’1 r2 ā’1

Substituting this into the second equation yields bq + bq (Ļ + 1)/Ļ +

Ļ + 1 = 0, and then

r1 ā’1 r2 ā’1 r2 ā’1

Ļ2 + (bq + bq + 1)Ļ + bq = 0. (VIII.4)

r

On the other hand, any further solution Ļ, Ī³, Ī² to (VIII.4), (VIII.3), Ī³ q 2 ā’1 =

Ļ and Ī² = b/Ī³ satisļ¬es mĪ³ = mĪ² = h because b = 0.

Since mb | h we have that Ī³/Ī² ā k. There are thus at least 2(q ā’ 1)

pairwise distinct solutions of the form (Ī»Ī³, Ī»ā’1 Ī²) and (Ī»Ī², Ī»ā’1 Ī³) with Ī» ā k Ć— .

On the other hand, there are at most two possibilities for Ļ and at most q ā’ 1

possibilities for Ī³ for each Ļ, resulting in at most 2(q ā’ 1) solutions. Namely,

r2

for any two solutions Ī³1 , Ī³2 with Ī³iq ā’1 = Ļ we have that (Ī³1 /Ī³2 )q 2 ā’1 = 1

r

and hence Ī³1 /Ī³2 ā Fqr2 ā© FĆ— = FĆ— since r2 and n are coprime.

qn q

Given b and h as in the lemma, Ī³ and Ī² can be computed eļ¬ciently as

follows, using Langrangeā™s resolvent [210, p. 289]:

r1 ā’1 r2 ā’1 r2 ā’1

1. Solve for Ļ such that Ļ2 + (bq + bq + 1)Ļ + bq = 0.

2. Compute Īø such that

nā’2 nā’1

2

Ī³ = Īø + Ļā’1 Īøq2 + Ļā’1ā’q2 Īøq2 + Ā· Ā· Ā· + Ļā’1ā’q2 ā’Ā·Ā·Ā·ā’q2 Īøq2 = 0,

where q2 = q r2 . This can be achieved by linear algebra over k.

3. Compute Ī² = b/Ī³.

164 VIII. WEIL DESCENT ATTACKS

If NK/k (Ļ) = 1 in step 1 or if Ī³ does not satisfy (VIII.3) in step 2, then there

are no solutions Ī³, Ī² with mĪ³ = mĪ² = h.

Example 5: Consider n = 7. Then tn ā’ 1 = (t ā’ 1)(t3 + t + 1)(t3 + t2 + 1),

d = 3 and s = 2. Using the ļ¬rst row of Table VIII.1 we see that a proportion

of about q ā’2 of all elliptic curves over Fq7 with Ī± = 0 leads to gC 0 = 7.

In Lemmas VIII.9 and VIII.11 we have discussed the decomposition b =

Ī³Ī² and how to check Ea,b ā Sm1 ,m2 in some special cases. A simple and

the currently only known method to do this in full generality is to take all

Ī³ ā Bm1 and to test whether mb/Ī³ = m2 . Of course, for any Ī³ we do not need

to check Ī»Ī³ with Ī» ā k Ć— .

VIII.2.6. Further Details. In this section we present some details on the

Artinā“Schreier construction of Theorem VIII.1 and provide the parts of the

proof of Theorem VIII.1 which have not occurred in the literature.

We let p denote an arbitrary prime for the moment, abbreviate F = K(x)

and let f ā F be a rational function. A simple Artinā“Schreier extension

denoted by Ef , is given by adjoining to F a root of the polynomial y p ā’yā’f ā

F [y]. Examples of such extensions are the function ļ¬elds of elliptic curves in

characteristics two and three.

The Artinā“Schreier operator is denoted by ā„˜(y) = y p ā’ y. We then also

write F (ā„˜ā’1 (f )) for Ef and ā„˜(F ) = { f p ā’ f : f ā F }. More generally, The-

orem VIII.1 uses the following construction and theorem, which is a special

version of [260, p. 279, Theorem 3.3]:

ĀÆ

Theorem VIII.12. Let F be a ļ¬xed separable closure of F . For every additive

subgroup ā ā¤ F with ā„˜(F ) ā ā ā F there is a ļ¬eld C = F ā„˜ā’1 (ā) with

ĀÆ

F ā C ā F obtained by adjoining all roots of all polynomials y p ā’ y ā’ d for

ĀÆ

d ā ā in F to F . Given this, the map

ā ā’ C = F ā„˜ā’1 (ā)

deļ¬nes a one-to-one correspondence between such additive subgroups ā and

ĀÆ

abelian extensions C/F in F of exponent p.

For our purposes this construction is only applied for very special ā,

which will be introduced in a moment. As in Section VIII.1.2, by a Frobe-

nius automorphism with respect to K/k of a function ļ¬eld over K we mean

an automorphism of order n = [K : k] of that function ļ¬eld which extends

the Frobenius automorphism of K/k. Raising the coeļ¬cients of a rational

function in F = K(x) to the qth power yields for example a Frobenius auto-

morphism of F with respect to K/k, which we denote by Ļ.

nā’1

For f ā F we deļ¬ne āf := { dp ā’ d + i=0 Ī»i Ļ i (f ) : d ā F and Ī»i ā Fp }.

This is the subgroup of the additive group of F which is generated by f

m i

and contains ā„˜(F ). Also, let mf = i=0 Ī»i t with Ī»m = 1 be the unique

VIII.2. THE GHS ATTACK 165

polynomial of smallest degree in Fp [t] such that m Ī»i Ļ i (f ) = dp ā’d for some

i=0

d ā F . As in Section VIII.2.4, we can deļ¬ne a multiplication of polynomials

h(t) = d Ī»i ti ā k[t] and rational functions z ā F by h(t)z = d Ī»i Ļ i (z).

i=0 i=0

This makes the additive group of F into a k[t]-module. The polynomials

mf (t) are then by deļ¬nition polynomials in Fp [t] of smallest degree such that

mf (t)f ā ā„˜(F ). The ļ¬eld F ā„˜ā’1 (āf ) exists by Theorem VIII.12 and has

degree pdeg(mf ) over F . Further statements on the existence of a Frobenius

automorphism of this ļ¬eld with respect to K/k and it genus can be found

in [168].

We now let p = 2 and f = Ī³/x + Ī± + Ī²x. The ļ¬eld F ā„˜ā’1 (āf ) is then

equal to the ļ¬eld C of Theorem VIII.1 deļ¬ned in Section VIII.2.1. Let us

exhibit an explicit model for C. We have

lcm{mĪ³ , mĪ² } if TrK/F2 (Ī±) = 0,

mf = (VIII.5)

lcm{mĪ³ , mĪ² , t + 1} otherwise.

Let m = deg(mf ). The classes of Ļ i (f ) for 0 ā¤ i ā¤ m ā’ 1 form an F2 -basis of

āf /ā„˜(F ). From Theorem VIII.12 it follows that C is obtained by adjoining

one root of every y 2 ā’ y ā’ Ļ i (f ) to F . In other words, C = F [y0 , . . . , ymā’1 ]/I,

where I is the ideal of the polynomial ring F [y0 , . . . , ymā’1 ] generated by the

polynomials yi ā’ yi ā’ Ļ i (f ) for 0 ā¤ i ā¤ m ā’ 1. We write yi for the images of

2

ĀÆ

the yi in C and abbreviate y = y0 . ĀÆĀÆ

Using this notation we are able to prove Theorem VIII.1(iii) and (iv).

Assume without loss of generality that deg(mĪ³ ) ā¤ deg(mĪ² ). Let h ā F2 [t].

The ļ¬eld C then contains the roots of y 2 ā’ y ā’ h(t)f and is generated by these

roots for all h of degree less than m. Using polynomial division write h =

smĪ³ + r with s, r ā F2 [t] and deg(r) < deg(mĪ³ ). Thus h(t)f = s(t)(mĪ³ (t)f ) +

r(t)f . The rational function mĪ³ (t)f is of the form Ļ + Ī“x with Ļ, Ī“ ā K.

As a result, h(t)f is an F2 -linear combination of the conjugates Ļ i (f ) for

0 ā¤ i ā¤ deg(mĪ³ ) ā’ 1 and Ļ j (mĪ³ (t)f ) for 0 ā¤ j ā¤ m ā’ deg(mĪ³ ) ā’ 1. We

write wj for a root of the polynomials wj ā’ wj ā’ Ļ j (mĪ³ (t)f ) in C. Then C =

2

ĀÆ

F [ĀÆ0 , . . . , ydeg(mĪ³ )ā’1 , w0 , . . . , wmā’deg(mĪ³ )ā’1 ]. By [145, Lemma 7] the ļ¬eld L =

y ĀÆ ĀÆ ĀÆ

F [w0 , . . . , wmā’deg(mĪ³ )ā’1 ] is a rational function ļ¬eld and the extension L/F has

ĀÆ ĀÆ

mā’deg(mĪ³ )

. Since C/F has degree 2m , we see that L has index 2deg(mĪ³ )

degree 2

in C. Furthermore, L is equal to F (ā„˜ā’1 (āmĪ³ (t)f )). Since Ļ(āmĪ³ (t)f ) = āmĪ³ (t)f

we have that the Frobenius automorphism Ļ on C restricts to a Frobenius

automorphism on L. It thus follows that the ļ¬xed ļ¬eld L0 of Ļ in L is

a rational function ļ¬eld over k and has index 2deg(mĪ³ ) in C 0 . This proves

Theorem VIII.1(iii).

The hyperellipticity in Theorem VIII.1(iv) is proven in [145] and can be

seen as follows. If Ī³ ā k, then mĪ³ = t ā’ 1. Consequently, by (iii) we see that

C 0 contains a rational subļ¬eld of index 2, which yields the statement.

166 VIII. WEIL DESCENT ATTACKS

VIII.3. Extending the GHS Attack Using Isogenies

VIII.3.1. The Basic Idea. The GHS attack can be extended to a much

larger class of curves by using isogenies. Consider two elliptic curves E and E

deļ¬ned over K. An isogeny Ļ : E ā’ E deļ¬ned over K homomorphically maps

points in E(K) to points in E (K). The coordinates of an image point are

deļ¬ned by algebraic expressions involving the coordinates of the input point

and elements of K, in a similar way to the addition formulae. In particular,

a discrete logarithm problem P = Ī»Q is mapped to the discrete logarithm

problem Ļ(P ) = Ī»Ļ(Q). The basic idea is that E might be susceptible to

the GHS attack while E is not. In this case we would transfer the discrete

logarithm problem on E to E using Ļ and attempt to solve it there.

For every isogeny Ļ : E ā’ E deļ¬ned over K there is a dual isogeny

Ė : E ā’ E deļ¬ned over K and E is said to be isogenous to E . This yields an

Ļ

equivalence relation so that elliptic curves deļ¬ned over K can be partitioned

into isogeny classes. Also, the isogeny class of an elliptic curve deļ¬ned over K

is uniquely determined by #E(K) = q n + 1 ā’ t and its cardinality is roughly,

and on average, of the order (4q n ā’ t2 )1/2 , where t satisļ¬es |t| ā¤ 2q n/2 (more

precisely; the cardinality is equal to the Kroneckerā“Hurwitz class number

H(t2 ā’ 4q n ), see [136], [293]).

If an isogeny class contains an elliptic curve which is susceptible to the

GHS attack, the whole isogeny class can be considered susceptible using the

above idea. Of course this raises the following two questions: Can it be eļ¬-

ciently determined whether an isogeny class contains a susceptible curve and

if so, can the isogeny be eļ¬ciently computed? There are two main strategies:

Isogeny Strategy 1. For all E which are susceptible to the GHS at-

tack check whether #E (K) = #E(K). If so, compute the isogeny between

E and E .

Isogeny Strategy 2. Compute random (all) E in the isogeny class of E

and the corresponding isogenies from E to E . Check whether one of the E is

susceptible to the GHS attack.

Again, we only consider elliptic curves in the unique form (VIII.1) so that we

are eļ¬ectively dealing here and in the following with isomorphism classes of

elliptic curves.

Assuming that the cardinality of the isogeny class of E is roughly q n/2 and

that isogeny class membership and being susceptible to the GHS attack are

basically independent properties, we expect that Strategy 1 is more eļ¬cient

in terms of checks than Strategy 2 if the number of the susceptible E is less

than q n/2 , and that Strategy 2 is more eļ¬cient otherwise.

VIII.3.2. Isogeny Probabilities. Let Sm1 (t),m2 (t) denote a system of con-

jugacy class representatives of the operation of the 2-power Frobenius on

VIII.3. EXTENDING THE GHS ATTACK USING ISOGENIES 167

Sm1 (t),m2 (t) . In order to obtain some quantitative statements about the above

strategies we assume that Sm1 (t),m2 (t) behaves like any randomly and uni-

formly chosen set of ordinary elliptic curves deļ¬ned over K of the same car-

dinality. We want to estimate the probability that a randomly and uniformly

chosen elliptic curve E is isogenous to a ļ¬xed subset of N elliptic curves Ei

from Sm1 (t),m2 (t) .

Lemma VIII.13. Let E, E1 , . . . , EN be randomly, uniformly and independently

chosen ordinary elliptic curves. Then

N

1

Pr(E ā¼ E1 or . . . or E ā¼ EN ) ā„ 1 ā’ 1 ā’ .

(1 ā’ 1/p)4q n/2 + 2

Proof. Abbreviate AN = Pr(E ā¼ E1 or . . . or E ā¼ EN ) and let E denote a

further randomly, uniformly and independently chosen ordinary elliptic curve.

Using the complementary event it is straightforward to prove that

AN = 1 ā’ (1 ā’ Pr(E ā¼ E ))N . (VIII.6)

If ai are M non-negative numbers such that M ai = 1, then M a2 ā„ i=1 i

i=1

1/M . This is easily seen by writing ai = 1/M + Īµi with Īµi = 0 and

i

expanding this in M a2 .

i=1 i

The following sums are over all ordinary isogeny classes I and the symbol

#{I} denotes the number of such classes. Using the above observation with

ai = Pr(E ā I) and M = #{I} we see

Pr(E ā¼ E ) = Pr(E ā I and E ā I) = Pr(E ā I) Pr(E ā I)

I I

Pr(E ā I)2 ā„ 1/#{I}.

= (VIII.7)

I

The number of ordinary isogeny classes satisļ¬es

#{I} ā¤ (1 ā’ 1/p)4q n/2 + 2. (VIII.8)

This is because every integer q n + 1 ā’ t with t2 ā¤ 4q n and p | t occurs as the

number of points of an ordinary elliptic curve over K (see [344]).

Combining (VIII.8), (VIII.7) and (VIII.6) yields the lemma.

According to Lemma VIII.13, it is reasonable to expect that a randomly

and uniformly chosen elliptic curve E will be isogenous to at least one of the

Ei from Sm1 ,m2 with probability approximately at least N/(2q n/2 ), if N is

much less than q n/2 , and with probability approximately one, if N is much

larger than q n/2 . The ļ¬rst probability can in fact be improved slightly when

one restricts for example to elliptic curves (VIII.1) with a = 0. Recall that if

TrK/F2 (a) = 0, then the group order #E(K) of the elliptic curve is congruent

to 0 modulo 4 and if TrK/F2 (a) = 1, then it is congruent to 2 modulo 4

(see [ECC, p. 38]). Thus elliptic curves with a = 0 represent only about

half of all isogeny classes. It follows that the ļ¬rst of the above probabilities

168 VIII. WEIL DESCENT ATTACKS

improves by a factor of two. Another property in this line is #E(K) =

0 mod 8 if and only if TrK/F2 (b) = 0 for a = 0 and nr ā„ 3 ([242]).

By our assumption on Sm1 ,m2 and in view of Isogeny Strategy 2 we ex-

pect that membership in Sm1 ,m2 and being isogenous to a randomly and

uniformly chosen elliptic curve E are approximately independent events if

#Sm1 ,m2 is much larger than q n/2 . More precisely, we expect #(Sm1 ,m2 ā© I) ā

#Sm1 ,m2 #I/(2q n ) since the curves from Sm1 ,m2 should distribute over the

isogeny classes relative to their sizes.

VIII.3.3. Computing Isogenies. Isogeny Strategies 1 and 2 require the

computation of isogenies. In Isogeny Strategy 1 we have to construct the

isogeny between E and E given only that #E(K) = #E (K). In Isogeny

Strategy 2 we start with E and have to construct the isogeny to a randomly

and uniformly chosen E of the unique form (VIII.1) in the isogeny class of E.

We recall some additional basic facts about isogenies and endomorphism

rings for ordinary elliptic curves. Useful references for the required theory

and algorithmic aspects are [238, 307, 293, 129, 134, 207].

Endomorphisms of E are isogenies of E to itself. Addition and composition

of maps make the set of endomorphisms into a ring End(E). For elliptic curves

deļ¬ned over K all endomorphismus are deļ¬ned over K as well. The q n th

n n

power Frobenius endomorphism Ļ : (x, y) ā’ (xq , y q ) satisļ¬es Ļ 2 ā’ tĻ + q n =

0 with t = q n + 1 ā’ #E(K), t2 ā¤ 4q n and t ā” 0 mod p, so Q(Ļ) is an

imaginary qadratic number ļ¬eld. The ring End(E) is an order in Q(Ļ) with

Z[Ļ] ā End(E) ā Omax , where Omax is the maximal order or ring of algebraic

integers of Q(Ļ). Conversely, if Ļ 2 ā’ tĻ + q n = 0, t2 ā¤ 4q n and t ā” 0 mod p

for some algebraic integer Ļ, then every order O with Z[Ļ] ā O ā Omax

occurs as the endomorphism ring of an elliptic curve E deļ¬ned over K with

#E(K) = q + 1 ā’ t, such that Ļ corresponds to the q n th power Frobenius

endomorphism. There is a bijection of positive integers d and suborders Od

of Omax of index d, given by d ā’ Od = Z + dOmax . The integer d is called

conductor of Od .

The degree of an isogeny Ļ : E ā’ E deļ¬ned over K is equal to the degree

of the function ļ¬eld extension K(E)/K(E ) deļ¬ned by Ļ and coincides roughly

with the degrees of its deļ¬ning algebraic expressions. The degree of isogenies

is multiplicative with respect to composition. Every isogeny deļ¬ned over K

can be decomposed into a chain of isogenies of prime degree deļ¬ned over K.

The cardinality of the kernel of Ļ as a homomorphism from E(K) to E (K)

is bounded by the degree of Ļ (and equal to the degree if Ļ is separable).

An isomorphism is an isogeny of degree one. For every E deļ¬ned over K

there is an E deļ¬ned over K (a quadratic twist of E) such that for the j-

invariants j(E) = j(E ), E and E are isomorphic over a quadratic extension

of K, and every E2 deļ¬ned over K with j(E2 ) = j(E) is isomorphic over K to

E or E . Furthermore, #E(K) + #E (K) = 2q n + 2. If Ļ is of degree r, then

Ļr (j(E), j(E )) = 0 where Ļr is the rth modular polynomial. Conversely, if

VIII.3. EXTENDING THE GHS ATTACK USING ISOGENIES 169

Ļr (j(E), x) = 0 for x ā K, then there is an E deļ¬ned over K with j(E ) = x

and an isogeny Ļ : E ā’ E deļ¬ned over K of degree r.

If E and E are isogenous, then End(E) and End(E ) are (isomorphic to)

orders within the same imaginary quadratic number ļ¬eld. More speciļ¬cially it

holds that End(E) = End(E ), End(E) ā End(E ) with (End(E ) : End(E)) =

or End(E ) ā End(E) with (End(E) : End(E )) = , if there is an isogeny

Ļ : E ā’ E of prime degree . The cases where the index changes can be

(partly) read oļ¬ the number of zeros of Ļ (j(E), x). An isogeny Ļ : E ā’ E

of elliptic curves with O = End(E) = End(E ) deļ¬nes a uniquely determined

invertible (and integral) ideal I of O with N(I) = deg(Ļ), and any such I is

obtained this way. Isomorphisms Ļ correspond to I = O. Composition of

isogenies corresponds to ideal multiplication. If Ļ1 : E ā’ E1 and Ļ2 : E ā’ E2

are isogenies with the ideals I1 and I2 , then E1 is isomorphic to E2 if and only if

I1 /I2 is principal. As a result, the isogeny structure between the isomorphism

classes is equivalent to the group structure of Pic(O), the group of classes of

invertible ideals of O modulo principal ideals.

The basic technique in Isogeny Strategies 1 and 2 is as follows. For O =

End(E) we can use the group structure of Pic(O) for random walks along

chains of isogenies of prime degree starting at E. This way we can generate

random elliptic curves E with End(E ) = O and known isogenies E ā’ E

for Isogeny Strategy 2. For Isogeny Strategy 1 we use a second random

walk starting at the second elliptic curve E , assuming End(E ) = O for

the moment. If these walks meet, we can connect the two parts using dual

isogenies to obtain a chain of isogenies from E to E . Since we consider only

elliptic curves of the unique form (VIII.1) we are eļ¬ectively working with

isomorphism classes.

A single step in the random walk from a curve Ei to a curve Ei+1 to be

determined proceeds as follows. We assume that O = End(E) is known and

End(Ei ) = O holds, where O can be computed by the algorithm of Kohel

[207]. A prime number is chosen which does not divide the conductor of

O = End(Ei ) and is split or ramiļ¬ed in O. The j-invariants of the curves Ei+1

related to Ei by an isogeny of degree are the roots x of Ļ (j(Ei ), x) in K. If

(and only if) divides the index of Z[Ļ] in O, then not all of these roots result

in an Ei+1 with End(Ei+1 ) = End(Ei ); the case (End(Ei ) : End(Ei+1 )) = is

also possible. Using the techniques of [207, p. 46] we determine those x for

which Ei+1 isogenous to Ei has the same endomorphism ring. According to

whether is split or ramiļ¬ed, there are one or two such values. We choose a

value and compute Ei+1 of the unique form (VIII.1) and the isogeny from it.

Checking the action of the Frobenius or another suitable endomorphism on

the kernel of the isogeny allows one to determine the prime ideal of norm

above which corresponds to the isogeny [ECC, 294].

170 VIII. WEIL DESCENT ATTACKS

For the whole random walk we note that any class in Pic(O) can be repre-

sented by an ideal of O of (small) norm O(|d(O)|1/2 ), where d(O) denotes the

discriminant of O and is O(q n ). Furthermore, #Pic(O) ā O(|d(O)|1/2 ) and

Pic(O) is generated by split prime ideals of (very small) norm O(log(|d(O)|)2 )

under the GRH (generalized Riemann hypothesis). We let B denote a set of

split or ramiļ¬ed prime ideals of very small norm which generate Pic(O), and

let B0 the corresponding prime numbers. The prime numbers in every sin-

gle step are chosen from B0 such that the walk extends over the whole of

Pic(O). Furthermore, the ith step of the random walk starting at E can be

represented by a single ideal Ii of small norm, corresponding to an isogeny

E ā’ Ei . The ideal Ii is deļ¬ned inductively as follows. First, I0 = O. For the

(i + 1)-th step the curve Ei+1 , an isogeny and a prime ideal P are computed

as above. Then Ii+1 is deļ¬ned to be a representative of small norm of the

class of Ii P and corresponds to an isogeny E ā’ Ei+1 .

Assume the random walk stops at Er , and the isogeny E ā’ Er is described

by Ir or a chain of isogenies of prime degree. The factorization of Ir is likely to

contain prime ideals which have too large a norm for our purpose. Also, the

chain may have length exponential in n log(q). We can obtain a much reduced

chain as follows. Using techniques from index-calculus in imaginary quadratic

orders we compute a representation of Ir in Pic(O) in terms of powers of the

elements of B or an enlargement of B in the form Ir = (Ī³) m Pidi , where

i=1

m and the di are (expected to be) polynomial in n log(q) if B is suļ¬ciently

large. Again using techniques from point counting we determine a chain of

explicitly given isogenies from E to Er , such that every step corresponds to

a Pi . This concludes the description of the random walks on (isomorphism

classes of) elliptic curves with endomorphism ring O.

In Isogeny Strategy 2 we do not want to restrict the possible endomor-

phism rings to a given O. In a precomputation we compute all intermediate

orders OĪ½ with Z[Ļ] ā OĪ½ ā Omax and isogenies E ā’ EĪ½ to curves EĪ½ with

OĪ½ = End(EĪ½ ), using [207]. We start random walks in every EĪ½ . In every

step we choose Ī½ with probability about Āµ=Ī½ #Pic(OĀµ )/ Āµ #Pic(OĀµ ) and

extend the walk from say EĪ½,i to some EĪ½,i+1 . The curve EĪ½,i+1 is returned.

In Isogeny Strategy 1 the curves E and E may have diļ¬erent endomor-

phism rings. In a precomputation we compute isogenies E ā’ E0 and E ā’ E0

such that End(E0 ) and End(E0 ) are equal to O = Omax . Following the Pol-

lard methods we start a random walk at E0 of length t = O(#Pic(O)1/2 ) =

O(q n/4 ). Here , x = j(Ei+1 ) and hence the prime ideal P are chosen in a way

that depends deterministically on j(Ei ) and gives a pseudorandom distribu-

tion close to uniform. Then we proceed analogously with a random walk start-

ing at E0 . After an expected t steps we ļ¬nd s such that j(Et ) = j(Es ). Since

#E(K) = #E (K), the curves Et and Es must be isomorphic, so I = It /Is

corresponds to an isogeny between E0 and E0 , where Ii and Ii are the ideals

describing the random walks as above. Applying the index-calculus trick for

VIII.3. EXTENDING THE GHS ATTACK USING ISOGENIES 171

the reduction of random walks to I and combining this with the isogenies from

the precomputation (and their duals) ļ¬nally yields a short chain of isogenies

E ā’E.

In many cases Z[Ļ] = Omax , so that the complications with intermediate

orders in Isogeny Strategy 1 and Isogeny Strategy 2 do not occur.

Theorem VIII.14. Let E and E be two ordinary isogenous elliptic curves

such that #E(K) = #E (K) = q n + 1 ā’ t, and let l be the largest prime or one

with l2 dividing (4q n ā’t2 ). Under the GRH and further reasonable assumptions

there is a probabilistic algorithm which computes O(n log(q)) isogenies Ļi :

Ei ā’ Ei+1 of degree O(max{(n log(q))2 , l}) such that Ļ = i Ļi is an isogeny

between E and E . The expected running time is O(max{q n/4+Īµ , l3+Īµ }).

The theorem follows from [129], [134] along the lines explained above.

The algorithm involves some not rigorously proven steps from index-calculus

in imaginary quadratic orders which accounts for the GRH and further ārea-

sonableā assumptions. In most cases l will be fairly small, so that the running

time of the algorithm is essentially O(q n/4+Īµ ). A worse running time can only

occur when l is large since potentially some isogenies Ļi of degree l could be

required. If End(E) and End(E ) are equal, then using isogenies of degree l

can be circumvented; but if the mutual index contains a large prime l, isoge-

nies of degree l cannot be avoided. The algorithm is particularly eļ¬cient if

4q n ā’ t2 is small or if Omax has a small class number #Pic(Omax ) and smooth

index (Omax : Z[Ļ]).

If E is our target curve and E ā Sm1 (t),m2 (t) is isogenous to E we can hence

compute the isogeny Ļ between E and E in (much) less time than the Pollard

methods require for solving the DLP on E, assuming that 4q n ā’ t2 is only

divisible by squares of primes l = O(q n/6ā’Īµ ) or that End(E) = End(E ). Then

Ļ is given in the product form Ļ = i Ļi and images Ļ(P ) are computed in

time about O(max{(n log(q))7 , (n log(q))l3 }). Furthermore, also due to the

degree bounds for the Ļi , the order of the kernel of Ļ cannot be divisible by

the large prime factor of #E(K) and hence the DLP is preserved under Ļ.

VIII.3.4. Implications for n Odd Prime. We now combine the previous

observations with the results of Sections VIII.2.3ā“VIII.2.5 and Table VIII.1

for n an odd prime. Since the 2-power Frobenius has order nr on K, the

cardinalities of the representative sets Shi ,hi , Stā’1,hi and Stā’1,(tā’1)hi are at

least 1/(nr) times the cardinalities of the sets Shi ,hi , Stā’1,hi and Stā’1,(tā’1)hi .

If we take N pairwise distinct elliptic curves Ei from these representative sets

q n/2 , we expect by Lemma VIII.13 and the discussion thereafter

with N

that a randomly and uniformly chosen elliptic curve E will be isogenous to

one of the Ei with probability at least min{1, N/(2q n/2 )} or min{1, N/q n/2 }

if the considered elliptic curves have a = 0.

Following Isogeny Strategy 1, we need to actually compute the Ei . Some

details on how this can be achieved are given in the appendix of [134]. For

172 VIII. WEIL DESCENT ATTACKS

each curve Ei we check #E(K) Ā· P = O for some random points P ā Ei (K). If

the check fails, Ei is not isogenous to E. Otherwise it is quite likely that it is

and we check #Ei (K) = #E(K) using fast point counting techniques. If we

ļ¬nd Ei such that #Ei (K) = #E(K), we are left to apply the algorithm from

Theorem VIII.14. This strategy requires a time linear in N , plus a time of

about O(q n/4 ) for the isogeny computation.

Following Isogeny Strategy 2, we need to sample random and uniformly

distributed elliptic curves E from the isogeny class of E as described in Sec-

tion VIII.3.3. We expect to compute approximately q n /#Shi ,hi , 2q n /#Stā’1,hi

and 2q n /#Stā’1,(tā’1)hi curves E and isogenies E ā’ E until E is isomorphic to

one of the curves in Shi ,hi , Stā’1,hi and Stā’1,(tā’1)hi , respectively. Table VIII.2

contains a summary.

Table VIII.2. Expected Probabilities that a Random E is

Isogenous to a Curve E in SmĪ³ ,mĪ² and Runtimes for Isogeny

Strategy 1 (Excluding the O(q n/4 ) Contribution) and Isogeny

Strategy 2, for n Odd Prime

Pr(E ā¼ E ā SmĪ³ ,mĪ² )

mĪ³ mĪ² Strat 1 Strat 2

min{1, sq 2dā’1ā’n/2 /(2nr)} sq 2dā’1 /(2nr) 2q nā’2d+1 /s

hi hi

tā’1 min{1, sq dā’n/2 /(nr)} 2sq d /(nr) q nā’d /s

hi

t ā’ 1 (t ā’ 1)hi min{1, s(q ā’ 1)q dā’n/2 /(nr)} 2sq d+1 /(nr) q nā’dā’1 /s

Example 6: Consider n = 7. By Example 5, a proportion of about q ā’2 of

all elliptic curves over Fq7 with Ī± = 0 leads to an eļ¬ciently computable, not

necessarily hyperelliptic C 0 of genus 7. Using Isogeny Strategy 2 and the ļ¬rst

row of Table VIII.2, we thus expect that sampling of the order of q 2 many

random elliptic curves from the isogeny class of the target curve E yields such

a C 0.

Example 7: Consider n = 31. The factorization of t31 ā’ 1 modulo 2 consists

of t ā’ 1 and s = 6 irreducible polynomials hi (t) of degree d = 5, two of which

are of the trinomial form of Lemma VIII.11. Using Table VIII.1 there are

hence about 3q 9 , 12q 5 and 12q 6 elliptic curves which lead to non-hyperelliptic

and hyperelliptic curves C 0 of genus 31, 31 and 32, respectively. Using Ta-

ble VIII.2 the probability that a random elliptic curve lies in the isogeny class

of one of these curves is 3q ā’13/2 /(31r), 6q ā’21/2 /(31r) and 6q ā’19/2 /(31r), re-

spectively. Since the above cardinalities are much smaller than q 31/2 Isogeny

Strategy 1 is more eļ¬cient and requires a run time of 3q 9 /(31r), 12q 5 /(31r)

VIII.4. SUMMARY OF PRACTICAL IMPLICATIONS 173

and 12q 6 /(31r), respectively, plus O(q 31/4 ) for the (possible) isogeny compu-

tation.

VIII.4. Summary of Practical Implications

We now describe practical implications of the techniques of the previous

sections for some values of n and ļ¬elds of cryptographical sizes. We say that

the GHS attack leads to a security reduction of a special family of elliptic

curves or general elliptic curves if it is more eļ¬cient than the appropriate

Pollard methods for these curves. As a rule of the thumb, the eļ¬ectiveness of

the GHS attack depends chieļ¬‚y on n, q and the āspecialnessā of the considered

elliptic curves (namely the genus of the resulting curve). With increasing n

the eļ¬ectiveness drops, and with increasing q or increasing āspecialnessā the

eļ¬ectiveness increases. This means for example that for suļ¬ciently large n

the set of elliptic curves for which the GHS attack is eļ¬ective is in general

negligibly small. Also by Theorem VIII.3 and the discussion thereafter, there

is always a (signiļ¬cant) security reduction due to the GHS attack for n ā„ 4

and partly for n ā„ 3 if the ļ¬eld size is large enough. The general method of

Theorem VIII.3 may however not readily apply to ļ¬elds of cryptographical

size.

Practical implications for elliptic curves in characteristic two have been

investigated in [80], [134], [168], [181], [233], [241], [242], [311].

For n = 1 or n = 2 there are no elliptic curves over Fq and Fq2 , respectively

for which the GHS attack would lead to a security reduction. The case n = 1

is clear as E = C 0 and there is nothing new to consider. The case n = 2

yields C 0 of genus at least two. Since the Pollard methods on E are more

eļ¬cient than index calculus on curves of genus at least two there is no security

reduction due to the GHS attack [80].

The case n = 3 has not been discussed in the literature. From the results

for n = 4 it however appears reasonable to expect no or only a minor security

reduction due to the GHS attack for any elliptic curve over Fq3 .

The cases n = 4 and n = 5 are discussed in detail in [311] considering

low genus index-calculus methods and in [233], [242] considering high genus

index-calculus methods. The conclusion for n = 4 is that there is (only) a

minor security reduction due to the GHS attack, applicable to any elliptic

curve over Fq4 , and a slightly more signiļ¬cant security reduction for a pro-

portion of around 1/q of these elliptic curves. The case n = 5 is particularly

interesting since there is an IETF standard [RFC 2412] using the ļ¬elds F155

and F185 . In [311] it is concluded that an arbitrary elliptic curve over F155

is subject to only a minor security reduction. In [233] it is argued that an

arbitrary elliptic curve over F185 is subject to a security reduction by a factor

of 216 , resulting in a security of 276 instead of 292 . In [242] timing estimates

are given for further ļ¬elds, the security reduction becomes larger as the ļ¬eld

174 VIII. WEIL DESCENT ATTACKS

size grows. For Fq600 the factor is for example already 269 , applicable to every

elliptic curve over that ļ¬eld.

The case n = 6 is partly discussed in [242], focusing on the ļ¬eld F2210 . The

conclusion is that about one quarter of all elliptic curves over F2210 , namely

those with TrF2210 (a) = TrF2210 (b) = 0 or equivalently #E(F2210 ) ā” 0 mod 8,

are subject to a security reduction by a factor of 220 . The attack uses isogenies

and maps the DLP to hyperelliptic curves of genus 15 or 16. Alternatively, we

can make use of the more general Example 4, which yields smaller genera up

to 14. Note that the resulting function ļ¬eld C 0 is in general not hyperelliptic,

so solving the DLP for C 0 will be more expensive. Precise experiments have

not been carried out, but we can still expect a signiļ¬cant security reduction

for essentially all elliptic curves over Fq6 .

The case n = 7 has been considered in [134] using the GHS reduction

with Ī³ = 1, and it was concluded that there should be a signiļ¬cant security

reduction for every elliptic curve over Fq7 if only C 0 could be found eļ¬ciently

enough. In [242] the ļ¬eld F2161 is brieļ¬‚y discussed, for which the GHS attack

would yield a feasible HCDLP for genus 7 or 8 over F223 . By Example 6 we

expect that sampling of the order of q 2 many random elliptic curves from the

isogeny class of a target elliptic curve Ea,b over Fq7 with a = 0 yields a not

necessarily hyperelliptic C 0 over Fq of genus 7. Comparing against the cost

of q 7/2 for the Pollard methods ļ¬nding C 0 thus takes negligible time. We can

hence expect a particularly signiļ¬cant security reduction of up to a factor of

q 3/2 for all elliptic curves over Fq7 . A precise analysis and whether the DLP

for elliptic curves over F2161 is feasible using these techniques has not been

carried out yet.

The case n = 8 has been discussed in [233]. There is a class of approxi-

mately q 5 elliptic curves Ea,b with TrK/F2 (a) = 0 and mb (t) = (t ā’ 1)5 whose

security is signiļ¬cantly reduced by the GHS attack. In [233] it is argued that

using Isogeny Strategy 1 would not present a feasible method of ļ¬nding such

a susceptible elliptic curve isogenous to a given arbitrary target curve. Apply-

ing Isogeny Strategy 2 however would seem to require sampling approximately

q 3 random curves in the isogeny class of the target curve before a susceptible

curve is found. As a result the security of any elliptic curve with TrK/F2 (a) = 0

and n = 8 could be reduced by a factor of approximately q. The case n = 8

is of particular interest since the ANSI X.962 standard [ANSI X9.62] lists

in Appendix H.4 speciļ¬c elliptic curves over ļ¬elds of characteristic two and

extension degrees 16 , where ā {11, 13, 17, 19, 23}. We remark that the

curves are deļ¬ned over F16 .

The case n = 15 is illustrated in [233]. A striking example is F2600 where

the GHS attack applies to 2202 curves and requires about 279 steps, which is

much less than the 2299 steps for the Pollard methods.

The case n = 31 has been discussed in [168],[181],[233]. The existing

methods do not yield a security reduction for random elliptic curves over Fq31 ,

VIII.5. FURTHER TOPICS 175

but do yield a very signiļ¬cant security reduction for special curves. Some of

these special curves are given as challenge curves in [233]. For example, over

F2155 and F2186 the Pollard methods have a run time of about 277 compared

to 237 and 292 compared to 242 for the GHS attack and a hyperelliptic C 0 ,

respectively. Example 7 shows some attack possibilities. For F2155 we expect

to transfer the DLP on an elliptic curve with a = 0 to a non-hyperelliptic

curve of genus 31 with approximate probability 3q ā’13/2 /(31r) ā 2ā’37 and a

run time of about 3q 9 /(31r) + q 31/4 ā 240 .

Further extension degrees and ļ¬eld sizes are investigated in [233]. The

above discussion shows that elliptic curves over composite extension ļ¬elds Fqn

with n ā {5, 6, 7, 8} (are likely to) oļ¬er less security due to the GHS attack

than expected. On the other hand, if n is a prime = 127 in the interval 100

to 600, then the GHS attack is infeasible and does not lead to a security

reduction for any elliptic curve over Fqn ; see [241] and Theorem VIII.5.

VIII.5. Further Topics

In this section we brieļ¬‚y discuss the Weil descent methodology and gen-

eralizations of the GHS attack in odd characteristic and for more general

curves. We also include some further applications.

The basic ideas of Section VIII.1 and Section VIII.2.1 can be generalized

to odd characteristic and to more general curves quite verbatim and are made

explicit by using Kummer and Artinā“Schreier constructions. Some indications

for the Artinā“Schreier case can already be found in Section VIII.2.6.

VIII.5.1. Kummer Constructions. The main reference here is [104], which

considers the case of elliptic and hyperelliptic curves in odd characteristic with

a particular emphasis on odd prime degree extension ļ¬elds. Since the sec-

ond roots of unity 1, ā’1 are always contained in the base ļ¬eld, an elliptic or

hyperelliptic curve H : Y 2 = f (X) deļ¬nes a Kummer extension H/K(X) of

degree two where H = K(H) is an elliptic or hyperelliptic function ļ¬eld. The

following statements are given and proved in [104].

Theorem VIII.15. Let K/k be an extension of ļ¬nite ļ¬elds of odd character-

istic and odd degree n = p pnp . Let H be an elliptic or hyperelliptic function

ļ¬eld of genus g and regular over K suitable for cryptographic applications.

Choose some element x ā H such that H/K(x) is of degree two, given by an

equation of the form y 2 = cf (x), where f is monic and c ā K Ć— .

Then, via the GHS attack, one obtains a function ļ¬eld C 0 regular over k

or its unique quadratic extension, an extension C/H of degree 2mā’1 for some

m ā¤ n with C = KC 0 , and a homomorphism from Pic0 (H) to Pic0 (C 0 ) with

K k

the following properties:

(i) If c = 1, C 0 /k is regular.

(ii) gC 0 ā¤ 2nā’1 ((g + 1)n ā’ 2) + 1.

176 VIII. WEIL DESCENT ATTACKS

(iii) If there exists some ļ¬eld L with k ā L ā K such that H/L(x) is

Galois, the large subgroup of prime order is not preserved under the

homomorphism.

(iv) If there does not exist such an L, the kernel of the homomorphism

contains only elements of 2-power order and

pnp )/(2g+2) ā’2

(

gC 0 ā„ 2 pnp ā’ 4 + 1.

p,np =0

p,np =0

(v) If n is prime, then additionally

gC 0 ā„ 2Ļ2 (n)ā’2 (n ā’ 4) + 1,

where Ļ2 (n) denotes the multiplicative order of 2 modulo n.

ĀÆ ĀÆ

(vi) If [KC : K(x)] ā„ 24 , then C/K(x) does not contain an intermediate

ļ¬eld which is rational and of index 2 in C.

Let Ļ be the extension of the Frobenius automorphism of K/k to K(x) via

Ļ(x) = x. Let U be the (multiplicative) F2 -subspace of K(x)Ć— /K(x)Ć—2 gener-

ated by the conjugates Ļ i (f ) and let U be the F2 -subspace of K(x)Ć— /K(x)Ć—2

ĀÆ ĀÆ ĀÆ

0

generated by U . Then C = KC is obtained by adjoining all square roots

of class representatives of U to K(x). Furthermore, [C : K(x)] = 2m and

ĀÆ ĀÆ ĀÆ

[KC : K(x)] = 2m , where m = dim U and m = dim U . Also, m = m if and

ĀÆ

ĀÆ ĀÆ

only if C/K is regular, and m = m ā’ 1 otherwise.

ĀÆ

For n = 5 and n = 7 there are families of elliptic curves over any extension

ļ¬eld of degree n for which gC 0 assumes the lower bounds 5 and 7, respectively,

given by (v). There is for example an elliptic curve over F100000197 whose group

order is four times a prime and which yields gC 0 = 7. Moreover, a deļ¬ning

polynomial for C 0 can be given in these cases. For n = 11, 13, 17, 19, 23 and

elliptic curves we have gC 0 ā„ 1793, 9217, 833, 983041, 9729. The attack is not

feasible for prime n ā„ 11.

A further study of Kummer techniques is carried out in [326] and leads

to examples of attackable (or reduced security) classes of elliptic and hy-

perelliptic curves for n = 2 and n = 3. We summarise the examples of

[104, 326, 106] in Table VIII.5.1. A nice table of smallest possible genera

depending on small values of n and g = gH is given in [106]. We remark that

[326] also deals with a class of superelliptic curves.

VIII.5.2. Artinā“Schreier Constructions. An elliptic or hyperelliptic curve

H : Y 2 + h(X)Y = f (X) in characteristic two deļ¬nes (after a transforma-

tion similar to the one from (VIII.1) to (VIII.2)) an Artinā“Schreier extension

H/K(X) of degree two where H = K(H) is an elliptic or hyperelliptic func-

tion ļ¬eld.

A generalization of the Artinā“Schreier construction for elliptic curves as

in [145] to hyperelliptic curves in characteristic two was ļ¬rst considered in

[131]. There conditions for the hyperelliptic curves are derived such that the

VIII.5. FURTHER TOPICS 177

Table VIII.3. Examples of [104, 326, 106] for a, ai ā K\k

and h ā k[X] (no Multiple Factors Allowed on the Right Hand

Sides of =)

C0

n H g gC 0

Y = (X ā’ a)h(X)

2

2 deg(h)/2 hyperell. 2g

Y 2 = (X ā’ a)h(X)

3 deg(h)/2 hyperell. 4g + 1

3 Y 2 = (X ā’ a)(X ā’ Ļ(a))h(X) (deg(h) ā’ 1)/2 hyperell. 4g ā’ 1

3 Y 2 = g+1 (X ā’ ai )(X ā’ Ļ(ai )) g ā“ 3g

i=1

Y 2 = iā{0,1,2,3} (X ā’ Ļ i (a))

5 1 ā“ 5

Y 2 = iā{0,1,2,4} (X ā’ Ļ i (a))

7 1 ā“ 7

construction of [145] carries through in an analogous way. Some examples of

the resulting curves are

Y 2 + XY = X 2g+1 + Ā· Ā· Ā· + c3 X 3 + c2 X 2 + c1 X + Īø,

Y 2 + XY = X 2g+1 + Ā· Ā· Ā· + c3 X 3 + c2 X 2 + ĪøX + c1 ,

Y 2 + XY = X 2g+1 + Ā· Ā· Ā· + ĪøX 3 + c3 X 2 + c2 X + c1 ,

Y 2 + XY = X 2g+1 + Ā· Ā· Ā· + Īø X 3 + c1 X 2 + ĪøX + Īø2 ,

where ci ā k, Īø, Īø ā K and Īø, Īø have n distinct conjugates. A bound

gC 0 ā¤ g2mā’1 for the genus of the corresponding C 0 holds, where m is de-

ļ¬ned similarly as in Section VIII.2.6.

Another family of curves is given in [327], of the form Y 2 + h(X)Y =

f (X)h(X) + (Ī±X + Ī²)h(X)2 with f, h ā k[X], Ī±, Ī² ā K and some further

conditions. Here the genus gC 0 is proven to be equal to g2mā’1 ā’ 1 or g2mā’1 .

A discussion of general Artinā“Schreier extensions is carried out in [168].

The main consequences for elliptic curves are presented in Section VIII.1. One

result for general Artinā“Schreier extensions is that gC 0 grows exponentially

in m whence the attack can only apply to very special families of curves or if

n is small. A similar statement holds true for Kummer extensions.

We remark that [327] and [168] also include Artinā“Schreier extensions in

characteristic p > 2.

VIII.5.3. Kernel of Norm-Conorm Maps and Genera. We consider a

generalization of the situation in Section VIII.1.2. Let E be a function ļ¬eld

of transcendence degree one over the ļ¬nite exact constant ļ¬eld K, C/E a

ļ¬nite extension and U a ļ¬nite subgroup of Aut(C). The ļ¬xed ļ¬eld of U in C

is denoted by C 0 . As in Section VIII.1.2, we obtain a homomorphism of the

divisor class groups Ļ : Pic0 (E) ā’ Pic0 (C 0 ) by NC/C 0 ā—¦ ConC/E , the conorm

K k

from E to C followed by the norm from C to C 0 . This situation is quite

general; for example, we do not require U to be abelian.

Theorem VIII.16. The kernel of Ļ satisļ¬es

178 VIII. WEIL DESCENT ATTACKS

(i) ker(NE/E V ) ā ker(Ļ), where V is any subgroup of U with V E ā E, so

V restricts to a subgroup of Aut(E) and E V is the ļ¬xed ļ¬eld of V in

E.

(ii) If the intersection E ā© ĻE is a function ļ¬eld and E, ĻE are linearly

disjoint over E ā© ĻE for every Ļ ā U , then

[C : E] Ā· ker Ļ ā ConE/Eā©ĻE Pic0 (E ā© ĻE) .

K

ĻāU \{1}

For example, E and ĻE are linear disjoint over E ā© ĻE if at least one is

Galois over E ā© ĻE.

The theorem applies in particular to the Kummer and Artinā“Schreier con-

structions discussed so far. Condition (i) basically means that for subļ¬eld

curves, ker(Ļ) contains the large prime factor subgroup of Pic0 (E). In con-

K

dition (ii) we have that the Pic0 (E ā© ĻE) do not contain the large prime

K

factor subgroup since E ā© ĻE = K(x), and [C : E] is also not divisible by

the large prime factor. As a result, ker(Ļ) does not contain the large prime

factor subgroup either.

A proof of a more general version of Theorem VIII.16 is given in [168].

The case of elliptic and hyperelliptic curves has been independently dealt

with in [104].

The genus of C 0 can be computed in a number of ways. A general way,

which also determines the L-polynomial of C 0 , is as follows. Let G be a

ļ¬nite subgroup of Aut(C) and let H and U be subgroups of G such that H

is normal in G, H ā© U = {1} and G = HU . The subgroup U operates on

H by conjugation. Assume further that H is elementary abelian of prime

exponent l and let { HĪ½ | Ī½ ā I } be a system of representatives under the

operation of U on the subgroups of H of index l for some index set I. Let UĪ½

be the largest subgroup of U which leaves HĪ½ invariant. If A is any subgroup

of G, then the ļ¬xed ļ¬eld of A in C is denoted by C A and the degree of the

exact constant ļ¬eld of C A over that of C G by dC A .

Theorem VIII.17. Under the above assumptions the L-polynomials satisfy

LC U (tdC U ) / LC G (t) = LC HĪ½ UĪ½ (tdC HĪ½ UĪ½ ) / LC HUĪ½ (tdC HUĪ½ ).

Ī½āI

Corollary VIII.18. The genera satisfy the equation

dC U gC U ā’ gC G = dC HĪ½ UĪ½ gC HĪ½ UĪ½ ā’ dC HUĪ½ gC HUĪ½ .

Ī½āI

Theorem VIII.17 and Corollary VIII.18 are proved in [168]. They can

be applied to the Artinā“Schreier and prime degree Kummer constructions

quite straightforwardly by analysing the deļ¬ning groups ā (and U as in

Section VIII.5.1).

VIII.5. FURTHER TOPICS 179

VIII.5.4. Construction of Models. The construction of explicit deļ¬ning

equations for C 0 obtained by the Kummer or Artinā“Schreier constructions

and the computation of images under Ļ by means of computer algebra systems

is quite technical but does not pose principal algorithmic problems. We refer

to [145, 168, 131, 104, 326, 327] for details.

VIII.5.5. Trap Door Systems. The GHS attack with isogenies from Sec-

tion VIII.3 can also be used constructively for a trap door system [324]. The

basic idea is as follows. A user creates a secret elliptic curve Es which is sus-

ceptible to the GHS attack. The user then computes a public elliptic curve Ep

by means of a secret, suļ¬ciently long and random isogeny chain starting at

Es . The curve Es and the isogeny chain are submitted to a trusted authority

for key escrow, while Ep is used as usual in elliptic curve cryptosystems. The

parameters are chosen such that the Pollard methods are the most eļ¬cient

way to solve the DLP on Ep , while solving the DLP on Es is much easier but

still suļ¬ciently hard. The trusted authority thus has to invest considerable

computing power to decrypt which makes widespread wire tapping infeasible.

For further details and parameter choices see [324].

VIII.5.6. Other Approaches. Covering techniques can also be applied

when the target function ļ¬eld E comes from a true subļ¬eld curve. The

methods described so far do not readily apply because ĻE = E, in view of

Theorem VIII.16. One strategy to overcome this problem is to perform a

suitable change of variable such that there are n diļ¬erent conjugate ļ¬elds

Ļ i (E), so basically one considers a diļ¬erent Ļ. Accordingly, another strategy

is to twist Ļ by an automorphism Ļ„ of order n such that there are n diļ¬erent

conjugate ļ¬elds (ĻĻ„ )i (E). If E0 is the target ļ¬eld deļ¬ned over k, such that

E = E0 K, then this strategy leads to the construction of suitable extensions

C0 /E0 and Ļ„0 ā Aut(C0 ) with Ļ„0 (E0 ) = E0 and departs from the Kummer

and Artinā“Schreier paradigms. We refer to [103, 106] for details. As a con-

sequence, with respect to an extension K/k of degree 3 and char(k) = 2, 3,

the DLP (in the trace zero group) of a genus 2 curve can always be trans-

formed into a DLP of a genus 6 curve deļ¬ned over k. For a non-negligible

percentage even genus 5 is possible, which leads to a more eļ¬cient attack via

index calculus than by the Pollard methods.

A further approach described in [106] uses special classes of hyperelliptic

curves deļ¬ned over k which admit maps to elliptic curves deļ¬ned over K. The

genus of these hyperelliptic curves is equal to n = [K : k], so these attacks

would be very eļ¬cient. However, the maps between the curves are not (yet)

known explicitly and upper bounds for their degrees are very large.

We close with two more remarks. In [45] the GHS construction is used

ĀÆ

to construct elliptic curves over F2 (x) of high rank with constant j-invariant.

In [290] a covering technique is used to construct genus 2 curves deļ¬ned

over k with Jacobian isogenous to the Weil restriction of a large class of

180 VIII. WEIL DESCENT ATTACKS

elliptic curves deļ¬ned over K with respect to a quadratic extension K/k of

ļ¬nite ļ¬elds in odd characteristic. This allows for SEA point counting while

avoiding patents in ECC (see also [170, 132]).

Part 4

Pairing Based Techniques

CHAPTER IX

Pairings

S. Galbraith

Pairings in elliptic curve cryptography are functions which map a pair

of elliptic curve points to an element of the multiplicative group of a ļ¬nite

ļ¬eld. They have been used in several diļ¬erent contexts. The purpose of

this chapter is to explain some of the mathematics behind pairings, to show

how they may be implemented and to give some applications of them. This

builds on material of III.5 and V.2 of [ECC]. Cryptographic schemes based

on pairings will be described in Chapter X.

IX.1. Bilinear Pairings

Let n be a positive integer. Let G1 and G2 be abelian groups written

in additive notation with identity element 0. Suppose that G1 and G2 have

exponent n (i.e., [n]P = 0 for all P ā G1 , G2 ). Suppose G3 is a cyclic group of

order n written in multiplicative notation with identity element 1. A pairing

is a function

e : G1 Ć— G2 ā’ā’ G3 .

All pairings we consider will satisfy the following additional properties:

ńņš. 6 |