Cryptography Reference
In-Depth Information
F
p
to an elliptic curve
E
over
he considered “lifting” an elliptic curve
E
over
Q
(i.e., so
that reducing the coefficients of
E
modulo
p
yields
E
). The factor base
was defined to
be the points of small height (see Section VIII.6 of [
505
] for details of heights) in
E
(
B
).
The theory of descent (see Chapter VIII of Silverman [
505
]) essentially gives an algorithm
to decompose a point as a sum of points of small height (when this is possible). The idea
would therefore be to take random points [
a
]
P
Q
F
p
), lift them to
E
(
) and then
decompose them over the factor base. There are several obstructions to this method. First,
lifting a random point from
E
(
+
[
b
]
Q
∈
E
(
Q
F
p
)to
E
(
) seems to be hard in general. Indeed, Miller
argued (see also [
507
]) that there are very few points of small height in
E
(
Q
Q
) and so (since
we are considering random points [
a
]
P
+
[
b
]
Q
from the exponentially large set
E
(
F
p
)) it
would be necessary to lift to exponentially large points in
E
(
). Second, the lifting itself
seems to be a non-trivial computational task (essentially, solving a non-linear diophantine
equation over
Q
).
Silverman propsed the
Xedni calculus
attack,
11
which was designed to solve the lifting
problem. This algorithm was analysed in [
288
], where it is shown that the probability of
finding useful relations is too low.
By now, many people have tried and failed to discover an index calculus algorithm for
the DLP on general elliptic curves. However, this does not prove that no such algorithm
exists, or that a different paradigm could not lead to faster attacks on the elliptic curve DLP.
Z
11
“Xedni” is “Index” spelled backwards.
