Cryptography Reference
In-Depth Information
Towards Quantum-Resistant Cryptosystems
from Supersingular Elliptic Curve Isogenies
David Jao
1
and Luca De Feo
2
1
Department of Combinatorics and Optimization
University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada
djao@math.uwaterloo.ca
2
Laboratoire PRiSM
Universite de Versailles, 78035 Versailles, France
http://www.prism.uvsq.fr/~dfl
Abstract.
We present new candidates for quantum-resistant public-key
cryptosystems based on the conjectured diculty of finding isogenies
between supersingular elliptic curves. The main technical idea in our
scheme is that we transmit the images of torsion bases under the isogeny
in order to allow the two parties to arrive at a common shared key despite
the noncommutativity of the endomorphism ring. Our work is motivated
by the recent development of a subexponential-time quantum algorithm
for constructing isogenies between ordinary elliptic curves. In the super-
singular case, by contrast, the fastest known quantum attack remains ex-
ponential, since the noncommutativity of the endomorphism ring means
that the approach used in the ordinary case does not apply. We give
a precise formulation of the necessary computational assumption along
with a discussion of its validity. In addition, we present implementation
results showing that our protocols are multiple orders of magnitude faster
than previous isogeny-based cryptosystems over ordinary curves.
Keywords:
elliptic curves, isogenies,
quantum-resistant public-key
cryptosystems.
1
Introduction
The Die-Hellman scheme is a fundamental protocol for public-key exchange
between two parties. Its original definition over finite fields is based on the hard-
ness of computing the map
g, g
a
,g
b
∈
F
p
, while its elliptic curve
analogue depends on the diculty of computing
P, aP, bP
g
ab
for
g
→
abP
for points
P
on an elliptic curve. Recently, Stolbunov [19] proposed a Die-Hellman type
system based on the diculty of computing isogenies between ordinary ellip-
tic curves, with the stated aim of obtaining quantum-resistant cryptographic
protocols. The fastest known (classical) probabilistic algorithm for solving this
problem is the algorithm of Galbraith and Stolbunov [9], based on the algorithm
of Galbraith, Hess, and Smart [8]. This algorithm is exponential, with a worst-
case running time of
O
(
√
q
). However, on a quantum computer, recent work of
→
