Cryptography Reference
In-Depth Information
The common
j
-invariant of
E
AB
=
E
BA
, computed by both Alice and Bob,
is equal to
j
(
E
AB
) = 1437145494362655119168482808702111413744
i
+ 833498096778386452951722285310592056351
.
7Conluon
We propose a new family of conjecturally quantum-resistant cryptographic pro-
tocols for key exchange and public-key cryptosystems using isogenies between
supersingular elliptic curves of smooth order. In order to compensate for the
noncommutative endomorphism rings that arise in this setting, we introduce the
idea of providing the images of torsion bases as part of the protocol. Against
the fastest known attacks, the resulting scheme improves upon all previous
isogeny-based schemes by orders of magnitude in performance at conventional se-
curity levels, making it the first practical isogeny-based public-key cryptosystem.
Unlike prior such schemes, our proposal admits no known subexponential-time
attacks even in the quantum setting.
Acknowledgements.
We thank Andrew M. Childs, Alfred Menezes, Vladimir
Soukharev, and the anonymous reviewers for helpful comments and suggestions.
This work is supported in part by NSERC CRD Grant CRDPJ 405857-10.
References
1. Bostan, A., Morain, F., Salvy, B., Schost, E.: Fast algorithms for computing iso-
genies between elliptic curves. Math. Comp. 77(263), 1755-1778 (2008)
2. Broker, R.: Constructing supersingular elliptic curves. J. Comb. Number The-
ory 1(3), 269-273 (2009)
3. Canetti, R., Krawczyk, H.: Analysis of Key-Exchange Protocols and their Use for
Building Secure Channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS,
vol. 2045, pp. 453-474. Springer, Heidelberg (2001)
4. Charles, D., Lauter, K., Goren, E.: Cryptographic hash functions from expander
graphs. Journal of Cryptology 22, 93-113 (2009)
5. Childs, A., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum
subexponential time (2010),
http://arxiv.org/abs/1012.4019/
6. Couveignes, J.: Hard homogeneous spaces (2006),
http://eprint.iacr.org/2006/291/
7. Galbraith, S.: Constructing isogenies between elliptic curves over finite fields. LMS
J. Comput. Math. 2, 118-138 (1999)
8. Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil Descent Attack.
In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 29-44. Springer,
Heidelberg (2002)
9. Galbraith, S., Stolbunov, A.: Improved algorithm for the isogeny problem for or-
dinary elliptic curves (2011),
http://arxiv.org/abs/1105.6331/
10. Joux, A.: The Weil and Tate Pairings as Building Blocks for Public Key Cryp-
tosystems. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp.
20-32. Springer, Heidelberg (2002)
