Paper 2018/485

Towards practical key exchange from ordinary isogeny graphs

Luca De Feo, Jean Kieffer, and Benjamin Smith

Abstract

We revisit the ordinary isogeny-graph based cryptosystems of Couveignes and Rostovtsev–Stolbunov, long dismissed as impractical. We give algorithmic improvements that accelerate key exchange in this framework, and explore the problem of generating suitable system parameters for contemporary pre- and post-quantum security that take advantage of these new algorithms. We also prove the session-key security of this key exchange in the Canetti–Krawczyk model, and the IND-CPA security of the related public-key encryption scheme, under reasonable assumptions on the hardness of computing isogeny walks. Our systems admit efficient key-validation techniques that yield CCA-secure encryption, thus providing an important step towards efficient post-quantum non-interactive key exchange.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
post-quantum cryptographykey exchangeelliptic curvesisogenies
Contact author(s)
luca de-feo @ uvsq fr
History
2018-05-23: received
Short URL
https://ia.cr/2018/485
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/485,
      author = {Luca De Feo and Jean Kieffer and Benjamin Smith},
      title = {Towards practical key exchange from ordinary isogeny graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/485},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/485}},
      url = {https://eprint.iacr.org/2018/485}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.