Cryptography Reference
In-Depth Information
a
i
or b
i
. After a walk hits a distinguished point there are two choices: it could be allowed to
continue or it could be restarted at a
j
-invariant obtained by taking a short random isogeny
chain (perhaps corresponding to primes not in
S
)from
E
or
E
.
Once a collision is detected one has an isogeny corresponding to ideal a from
j
(
E
)to
some
j
, and an isogeny corresponding to ideal b from
j
(
E
)to
j
. Hence, the ideal ab
−
1
gives the isogeny from
j
(
E
)to
j
(
E
).
Stolbunov has noted that, since the ideal class group is Abelian, it is not advisable to
choose
S
such that l
,
l
−
1
S
(since such a choice means that walks remain “close” to the
original
j
-invariant, and cycles in the random walk might arise). It is also faster to use
isogenies of small degree more often than those with large degree. We refer to Galbraith
and Stolbunov [
213
] for further details.
The remaining problem is that the ideal ab
−
1
is typically of large norm. By construction, it
is a product of exponentially many small primes. Since the ideal class group is commutative,
such a product has a short representation (storing the exponents for each prime), but this
leads to an isogeny that requires exponential computation. The proposal from [
204
]is
to represent ideals using the standard representation for ideals in quadratic fields, and to
“smooth” the ideal using standard techniques from index calculus algorithms in ideal class
groups. It is beyond the scope of this topic to discuss these ideas in detail. However, we note
that the isogeny then has subexponential length and uses primes
of subexponential degree.
Hence, the second stage of the isogeny computation is subexponential-time; this is not as
fast as it would be with the basic Galbraith algorithm. The idea of smoothing an isogeny
has also been used by Broker, Charles and Lauter [
101
] and Jao and Soukharev [
279
].
Since the ordinary isogeny graph is conjecturally an expander graph, we know that a
random walk on it behaves close to the uniform distribution after sufficiently many steps.
We make the heuristic assumption that the pseudorandom walk proposed above has this
property when the number of different primes used is sufficiently large and the hash function
H
is good. Then, by the birthday paradox, one expects a collision after
√
πh
(
∈
) vertices
have been visited. As a result, the heuristic expected running time of the algorithm is
O
(
q
1
/
4
) isogeny chain steps, and the storage can be made low by making distinguished
elements rare. The algorithm can be distributed: using
L
processors of equal power one
solves the isogeny problem in
O
O
(
q
1
/
4
/L
) bit operations.
25.6 Relating the discrete logarithm problem on isogenous curves
The main application of the algorithms in Section
25.5
is to relate the discrete logarithm
problem on curves with the same number of points. More precisely, let
E
and
E
be elliptic
curves over
#
E
(
F
q
). A natural
question is whether the discrete logarithm problem (in the subgroup of order
r
) has the
same difficulty in both groups
E
(
F
q
with #
E
(
F
q
)
=
F
q
). Let
r
be a large prime dividing #
E
(
F
q
) and
E
(
F
q
). To study this question one wants to reduce
F
q
)to
E
(
→
E
the discrete logarithm problem from
E
(
F
q
). If we have an isogeny
φ
:
E
