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 metadatas

Cited literature [72 references]  Display  Hide  Download

https://hal.inria.fr/hal-01872817
Contributor : Benjamin Smith <>
Submitted on : Wednesday, September 19, 2018 - 2:05:12 PM
Last modification on : Thursday, November 21, 2019 - 6:32:53 PM
Long-term archiving on: Thursday, December 20, 2018 - 12:52:28 PM

Files

hhs-keyx.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

489

Files downloads

375