Paper 2018/760

Strongly Secure Authenticated Key Exchange from Supersingular Isogenies

Xiu Xu, Haiyang Xue, Kunpeng Wang, Man Ho Au, Bei Liang, and Song Tian


This paper aims to address the open problem, namely, to find new techniques to design and prove security of supersingular isogeny-based authenticated key exchange (AKE) protocols against the widest possible adversarial attacks, raised by Galbraith in 2018. Concretely, we present two AKEs based on a double-key PKE in the supersingular isogeny setting secure in the sense of CK$^+$, one of the strongest security models for AKE. Our contributions are summarised as follows. Firstly, we propose a strong $\textsf{OW-CPA}$ secure PKE, $\mathsf{2PKE_{sidh}}$, based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a $[\textsf{OW-CCA}, \textsf{OW-CPA}]$ secure KEM, $\mathsf{2KEM_{sidh}}$. Secondly, we propose a two-pass AKE, $\textsf{SIAKE}_2$, based on SI-DDH assumption, using $\mathsf{2KEM_{sidh}}$ as a building block. Thirdly, we present a modified version of $\mathsf{2KEM_{sidh}}$ that is secure against leakage under the 1-Oracle SI-DH assumption. Using the modified $\mathsf{2KEM_{sidh}}$ as a building block, we then propose a three-pass AKE, $\textsf{SIAKE}_3$, based on 1-Oracle SI-DH assumption. Finally, we prove that both $\textsf{SIAKE}_2$ and $\textsf{SIAKE}_3$ are CK$^+$ secure in the random oracle model and supports arbitrary registration. We also provide an implementation to illustrate the efficiency of our schemes. Our schemes compare favourably against existing isogeny-based AKEs. To the best of our knowledge, they are the first of its kind to offer security against arbitrary registration, wPFS, KCI and MEX simultaneously. Regarding efficiency, our schemes outperform existing schemes in terms of bandwidth as well as CPU cycle count.

Note: Correct the definition of Corrupt in the security model.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
authenticated key exchangekey encapsulation mechanismsupersingular elliptic curve isogenypost quantum
Contact author(s)
haiyangxc @ gmail com
2020-12-13: last of 6 revisions
2018-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiu Xu and Haiyang Xue and Kunpeng Wang and Man Ho Au and Bei Liang and Song Tian},
      title = {Strongly Secure Authenticated Key Exchange from Supersingular Isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2018/760},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.