Highly Efficient Key Exchange Protocols with Optimal Tightness

Abstract

In this paper we give nearly-tight reductions for modern implicitly authenticated Diffie-Hellman protocols in the style of the Signal and Noise protocols, which are extremely simple and efficient. Unlike previous approaches, the combination of nearly-tight proofs and efficient protocols enables the first real-world instantiations for which the parameters can be chosen in a theoretically sound manner.

Our reductions have only a linear loss in the number of users, implying that our protocols are more efficient than the state of the art when instantiated with theoretically sound parameters. We also prove that our security proofs are optimal: a linear loss in the number of users is unavoidable for our protocols for a large and natural class of reductions.

Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 802823, and the Deutsche Forschungsgemeinschaft (DFG), project number 265919409.

K. Cohn-Gordon—Independent Scholar.

1 Introduction

Key exchange protocols serve as a building block for almost all secure communication today. However, deploying a key exchange protocol requires implementors to carefully choose concrete values for several parameters, such as group and key sizes, which we here abstract into a single security parameter n. But how should n be selected? An answer is to select it based on formal reductionist arguments in the style of concrete security [7]. These arguments relate the security parameter n of a protocol to the security parameter f(n) of an assumed-hard problem, such that breaking the protocol with parameter n would lead to an attack on the hard problem with parameter f(n). We say a protocol is deployed in a theoretically sound way if n is chosen such that the underlying problem is “hard enough” with parameter f(n).

Unfortunately, for most deployed protocols the parameters are actually not chosen in a theoretically sound way. This means that the formal security arguments are in reality vacuous since f(n) is too small for the underlying problem to be hard. For example, existing security proofs for TLS [11, 22, 27] have a security loss which is quadratic in the total number of sessions, but the parameters chosen in practice does not account for this. If one aims for “128-bit security”, and assumes $2^{30}$ users and up to $2^{30}$ sessions per user (very plausible for TLS), then a theoretically sound choice of parameters would have to provide at least “248-bit security”. In the particular case of the algebraic groups used for Diffie-Hellman (DH) in TLS, this would require a group of order $|\mathbb {G} | \approx 2^{496}$ instead of the common 128-bit-secure choice of $|\mathbb {G} | \approx 2^{256}$. But larger parameters typically leads to worse performance so this is not done in practice. Thus, for TLS as actually used, the proofs do not provide any meaningful security guarantees since they relate the hardness of breaking TLS to a DH instance which is too easy to solve.

It would be desirable if protocols could be instantiated in a theoretically sound way without sacrificing efficiency. This has led to the study of so-called tight security, in which one aims to construct proofs such that the gap between n and f(n) is as small as possible. While there have been several recent advances in this field [3, 19], typically they trade tighter proofs for the use of more complex primitives and constructions—which themselves require more or larger keys. This leads to the perhaps counter-intuitive observation that the resulting protocols have a tighter security proof, but are substantially less efficient in practice. For example, the recent protocol of Gjøsteen and Jager [19] has a constant security loss, meaning that an attack on their protocol leads to an attack on decisional DH with essentially the same parameter. However, it is a signed DH protocol, and thus must be instantiated with a tightly-secure signature scheme. The solution used by Gjøsteen and Jager [19] requires a total of 17 exponentiations which can negate the efficiency savings from using a smaller group. In some sense they overshoot their target: they achieve tightness without reaching the actual goal of efficient theoretically sound deployment in practice.

In this work we will instead aim between the two extremes of real-world protocols on the one end having very non-tight proofs, and the more theoretical protocols on the other having fully tight proofs, focusing instead on the actual end-goal of achieving efficient theoretically sound deployments in practice. Our constructions fall into the class of implicitly authenticated DH protocols, which often are more efficient than signed DH variants, and can additionally offer various forms of deniability. Implicitly authenticated key exchange protocols have been studied extensively in the literature, and in the past few years have also started to see deployments in the real world. Perhaps the most well-known example is the Signal protocol [38], which encrypts messages for WhatsApp’s 1.5 billion users. Another example is the Noise protocol framework [36], whose so-called IK pattern powers the new Linux kernel VPN Wireguard [16]. Similar protocols in the literature include KEA+ [30] and UM [24].

We will give a security proof for a simple instance of this class, very close to Signal’s basic design. In and of itself this isn’t particularly noteworthy. What is noteworthy, however, is the tightness of the proof. Unlike any other proof for a protocol as simple and efficient as ours, our proof only incurs a security loss which is linear in the number of users $\mu$ and constant in the number of sessions per user $\ell$. This is in stark contrast to most other key exchange proofs that are typically quadratic in at least one of these parameters, and most of the time quadratic even in their product $\mu \ell$.

Our Contributions. Our contributions revolve around three protocols which all aim for high practical efficiency when instantiated with theoretically sound parameters. The first protocol, which we call ${\Pi }$, is a simple and clean implicitly authenticated DH protocol very close to Signal, Noise-KK, KEA+ and UM, and provides weak forward secrecy. In protocol ${\Pi }$ users exchange a single group element and perform four group exponentiations to establish a session key. Protocol ${\Pi }$—specified precisely in Sect. 4—aims for maximal efficiency under the strong DH assumption.

The other two protocols, which can be seen as variants of protocol ${\Pi }$, are designed to avoid the strong DH assumption of ${\Pi }$. The first protocol, which we call ${\Pi }_{\mathrm {Twin}}$, adapts the “twinning” technique of Cash et al. [13] to protocol ${\Pi }$, and needs four more exponentiations. The second, which we call ${\Pi }_{\mathrm {Com}}$, additionally adapts the “commitment” technique of Gjøsteen and Jager [19], and only needs two more exponentiations than protocol ${\Pi }$. On the other hand, it requires one more round of communication. Both ${\Pi }_{\mathrm {Twin}}$ and ${\Pi }_{\mathrm {Com}}$ are slightly more costly than protocol ${\Pi }$, but in return require only the standard CDH and DDH assumptions.

Common to all our protocols is that they are simple and conventional, with no heavyweight cryptographic machinery. They exchange ephemeral keys and derive a session key from the combination of static-ephemeral, ephemeral-static and ephemeral-ephemeral DH values via a hash function $H$. In our proofs $H$ will be a random oracle.

Our first core contribution is thus to give new reductions for all these protocols with a linear loss $L=O(\mu )$ in the random oracle model. This is better than almost all known AKE protocols. As we will see, even though the loss is not constant, our protocols are so efficient that they perform better than both fully-tight protocols as well as the most efficient non-tight AKEs¹. In contrast to previous works, our proofs enable theoretically sound deployment of conventional protocols while maintaining high efficiency.

Our second core contribution is to show that the $O(\mu )$ tightness loss is essentially optimal for the protocols considered in this paper, at least for “simple” reductions. A “simple” reduction runs a single copy of the adversary only once. To the best of our knowledge, all known security reductions for AKE protocols are either of this type or use the forking lemma (which of necessity leads to a non-tight proof). Hence, to give a tighter security proof, one would have to develop a completely new approach to prove security.

The lower-bound proof will be based on the meta-reduction techniques described by Bader et al. [4]. However, these techniques are only able to handle tight reductions from non-interactive assumptions, while our first protocol is based on the interactive strong DH assumption. Therefore we develop a new variant of the approach, which makes it possible to also handle the strong DH assumption.

Finally, we prove that our protocols can be enhanced to also provide explicit entity authentication by adding key-confirmation messages, while still providing tight security guarantees. To do so, we generalise a theorem of Yang [41] in two ways: we apply it to n-message protocols for $n>2$, and we give a tight reduction to the multi-user versions of the underlying primitives.

To summarise:

• 1. We give three protocols with linear-loss security reductions, making them faster than both fully-tight protocols and the most efficient non-tight ones when instantiated in a theoretically sound manner for reasonable numbers of users and sessions.

• 2. We prove optimality of linear loss for our protocols under “simple” reductions.

• 3. We tightly extend our protocols with key confirmation messages to provide explicit entity authentication.

Related Work. We briefly touch upon some other protocols with non-quadratic security loss. KEA+ [30] achieves $L =O(\mu \ell )$ under the Gap-DH assumption, and where the reduction for pairing-friendly curves takes $O(t \log t)$ time. However, for non-pairing-friendly curves the reduction takes $O(t^2)$ time. Moreover, KEA+ also does not achieve weak forward secrecy in a modern model: only one side’s long term key can be corrupted.

The first AKE protocols with L independent of $\mu$ and $\ell$ were described by Bader et al. [3] at TCC 2015. They describe two protocols, one with constant security loss $L = O(1)$ and another with loss $L = O(\kappa )$ linear in the security parameter. Both protocols make use of rather heavy cryptographic building blocks, such as tree-based signature schemes, Groth-Sahai proofs [20], and cryptographic pairings, and are therefore not very efficient.

As already mentioned, Gjøsteen and Jager [19] recently described a more practical protocol, which essentially is a three-message variant of “signed Diffie-Hellman”. Even though their protocol uses a rather complex signature scheme to achieve tightness (a single key exchange requires 17 exponentiations and the exchange of in total 16 group elements/exponents), when instantiated with theoretically sound parameters it turns out to be more efficient than even plain signed DH with ECDSA, at least for large-scale deployments. Unlike [3], the security analysis in [19] is in the random oracle model [8] since the paper aims at maximal practical efficiency.

2 Background

In this section we recap some background and standard definitions. Let $\mathbb {G}$ be a cyclic group of prime order p with generator $g$.

Diffie-Hellman Problems. The computational and decisional Diffie-Hellman problems are natural problems related to breaking the Diffie-Hellman protocol.

Definition 1

Consider the following experiment involving an adversary $\mathcal {A}$. The experiment samples $x, y\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\mathbb {Z} _p$ and starts $\mathcal {A} (g^x, g^y)$. The advantage of $\mathcal {A}$ in solving the computational Diffie-Hellman problem is defined as

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {CDH} }}(\mathcal {A}) := \Pr \left[ \mathcal {A} (g^x, g^y) = g^{xy}\right] \end{aligned}$$

Definition 2

Consider the following experiment involving an adversary $\mathcal {A}$. The experiment samples $x, y, z\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\mathbb {Z} _p$ and tosses a coin ${\hat{b}}\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\{0,1\}$. If ${\hat{b}}=1$ then it sets $Z := g^{xy}$, while if ${\hat{b}}=0$ then it sets $Z = g^z$. We define the advantage of $\mathcal {A}$ in solving the decisional Diffie-Hellman problem as

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {DDH} }}(\mathcal {A}) := |\Pr \left[ \mathcal {A} (g^x, g^y, Z) = {\hat{b}}\right] - 1/2 |\end{aligned}$$

Let $\mathsf {DDH}(g^x, g^y, g^z)$ be an oracle that returns 1 if and only if $xy = z$. The gap Diffie-Hellman problem asks to solve the computational Diffie-Hellman problem, given access to the oracle $\mathsf {DDH}(\cdot , \cdot , \cdot )$. The strong Diffie-Hellman problem is related to the gap Diffie-Hellman problem, except that the adversary now gets a less capable oracle where the first input is fixed, i.e., $\mathsf {stDH}_x(\cdot ,\cdot ) = \mathsf {DDH}(g^x, \cdot , \cdot )$.

Definition 3

Consider the following experiment involving an adversary $\mathcal {A}$. The experiment samples $x, y\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\mathbb {Z} _p$ and starts $\mathcal {A} ^{\mathsf {stDH}_x(\cdot , \cdot )}(g^x, g^y)$. The advantage of $\mathcal {A}$ in solving the strong Diffie-Hellman problem is defined as

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {A}) := \Pr \left[ \mathcal {A} ^{\mathsf {stDH}_x(\cdot , \cdot )}(g^x, g^y) = g^{xy}\right] . \end{aligned}$$

One may wonder to which extent the number of oracle queries to the strong DH oracle affects the concrete security of this assumption. That is, how does the security of strong DH degrade with the number of queries to the $\mathsf {stDH}$ oracle? We are not aware of any concrete attacks that exploit the oracle to solve the CDH problem more efficiently than other algorithms for CDH. In particular, in many elliptic curves with practical bilinear pairings it is reasonable to assume hardness of CDH, even though the bilinear pairing is a much stronger tool than a strong DH oracle.

A crucial technique in any tight proof using Diffie-Hellman problems is rerandomisation [6], where a single Diffie-Hellman problem instance can be turned into many, in such a way that an answer to any one of them can be turned into an answer to the original instance. We will use this technique in our proofs.

The Strong Twin Diffie-Hellman Problem. The strong twin Diffie-Hellman problem was introduced by Cash, Kiltz, and Shoup [13] at EUROCRYPT 2008. It is closely related to the standard computational Diffie-Hellman (CDH) problem, except that it “twins” certain group elements, in order to enable an efficient “trapdoor-DDH” test that makes it possible to simulate a strong-CDH oracle. This makes it possible to show that the twin-DH problem is equivalent to the standard CDH problem. Let $\mathsf {twinDH}_{x_0,x_1}(Y,Z_0,Z_1)$ be an oracle which returns 1 if and only if $\mathsf {DDH}(g^{x_0}, Y, Z_0) = 1$ and $\mathsf {DDH}(g^{x_1}, Y, Z_1) = 1$.

Definition 4

Consider the following experiment involving an adversary $\mathcal {A}$. The experiment samples $x_0, x_1, y\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\mathbb {Z} _p$ and starts $\mathcal {A} ^{\mathsf {twinDH}_{x_0,x_1}(\cdot , \cdot ,\cdot )}(g^{x_0}, g^{x_1}, g^y)$. The advantage of $\mathcal {A}$ in solving the strong twin Diffie-Hellman problem is defined as

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {2\text {-}CDH} }}(\mathcal {A}) := \Pr \left[ \mathcal {A} ^{\mathsf {twinDH}_{x_0,x_1}(\cdot , \cdot ,\cdot )}(g^{x_0}, g^{x_1}, g^y) = (g^{x_0y}, g^{x_1y})\right] \end{aligned}$$

The following theorem was proven by Cash, Kiltz, and Shoup [[13], Theorem 3].

Theorem 1

Let $\mathcal {A}$ be a strong twin DH adversary that makes at most Q queries to oracle $\mathcal {O}$ and runs in time $t_\mathcal {A}$. Then one can construct a DH adversary $\mathcal {B}$ that runs in time $t_\mathcal {A} \approx t_\mathcal {B}$ such that

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {2\text {-}CDH} }}(\mathcal {A}) \le \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {CDH} }}(\mathcal {B}) + Q/p. \end{aligned}$$

3 AKE Security Model

In this section we define our game-based key exchange security model. It is based on the real-or-random (“RoR”) security definition of Abdalla, Fouque, and Pointcheval [2], and incorporates the extension of Abdalla, Benhamouda, and MacKenzie [1] to capture forward secrecy. The central feature of the RoR-model is that the adversary can make many $\mathsf {Test}$-queries, and that all queries are answered with a “real” or “random” key based on the same random bit ${\hat{b}}$.

We prefer to work in a RoR-model because it automatically lends itself to tight composition with protocols that use the session keys of the key exchange protocol. For security models where there is only a single $\mathsf {Test}$-query, or where each $\mathsf {Test}$-query is answered based on an individual random bit [3, 19], such a composition is not automatically tight.

Although we mainly consider key exchange protocols with implicit authentication in this paper, we show in Sect. 8 how they can easily be upgraded to also have explicit authentication by adding key-confirmation messages to the protocol. The advantage of working in the RoR-model is that it allows us to do this transformation tightly.

Execution Environment. We consider $\mu$ parties $1,\ldots ,\mu$. Each party $i$ is represented by a set of $\ell$ oracles, $\{\pi _i^1, \ldots , \pi _i^{\ell }\}$, where each oracle corresponds to a session, i.e., a single execution of a protocol role, and where $\ell \in \mathbb {N}$ is the maximum number of protocol sessions per party. Each oracle is equipped with a randomness tape containing random bits, but is otherwise deterministic. Each oracle $\pi _i^s$ has access to the long-term key pair $(sk_i,pk_i)$ of party $i$ and to the public keys of all other parties, and maintains a list of internal state variables that are described in the following:

• $\mathsf {Pid}_i^s$ (“peer id”) stores the identity of the intended communication partner.

• $\varPsi _i^s \in \{\emptyset ,\mathtt {accept},\mathtt {reject} \}$ indicates whether oracle $\pi _i^s$ has successfully completed the protocol execution and “accepted” the resulting key.

• $k_i^s$ stores the session key computed by $\pi _i^s$.

• $\mathsf {sent}_i^s$ contains the list of messages sent by $\pi _i^s$ in chronological order.

• $\mathsf {recv}_i^s$ contains the list of messages received by $\pi _i^s$ in chronological order.

• $\mathsf {role}_i^s \in \{\emptyset , \mathtt {init}, \mathtt {resp} \}$ indicates $\pi _i^s$’s role during the protocol execution.

For each oracle $\pi _i^s$ these variables are all initialized to the empty string $\emptyset$. The computed session key is assigned to the variable $k_i^s$ if and only if $\pi _i^s$ reaches the $\mathtt {accept}$ state, that is, we have $k_i^s \ne \emptyset \iff \varPsi _i^s = \mathtt {accept}$.

Partnering. To define when two oracles are supposed to derive the same session key we use a variant of matching conversations. In addition to agreement on their message transcripts, they should also agree upon each other’s identities and have compatible roles (one being the initiator the other the responder). We remark that our protocol messages consist only of group elements and deterministic functions of them. This means that they are not vulnerable to the “no-match” attacks of Li and Schäge [32].

Definition 5

(Origin-oracle). An oracle $\pi _j^t$ is an origin-oracle for an oracle $\pi _i^s$ if $\varPsi _j^t\ne \emptyset$, $\varPsi _i^s=\mathtt {accept}$, and the messages sent by $\pi _j^t$ equal the messages received by $\pi _i^s$, i.e., if $\mathsf {sent}_j^t = \mathsf {recv}_i^s$.

Definition 6

(Partner oracles). We say that two oracles $\pi _i^s$ and $\pi _j^t$ are partners if (1) each is an origin-oracle for the other; (2) each one’s identity is the other one’s peer identity, i.e., $\mathsf {Pid}_i^s = j$ and $\mathsf {Pid}_j^t = i$; and (3) they do not have the same role, i.e., $\mathsf {role}_i^s \ne \mathsf {role}_j^t$.

Attacker Model. The adversary $\mathcal {A}$ interacts with the oracles through queries. It is assumed to have full control over the communication network, modeled by a $\mathsf {Send}$ query which allows it to send arbitrary messages to any oracle. The adversary is also granted a number of additional queries that model the fact that various secrets might get lost or leaked. The queries are described in detail below.

• $\mathsf {Send}(i,s,j,m)$: This query allows $\mathcal {A}$ to send any message m of its choice to oracle $\pi _i^s$ on behalf of party $P_j$. The oracle will respond according to the protocol specification and depending on its internal state. For starting a role there are additional actions:

  [Initiator] If $(\mathsf {Pid}_i^s, \varPsi _i^s) = (\emptyset , \emptyset )$ and $m = \emptyset$, then this means that $\mathcal {A}$ requests $\pi _i^s$ to start the initiator role with peer $P_j$. In this case, $\pi _i^s$ will set $\mathsf {Pid}_i^s := j$ and $\mathsf {role}_i^s := \mathtt {init}$.

  [Responder] If $(\mathsf {Pid}_i^s, \varPsi _i^s) = (\emptyset , \emptyset )$ and $m \ne \emptyset$, then this means that $\mathcal {A}$ requests $\pi _i^s$ to start the responder role with peer $P_j$ with first message m. In this case, $\pi _i^s$ will set $\mathsf {Pid}_i^s := j$ and $\mathsf {role}_i^s := \mathtt {resp}$.

• $\mathsf {RevLTK}(i)$: For $i \le \mu$, this query allows the adversary to learn the long-term private key $sk_i$ of user $i$. After the query $i$ is said to be corrupted, and all oracles $\pi _i^1, \ldots , \pi _i^\ell$ now respond with $\bot$ to all queries.

• $\mathsf {RegisterLTK}(i,pk_i)$: For $i > \mu$, this query allows the adversary to register a new party $i$ with public key $pk_i$. We do not require that the adversary knows the corresponding private key. After the query the pair $(i,pk_i)$ is distributed to all other parties. Parties registered by $\mathsf {RegisterLTK}$ are corrupted by definition.

• $\mathsf {RevSessKey}(i,s)$: This query allows the adversary to learn the session key derived by an oracle. That is, query $\mathsf {RevSessKey}(i,s)$ returns the contents of $k^s_i$. Recall that we have $k^s_i \ne \emptyset$ if and only if $\varPsi ^s_i = \mathtt {accept}$. After this query $\pi _i^s$ is said to be revealed.

Note that unlike, e.g., [10, 12], we do not allow the adversary to learn the sessions’ ephemeral randomness.

Security Experiment. To define the security of a key exchange protocol we want to evaluate the attacker’s knowledge of the session keys. Formally, we have an AKE security game, played between an adversary $\mathcal {A}$ and a challenger $\mathcal {C}$, where the adversary can issue the queries defined above. Additionally, it is given access to a special $\mathsf {Test}$ query, which, depending on a secret bit ${\hat{b}}$ chosen by the challenger, either returns real or random keys. The goal of the adversary is to guess ${\hat{b}}$.

• $\mathsf {Test}(i,s)$: If $\varPsi _i^s \ne \mathtt {accept}$, return $\bot$. Else, return $k_{{\hat{b}}}$, where $k_0 = k_s^i$ and $k_1\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\mathcal {K}$ is a random key. If a $\mathsf {Test}$ query is repeated in the case $b=1$, the same random key is returned. After the query, oracle $\pi _i^s$ is said to be tested.

The adversary can issue many $\mathsf {Test}$ queries, to different oracles, but all are answered using the same bit ${\hat{b}}$.

The AKE security game, denoted $G_{\Pi }(\mu ,\ell )$, is parameterized by the protocol ${\Pi }$ and two numbers $\mu$ (the number of honest parties) and $\ell$ (the maximum number of protocol executions per party), and is run as follows.

• 1. $\mathcal {C}$ begins by drawing a random bit ${\hat{b}}\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,\{0,1\}$, then generates $\mu$ long-term key pairs $\bigl \{ (sk_i,pk_i) \bigm | i \in [1,\ldots ,\mu ] \bigr \}$, and initializes the collection of oracles $\bigl \{\pi _i^s \bigm | i \in [1,\ldots , \mu ], s \in [1,\ldots ,\ell ] \bigr \}$.

• 2. $\mathcal {C}$ now runs $\mathcal {A}$, providing all the public keys $pk_1,\ldots ,pk_\mu$ as input. During its execution, $\mathcal {A}$ may adaptively issue $\mathsf {Send}$, $\mathsf {RevLTK}$, $\mathsf {RevSessKey}$, $\mathsf {RegisterLTK}$ and $\mathsf {Test}$ queries any number of times and in arbitrary order. The only requirement is that all tested oracles remain fresh throughout the game (see Definition 7 below). Otherwise, the game aborts and outputs a random bit.

• 3. The game ends when $\mathcal {A}$ terminates with output $b'$, representing its guess of ${\hat{b}}$. If not all test oracles are fresh, the security game outputs a random bit. If all test oracles are fresh and $b' = {\hat{b}}$, it outputs 1. Otherwise, it outputs 0.

Definition 7

(Freshness). An oracle $\pi _i^s$ is fresh, written $\mathsf {fresh}(i,s)$, if:

• (i) $\mathsf {RevSessKey}(i,s)$ has not been issued,

• (ii) no query $\mathsf {Test}(j,t)$ or $\mathsf {RevSessKey}(j,t)$ has been issued, where $\pi _j^t$ is a partner of $\pi _i^s$, and

• (iii) $\mathsf {Pid}_i^s$ was:

  • (a) not corrupted before $\pi _i^s$ accepted if $\pi _i^s$ has an origin-oracle, and

  • (b) not corrupted at all if $\pi _i^s$ has no origin-oracle.

Definition 8

(Winning Events). We define the following three winning events on game $G_{\Pi }(\mu ,\ell )$.

• (i) Event $\mathsf {break} _\mathrm {Sound}$ occurs if there exist two partner oracles $\pi _i^s$ and $\pi _j^t$ with $k_i^s\ne k_j^t$. In other words, there are two partner oracles which compute different session keys.

• (ii) Event $\mathsf {break} _\mathrm {Unique}$ occurs if for some oracle $\pi _i^s$ there exist distinct oracles $\pi _j^t$ and $\pi _{j'}^{t'}$ such that $\pi _i^s$ is a partner oracle to both $\pi _j^t$ and $\pi _{j'}^{t'}$. In other words, there exists an oracle with more than one partner oracle.

• (iii) Let $\mathsf {guess}_{\mathrm {KE}}$ be the output of game $G_{\Pi }(\mu ,\ell )$. We define $\mathsf {break} _\mathrm {KE}$ to be the event $\mathsf {guess}_{\mathrm {KE}} = 1$.

Definition 9

(AKE Security). An attacker $\mathcal {A}$ breaks the security of protocol ${\Pi }$, if at least one of $\mathsf {break} _\mathrm {Sound}$, $\mathsf {break} _\mathrm {Unique}$, or $\mathsf {break} _\mathrm {KE}$ occurs in $G_{\Pi }(\mu ,\ell )$. The advantage of the adversary $\mathcal {A}$ against AKE security of ${\Pi }$ is

$$\begin{aligned} \mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {A}) = \max \left\{ \Pr \left[ \mathsf {break} _\mathrm {Sound} \right] , \Pr \left[ \mathsf {break} _\mathrm {Unique} \right] , |\Pr \left[ \mathsf {break} _\mathrm {KE} \right] - 1/2| \right\} \text{. } \end{aligned}$$

We say that $\mathcal {A}$ $(\epsilon _\mathcal {A} , t, \mu , \ell )$-breaks ${\Pi }$ if its running time is t and $\mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {A}) \ge \epsilon _\mathcal {A}$. The running time of $\mathcal {A}$ includes the running time of the security experiment (see [19, Remark 1]).

Security Properties. The core aspects of the security properties in our model are captured by the $\mathsf {break} _\mathrm {KE}$ event, combined with the adversary’s capabilities and the restrictions imposed on them through the freshness predicate.

The freshness clauses (i) and (ii) imply that we only exclude the reveal of session keys for tested oracles as well as their partners. This encodes both (a) key independence if the revealed key is different from the session key: knowing some keys must not enable computing other keys, as well as (b) implicitly ensuring agreement on the involved parties, since sessions that compute the same session key but disagree on the parties would not be partnered, and reveal the Test session’s key.

Our freshness clause (iii) encodes weak forward secrecy: the adversary can learn the peer’s long-term key after the tested oracle accepted, but only if it has been passive in the run of the oracle [26]. Another property captured by our model is resistance to key-compromise impersonation attacks. Recall that KCI attacks are those where the adversary uses a party A’s own private long-term key to impersonate other users towards A. This is (implicitly) encoded by the absence of any adversary restrictions on learning the private long-term key of a test-oracle itself. Additionally, the $\mathsf {break} _\mathrm {Unique}$ event captures the resistance to replay attacks. The $\mathsf {break} _\mathrm {Sound}$ event ensures that two parties that execute the protocol together in the absence of an attacker (or at least a passive one), compute the same session key.

Some recent protocols also offer post-compromise security, in which the communication partner $\pi _j^t$ may be corrupted before $\pi _i^s$ has accepted. However, in this work we consider only stateless protocols, which cannot achieve this goal [14].

4 Protocol ${\Pi }$

Protocol ${\Pi }$, defined in Fig. 1, uses a mix of static-ephemeral and ephemeral-ephemeral Diffie-Hellman key exchanges to get a protocol that is extremely efficient in terms of communications as well as computational effort required. Specifically, the two protocol participants exchange ephemeral Diffie-Hellman shares $g^r$ and $g^s$ for random r, s, and then compute a session key from three Diffie-Hellman shared secrets (static-ephemeral, ephemeral-static, ephemeral-ephemeral) as well as identities and a transcript. Note that this is very close to the Noise-KK pattern [36].

Fig. 1.

Protocol ${\Pi }$. The session key is derived from the combination of the parties’ static-ephemeral, ephemeral-static, and ephemeral-ephemeral DH values.

Theorem 2

Consider the protocol ${\Pi }$ defined in Fig. 1 where $H$ is modeled as a random oracle. Let $\mathcal {A}$ be an adversary against the AKE security of ${\Pi }$. Then there exist adversaries $\mathcal {B} _1$, $\mathcal {B} _2$ and $\mathcal {B} _3$ against strong Diffie-Hellman such that

$$\begin{aligned} \mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {A}) \le \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _1) + \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _2) + \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _3) + \frac{\mu \ell ^2}{p} \text{. } \end{aligned}$$

The strong Diffie-Hellman adversaries all run in essentially the same time as $\mathcal {A}$, and make at most as many queries to their strong DH-oracle as $\mathcal {A}$ makes to its hash oracle $H$.

The proof of the theorem is structured as a sequence of games running variations on the security experiment, with the first game identical to the experiment. We bound the difference in the probability of the event that the experiment outputs 1 in each game. As a side effect, along the way we also get a bound on $\mathsf {break} _\mathrm {Unique}$. Then we argue that the probability that the experiment outputs 1 is $1\mathrm{{/}}2$ in the final game, which gives us a bound on $\mathsf {break} _\mathrm {KE}$. Since the scheme has perfect correctness, the theorem follows.

To achieve this result in the final game, we shall have our oracles choose session keys at random, without reference to secret keys or messages. Obviously, we have to ensure consistency with what the adversary can learn. This means that we have to make sure that partnered oracles both choose the same key (Game 2); that keys the adversary should be able to compute on his own are the same as chosen by the oracle (Game 2), and that corruptions of long-term keys that enable the adversary to compute session keys on his own return results consistent with previous $\mathsf {RevSessKey}$-queries (Game 3 and 5).

The general technique we use is to have our oracles refrain from computing the input to the key derivation hash oracle, but instead check to see if the adversary somehow computes it. The idea is that computing the hash input is hard to simulate in the strong Diffie-Hellman game, but checking if someone else has computed the hash input is easy using the strong DH oracle provided.

We call an oracle honest (at some point) if the user it belongs to has not yet been corrupted (at that point). There are five types of oracles that we will have to deal with in separate ways, and the first four are essentially fresh oracles:

• (I) initiator oracles whose response message comes from a responder oracle, which has the same $\mathtt {ctxt}$ (i.e., they agree on the message transcript and participant identities and public keys) and which is honest when the response is received;

• (II) other initiator oracles whose intended peer is honest until the oracle accepts;

• (III) responder oracles whose initial message comes from an initiator, which has the same $\mathtt {ctxt}$ up to the responder message (thus agreeing on the first message and participant identities and public keys) and which is honest when the response is received;

• (IV) other responder oracles whose intended peer is honest until the oracle accepts; and

• (V) oracles whose intended peer is corrupted.

Note that at the time an initiator oracle starts, we cannot know if it will be of type I or II. However, we will know what type it is when it is time to compute the oracle’s session key. We also remark that types I and III correspond to case (iii)a in the definition of freshness. Types II and IV correspond to case (iii)b.

In the following, let $S_j$ denote the event that the experiment in Game j outputs 1.

Game 0

Our starting point Game 0 is the security experiment defining AKE security. We have that

$$\begin{aligned} \Pr \left[ \mathsf {break} _\mathrm {KE} \right] = \Pr [ S_{0}] \text{. } \end{aligned}$$

(1)

We begin with an administrative step to avoid pathologies where honest players choose the same random nonces.

Game 1

In this game, we abort if two initiator oracles or two responder oracles ever arrive at the same $\mathtt {ctxt}$. The probability of this happening can be upper-bounded by the probability of two oracles for the same peer choosing the same random exponents, and we get that

$$\begin{aligned} |\Pr [ S_{1} ] - \Pr [ S_{0} ]| \le \frac{\mu \ell ^2}{p} \text{. } \end{aligned}$$

(2)

We also note that the event in this game that corresponds to $\mathsf {break} _\mathrm {Unique}$ cannot happen in this game. It follows that

$$\begin{aligned} \Pr [ \mathsf {break} _\mathrm {Unique} ] \le \frac{\mu \ell ^2}{p} \text{. } \end{aligned}$$

(3)

4.1 Preparing Oracles

Our goal in this game is to change every oracle so that it no longer computes the input to the key derivation hash $H$, but instead checks if the adversary computes this input and adapts accordingly. This is essential for later games, since it allows us to replace every use of the secret key with queries to a strong DH oracle.

Game 2

In this game, we modify how our oracles determine their session keys. Note that at the point in time where an initiator oracle determines its session key, we know its type exactly.

A type III, IV or V responder oracle with $\mathtt {ctxt} = \hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\,$, secret key $b$ and random exponent $s_{}$ does the following to determine its session key $k$: First, it checks to see if any oracle queries $\hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert W_1 \Vert W_2 \Vert W_3$ have been made satisfying

$$\begin{aligned} W_1&= pk _i^{s_{}}&W_2&= U_{}^{b}&W_3&= U_{}^{s_{}} \text{. } \end{aligned}$$

(4)

If any such query is found $k$ is set to the corresponding hash value. Otherwise, the session key is chosen at random. And if such a hash query happens later, the hash value is set to the chosen session key.

A type I initiator oracle will simply use the key from the corresponding responder oracle.

A type II or V initiator oracle with $\mathtt {ctxt} = \hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\,$, secret key $a$ and random exponent $r_{}$ does the following to determine its session key $k$: First, it checks to see if any oracle queries $\hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert W_1 \Vert W_2 \Vert W_3$ have been made satisfying

$$\begin{aligned} W_1&= V_{}^{a}&W_2&= pk _j^{r_{}}&W_3&= V_{}^{r_{}} \text{. } \end{aligned}$$

(5)

If any such query is found, $k$ is set to the corresponding hash value. Otherwise, the session key is chosen at random. And if such a hash query happens later, the hash value is set to the chosen session key.

The only potential change in this game is at which point in time the key derivation hash oracle value is first defined, which is unobservable. It follows that

$$\begin{aligned} \Pr [ S_{2} ] = \Pr [ S_{1} ] \text{. } \end{aligned}$$

(6)

4.2 Type IV Responder Oracles

Game 3

In this game type IV oracles choose their session key at random, but do not modify the hash oracle unless the intended peer is corrupted. If the adversary corrupts the intended peer i of a type IV oracle running as user j with secret key $b$, random exponent $s_{}$ and chosen key $k$, then from that point in time, any query of the form

$$\begin{aligned} \hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert pk _{i}^{s_{}} \Vert U_{}^{b} \Vert U_{}^{s_{}} \end{aligned}$$

to the key derivation hash oracle $H$ will result in the hash value $k$.

Unless one of these queries happen before user i is corrupted, the only change is at which point in time the key derivation hash oracle value is first defined, which is unobservable. Let $F$ be the event that a query as above happens before the corresponding long-term key is corrupted. Then

$$\begin{aligned} |\Pr [ S_{3} ] - \Pr [ S_{2} ]| \le \Pr [ F] \text{. } \end{aligned}$$

Let $F_i$ be the same event as $F$, but with the intended peer being user i. We then have that $\Pr [ F] = \sum _i \Pr [ F_i ]$.

Next, consider the event $E_i$ which is that for some type IV oracle as above, any query of the form

$$\begin{aligned}&\hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert W_1 \Vert W_2 \Vert W_3&W_1&= pk _{i}^{s_{}} = V_{}^{a} \end{aligned}$$

(7)

to the key derivation hash oracle $H$ happens before user i is corrupted. Then $\Pr [ F_i ] \le \Pr [ E_i ]$.

We shall now bound the probability of the event $E_i$ by constructing an adversary against strong Diffie-Hellman. This adversary will embed its DH challenge in some user i’s public key and type IV oracle responses for oracles whose intended peer is user i, and recover the solution to its DH challenge from the hash query in event $E_i$.

Strong Diffie-Hellman Adversary $\mathcal {B} _1$. The algorithm $\mathcal {B} _1$ takes as input a DH challenge $(X, Y) = (g^x,g^y)$ and outputs a group element $Z$. It has access to a strong Diffie-Hellman oracle $\mathsf {stDH}_x(\cdot , \cdot )$.

Reduction $\mathcal {B} _1$ runs Game 2 with the following changes: it chooses i uniformly at random and sets user i’s public key to $pk _i = X$ (and thus implicitly sets i’s private key to the unknown value $x$). For type IV oracles whose intended peer is user i, $\mathcal {B} _1$ sets $V_{}= Y\cdot g^{\rho _0}$, with $\rho _0$ random. If the adversary corrupts user i, the reduction $\mathcal {B} _1$ aborts. (For other users, the reduction simply returns the secret key, as in Game 2.)

We need to recognise hash queries of the form (4) and (5) that involve user i, as well as queries of the form (7). For (4), where user i acts in the responder role, we know the oracle’s random exponent $s_{}$, so we only need to recognise if $W_2$ is $U_{}$ raised to user i’s secret key, which can be done by checking if $\mathsf {stDH}_x(U_{}, W_2) = 1$.

For (5), where user i is the initiator, we know the oracle’s random exponent $r_{}$, so we only need to recognise if $W_1$ is $V_{}$ raised to user i’s secret key, which can be done by checking if $\mathsf {stDH}_x(V_{}, W_1) = 1$.

Finally, for (7), we need to recognise if a group element $W_1$ is $V_{}$ raised to user i’s secret key, which can be done by checking if $\mathsf {stDH}_x(V_{}, W_1) = 1$. When we recognise a query of the form (7), since we know that $V_{}= Y\cdot g^{\rho _0}$, we output

$$\begin{aligned} Z= W_1 X^{-\rho _0} = V_{}^{x} X^{-\rho _0} = Y^{x} g^{\rho _0x} g^{-x\rho _0} = Y^{x} \text{. } \end{aligned}$$

In other words, our adversary $\mathcal {B} _1$ succeeds whenever $E_i$ would happen in Game 2. Furthermore, $E_i$ in Game 2 can only happen before user i is corrupted, so whenever $E_i$ would happen in Game 2, $\mathcal {B} _1$ would not have aborted.

We get that

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _1) \ge \frac{1}{\mu } \sum _i \Pr [ E_i ] \ge \frac{1}{\mu } \sum _i \Pr [ F_i ] = \frac{1}{\mu } \Pr [ F] \text{, } \end{aligned}$$

from which it follows that

$$\begin{aligned} |\Pr [ S_{3} ] - \Pr [ S_{2} ]| \le \Pr [ F] \le \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _1) \text{. } \end{aligned}$$

(8)

4.3 Type III Responder Oracles

Game 4

In this game type III responder oracles choose their session key at random, and do not modify the key derivation hash oracle.

Consider a type III responder oracle for user j with secret key $b$, random exponent $s_{}$ and intended peer i, who has secret key $a$. Unless the adversary ever makes a hash query of the form

$$\begin{aligned}&\hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert W_1 \Vert W_2 \Vert W_3&W_3 = U_{}^{s_{}} \text{, } \end{aligned}$$

(9)

this change is unobservable. Call this event $F$. We thus have

$$\begin{aligned} |\Pr [ S_{4} ] - \Pr [ S_{3} ]| \le \Pr [ F]. \end{aligned}$$

(10)

We shall bound the probability of $F$ by constructing an adversary against strong Diffie-Hellman. This adversary will embed its challenge in type I or II initiator oracles’ message, as well as in type III responder oracles’ message. It will recover the solution to its DH challenge from the hash query in event $F$.

Strong Diffie-Hellman Adversary $\mathcal {B} _2$. The algorithm $\mathcal {B} _2$ takes as input a DH challenge $(X, Y) = (g^x,g^y)$ and outputs a group element $Z$. It has access to a strong DH-oracle $\mathsf {stDH}_x(\cdot , \cdot ).$

Our reduction $\mathcal {B} _2$ runs Game 3 with the following changes: for type I and II initiator oracles (we cannot distinguish these at this point in time), it computes $U_{}= X\cdot g^{\rho _0}$, with $\rho _0$ random. For type III responder oracles, it computes $V_{}= Y\cdot g^{\rho _1}$, with $\rho _1$ random. Note that in this game, the reduction knows all static secret keys, so user corruption is handled exactly as in Game 3.

We need to recognise hash queries of the form (5) for type II initiator oracles, as well as queries of the form (9) for type III oracles. Although we do not know the oracle’s random exponents, we do know their secret keys. This means that we only need to recognise if $W_3$ is $V_{}$ raised to $\log _g U_{}= x+ \rho _0$. Of course, if $W_3 = V_{}^{x+ \rho _0}$, then $W_3 V_{}^{-\rho _0} = V_{}^{x}$, which we can detect by checking if $\mathsf {stDH}_x(V_{}, W_3 V_{}^{-\rho _0}) = 1$. If this is the case for a query of the form (9), then we output

$$\begin{aligned} Z = W_3 \cdot V_{}^{-\rho _0} \cdot X^{-\rho _1} = V_{}^{x} \cdot X^{-\rho _1} = g^{yx+ \rho _1x}g^{-x\rho _1} = Y^{x} \end{aligned}$$

as the solution to the DH challenge. In other words, $\mathcal {B} _2$ succeeds whenever $F$ would happen in Game 3, hence

$$\begin{aligned} |\Pr [ S_{4} ] - \Pr [ S_{3} ]| \le \Pr [ F] \le \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _2) \text{. } \end{aligned}$$

(11)

Note that we do not stop the simulation in the case we detect a hash query of the form (5) for a type II initiator oracle, because in this case the responder message $V_{}$ does not contain the embedded DH challenge.

4.4 Type II Initiator Oracles

Game 5

In this game type II initiator oracles choose their session key at random, but do not modify the hash oracle unless the intended peer is corrupted. If the adversary corrupts the intended peer j of a type II oracle running as user i with secret key $a$, random exponent $r_{}$ and chosen key $k$, then from that point in time, any query of the form

$$\begin{aligned} \hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert V_{}^{a} \Vert pk _j^{r_{}} \Vert V_{}^{r_{}} \end{aligned}$$

to the key derivation hash oracle $H$ will result in the hash value $k$.

Unless one of these queries happen before the user j is corrupted, the only change is at which point in time the key derivation hash oracle value is first defined, which is unobservable. Let $F$ be the event that a query as above happens before the corresponding long-term key is corrupted. Then

$$\begin{aligned} |\Pr [ S_{5} ] - \Pr [ S_{4} ]| \le \Pr [ F] \text{. } \end{aligned}$$

Let $F_j$ be the same event as $F$, but with the intended peer being user j. We then have that $\Pr [ F] = \sum _j \Pr [ F_j ]$.

Next, consider the event $E_j$ which is that for some type II oracle as above, any query of the form

$$\begin{aligned}&\hat{i} \Vert \hat{j} \Vert pk _{i} \Vert pk _{j} \Vert U_{}\Vert V_{}\, \Vert W_1 \Vert W_2 \Vert W_3&W_2&= pk _{j}^{r_{}} = U_{}^{b} \end{aligned}$$

(12)

to the key derivation hash oracle $H$ happens before user j is corrupted. Then $\Pr [ F_j ] \le \Pr [ E_j ]$.

We shall now bound the probability of the event $E_j$ by constructing an adversary against strong Diffie-Hellman. This adversary will embed its DH challenge in some user j’s public key and type II oracle messages for oracles whose intended peer is user j, and recover the solution to its DH challenge from the hash query in event $E_j$.

Strong Diffie-Hellman Adversary $\mathcal {B} _3$. The algorithm $\mathcal {B} _3$ takes as input a DH challenge $(X, Y) = (g^x,g^y)$ and outputs a group element $Z$. It has access to a strong DH-oracle $\mathsf {stDH}_x(\cdot , \cdot )$.

Our reduction $\mathcal {B} _3$ runs Game 4 with the following changes: It chooses j uniformly at random and sets user j’s public key to $pk _j = X$ (and thus implicitly sets j’s private key to the unknown value $b= x$). For type I and II initiator oracles whose intended peer is user j, $\mathcal {B} _3$ sets $U_{}= Y\cdot g^{\rho _0}$, with $\rho _0$ random. If the adversary corrupts user j, the reduction $\mathcal {B} _3$ aborts. (For other users, the reduction simply returns the secret key, as in Game 4.)

We need to recognise hash queries of the form (4) and (5) that involve user j, as well as queries of the form (12). For (4), where user j is the responder, we know the oracle’s random exponent $s_{}$, so we only need to recognise if $W_2$ is $U_{}$ raised to user j’s secret key, which can be done by checking if $\mathsf {stDH}_x(U_{}, W_2) = 1$. For (5), where user j is the initiator, we know the oracle’s random exponent $r_{}$, so we only need to recognise if $W_1$ is $V_{}$ raised to user j’s secret key, which can be done by checking if $\mathsf {stDH}_x(V_{}, W_1)=1$. Finally, for (12), we need to recognise if a group element $W_2$ is $U_{}$ raised to user j’s secret key, which can be done by checking if $\mathsf {stDH}_x(U_{}, W_2) = 1$.

When we recognise a query of the form (12), meaning that $W_2 = U_{}^{x}$ where know that $U_{}= Y\cdot g^{\rho _0}$, then we output

$$\begin{aligned} Z= W_2 X^{-\rho _0} = U_{}^{x} X^{-\rho _0} = Y^{x} g^{\rho _0x} g^{-x\rho _0} = Y^{x} \text{. } \end{aligned}$$

In other words, our adversary $\mathcal {B} _3$ succeeds whenever $E_j$ would happen in Game 4. Furthermore, $E_j$ in Game 4 can only happen before user j is corrupted, so whenever $E_j$ would happen in Game 4, $\mathcal {B} _3$ would not have aborted. We get that

$$\begin{aligned} \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _3) \ge \frac{1}{\mu } \sum _j \Pr [ E_j ] \ge \frac{1}{\mu } \sum _j \Pr [ F_j ] = \frac{1}{\mu } \Pr [ F] \text{, } \end{aligned}$$

from which it follows that

$$\begin{aligned} |\Pr [ S_{5} ] - \Pr [ S_{4} ]| \le \Pr [ F] \le \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {stDH} }}(\mathcal {B} _3) \text{. } \end{aligned}$$

(13)

4.5 Summary

Note that in Game 5, every session key is chosen at random independent of every key and sent message.

For type V oracles, the key derivation oracle is immediately programmed so that the session key is available to the adversary. But type V oracles are never fresh and therefore never subject to a Test query.

For type II and IV oracles, the key derivation hash oracle is programmed to make the session key available to the adversary only after the intended peer is corrupted. But if the intended peer is corrupted, a type II or IV oracle will become non-fresh, hence no Test query can be made to it.

For type I and III oracles, the key derivation hash oracle will never make the session key available to the adversary.

This means that for any oracle subject to a Test query, the session key is and will remain independent of every key and sent message. Which means that the adversary cannot distinguish the session key from a random key. It follows that

$$\begin{aligned} \Pr [ S_{5} ] = \frac{1}{2} \text{. } \end{aligned}$$

(14)

Furthermore, (3) from Game 1 gives us $\Pr [ \mathsf {break} _\mathrm {Unique} ] \le \mu \ell ^2/p$. Because of perfect correctness $\Pr [ \mathsf {break} _\mathrm {Sound} ] = 0$. It is now easy to see that Theorem 2 follows from the construction of $\mathcal {B} _1$, $\mathcal {B} _2$ and $\mathcal {B} _3$ as well as Eqs. (1), (2), (6), (8), (11), (13) and (14).

5 Avoiding the Strong Diffie-Hellman Assumption

The proof of ${\Pi }$ relies on the strong Diffie-Hellman assumption, which is an interactive assumption. A natural goal is to look for a protocol whose proof relies on standard non-interactive assumptions. In this section we present two protocols that solve this problem. Both can be seen as different modifications of ${\Pi }$.

5.1 Protocol ${\Pi }_{\mathrm {Twin}}$

The first protocol, which we call ${\Pi }_{\mathrm {Twin}}$, applies the twinning technique of [13] to the different DH values in ${\Pi }$. This requires some additional exponentiations over protocol ${\Pi }$, as well as the need to transmit one extra group element. The details are given in Fig. 2: instead of sending a single Diffie-Hellman share, the protocol initiator samples and sends two ephemeral shares, and both shares are used in the key derivation. This duplication allows us to reduce to twin Diffie-Hellman.

Fig. 2.

Protocol ${\Pi }_{\mathrm {Twin}}$. It is obtained from protocol ${\Pi }$ by applying the twinning trick of [13] to the DH values

Theorem 3

Consider the protocol ${\Pi }_{\mathrm {Twin}}$ defined in Fig. 2 where $H$ is modeled as a random oracle. Let $\mathcal {A}$ be an adversary against the AKE security of ${\Pi }_{\mathrm {Twin}}$. Then there exists adversaries $\mathcal {B} _1$, $\mathcal {B} _2$ and $\mathcal {B} _3$ against twin Diffie-Hellman such that

$$\begin{aligned} \mathrm {Adv}_{{\Pi }_{\mathrm {Twin}}}^{{\textsf {AKE} }}(\mathcal {A}) \le \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {2\text {-}CDH} }}(\mathcal {B} _1) + \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {2\text {-}CDH} }}(\mathcal {B} _2) + \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {2\text {-}CDH} }}(\mathcal {B} _3) + \frac{\mu \ell ^2}{p} \text{. } \end{aligned}$$

The adversaries all run in essentially the same time as $\mathcal {A}$ and make at most as many queries to their twin DH oracle as $\mathcal {A}$ makes to its hash oracle $H$.

The proof is given in the full version. Note that by Theorem 1, we can tightly replace the twin Diffie-Hellman terms in the theorem statement by ordinary computational Diffie-Hellman terms.

5.2 Protocol ${\Pi }_{\mathrm {Com}}$

The second protocol, which we call ${\Pi }_{\mathrm {Com}}$, again uses the twinning technique of [13], but this time only applied to the static DH values in ${\Pi }$. This provides tight implicit authentication. However, instead of also twinning the ephemeral DH values we use a variant of the commitment trick of [19]. This reduces the number of exponentiations compared to ${\Pi }_{\mathrm {Twin}}$, but adds another round of communication. Also, we need to rely on the Decision Diffie-Hellman assumption instead of computational Diffie-Hellman. The details are given in Fig. 3. The proof of the following theorem is given in the full version.

Fig. 3.

Protocol ${\Pi }_{\mathrm {Com}}$. It is obtained from protocol ${\Pi }$ by applying the twinning trick of [13] to the static DH values and the commitment trick of [19] to the ephemeral DH values.

Theorem 4

Consider the protocol ${\Pi }_{\mathrm {Com}}$ defined in Fig. 3 where $H$ and $G$ are modeled as random oracles. Let $\mathcal {A}$ be an adversary against the AKE security of ${\Pi }_{\mathrm {Com}}$. Then there exists adversaries $\mathcal {B} _1$ and $\mathcal {B} _3$ against computational Diffie-Hellman and an adversary $\mathcal {B} _2$ against Decision Diffie-Hellman such that

$$\begin{aligned} \mathrm {Adv}_{{\Pi }_{\mathrm {Twin}}}^{{\textsf {AKE} }}(\mathcal {A}) \le \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {CDH} }}(\mathcal {B} _1) + \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {DDH} }}(\mathcal {B} _2) + \mu \cdot \mathrm {Adv}_{\mathbb {G}, g}^{{\textsf {CDH} }}(\mathcal {B} _3) + \frac{\mu \ell ^2(1+2t)}{p} \text{. } \end{aligned}$$

The adversaries all run in essentially the same time $t$ as $\mathcal {A}$ and make at most as many queries to their twin DH oracle as $\mathcal {A}$ makes to its hash oracle $H$.

6 Efficiency Analysis

In this section we argue that our protocols are more efficient than other comparable² protocols in the literature when instantiated with theoretically sound parameter choices. There are two reasons for this. First, the most efficient key protocols do not have tight proofs. Hence, for theoretically sound deployment they must use larger parameters to compensate for the proof’s security loss, which directly translates into more expensive operations. The result is that although some protocols require fewer operations than ours (typically group exponentiations), the increase in computational cost per operation dominates whatever advantage they might have over our protocols in terms of number of operations.

Second, the few known key exchange protocols which do have tight proofs, require a large number of operations or heavy cryptographic machinery. Thus, even though they can use small parameters, such as the P-256 elliptic curve, here the sheer number of operations dominates their advantage over our protocols.

To illustrate the first point in more detail, here are some examples of very efficient key exchange protocols having non-tight security proofs: UM [33], KEA+ [30], HMQV [26], CMQV [39], $\mathcal {TS}1/2/3$ [24], Kudla-Paterson [28], and NAXOS [29]. Typically, these proofs have a tightness loss between $L = O(\mu \ell )$ and $L = O(\mu ^2\ell ^2)$ as illustrated for a few of the protocols in Table 1.

Table 1. The number of group exponentiations in our protocols compared to other protocols in the literature. All protocols are one-round except ${\Pi }_{\mathrm {Com}}$, which has two rounds of communication. All security proofs are in the random oracle model. The security loss is in terms of the number of users ($\mu$), the number of protocol instances per user ($\ell$), and reduction’s running time (t).

Suppose we now want to compare the efficiency of the protocols ${\Pi }$, ${\Pi }_{\mathrm {Twin}}$, ${\Pi }_{\mathrm {Com}}$ and HMQV, aiming for around 110-bits of security. Following Gjøsteen and Jager [19], let us imagine two different scenarios: a small-to-medium-scale setting with $\mu = 2^{16}$ users and $\ell = 2^{16}$ sessions per user, and a large-scale setting with $\mu = 2^{32}$ users and $\ell = 2^{32}$ sessions per user. To instantiate the protocols in a theoretically sound manner we need to select a group large enough so that the underlying DH-assumptions are still hard even when accounting for the security loss. For simplicity, we only consider selecting among elliptic curve groups based on the NIST curves P-256, P-384, and P-521, and assume that the CDH, DDH, and Gap-DH problems are equally hard in each group.  

HMQV. :

Supposing HMQV has a tightness loss of $L \approx \mu ^2\ell ^2$, this translates into a loss of $2^{64}$ in the small-to-medium-scale setting, and a loss of $2^{128}$ in the large-scale setting. To compensate we have to increase the group size by a factor of $L^2 \approx 2^{128}$ and $L^2 \approx 2^{256}$, respectively. With a target of 110-bit security, this means that we have to instantiate HMQV with curve P-384 and P-521, respectively.

$\mathbf {{\Pi }}, \mathbf {{\Pi }_{\mathrm {Twin}}}, \mathbf {{\Pi }_{\mathrm {Com}}}{} \mathbf .$ :

Our protocols’ security proofs have a tightness loss of $L \approx \mu$, which translates into $2^{16}$ in the small-to-medium-scale setting and $2^{32}$ in the large-scale setting. In the first setting P-256 is still sufficient for 110-bit security, but in the later setting P-384 must be used instead.

 

We can now compare these instantiations by multiplying the number of exponentiations required with the cost of an exponentiation in the relevant group. For the latter values we use the OpenSSL benchmark numbers from Gjøsteen and Jager [19] (reproduced in Table 2). Calculating the numbers we get:

	HMQV	${\Pi }$	${\Pi }_{\mathrm {Twin}}$	${\Pi }_{\mathrm {Com}}$
S-M	$2.5 \times 5.6 = 14$	$4 \times 2.1 = 8.4$	$8 \times 2.1 = 16.8$	$6 \times 2.1 = 12.6$
L	$2.5 \times 16.1 = 40.3$	$4 \times 5.6 = 22.4$	$8 \times 5.6 = 44.8$	$6 \times 5.6 = 33.6$

Table 2. OpenSSL benchmark results for NIST curves [19, Table 1].

Observe that ${\Pi }$ is more efficient than HMQV in both the small-to-medium-scale setting as well as in the large-scale setting despite needing more exponentiations. This is because it can soundly use smaller curves than HMQV due to the relative tightness of its reduction. Protocol ${\Pi }_{\mathrm {Twin}}$ is about as efficient as HMQV in both settings, while ${\Pi }_{\mathrm {Com}}$ lies somewhere in between ${\Pi }$ and ${\Pi }_{\mathrm {Twin}}$, but since it requires one extra round of communication a direct comparison is more difficult. Of course, the main reason to prefer ${\Pi }_{\mathrm {Twin}}$ and ${\Pi }_{\mathrm {Com}}$ over ${\Pi }$ is the reliance on the weaker CDH and DDH assumptions rather than strong DH. A complicating factor in comparing with HMQV is the difference in security properties and security models (see the end of this section).

To illustrate the second point mentioned above—that our protocols are also more efficient than protocols with fully tight proofs—we also compute the numbers for the recent protocol of Gjøsteen and Jager (GJ) which is currently the most efficient key exchange protocol with a fully tight proof. Since GJ can use P-256 independent of the number of users and sessions its cost is $17 \times 2.1 = 35.7$ in both the small-to-medium scale setting as well as the large-scale setting. Nevertheless, we observe that the large number of exponentiations in GJ dominates its tightness advantage in realistic settings.

Thus, absent a fully tight proof, our protocols hit a proverbial “sweet spot” between security loss and computational complexity: they can be instantiated soundly on relatively small curves using only a few exponentiations.

Communication Complexity. For completeness we also briefly mention communication complexity. Since in most implicitly-authenticated DH-based protocols each user only sends one or two group elements, there is in practice little difference between ${\Pi }$, ${\Pi }_{\mathrm {Twin}}$, and ${\Pi }_{\mathrm {Com}}$, and protocols like HMQV when it comes to communication cost. Especially if elliptic curve groups are used.

This is in contrast to the fully tight signature-based GJ protocol, which in total needs to exchange two group elements for the Diffie-Hellman key exchange, two signatures (each consisting of a random 256-bit exponent, two group elements, and four 256-bit exponents), and one hash value. Altogether, this gives a total of $\approx 545$ bytes communicated when instantiated for a security level of, say, 128 bits [19, Sect. 5]. In comparison, ${\Pi }$, ${\Pi }_{\mathrm {Twin}}$, and ${\Pi }_{\mathrm {Com}}$ would only need to exchange around 160 to 224 bytes for the same security level. This assumes curve P-384 and includes the addition of two 256-bit key-confirmation messages to provide explicit entity authentication in order to make the comparison with the GJ protocol fair.

On the (Im)possibility of Fairly Comparing Protocols. Our protocols are the first implicitly authenticated key exchange protocols that were designed to provide efficient deployment in a theoretically sound manner. This implies that we must compare their efficiency with other protocols with slightly different goals. In Table 1 we included protocols with closely related goals and similar structure, but not aiming for exactly the same target.

One example of such a different goal is that NAXOS was designed to be proven in the eCK model, which also allows the reveal of the randomness of the tested session, similar to HMQV. Our protocols, like TLS 1.3, currently do not offer this property. We conjecture that the NAXOS transformation could be directly applied to our protocols to obtain eCK-secure protocols without adding exponentiations, but it is currently unclear if this could be done with a tight proof, and hence we leave this to future work.

7 Optimality of Our Security Proofs

In this section we will show that the tightness loss of $L = O(\mu )$ in Theorems 2, 3 and 4 is essentially optimal—at least for “simple” reductions. Basically, a “simple” reduction runs a single copy of the adversary only once. To the best of our knowledge, all known security reductions for AKE protocols are either of this type or use the forking lemma. For example, the original reduction for HMQV uses the forking lemma and thus is very non-tight, but does not fall under our lower bound. In contrast, the HMQV reduction by Barthe et al. [5] is simple and thus our lower bound applies. Hence, in order to give a tighter security proof, one would have to develop a completely new approach to prove security for such protocols.

Tightness bounds for different cryptographic primitives were given in [4, 15, 17, 18, 21, 23, 25, 31, 35, 37, 40], for instance. Bader et al. [4] describe a generic framework that makes it possible to derive tightness lower bounds for many different primitives. However, these techniques are only able to consider tight reductions from non-interactive assumptions, while our first protocol is based on the interactive strong Diffie-Hellman assumption. Morgan and Pass [34] showed how to additionally capture bounded-round interactive assumptions, but the strong Diffie-Hellman assumption does not bound the number of possible oracle queries, so we cannot use their approach directly.

Therefore we develop a new variant of the approach of Bader et al. [4], which makes it possible to capture interactive assumptions with an unbounded number of oracle queries, such as strong Diffie-Hellman assumption. For clarity and simplicity, we formulate this specifically for the class of assumptions and protocols that we consider, but we discuss possible extensions below.

Considered Class of Protocols. In the following we consider protocols where public keys are group elements of the form $pk = g^x$ and the corresponding secret key is $sk = x$. We denote the class of all protocols with this property with ${\Pi }_\mathsf {DH}$. Note that this class contains, in particular, NAXOS [29], KEA+ [30], and HMQV [26].

Remark 1

One can generalize our results to unique and verifiable secret keys, which essentially requires that for each value $pk$ there exists only one unique matching secret key $sk$, and that there exists an efficiently computable relation R such that $R( pk , sk )=1$ if and only if $( pk , sk )$ is a valid key pair. Following Bader et al. [4], one can generalize this further to so-called efficiently re-randomizable keys. We are not aware of concrete examples of protocols that would require this generality, and thus omit it here. All protocols considered in the present paper and the vast majority of high-efficiency protocols in the literature have keys of the form $( pk , sk ) = (g^x,x)$, so we leave such extensions for future work.

Why Does GJ18 Not Contradict Our Lower Bound? As mentioned in Remark 1, our bound applies to protocols with unique and verifiable secret keys. In contrast, the protocol of Gjøsteen and Jager [19] constructs a tightly-secure digital signature scheme based on OR-proofs, where secret keys are not unique. As explained in [19, Section 1.1], these non-unique secret keys seem inherently necessary to achieve fully-tight security.

Simple Reductions from (Strong) Diffie-Hellman. Intuitively, a simple reduction ${\mathcal {R}} = {\mathcal {R}} ^\mathcal {O}$ from (strong) CDH takes as input a CDH instance $(g^x,g^y)$ and may query an oracle $\mathcal {O}$ that, on input Y, Z, returns 1 if and only if $Y^x = Z$ (cf. Definition 3). More formally:

Definition 10

A simple reduction ${\mathcal {R}}$ interacts with an adversary $\mathcal {A}$ as follows.

• 1. ${\mathcal {R}}$ receives as input a CDH instance $(g^x,g^y)$.

• 2. It generates $\mu$ public keys and starts $\mathcal {A} ( pk _1, \ldots , pk _\mu )$. ${\mathcal {R}}$ provides $\mathcal {A}$ with access to all queries provided in the security model described in Sect. 3.

• 3. ${\mathcal {R}}$ outputs a value h.

We say that ${\mathcal {R}}$ is a $(t_{\mathcal {R}},\epsilon _{\mathcal {R}},\epsilon _\mathcal {A} )$-reduction, if it runs in time at most $t_{\mathcal {R}}$ and for any adversary $\mathcal {A}$ with $\epsilon _\mathcal {A} = \mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {A})$ holds that

$$\begin{aligned} \Pr \left[ h = g^{xy}\right] \ge \epsilon _{\mathcal {R}}. \end{aligned}$$

We say that ${\mathcal {R}} = {\mathcal {R}} ^\mathcal {O}$ is a reduction from the strong CDH problem if it makes at least one query to its oracle $\mathcal {O}$, and a reduction from the CDH problem if not.

Remark 2

The formalization in this section very specifically considers the computational problems CDH and sCDH, as concrete examples of reasonable hardness assumptions that a typical security proof for the protocols considered in this work may be based on. We will later discuss how our results can be extended to other interactive and non-interactive problems.

Theorem 5

Let $\Pi$ be an AKE protocol such that $\Pi \in \Pi _\mathsf {DH}$. Let ${|{\mathcal {K}}|}$ denote the size of the key space of $\Pi$. For any simple $(t_{\mathcal {R}},\epsilon _{\mathcal {R}},1-1/{|{\mathcal {K}}|})$-reduction ${\mathcal {R}} ^\mathcal {O}$ from (strong) CDH to breaking $\Pi$ in the sense of Definition 9 there exists an algorithm ${\mathcal {M}} ^\mathcal {O}$, the meta-reduction, that solves the (strong) CDH problem in time $t_{\mathcal {M}}$ and with success probability $\epsilon _{\mathcal {M}}$ such that $t_{\mathcal {M}} \approx \mu \cdot t_{\mathcal {R}}$ and

$$\begin{aligned} \epsilon _{\mathcal {M}} \ge \epsilon _{\mathcal {R}}- \frac{1}{\mu } \text {.} \end{aligned}$$

Remark 3

Note that the lower bound $\epsilon _{\mathcal {M}} \ge \epsilon _{\mathcal {R}}- 1/\mu$ implies that the success probability $\epsilon _{\mathcal {R}}$ cannot significantly exceed $1/\mu$, as otherwise there exists an efficient algorithm ${\mathcal {M}}$ for a computationally hard problem. Note also that this implies that the reduction cannot be tight, as it “loses” a factor of at least $1/\mu$, even if the running time of ${\mathcal {R}}$ is not significantly larger than that of the adversary.

In the sequel we write $[\mu \setminus i]$ as a shorthand for $[1\ldots i-1, i+1 \ldots \mu ]$.

Proof

We describe a meta-reduction ${\mathcal {M}}$ that uses ${\mathcal {R}}$ as a subroutine to solve the (strong) CDH problem. Following Hofheinz et al. [21] and Bader et al. [4], we will first describe a hypothetical inefficient adversary $\mathcal {A}$. Then we explain how this adversary is efficiently simulated by ${\mathcal {M}}$. Finally, we bound the success probability of ${\mathcal {M}}$, which yields the claim.

Hypothetical Adversary. The hypothetical adversary $\mathcal {A}$ proceeds as follows.

• 1. Given $\mu$ public keys $pk _1 = g^{x_1}, \ldots , pk _\mu = g^{x_\mu }$, $\mathcal {A}$ samples a uniformly random index $j^*\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,[\mu ]$. Then it queries $\mathsf {RevLTK}(i)$ for all $i \in [\mu \setminus j^*]$ to obtain all secret keys except for $sk _{j^*}$.

• 2. Next, $\mathcal {A}$ computes $sk _{j^*} = x_{j^*}$ from $pk _{j^*} = g^{x_{j^*}}$, e.g., by exhaustive search.³

• 3. Then $\mathcal {A}$ picks an arbitrary oracle, say $\pi _{s}^1$ for $s = ({j^*+1}) \bmod \mu$, and executes the protocol with $\pi _{s}^1$, impersonating user ${j^*}$. That is, $\mathcal {A}$ proceeds exactly as in the protocol specification, but on behalf of user $j^*$. Note that $\mathcal {A}$ it is able to compute all messages and the resulting session key on behalf of user ${j^*}$, because it “knows” $sk _{j^*}$.

• 4. Finally, $\mathcal {A}$ asks $\mathsf {Test}(s, 1)$. Note that this is a valid $\mathsf {Test}$-query, as $\mathcal {A}$ has never asked any $\mathsf {RevSessKey}$-query or $\mathsf {RevLTK}({j^*})$ to the peer $j^*$ of oracle $\pi _{s}^1$. If the experiment returns the “real” key, then $\mathcal {A}$ outputs “1”. Otherwise it outputs “0”.

Note that $\mathcal {A}$ wins the security experiment with optimal success probability $1-1/{|{\mathcal {K}}|}$, where ${|{\mathcal {K}}|}$ is the size of the key space. The loss of $1/{|{\mathcal {K}}|}$ is due to the fact that the random key chosen by the $\mathsf {Test}$-query may be equal to the actual session key.

Description of the Meta-reduction. Meta-reduction ${\mathcal {M}}$ interacts with reduction ${\mathcal {R}}$ by simulating the hypothetical adversary $\mathcal {A}$ as follows.

• 1. ${\mathcal {M}}$ receives as input a CDH instance $(g^x,g^y)$. It starts ${\mathcal {R}}$ on input $(g^x,g^y)$.

• 2. Whenever ${\mathcal {R}}$ issues a query to oracle $\mathcal {O}$, ${\mathcal {M}}$ forwards it to its own oracle. Note that both oracles are equivalent, because ${\mathcal {M}}$ has simply forwarded the CDH instance.

• 3. When ${\mathcal {R}}$ outputs public keys $pk _1 = g^{x_1}, \ldots , pk _\mu = g^{x_\mu }$ to $\mathcal {A}$, ${\mathcal {M}}$ makes a snapshot of the current state $st_{\mathcal {R}}$ of ${\mathcal {R}}$.

• 4. For $j \in [1 \ldots \mu ]$, ${\mathcal {M}}$ now proceeds as follows.

  • (a) It lets $\mathcal {A}$ query $\mathsf {RevLTK}(i)$ for all $i \in [\mu \setminus j]$, in order to obtain all secret keys except for $sk _j$. Note that the reduction may or may not respond to all $\mathsf {RevLTK}(i)$ queries. For instance, ${\mathcal {R}}$ may abort for certain queries.

  • (b) Then it resets ${\mathcal {R}}$ to state $st_{\mathcal {R}}$.

• 5. Now ${\mathcal {M}}$ proceeds to simulate the hypothetical adversary. That is:

  • (a) It picks a uniformly random index $j^*\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,[1 \ldots \mu ]$ and queries $\mathsf {RevLTK}(i)$ for all $i \in [\mu \setminus j^*]$.

  • (b) Then it executes the protocol with $\pi _{s}^1$, impersonating user $j^*$. Note that this works only if ${\mathcal {M}}$ was able to obtain $sk _{j^*}$ in Step (4).

  • (c) Finally, ${\mathcal {M}}$ lets $\mathcal {A}$ ask $\mathsf {Test}(s, 1)$. If the experiment returns the “real” key, then $\mathcal {A}$ outputs “1”. Otherwise it outputs “0”.

• 6. If ${\mathcal {R}}$ outputs some value h throughout the experiment, then ${\mathcal {M}}$ outputs the same value.

Note that ${\mathcal {M}}$ provides a perfect simulation of the hypothetical adversary, provided that it “learns” $sk _{j^*}$ in the loop in Step (4).

Analysis of the Meta-reduction. ${\mathcal {M}}$ essentially runs reduction ${\mathcal {R}}$ at most $\mu$ times. Apart from that, it performs only minor additional operations, such that we have $t_{\mathcal {M}} \approx \mu \cdot t_{\mathcal {R}}$.

In order to analyse the success probability of ${\mathcal {M}}$, let us say that $\mathsf {bad}$ occurs, if $j^*$ is the only index for which ${\mathcal {R}}$ did not abort in Step (4) of the meta-reduction. Note that in this case ${\mathcal {M}}$ learns all secret keys, except for $sk _{j^*}$, in which is the only case where the simulation of $\mathcal {A}$ in Step (5.b) fails. Since we may assume without loss of generality that the reduction ${\mathcal {R}}$ works for at least one index $j \in [\mu ]$ and we chose $j^*\,{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\,[\mu ]$ uniformly random, we have

$$\begin{aligned} \Pr \left[ \mathsf {bad} \right] \le \frac{1}{\mu }. \end{aligned}$$

Let $\mathsf {win}({\mathcal {R}},\mathcal {A})$ denote the event that ${\mathcal {R}}$ outputs $h = g^{xy}$ when interacting with $\mathcal {A}$, and $\mathsf {win}({\mathcal {R}},{\mathcal {M}})$ the corresponding event with ${\mathcal {M}}$. Since ${\mathcal {M}}$ simulates $\mathcal {A}$ perfectly unless $\mathsf {bad}$ occurs, we have

$$\begin{aligned} \left| \Pr \left[ \mathsf {win}({\mathcal {R}},\mathcal {A}) \right] - \Pr \left[ \mathsf {win}({\mathcal {R}},{\mathcal {M}}) \right] \right| \le \Pr \left[ \mathsf {bad} \right] . \end{aligned}$$

Furthermore, note that by definition we have $\epsilon _{\mathcal {R}} = \Pr \left[ \mathsf {win}({\mathcal {R}},\mathcal {A}) \right]$ and $\epsilon _{\mathcal {M}} = \Pr \left[ \mathsf {win}({\mathcal {R}},{\mathcal {M}}) \right]$. Hence we get $\left| \epsilon _{\mathcal {R}}- \epsilon _{\mathcal {M}} \right| \le 1/\mu$, which in turn yields the lower bound $\epsilon _{\mathcal {M}} \ge \epsilon _{\mathcal {R}}- 1/\mu$.

Generalizations. The tightness lower bound proven above makes several very specific assumptions about the considered protocols, hardness assumptions, and security models. The main purpose of this is to keep the formalization and proof focused on the type of protocols that we are considering in this paper. However, a natural question is to which extent the results also apply to more general protocols, models, and assumptions, and whether and how the tightness bound can be evaded by tweaking the considered setting.

First of all, we consider only protocols where long-term secrets are of the form $( pk , sk ) = (g^x, x)$. As already briefly discussed above, one can generalize this to other protocols, as long as the simulation of the hypothetical adversary by the meta-reduction is able to recover properly distributed secret keys. In particular, one can generalize to arbitrary efficiently re-randomizable long-term keys, as defined by Bader et al. [4]. Note that current AKE protocols with tight security proofs [3, 19] do not have efficiently rerandomizable keys, and therefore do not contradict our result.

In order to obtain a tighter security proof one may try to make different complexity assumptions. These can be either non-interactive (i.e., the reduction does not have access to an oracle $\mathcal {O}$, such as e.g. DDH), or stronger interactive assumptions. Let us first consider non-interactive assumptions. A very general class of such assumptions was defined abstractly in Bader et al. [4], and it is easy to verify that our proof works exactly the same way with such an abstract non-interactive assumption instead of CDH.

Some stronger assumptions may yield tight security proofs, but not all of them do. Consider for instance the gap Diffie-Hellman assumption, which is identical to strong Diffie-Hellman, except that the first input to the provided DDH-oracle is not fixed, but can be arbitrary. It is easy to verify that our proof also works for this assumption, in exactly the same way. More generally, our proof works immediately for any assumption for which the “winning condition” of the reduction is independent of the sequence of oracle queries issued by the reduction. An example of an interactive assumptions where this does not hold is the trivial interactive assumption that the protocol is secure (which, of course, immediately yields a tight security proof).

Finally, we note that our impossibility result holds also for many weaker or stronger AKE security models. We only require that the model allows for active attacks and provides a $\mathsf {RevLTK}$ query. Thus, the result immediately applies also to weaker models that, e.g., do not provide a $\mathsf {RevSessKey}$-query or only a single $\mathsf {Test}$-query, and trivially also for stronger models, such as eCK-style ephemeral key reveals [10, 12]. It remains an interesting open question whether stronger impossibility results (e.g., with quadratic lower bound) can be proven for such eCK-style definitions.

8 Adding Explicit Entity Authentication

In this section we describe how explicit entity authentication (EA) [9] can be added to our protocols by doing an additional key-confirmation step. Recall that EA is the aliveness property that fresh oracles are guaranteed to have a partner once they accept. Our construction is a generic compiler which transforms an arbitrary AKE protocol ${\Pi }$, secure according to Definition 9, into one that also provides EA. The details of the compiler are given in Fig. 4.

Fig. 4.

Generic compiler from an AKE protocol ${\Pi }$ with implicit authentication to a protocol ${\Pi }^{+}$ with explicit entity authentication.

Specifically, protocol ${\Pi }^{+}$ begins by running protocol ${\Pi }$ to obtain a session key $k_{{\Pi }}$. This key, which we henceforth call the intermediate key for protocol ${\Pi }^{+}$, is then used to derive two additional keys: $k_a$ and $k_m$. The first key becomes the final session key of protocol ${\Pi }^{+}$, while $k_m$ is used to compute a key-confirmation message, i.e., a MAC, for each party. The EA property of ${\Pi }^{+}$ reduces to the AKE security of the initial protocol ${\Pi }$, the multi-user PRF security of the function used to derive $k_a$ and $k_m$, as well as the multi-user strong UF-CMA (mu-SUF-CMA) security of the MAC scheme (see the full version for the formal definitions).

Theorem 6

Let ${\Pi }$ be an AKE protocol, let ${\Pi }^{+}$ be the protocol derived from ${\Pi }$ as defined in Fig. 4, and let $\mathcal {A}$ be an adversary against the EA security of protocol ${\Pi }^{+}$. Then there exists adversaries $\mathcal {B} _1$, $\mathcal {B} _2$, $\mathcal {D}$, and $\mathcal {F}$, such that

$$\begin{aligned} \begin{aligned} \mathrm {Adv}_{{\Pi }^{+}}^{{\textsf {EA} }}(\mathcal {A}) \le \mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {B} _1) + 2 \cdot \mathrm {Adv}_{{\Pi }}^{{\textsf {AKE} }}(\mathcal {B} _2) + \mathrm {Adv}_{\mathsf {PRF},\mu \ell }^{{\textsf {mu-PRF} }}(\mathcal {D}) + \mathrm {Adv}_{\mathsf {MAC},\mu \ell }^{{\textsf {mu-SUF-CMA} }}(\mathcal {F}), \end{aligned} \end{aligned}$$

where $\mu \ell$ is the number of sessions created by $\mathcal {A}$. The adversaries $\mathcal {B} _1$, $\mathcal {B} _2$, $\mathcal {D}$, and $\mathcal {F}$ all run in essentially the same time as $\mathcal {A}$.

Our result is basically a restatement of the theorem proved by Yang [41], but with two minor differences: (1) our result is stated for arbitrary protocols and not only two-message protocols, and (2) since we use the AKE-RoR model the proof is tighter and slightly simpler.

9 Conclusion

We showed that it is possible to achieve highly efficient AKE protocols that can be instantiated with theoretically sound parameters. Specifically, we gave protocol constructions that have only a linear tightness loss in the number of users, while using only a handful of exponentiations. Our constructions are at least as efficient as the best known AKE protocols in this setting. Perhaps surprisingly, our constructions only use standard building blocks as used by widely deployed protocols and are very similar to protocols like Noise-KK, and offer similar security guarantees.

While our proofs have a linear loss we have showed that this is actually unavoidable: any reduction from a protocol in our class to a wide class of hardness assumptions must lose a factor of at least $\mu$. Thus, our reductions are optimal in this regard. Additionally, we proved that adding a key confirmation step tightly provides explicit authentication.

Taken together, these results demonstrate for the first time that AKE protocols can be instantiated in a theoretically sound way in real-world deployments without sacrificing performance.