International Association
for Cryptologic Research

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 OW-CPA secure PKE, $$\mathsf {2PKE_{sidh}}$$, based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a [OW-CCA, OW-CPA] secure KEM, $$\mathsf {2KEM_{sidh}}$$. Secondly, we propose a two-pass AKE, $$\mathsf {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, $$\mathsf {SIAKE}_3$$, based on 1-Oracle SI-DH assumption. Finally, we prove that both $$\mathsf {SIAKE}_2$$ and $$\mathsf {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.

Motivated by abstracting the common idea behind several implicitly authenticated key exchange (AKE) protocols, we introduce a primitive that we call double-key key encapsulation mechanism (2-key KEM). It is a special type of KEM involving two pairs of secret-public keys and satisfying some function and security property. Such 2-key KEM serves as the core building block and provides alternative approaches to simplify the constructions of AKE. To see the usefulness of 2-key KEM, we show how several existing constructions of AKE can be captured as 2-key KEM and understood in a unified framework, including widely used HMQV, NAXOS, Okamoto-AKE, and FSXY12-13 schemes. Then, we show (1) how to construct 2-key KEM from concrete assumptions, (2) how to adapt the classical Fujisaki-Okamoto transformation and KEM combiner to achieve the security requirement of 2-key KEM, (3) an elegant Kyber-AKE over lattice using the improved Fujisaki-Okamoto technique.