One-Round Authenticated Group Key Exchange from Isogenies

Abstract

This paper proposes two one-round authenticated group key exchange protocols from newly employed cryptographic invariant maps (CIMs): one is secure in the quantum random oracle model and the other resists against maximum exposure where a non-trivial combination of secret keys is revealed. The security of the former (resp. latter) is proved under the n-way decisional (resp. n-way gap) Diffie–Hellman assumption on the CIMs in the quantum random (resp. random) oracle model.

We instantiate the proposed protocols on the hard homogeneous spaces with limitation where the number of the user group is two. In particular, the protocols instantiated by using the CSIDH, commutative supersingular isogeny Diffie–Hellman, key exchange are currently more realistic than the general n-party CIM-based ones due to its realizability. Our two-party one-round protocols are secure against quantum adversaries.

1 Introduction

1.1 Background

Recently, National Institute of Standards and Technology (NIST) has initiated a process to standardize quantum-resistant public-key cryptographic algorithms [17], so, to study quantum-resistant cryptosystems is a hot research area. A wide range of quantum-resistant primitives (i.e., mathematical foundations) have been scrutinized by experts on cryptography and mathematics over the world. They include lattice-based, code-based, and multivariate cryptography. We treat with one (relatively) newly entered quantum-resistant primitive, which is called isogeny-based cryptography.

Key establishing over insecure channels is one of important cryptographic techniques. Recent researches on this have led to authenticated key exchange (AKE) and its multiparty extension, that is, authenticated group key exchange (AGKE). We then propose quantum-resistant AKE and AGKE schemes from isogenies on elliptic curves. In fact, we establish them on some abstract notions obtained from isogenies called cryptographic invariant maps (CIMs) and hard homogeneous spaces (HHSs).

HHS, CIM and CSIDH Key Exchange. In an unpublished but seminal paper [3], Couveignes initiated the research of isogeny-based cryptography where he formulated the basic notion of HHSs which is an abstract form of isogeny graphs and class groups of endomorphism rings of (ordinary) elliptic curves.

Independently, Rostovtsev and Stolbunov [18] proposed a Diffie–Hellman type key exchange from ordinary elliptic curve isogenies, which is now called RS key exchange and intensively studied very recently in [4]. While the RS key exchange uses ordinary curves, De Feo et al. employed supersingular isogenies for a practical key exchange protocol called supersingular isogeny Diffie–Hellman (SIDH) key exchange since ordinary isogeny problems suffer from subexponential quantum attacks. Jao et al. submitted an isogeny-based encryption scheme called SIKE (supersingular isogeny key encapsulation) to the NIST post-quantum cryptography competition, and the scheme is an enhanced form of the SIDH key exchange.

Castryck et al. [2] put forward a new HHS-based cryptographic construction called CSIDH (commutative SIDH) key exchange, which is constructed from a group action on the set of supersingular elliptic curves defined over a prime field. This ingenious key exchange opened a new research avenue in isogeny cryptography. As another new proposal, Boneh et al. [1] initiated to study a candidate multiparty non-interactive key exchange on CIMs, whose underlying structure is given by a HHS, (X, G), where X is a finite set and G is a finite abelian group, and the invariant map is defined on the n-th product $X^n$ equipped with nice homomorphic (or equivariant) properties. As in the traditional Diffie–Hellman and pairing primitives, we can consider n-way computational, decisional, and gap Diffie–Hellman problems and assumptions on CIMs.

The notions of HHS and CIM give very concise conceptualizations of the above wonderful recent developments. We propose a generic conversion method from these key exchanges to authenticated ones.

We omit definitions, proofs and discussions because of page limitation. See [6] in details.

1.2 Our Contributions

One-Round AGKE from CIM. We propose two one-round AGKE protocols on the CIMs. One is called n-UM (n-Unified Model) which satisfies the $\mathrm {G}\text {-}\mathrm {CK}$ security. The security of n-UM is proved under the n-way DDH assumption in the quantum random oracle model. The other is called BC n-DH (biclique n-Diffie–Hellman) which satisfies the $\mathrm {G}\text {-}\mathrm {CK}^{+}$ security. The security of BC n-DH is proved under the n-way GDH assumption in the random oracle model. The BC n-DH protocol requires that the number of the user group is bounded by logarithm of the security parameter. Comparison with existing one-round AGKE protocols is shown in Table 1.

Table 1. Comparison of one-round AGKE protocols.

Instantiating One-Round Two-Party AKE from HHS. We instantiate the proposed protocols on the HHS with limitation where the number of the user group is two. In particular, the CSIDH-based protocols are currently more realistic than the general n-party CIM-based ones due to its realizability. Our two-party one-round protocols are secure against quantum adversaries.

Table 2. Comparison of isogeny-based AKE protocols.

Compared to the previous SIDH-based one-round (two-party) AKE protocols [5, 7], the proposed protocols have several merits. While Galbraith et al. [8] proposed an active attack on the SIDH protocol by using the auxiliary points exchanged between users, the attack cannot be applied to our CSIDH-based ones since they include no auxiliary points. In [9], one attack scenario for the gap Diffie–Hellman (GDH) problem on the SIDH protocol is given since the degrees of isogenies used are fixed by public parameters as $\ell _i^{e_i}$ for small primes $\ell _i$, e.g., $\ell _1=2, \ell _2=3$. As the CSIDH protocol uses random multiples consisting of several primes $\ell _i$ ($i=1,\ldots ,n$) for the degrees and they are not fixed by public parameters, the attack cannot be applied to the CSIDH setting. Thus, the GDH assumption on CSIDH has no effective attacks at present, and we have a strong confidence on the security of our CSIDH-based BC protocol, which is reduced from the CSIDH GDH assumption. Comparison with existing isogeny-based AKE protocols is shown in Table 2.

2 n-UM: $\mathrm {G}\text {-}\mathrm {CK}$ Secure n-Party Authenticated Group Key Exchange

2.1 Protocol

Public Parameters. We set $\mathsf {\Pi }= \mathrm {nUM}$. Let $\lambda$ be a security parameter. Let $\mathsf {MapGen}$ be a generation algorithm of a cryptographic invariant map, and $(X, S, G, e) \,\leftarrow _R\,\mathsf {MapGen}(1^{\lambda })$ and $x \,\leftarrow _R\,X$ are chosen. Let $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ be a hash function modeled as a quantum random oracle. Public parameters are $(\mathsf {\Pi }, X, S, G, e,$ x, H).

Static Secret and Public Keys. Party $U_i$ chooses $t_i \in G$ as the SSK. Then, $U_i$ computes $T_i = t_i *x$ as the SPK.

Key Exchange. W.l.o.g, we suppose a session executed by $\mathbf {U} = (U_1, \dots , U_n) \subseteq \mathcal {U}$.

• 1. $U_i$ chooses $r_i \,\leftarrow _R\,G$ as the ESK, and computes $R_i = r_i *x$ as the EPK. Then, $U_i$ broadcasts $(\mathsf {\Pi }, \mathsf {role}_{i'}, U_i, R_i)$ to $\mathbf {U} \setminus U_i$.

• 2. On receiving $(\mathsf {\Pi }, \mathsf {role}_{j'},U_j, R_j)$ for all $j \not = i$, $U_i$ computes $Z_1 = e_{n-1}(T_1, \dots ,$ $T_{i-1},$ $t_i *T_{i+1}, \dots , T_n)$ and $Z_2 = e_{n-1}(R_1, \dots , R_{i-1}, r_i *R_{i+1}, \dots ,$ $R_n)$.¹ Then, $U_i$ generates the session key $SK = H(\mathsf {\Pi },$ $U_1, \dots ,$ $U_n,$ $R_1, \dots ,$ $R_n,$ $Z_1,$ $Z_2)$, and completes the session (Fig. 1).

Fig. 1.

Outline of n-UM protocol.

2.2 Security

Theorem 2.1

Suppose that $H$ is modeled as a quantum random oracle and that the n-DDH assumption holds. Then the n-UM protocol is a post-quantum $\mathrm {G}\text {-}\mathrm {CK}$-secure n-party authenticated group key exchange protocol in the quantum random oracle model.

In particular, for any quantum adversary $\mathcal {A}$ against the n-UM protocol that runs in time at most $t$, involves at most $n_{u}$ honest parties and activates at most $n_{s}$ sessions, and makes at most $n_{h}$ queries to the quantum random oracle and $n_{q}$ $\mathsf {SessionReveal}$ queries, there exists a n-DDH quantum solver $\mathcal {S}$ such that

$$\begin{aligned} {\mathbf {Adv}}_{\mathcal {S}}^{n\text {-}\mathrm {DDH}}(\lambda )\ge \frac{2{\mathbf {Adv}}_{\mathrm {nUM},\mathcal {A}}^{\mathrm {g}\text {-}\mathrm {ck}}(\lambda )^2}{n_{u}^2 n_{s}^2 (8n_{h}n_{q}+ 3(n_{h}+n_{q}+1)^4)}, \end{aligned}$$

where $\mathcal {S}$ runs in time t plus time to perform $\mathcal {O}\big ((n_{u}+ n_{s}) \lambda \big )$ group action operations.

3 Biclique n-DH : $\mathrm {G}\text {-}\mathrm {CK}^{+}$ Secure n-Party Authenticated Group Key Exchange

3.1 Protocol

Public Parameters. We set $\mathsf {\Pi }= \mathrm {BCnDH}$. Let $\lambda$ be a security parameter. Let $\mathsf {MapGen}$ be a generation algorithm of a cryptographic invariant map, and (X,  S,  G,  $e) \leftarrow _{R} \mathsf {MapGen}(1^{\lambda })$ and $x \leftarrow _{R} X$ are chosen. Let $H : \{0,1\}^{*} \rightarrow \{0,1\}^{\lambda }$ be a hash function modeled as a random oracle. Public parameters are $(\mathsf {\Pi }, X, S, G, e, x, H)$.

Static Secret and Public Keys. Party $U_{i}$ chooses $t_{i} \in G$ as the SSK. Then, $U_{i}$ computes $T_{i} = t_{i} *x$ as the SPK.

Key Exchange. As in Sect. 2, we suppose a session executed by $\mathbf {U} = (U_{1}, \dots ,$ $U_{n}) \subseteq \mathcal {U}$.

• 1. $U_{i}$ chooses $r_{i} \leftarrow _{R} G$ as the ESK, and computes $R_{i} = r_{i} *x$ as the EPK. Then, $U_{i}$ broadcasts $(\mathsf {\Pi },$ $\mathsf {role}_{i'},$ $U_{i},$ $R_{i})$ to $\mathbf {U} \setminus U_{i}$.

• 2. On receiving $(\mathsf {\Pi },$ $\mathsf {role}_{j'},$ $U_{j},$ $R_{1}, \ldots ,$ $R_{n})$, $U_{i}$ computes $Z_{\emptyset } = e_{n-1}(T_{1}, \dots ,$ $T_{i-1},$ $t_{i} *T_{i+1},$ $T_{i+2}, \dots ,$ $T_{n}), \dots ,$ $Z_{I} = e_{n-1}(R_{1}, \dots ,$ $R_{i-1},$ $r_{i} *R_{i+1},$ $R_{i+2}, \dots ,$ $R_{n})$ as follows:² for all $P \in \mathcal {P}(I)$,

  • if $i \in P$, then $v_{i}=r_{i}$, and else if $i \not \in P$, then $v_{i}=t_{i}$,

  • for all $k \in I$ ($k \ne i$), if $k \in P$, then $V_{k}=R_{k}$, and else if $k \not \in P$, then $V_{k}=T_{k}$, and

  • $U_{i}$ computes $Z_{P}$ as $Z_{P}=e_{n-1}(V_{1}, \ldots , V_{i-1}, v_{i} *V_{i+1}, V_{i+2}, \ldots , V_{n})$.

  Then, $U_{i}$ generates the session key $SK = H(\mathsf {\Pi },$ $U_{1}, \dots ,$ $U_{n},$ $R_{1}, \dots ,$ $R_{n},$ $Z_{\emptyset }, \dots ,$ $Z_{I})$, and completes the session (Fig. 2).

Fig. 2.

Outline of biclique n-DH protocol.

It is worth to note here that we need to assume that the number of the user group is bounded by logarithm of the security parameter, $\lambda$.

Otherwise, we need exponential computations in $\lambda$ as the number of the shared values is $2^{n}$.

3.2 Security

Theorem 3.1

Suppose that $H$ is modeled as a random oracle and that the n-way GDH assumption holds for $\mathcal {S}$. Then the biclique n-DH protocol is a post-quantum $\mathrm {G}\text {-}\mathrm {CK}^{+}$ secure n-party authenticated group key exchange protocol in the random oracle model.

In particular, for any AGKE quantum adversary $\mathcal {A}$ against the biclique n-DH protocol that runs in time at most t, involves at most $n_{u}$ honest parties and activate at most $n_{s}$ sessions, and makes at most $n_{h}$ queries to the random oracle, there exists a n-way GDH quantum solver $\mathcal {S}$ such that

$$\begin{aligned} {\mathbf {Adv}}_{\mathcal {S}}^{n\text {-}\mathrm {GDH}}(\lambda )\ge \min \Big \{ \frac{1}{n_{u}^{n}}, \frac{1}{n_{u}^{n-1}n_{s}}, \ldots , \frac{1}{n_{u}n_{s}^{n-1}}, \frac{1}{n_{s}^{n}}\Big \} \cdot {\mathbf {Adv}}_{{\mathrm {BCnDH}},\mathcal {A}}^{\mathrm {g}\text {-}\mathrm {ck}+}(\lambda ), \end{aligned}$$

where $\mathcal {S}$ runs in time t plus time to perform $\mathcal {O}\big ((n_{u}+ n_{s}) \lambda \big )$ group action operations and make $\mathcal {O}(n_{h}+ n_{s})$ queries to the n-DDH oracle.

4 Two-Party Authenticated Key Exchanges from Hard Homogeneous Spaces

4.1 $\mathrm {G}\text {-}\mathrm {CK}$ Secure AKE Protocol (from HHS)

We give our HHS-based UM protocol. Public parameters are $pp =(X, G)$. We set , that is, the protocol ID is “HHS-UM.” The secret-key space for initiators and responders is given by the group G.

User $U_1$ has static public key, $T_1 = t_1 * x$, where $t_1 \,\leftarrow _R\,G$, and $t_1$ is $U_1$’s static secret key. User $U_2$ has static public key, $T_2=t_2 * x$, where $t_2 \,\leftarrow _R\,G$, and $t_2$ is $U_2$’s static secret key. Here, ephemeral secret keys for $U_1$ and $U_2$ are given as $r_1 \,\leftarrow _R\,G, \ \text {and} \ \ r_2 \,\leftarrow _R\,G,$ respectively. $U_1$ sends a ephemeral public key $R_1$ as $R_1=r_1 * x$ to $U_2$, $U_2$ sends back a ephemeral public key $R_2$ as $R_2=r_2 * x$ to $U_1$.

$U_1$ computes $Z_{1}=t_1 * T_2$, and $Z_{2}=r_1 * R_2$, and then, obtains the session key SK as $SK=H(\mathsf {\Pi }, U_1, U_2, R_1, R_2, Z_{1}, Z_{2} )$, where H is a hash function.

$U_2$ can computes the session key SK as $SK=H(\mathsf {\Pi }, U_1, U_2, R_1, R_2, Z_{1}, Z_{2} )$ from $Z_{1}=t_2 * T_1$, and $Z_{2}=r_2 * R_1$ (Fig. 3).

It is clear that the session keys of both parties are equal.

The security of this scheme is given as a corollary of Theorem 2.1.

Corollary 4.1

Suppose that $H$ is modeled as a quantum random oracle and that the 2-DDH assumption holds on the HHS (X, G). Then the 2-UM protocol is a post-quantum $\mathrm {G}\text {-}\mathrm {CK}$-secure 2-party authenticated key exchange protocol in the quantum random oracle model.

Fig. 3.

Outline of HHS UM protocol.

Fig. 4.

Outline of HHS biclique protocol.

4.2 $\mathrm {G}\text {-}\mathrm {CK}^{+}$ Secure AKE Protocol (from HHS)

We give our HHS-based biclique protocol. Public parameters are $pp =(X, G)$. We set , that is, the protocol ID is “HHS-BC.” Static and ephemeral keys are the same as our HHS UM protocol. The secret-key space for initiators and responders is given by the group G.

User $U_1$ has static public key, $T_1=t_1 * x$, where $t_1 \,\leftarrow _R\,G$, and $t_1$ is $U_1$’s static secret key. User $U_2$, also, has static public key, $B=t_2 * x$, where $t_2 \,\leftarrow _R\,G$, and $t_2$ is $U_2$’s static secret key. Here, ephemeral secret keys for $U_1$ and $U_2$ are given as $r_1 \,\leftarrow _R\,G, \ \text {and} \ \ r_2 \,\leftarrow _R\,G,$ respectively. $U_1$ sends an ephemeral public key $R_1$ as $R_1=r_1 * x$ to $U_2$, $U_2$ sends back an ephemeral public key $R_2$ as $R_2=r_2 * x$ to $U_1$.

$U_1$ computes the non-trivial combinations of the ephemeral and static public keys as $Z_{1}=t_1 * T_2$, $Z_{2}=r_1 * T_2$, $Z_{3}=t_1 * R_2$, and $Z_{4}=r_1 * R_2$, and then, obtains the session key $SK$ as $SK =H(\mathsf {\Pi }, U_1, U_2, R_1, R_2, Z_{1}, Z_{2}, Z_{3}, Z_{4} )$, where H is a hash function.

$U_2$ can computes the session key $SK$ as $SK =H(\mathsf {\Pi }, U_1, U_2, R_1, R_2, Z_{1}, Z_{2}, Z_{3},$ $Z_{4})$ from $Z_{1}= t_2 * T_1$, $Z_{2}=t_2 * R_1$, $Z_{3}=r_2 * T_1$, and $Z_{4}=r_2 * R_1$ (Fig. 4).

It is clear that the session keys of both parties are equal.

The security of this scheme is given as a corollary of Theorem 3.1.

Corollary 4.2

Suppose that $H$ is modeled as a random oracle and that the 2-way GDH assumption holds on the HHS (X, G). Then the biclique 2-DH protocol is a post-quantum $\mathrm {G}\text {-}\mathrm {CK}^{+}$ secure authenticated key exchange protocol in the random oracle model.