Cryptography Reference
In-Depth Information
25
Isogenies of elliptic curves
Isogenies are a fundamental object of study in the theory of elliptic curves. The definition
and basic properties were given in Sections 9.6 and 9.7 . In particular, they are group
homomorphisms.
Isogenies are used in algorithms for point counting on elliptic curves and for computing
class polynomials for the complex multiplication (CM) method. They have applications
to cryptanalysis of elliptic curve cryptosystems. They also have constructive applications:
prevention of certain side-channel attacks; computing distortion maps for pairing-based
cryptography; designing cryptographic hash functions; relating the discrete logarithm prob-
lem on elliptic curves with the same number of points. We do not have space to discuss all
these applications.
The purpose of this chapter is to present algorithms to compute isogenies from an elliptic
curve. The most important result is Velu's formulae, which compute an isogeny given an
elliptic curve and a kernel subgroup G . We also sketch the various ways to find an isogeny
given an elliptic curve and the j -invariant of an elliptic curve -isogenous to E . Once
these algorithms are in place we briefly sketch Kohel's results, the isogeny graph and some
applications of isogenies. Due to lack of space we are unable to give proofs of most results.
Algorithms for computing isogenies on Jacobians of curves of genus 2 or more are much
more complicated than in the elliptic case. Hence, we do not discuss them in this topic.
25.1 Isogenies and kernels
Let E : y 2
x 3
a 2 x 2
+
a 1 xy
+
a 3 =
+
+
a 4 x
+
a 6 be an elliptic curve over
k
. Recall from
E over
Section 9.6 that a non-zero isogeny φ : E
k
of degree d is a morphism of degree
d such that φ (
= O E . Such a map is automatically a group homomorphism and has
kernel of size dividing d .
Theorem 9.7.5 states that a separable isogeny φ : E
O E )
E over
k
may be written in the
form
( φ 1 ( x ) ,cyφ 1 ( x ) +
φ ( x,y )
=
φ 3 ( x ))
(25.1)
( x ), where φ 1 ( x ) =
where φ 1 ( x ) 3 ( x )
∈ k
1 ( x ) /dx is the (formal) derivative of the
is a non-zero constant and where (writing
rational function φ 1 ( x ), where c
∈ k
a i for the
Search WWH ::




Custom Search