Cryptography Reference
In-Depth Information
In the relation generation stage, one attempts to decompose a randomly selected point
R
∈
E
(
F
q
n
)asasumofpointsin
B
. Gaudry observed that this can be accomplished by
finding solutions
q
such that
(
x
1
,x
2
,...,x
n
)
∈ F
Summ
n
+
1
(
x
1
,x
2
,...,x
n
,x
R
)
=
0
.
(15.13)
Note that Summ
n
+
1
(
x
1
,...,x
n
,x
R
)
F
q
n
and
x
R
∈ F
q
n
. The conditions
x
j
∈ F
q
in equation (
15.13
) can be expressed algebraically as
follows. Select a basis
∈ F
q
n
[
x
1
,...,x
n
] since
E
is defined over
{
θ
1
,...,θ
n
}
for
F
q
n
over
F
q
and write
n
Summ
n
+
1
(
x
1
,...,x
n
,x
R
)
=
G
i
(
x
1
,...,x
n
)
θ
i
(15.14)
i
=
1
∈ F
q
[
x
1
,...,x
n
]. Note that the degree of
G
i
in
x
j
is at most 2
n
−
1
.
The polynomials
G
i
of equation (
15.14
) define an algebraic set in
X
where
G
i
(
x
1
,...,x
n
)
n
and we are
⊆ A
interested in the points in
X
(
F
q
) (if there are any). Since
F
q
is finite there are only finitely
many
F
q
-rational solutions (
x
1
,...,x
n
) to the system.
Gaudry assumes that
X
is generically a zero-dimensional algebraic set (Gaudry justifies
this assumption by noting that if
F
is a variety then the variety
F
n
is
n
-dimensional, and so
the map from
F
n
to the Weil restriction of
E
, given by adding together
n
points in
F
,isa
morphism between varieties of the same dimension, and so generically has finite degree).
The
F
q
-rational solutions can therefore be found by finding a Grobner basis for the ideal
generated by the
G
i
and then taking roots in
F
q
of a sequence of univariate polynomials
each of which has degree at most 2
n
(
n
−
1)
. This is predicted to take
O
(2
cn
(
n
−
1)
M
(log(
q
))) bit
operations for some constant
c
. Alternatively, one could add some field equations
x
j
−
x
j
to the ideal, to ensure it is zero-dimensional, but this could have an adverse effect on
the complexity. Gaudry makes a further heuristic assumption, namely that the smoothness
probability behaves as expected when using the large prime variant.
The size of the set
is approximately
q
n
/n
! and so the
expected number of points
R
that have to be selected before a relation is obtained is about
n
!. One needs approximately #
{
P
1
+
P
2
+···+
P
n
:
P
i
∈
B
}
q
relations to be able to find a non-trivial element in
the kernel of the relation matrix and hence integers
a
and
b
such that [
a
]
D
1
+
B
≈
[
b
]
D
2
≡
0.
It follows that the heuristic expected running time of Gaudry's algorithm is
O
(2
cn
(
n
−
1)
n
!
qM
(log(
q
))
q
2
+
o
(1)
)
+
(15.15)
bit operations as
q
. This is exponential in terms of
n
and log(
q
). However, for fixed
n
, the running time can be expressed as
O
(
q
2
) bit operations.
Gaudry's focus was on
n
fixed and relatively small. For any fixed
n
→∞
≥
5 Gaudry's
heuristic algorithm for solving the ECDLP over
F
q
n
is asymptotically faster than Pollard's
rho method. The double large prime variant (mentioned in Section
15.6.3
) can also be
used in this setting. The complexity therefore becomes (heuristic)
2
n
) bit operations.
Hence, Gaudry's algorithm is asymptotically faster than Pollard rho even for
n
O
(
q
2
−
=
3 and
