Cryptography Reference
In-Depth Information
ring End(
E
) is isomorphic either to an order in a quaternion algebra or to an
order in an imaginary quadratic field [15, V.3.1]; in the first case we say
E
is
supersingular and in the second case we say
E
is ordinary.
Two elliptic curves
E
1
and
E
2
defined over
F
q
are said to be isogenous over
F
q
if there exists an isogeny
φ
:
E
1
→
E
2
defined over
F
q
.AtheoremofTate
states that two curves
E
1
and
E
2
are isogenous over
F
q
if and only if #
E
1
(
F
q
)=
#
E
2
(
3]. Since every isogeny has a dual isogeny [15, III.6.1], the property
of being isogenous over
F
q
)[21,
§
¯
F
q
is an equivalence relation on the finite set of
F
q
-
isomorphism classes of elliptic curves defined over
F
q
. Accordingly, we define
an isogeny class to be an equivalence class of elliptic curves, taken up to
¯
F
q
-
isomorphism, under this equivalence relation.
The
-torsion group of
E
, denoted
E
[
], is the set of all points
P
E
(
¯
∈
F
q
)such
,wehave
E
[
]
=
Z
that
P
is the identity. For
such that
p
.
Curves in the same isogeny class are either all supersingular or all ordinary.
Traditionally, most elliptic curve cryptography uses ordinary curves; however,
for this work we will be interested in supersingular curves. We assume for the
remainder of this paper that we are in the supersingular case.
Supersingular curves are all defined over
/
Z
⊕
Z
/
Z
p
,there
exist
+ 1 isogenies (counting multiplicities) of degree
originating from any
given such supersingular curve. Given an elliptic curve
E
and a finite subgroup
Φ
of
E
, there is up to isomorphism a unique isogeny
E
F
p
2
, and for every prime
E
having kernel
Φ
[15, III.4.12]. Hence we can identify an isogeny by specifying its kernel, and
conversely given a kernel subgroup the corresponding isogeny can be computed
using Velu's formulas [24]. Typically, this correspondence is of little use, since the
kernel, or any representation thereof, is usually as unwieldy as the isogeny itself.
However, in the special case of kernels generated by
→
F
p
2
-rational points of smooth
order, specifying a generator of the kernel allows for compact representation and
e
cient computation of the corresponding isogeny, as we demonstrate below.
3 Public-Key Cryptosystems Based on Supersingular
Curves
In this section we present a key-exchange protocol and a public-key cryptosys-
tem analogous to those of [14,19], using supersingular elliptic curves. Since the
discrete logarithm problem is unimportant when elliptic curves are used in an
isogeny-based system, we propose using supersingular curves of smooth order to
improve performance. In the supersingular setting, it is easy to construct curves
of smooth order, and using a smooth order curve will give a large number of
isogenies that are fast to compute. Specifically, we fix
F
q
=
F
p
2
as the field
of definition, where
p
is a prime of the form
e
A
e
B
1. Here
A
and
B
are small primes, and
f
is a cofactor such that
p
is prime. Alice and Bob will
each take a random walk on a different isogeny graph; Alice will use the graph
consisting of isogenies of degrees
A
, and Bob will use the graph of degree
B
isogenies. The main technical modification is that, since ideal classes no longer
commute (or indeed even multiply together) in the supersingular case, extra
·
f
±
