Cryptography Reference
In-Depth Information
Childs et al. [5] has shown that the private keys in Stolbunov's system can be
recovered in subexponential time. Moreover, even if we only consider classical at-
tacks in assessing security levels, Stolbunov's scheme requires 229 seconds (even
with precomputation) to perform a single key exchange operation at the 128-bit
security level on a desktop PC [19, Table 1].
In this work we present isogeny-based cryptosystems that address both the
performance and security drawbacks of Stolbunov's system. Our scheme achieves
performance on the order of one second (cf. Section 6) at the 128-bit security level
(as measured against the fastest known quantum attacks) using desktop PCs,
making it far faster than Stolbunov's scheme. In terms of security, our scheme
is not vulnerable to the algorithm of Childs et al. [5], nor to any algorithm of
this type, since it is not based on a group action. The fastest known attacks
against our scheme, even on quantum computers, require fully exponential time.
Our scheme involves a new computational assumption upon which its quantum
resistance is based, and like all new computational assumptions, further study
and the passage of time is needed for validation. Nevertheless, we believe our
proposal represents a promising candidate for quantum-resistant isogeny-based
public-key cryptography.
Our proposal uses isogenies between
supersingular
elliptic curves rather than
ordinary elliptic curves. The main technical diculty is that, in the supersingular
case, the endomorphism ring is noncommutative, whereas Die-Hellman type
protocols require commutativity. We show how to overcome this obstacle by
providing the outputs of the isogeny on certain points as auxiliary input to the
protocol. To the best of our knowledge, nothing similar to this idea has ever
previously appeared in the literature. Providing this auxiliary input does not
seem to make the problem of finding isogenies any easier; see Section 5.2 for a
full discussion. The multiple orders of magnitude of performance gains in our
scheme arise from the fact that supersingular isogeny graphs are much faster
to navigate than ordinary graphs. In Section 5.1 we provide formal statements
of the hardness assumptions and security reductions for our system. Finally,
in Section 6 we present implementation results confirming the correctness and
performance of our protocol.
2
Isogenies
Let
E
1
and
E
2
be elliptic curves defined over a finite field
F
q
. An isogeny
φ
:
E
1
→
E
2
defined over
F
q
is a non-constant rational map defined over
F
q
which is
also a group homomorphism from
E
1
(
F
q
) [15, III.4]. The degree of an
isogeny is its degree as a rational map. For separable isogenies, to have degree
means to have kernel of size
. Every isogeny of degree greater than 1 can be
factored into a composition of isogenies of prime degree over
¯
F
q
)to
E
2
(
F
q
[6].
An endomorphism of an elliptic curve
E
defined over
F
q
is an isogeny
E
→
E
defined over
F
q
m
for some
m
. The set of endomorphisms of
E
together with the
zero map forms a ring under the operations of pointwise addition and composi-
tion; this ring is called the endomorphism ring of
E
and denoted End(
E
). The
