Cryptography Reference
In-Depth Information
The first term in equation (
15.11
) is the running time for relation generation. If
g
is fixed
then asymptotically this is dominated by the second term, which is the running time for
the linear algebra stage. If
g
is fixed, then the running time is
O
(
q
2
) bit operations. Hence
Gaudry's algorithm is asymptotically faster than Pollard's rho method for hyperelliptic
curves of a fixed genus
g
5. However, the hidden constant in the expression
O
(
q
2
)
depends very badly on
g
. In practice, Gaudry's method seems to be superior to rho for
small
g
(e.g.,
g
≥
5
,
6
,
7).
Harley and Theriault (see [
545
]) suggested reducing the factor base size in Gaudry's
algorithm in order to balance the running times of the relation generation and linear algebra
stages. Theriault [
545
] also proposed a “large prime” variant of Gaudry's algorithm. Gaudry,
Theriault, Thome and Diem [
229
] proposed a “double large prime” variant of Gaudry's
algorithm that is based on the double large prime strategy that was successful in accelerating
integer factorisation algorithms. The factor base
=
B
is now chosen to be a subset of the degree
1 divisors, and degree 1 divisors that are not in
are called
large primes
. A divisor is defined
to be smooth if it can be written as a sum of prime divisors and at most two large primes.
Relations are collected as before, and then combined to eliminate the large primes (we
refer to Section 21.3 of [
16
] for further discussion of large primes and graph methods
for eliminating them). It is shown in [
229
] that, for fixed
g
, the expected running time of
the algorithm is
B
2
g
) bit operations. This is faster than Pollard rho for
g
O
(
q
2
−
3 when
q
is sufficiently large. Gaudry's approach was generalised to all curves of fixed genus by
Diem [
164
].
≥
15.7 Weil descent
As we have seen, there are subexponential algorithms for the DLP in the divisor class group
of a hyperelliptic curve of high genus. A natural approach to solve the DLP on elliptic
curves is therefore to transform the problem into a DLP on a high genus curve. However,
the naive way to do this embeds a small problem into a big one, and does not help to solve
the DLP. Frey proposed
10
to use Weil restriction of scalars to transform the DLP on an
elliptic curve
E
(
F
q
n
)for
n>
1 to the DLP on a curve of genus
g
≥
n
over
F
q
. Frey called
this idea
Weil descent
.
Geometrically, the principle is to identify the Weil restriction of an open affine subset
of
E
(
F
q
of dimension
n
. One can then try to find a curve
C
on
A
so that there is a map from the
Jacobian of
C
to
A
. Following Gaudry, Hess and Smart [
226
] it is more convenient to
express the situation in terms of function fields and divisor class groups. We only sketch
the details since an excellent survey is provided by Hess in Chapter VIII of [
61
] and many
important details are explained by Diem in [
159
].
F
q
n
) (see Section
5.7
) with an open affine subset of an Abelian variety
A
over
10
The standard reference is a lecture given by Frey at the ECC 1998 conference. His talk was mostly about a different (constructive)
application of Weil restriction of scalars. However, he did mention the possibility of using this idea for an attack. Galbraith
and Smart developed the details further in [
212
] and many works followed.
