Cryptography Reference
In-Depth Information
O
(
q
4
/
3
) rather than
O
(
q
3
/
2
)for
n
O
(
q
3
/
2
) rather than
O
(
q
2
)for
=
=
n
4, namely
3 and
n
=
4.
15.8.3 Diem's algorithm for the ECDLP
Gaudry's focus was on the DLP in
E
(
F
q
n
) when
n
is fixed. This yields an exponential-time
algorithm. Diem [
160
,
163
] considered the case where
n
is allowed to grow, and obtained
a subexponential-time algorithm.
The crux of Diem's method is remarkably simple: he assumes
n
≈
√
log(
q
) and obtains
F
q
n
) with complexity
O
(
q
c
) for some constant
c
(note that
even some exponential-time computations in
n
are polynomial in
q
as
e
n
2
an algorithm for the DLP in
E
(
q
). Now,
q
c
≈
=
exp(
c
log(
q
)) and log(
q
n
)
exp(
c
log(
q
n
)
2
/
3
)
<L
q
n
(2
/
3
,c
).
Diem's algorithm is very similar to Gaudry's. In Gaudry's algorithm, the factor base
consists of points whose
x
-coordinates lie in
log(
q
)
3
/
2
so
q
c
=
n
log(
q
)
≈
≈
F
q
. Diem defines a function
ϕ
=
α
◦
x
, where
1
α
is an automorphism over
F
q
n
of
P
that satisfies a certain condition, and defines the
1
(
factor base to be
. The process of generating relations
proceeds in the standard way. Some important contributions of [
163
] are to prove that
the algebraic set defined by the summation polynomials has a good chance of having
dimension 0, and that when this is the case the points can be found by taking resultants of
multi-homogeneous polynomials in time polynomial in
e
n
2
log(
q
) (which is exponential in
n
but polynomial in
q
).
The main result of [
163
] is the following. We stress that this result does not rely on any
heuristics.
B
={
P
∈
E
(
F
q
n
):
ϕ
(
P
)
∈ P
F
q
)
}
Theorem 15.8.4
(Diem) Let a,b
∈ R
be such that
0
<a<b. There is an algorithm for
F
q
n
such that if q is a prime power and n
∈ N
the DLP in
is such that
a
log(
q
)
b
log(
q
)
≤
n
≤
F
q
n
in an expected e
O
(log(
q
n
)
2
/
3
)
bit operations.
then the algorithm solves the DLP in
15.9 Further results
To end the chapter we briefly mention some methods for non-hyperelliptic curves. It
is beyond the scope of the topic to present these algorithms in detail. We then briefly
summarise the argument that there is no subexponential algorithm for the DLP on elliptic
curves in general.
15.9.1 Diem's algorithm for plane curves of low degree
Diem [
161
] used the Adleman-DeMarrais-Huang idea of generating relations using prin-
cipal divisors
a
(
x
)
−
yb
(
x
) for the DLP on plane curves
F
(
x,y
)
=
0 of low degree (the
