Skip to Main content Skip to Navigation
Conference papers

Towards practical key exchange from ordinary isogeny graphs

Luca de Feo 1 Jean Kieffer 2, 3 Benjamin Smith 4
2 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
4 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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 encryp-tion, thus providing an important step towards efficient post-quantum non-interactive key exchange (NIKE).
Complete list of metadata

Cited literature [78 references]  Display  Hide  Download
Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Wednesday, September 19, 2018 - 2:05:12 PM
Last modification on : Saturday, December 4, 2021 - 3:43:32 AM
Long-term archiving on: : Thursday, December 20, 2018 - 12:52:28 PM


Files produced by the author(s)


  • HAL Id : hal-01872817, version 1
  • ARXIV : 1809.07543



Luca de Feo, Jean Kieffer, Benjamin Smith. Towards practical key exchange from ordinary isogeny graphs. ASIACRYPT 2018 - 24th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2018, Brisbane, Australia. ⟨hal-01872817⟩



Les métriques sont temporairement indisponibles