<<

. 6
( 10)



>>

2g
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
( 10)



>>