Towards practical key exchange from ordinary isogeny graphs

Luca de Feo (1, 2) , Jean Kieffer (3, 4, 5) , Benjamin Smith (6, 4)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 LMV - Laboratoire de Mathématiques de Versailles
3 LFANT - Lithe and fast algorithmic number theory
4 IMB - Institut de Mathématiques de Bordeaux
5 ENS-PSL - École normale supérieure - Paris
6 GRACE - Geometry, arithmetic, algorithms, codes and encryption

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).

Mots clés: key exchange; elliptic curves; isogenies; post-quantum cryptography

Domaines: Cryptographie et sécurité [cs.CR]; Théorie des nombres [math.NT]

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. ⟨10.1007/978-3-030-03332-3_14⟩. ⟨hal-01872817⟩