Cryptography Reference
In-Depth Information
of degree not divisible by
r
and if
φ
can be efficiently computed then we have such a
reduction.
As we have seen, if there is a very large prime dividing the conductor of End(
E
) but not
the conductor of End(
E
) (or vice versa) then it is not efficient to compute an isogeny from
E
to
E
. In this case, one cannot make any inference about the relative difficulty of the DLP
in the two groups. No example is known of elliptic curves
E
and
E
of this form (i.e., with
a large conductor gap) but for which the DLP on one is known to be significantly easier
than the DLP on another. The nearest we have to an example of this phenomenon is with
elliptic curves
E
with #Aut(
E
)
>
2 (and so one can accelerate the Pollard rho method using
equivalence classes as in Section
14.4
) but with an isogeny from
E
to
E
with #Aut(
E
)
=
2.
On the other hand, if the conductors of End(
E
) and End(
E
)havethesameverylarge
prime factors (or no large prime factors) then we can (conditional on a generalised Riemann
hypothesis) compute an isogeny between them in
O
(
q
1
/
4
) bit operations. This is not a
polynomial-time reduction. But, since the current best algorithms for the DLP on elliptic
curves run in
O
(
q
1
/
2
) bit operations, it shows that from a practical point of view the two
DLPs are equivalent.
Jao, Miller and Venkatesan [
277
] have a different, and perhaps more useful, interpretation
of the isogeny algorithms in terms of random self-reducibility of the DLP in an isogeny
class of elliptic curves. The idea is that if
E
is an elliptic curve over
F
q
then by taking
a relatively short random walk in the isogeny graph one arrives at a “random” (again
ignoring the issue of large primes dividing the conductor) elliptic curve
E
over
F
q
such
that #
E
(
F
q
). Hence, one easily turns a specific instance of the DLP (i.e., for a
specific elliptic curve) into a random instance. It follows that if there were a “large” set
of “weak” instances of the DLP in the isogeny class of
E
then, after enough trials, one
should be able to reduce the DLP from
E
to one of the elliptic curves in the weak class.
One concludes that either the DLP is easy for “most” curves in an isogeny class, or is hard
for “most” curves in an isogeny class.
F
q
)
=
#
E
(
