Generic construction of an $\mathrm {eCK}$-secure key exchange protocol in the standard model

Abstract

LaMacchia, Lauter and Mityagin presented a strong security model for authenticated key agreement, namely the $\mathrm {eCK}$ model. They also constructed a protocol, namely the NAXOS protocol, that enjoys a simple security proof in the $\mathrm {eCK}$ model. However, the NAXOS protocol uses a random oracle-based technique to combine the long-term secret key and the per session randomness, so-called NAXOS trick, in order to achieve the $\mathrm {eCK}$ security definition. For NAXOS trick-based protocols, the leakage of per session randomness modeled in the $\mathrm {eCK}$ model is somewhat unnatural, because the $\mathrm {eCK}$ model leaks per session randomness, while the output of the NAXOS trick computation remains safe. In this work, we present a standard model $\mathrm {eCK}$-secure protocol construction, eliminating the NAXOS trick. Moreover, our protocol is a generic construction, which can be instantiated with arbitrary suitable cryptographic primitives. Thus, we present a generic $\mathrm {eCK}$-secure, NAXOS-free, standard model key exchange protocol. To the best of our knowledge this is the first paper on generic transformation of a $\mathrm {CCA2}$-secure public-key encryption scheme to an $\mathrm {eCK}$-secure key exchange protocol in the standard model.

1 Introduction

In 1976, Diffie and Hellman introduced a key exchange primitive [10], which enables two parties to exchange a secret key (session key) by communicating over a public channel. Users Alice and Bob agree on a group $\mathbb {G}$ of prime order q and on a generator g of this group. This is done before executing the rest of the protocol, and g and q are assumed to be public. Alice picks a random integer $a \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}_q$ and computes $A\leftarrow g^a$ and sends it to Bob. Then Bob picks a random integer $b \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}_q$ and computes $B\leftarrow g^b$ and sends it to Alice. After that, Alice computes ${ B^a } = ({g^b})^a = s \in \mathbb {G}$ and Bob computes ${ A^b } = ({g^a})^b = s \in \mathbb {G}$. Thus, both Alice and Bob end up with the same value $s \in \mathbb {G}$. An eavesdropper who watches this communication can see A and B values, but should be unable to determine the values of s (assuming $\mathrm {CDH}$ holds).

Many key exchange protocols have been created based on the Diffie–Hellman key exchange primitive [7, 11, 14]. In these key exchange protocols, different types of keys may be used to compute session keys: long-term secret keys are the static secrets belonging to the protocol participants which are often used to add authentication to the session key, and ephemeral keys are the session-specific secrets belonging to protocol participants which are used to add freshness to the session key. There are a number of known security features for key exchange protocols:

Implicit key authentication If a protocol provides a guarantee that no party apart from the protocol participants can compute the session key, that key exchange protocol is said to provide implicit key authentication. If a key exchange protocol provides implicit key authentication, that protocol is said to be an authenticated key exchange protocol.

Key confirmation If a key exchange protocol provides a guarantee that each party is assured that all other participants possess the session key, that key exchange protocol is said to provide key confirmation.

Known key security The knowledge of a session key should not enable the adversary to learn the session keys in other sessions; all session keys should not depend on the session keys of other sessions.

Unknown key share (UKS) security It should not happen that a party A shares a session key with some party B, but believes that it is sharing the session key with some one else C. That means public keys and identities of the parties should be certified and confirmed or incorporated into protocol execution.

Key compromise impersonation (KCI) resistance Knowing the long-term secret key of a party A should not enable the adversary to impersonate other honest parties to A.

Forward secrecy An adversary who knows the long-term secret keys of parties should not be able to compute the session keys of past sessions between those two particular parties.

1.1 Key exchange security models

In order to analyze the security of key exchange protocols, a formal methodology is needed. Therefore, key exchange security models have been created. A security model is a formal security statement of certain security features. Generally, security models are designed to reflect real-world adversarial capabilities, addressing the known security features (mentioned earlier). It is natural to design security models with theoretical adversaries which have more capabilities than real-world adversaries, because that way it is possible to address more powerful attacks which may exist in the future. Following is the general structure of a security model.

• Definition of the algorithm: Inputs, outputs and abstract description of the algorithm.

• Adversary capabilities: How the adversary can interact with the system and which information the adversary is allowed to learn, usually in the form of queries. As a usual practice the adversary is made as strong as possible by giving more capabilities to the adversary.

• Security game: The way in which the adversary performs queries.

• Security goal: The requirement for the adversary to win the security game.

In a security model, there is a predefined list of queries that an adversary can perform (adversary capabilities). Those queries reveal information such as session keys, ephemeral keys and long-term secret keys. Even after performing the queries, within the constraints defined in the security model, if the adversary’s advantage of distinguishing the real session key from a random key chosen from the same distribution is negligible, the protocol is said to be secure in the particular security model. The session in which the adversary tries to distinguish the real session key from a random key is known as the target session.

The Bellare–Rogaway models (BR93 [4], BR95 [6]), the Canetti–Krawczyk (CK) model [8] and the extended Canetti–Krawczyk (eCK) model [17] are a few such security models, and protocol designers use them to analyze the security of key exchange protocols. Security features like implicit key authentication, key confirmation, known key security and UKS security are addressed in the models such as BR models, CK model and the $\mathrm {eCK}$ model.

Table 1 Security features of different security models

In the BR models and the CK model, the adversary is not allowed to learn the long-term secret key of the owner of the target session, before it expires. Therefore, those models are not capable of addressing the key compromise impersonation attacks, whereas the $\mathrm {eCK}$ model allows the adversary to learn the long-term secret key of the owner of the target session. Therefore the $\mathrm {eCK}$ model addresses the KCI attacks. Moreover, the BR models and the CK model do not allow the adversary to reveal the session states or ephemeral keys of the target session or its partner session. Therefore, those models are not capable of addressing the ephemeral key leakage attacks, whereas the eCK model allows the adversary to reveal both of the ephemeral keys of the target session, as long as the owner and the partner principals to the target session are not corrupted. Therefore the eCK model addresses the ephemeral key reveal attacks. In the CK model, after the target session has expired, the adversary is allowed to learn the long-term secret keys of the protocol participants of the target session, regardless of whether the adversary actively interfered with the target session, whereas the eCK model only allows the adversary to learn the long-term secret keys of both protocol participants of the target session when the adversary has not actively interfered with the target session. Therefore, the CK model addresses the perfect forward secrecy, while the eCK model only addresses the weak perfect forward secrecy. Table 1 summarizes the security features of above discussed security models.

Table 2 Basic characteristics of few $\mathrm {eCK}$-secure key exchange protocols

Likewise, the $\mathrm {eCK}$ model is clearly defined to capture most of the demanding security features of key exchange protocols and thus widely used as a strong security model to analyze the security of key exchange protocols. We explain the $\mathrm {eCK}$ model in detail in Sect. 3.

1.2 $\mathrm {eCK}$-secure key exchange protocols

The initial effort of constructing the $\mathrm {eCK}$-secure key exchange protocols is combining the long-term secret key and the ephemeral secret key using a random oracle function [5] to obtain a pseudo-ephemeral value. This trick is first introduced by LaMacchia et al. [17] in their protocol, named NAXOS, and now it is widely known as the NAXOS trick. A “pseudo”-ephemeral key $\widetilde{esk}$ is computed as the random oracle function of the long-term key lsk and the actual ephemeral key esk: $\widetilde{esk} \leftarrow H(esk, lsk)$. The value $\widetilde{esk}$ is never stored, and thus, in the eCK model the adversary must learn both esk and lsk in order to be able to compute $\widetilde{esk}$. Note however, that in the NAXOS protocol, the initiator must compute $\widetilde{esk} = H(esk, lsk)$ twice: once when sending its Diffie–Hellman ephemeral public key $g^{\widetilde{esk}}$ and once when computing the Diffie–Hellman shared secrets from the received values. This is to avoid storing a single value that, when compromised, can be used to compute the session key. There are some key exchange protocols created using the NAXOS trick [17, 21].

Recently, some researchers worked on constructing $\mathrm {eCK}$-secure key exchange protocols without NAXOS trick [2, 16, 18, 22]. The motivation for such research can be explained as follows: the $\mathrm {eCK}$ model addresses the leakage of the ephemeral secret key. It is unnatural to assume that the ephemeral secret key is leaked, while the exponent of the ephemeral public key (e.g., the pseudo- ephemeral value in the NAXOS protocol) remains safe, without leaking. Therefore, it seems that there is an unnatural and indirect assumption of a leakage-free exponentiation computation or leakage-free random source, in the $\mathrm {eCK}$-security proof of the NAXOS-style key exchange protocols. Therefore, eliminating the NAXOS trick and still preserving the $\mathrm {eCK}$ security would be more realistic. Moreover, the NAXOS trick is a random oracle-based technique. Favorable things on random oracle-based constructions are that, the schemes are efficient, proofs are clean and the random oracles can be replaced with suitable hash functions in the real- world implementations. On the other hand, random oracle proofs are considered as ideal-world proofs, rather than real-world proofs. Therefore, perhaps cryptographers tend to construct cryptographic schemes which are proven secure in the standard model.

Table 3 Cost analysis of few standard model $\mathrm {eCK}$-secure key exchange protocols

1.3 Our contribution

In this paper our aim is to present a generic $\mathrm {eCK}$-secure, NAXOS-free, standard model key exchange protocol, namely the protocol $\mathrm {P1}$. Thus, our generic protocol is a strongly secure and realistic framework for real-world instantiations. Our protocol is a Diffie–Hellman-style key exchange protocol, and we assume on the hardness of the decisional Diffie–Hellman ($\mathrm {DDH}$) problem. Moreover, our protocol uses an arbitrary $\mathrm {CCA2}$-secure public-key encryption scheme to encrypt Diffie–Hellman public ephemeral values and exchange them between the protocol principals. An arbitrary pseudo-random function is used to derive the secret session key using the ephemeral Diffie–Hellman shared key, long-term Diffie–Hellman shared key and the message flow. Since our protocol is a generic protocol, this can be instantiated with an arbitrary $\mathrm {CCA2}$ public-key encryption scheme and an arbitrary pseudo-random function. Therefore, it is possible to instantiate our protocol with more efficient $\mathrm {CCA2}$-secure public-key encryption schemes and pseudo-random functions in future and achieve better performance. In Table 2, we look at the basic characteristics of few $\mathrm {eCK}$-secure key exchange protocols in the literature, comparing with our new protocol. Table 2 shows that our protocol captures all of the desired features that we discussed here.

The protocol execution cost of our protocol is one encryption, one decryption, three exponentiations and two pseudo-random operations. Table 3 shows the protocol execution costs of the standard model protocols that mentioned in Table 2. The generic GC-KKN protocol is instantiated with a factoring-based key encapsulation mechanism as mentioned by Yang [22], and our protocol is instantiated with Cramer–Shoup public-key encryption scheme [9]. In Table 3, CR denotes collision-resistant hash functions, TCR denotes target collision-resistant hash functions, Exp denotes exponentiations, Multi-exp denotes multi-exponentiations, Pair denotes pairings, PRF denotes pseudo-random functions, and $\pi$-$\mathrm {PRF}$ denotes pseudo-random function with pairwise independent random source. Compared to other protocols mentioned in Table 3, Cramer–Shoup-based instantiation of our protocol needs relatively simple multi-exponentiations and additionally two pseudo-random functions.

To the best of our knowledge, this is the first paper on generic transformation of a $\mathrm {CCA2}$ -secure public-key encryption scheme to an $\mathrm {eCK}$ -secure key exchange protocol in the standard model.

2 Preliminaries

In this section we review the preliminaries that we use in this paper.

2.1 Pseudo-random functions

We now describe the security definition of pseudo-random functions according to Katz and Lindell [15].

Definition 1

(Pseudo-random functions) Let $F: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ be an efficient, length preserving, keyed function. F is a pseudo-random function if for all PPT adversaries $\mathcal {B}$, there is a negligible function $\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})$ in k such that:

$$\begin{aligned} \Big | \Pr [\mathcal {B}^{F(key,\cdot )}(1^k)=1] - \Pr [\mathcal {B}^{f_{\mathrm{rnd}}(\cdot )}(1^k)=1] \le \mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\Big |, \end{aligned}$$

where the first probability is taken over uniform choice of $key \in \{0,1\}^k$ and the randomness of $\mathcal {B}$, and the second probability is taken over uniform choice of $f_{\mathrm{rnd}}$ and randomness of $\mathcal {B}$, and $\mathcal {B}$ is not given a key key.

2.2 Indistinguishability against adaptive chosen ciphertext attacks $(\mathrm {CCA2})$

A public-key encryption scheme consists of three algorithms as follows:

• $\mathrm {KG}$: This is a PPT algorithm that takes as input the security parameter and outputs a public/secret key pair (pk, sk). This also specifies the message (plaintext) space $\mathcal {M}$ and the ciphertext space $\mathcal {C}$.

• $\mathrm {Enc}$: This is a PPT algorithm that takes as input $m \in \mathcal {M}$ and a public-key pk, and outputs a ciphertext $c \in \mathcal {C}$.

• $\mathrm {Dec}$: This is a deterministic algorithm that takes as input a ciphertext $c \in \mathcal {C}$ and a secret key sk, and outputs either a message $m \in \mathcal {M}$ or the error symbol $\bot$.

A public-key encryption scheme must satisfy the correctness property: for all valid key pairs (pk, sk), if $c = \mathrm {Enc}_{pk}(m)$ for any $m\in \mathcal {M}$, then $\mathrm {Dec}_{sk}(c)=m$.

We now review a strong security notion for public-key encryption schemes: indistinguishability against adaptive chosen ciphertext attacks ($\mathrm {CCA2}$), referring Bellare et al. [3].

Definition 2

(Indistinguishability against adaptive chosen ciphertext attacks $(\mathrm {CCA2})$) Let $\mathcal {A}=(\mathcal {A}_1,\mathcal {A}_2)$ be any PPT adversary in the security parameter k, against a public-key encryption scheme $\mathrm {PKE}=(\mathrm {KG},\mathrm {Enc},\mathrm {Dec})$. The $\mathrm {CCA2}$ security experiment for the public-key encryption scheme $\mathrm {PKE}$, $\mathrm {Exp}^{\mathrm {CCA2}}_{\mathrm {PKE},\mathcal {A}}(1^k)$, is defined as follows:

• 1. $(pk,sk)\mathop {\leftarrow }\limits ^{\$}\mathrm {KG}(1^k)$

• 2. $(m_0,m_1,state)\leftarrow \mathcal {A}_1^{\mathrm {Dec}(sk,c)}(pk)$ such that $|m_0|=|m_1|$

• 3. $b\mathop {\leftarrow }\limits ^{\$} \{0,1\}$

• 4. $c^*\leftarrow \mathrm {Enc}(pk,m_b)$

• 5. $b'\leftarrow \mathcal {A}_2^{\mathrm {Dec}(sk,c)_{c^* \ne c}}(pk,c^*,state)$

• 6. $\mathcal {A}$ wins if $b'=b$

Decryption Oracle

• $\mathrm {Dec}(sk,c)\rightarrow m$ where m is the corresponding plaintext c.

• returns m to $\mathcal {A}$

The public-key encryption scheme $\mathrm {PKE}$ is $\mathrm {CCA2}$-secure, if for every PPT adversary $\mathcal {A}$ the advantage of winning the security experiment $\mathrm {Exp}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {A})$: $\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {A})$, is negligible in the security parameter k.

2.3 Diffie–Hellman assumptions

We now describe two Diffie–Hellman assumptions which form the basis of security for many cryptographic primitives. Let k be the security parameter, $\mathcal {G}$ be a group generation algorithm and $(\mathbb {G},q,g) \leftarrow \mathcal {G}(1^k)$, where $\mathbb {G}$ is a cyclic group of prime order q and g is an arbitrary generator of $\mathbb {G}$.

Definition 3

(Computational Diffie–Hellman ($\mathrm {CDH}$) assumption) We say that computational Diffie–Hellman assumption holds in $\mathbb {G}$ if for all PPT algorithms $\mathcal {A}$, the probability of solving the $\mathrm {CDH}$ problem in $\mathbb {G}$ given as:

$$\begin{aligned} \text {Pr}^{\mathrm {CDH}}_{g,q}(\mathcal {A})=\Pr \big (\mathcal {A}(\mathbb {G},g,q,g^a,g^b)=g^{ab}\big ) \end{aligned}$$

is negligible for a given security parameter k.

Definition 4

(Decisional Diffie–Hellman ($\mathrm {DDH}$) assumption) Consider the following two distributions: $\mathcal {DH}_{\mathbb {G}}=\{(g,g^a,g^b,g^{ab}); a,b\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q\}$ and $\mathcal {R}_{\mathbb {G}}=\{(g,g^a,g^b,g^{c}); a,b,c\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q\}$. It is said that $\mathrm {DDH}$ assumption holds in $\mathbb {G}$ if for all PPT algorithms $\mathcal {A}$, the advantage in distinguishing the two distributions $\mathcal {DH}$ and $\mathcal {R}$ given as:

$$\begin{aligned} \mathrm {Adv}^{\mathrm {DDH}}_{g,q}(\mathcal {A})=\Big |\Pr [\mathcal {A}(\mathcal {DH}_{\mathbb {G}})=1]-\Pr [\mathcal {A}(\mathcal {R}_{\mathbb {G}})=1] \Big | \end{aligned}$$

is negligible for a given security parameter k.

3 Extended Canetti–Krawczyk model ($\mathrm {eCK}$)

The motivation of LaMacchia et al. [17] in designing the $\mathrm {eCK}$ model was that an adversary should have to compromise both the long-term and ephemeral secret keys of a party in order to recover the session key.

Parties and long-term keys

Let $\mathcal {U}=\{U_1,\dots ,U_{N_P}\}$ be a set of $N_P$ parties. Each party $U_i$ where $i \in [1,N_P]$ has a pair of long-term public and secret keys, $(pk_{U_i}, sk_{U_i})$. Each party $U_i$ owns at most $N_S$ number of protocol sessions.

Sessions

Each party may run multiple instances of the protocol concurrently or sequentially; we use the term principal to refer a party involved in a protocol instance and the term session to identify a protocol instance at a principal. The notation $\varPi _{U,V}^{s}$ represents the sth session at the owner principal U, with intended partner principal V. The principal which sends the first protocol message of a session is the initiator of the session, and the principal which responds to the first protocol message is the responder of the session. A session $\varPi _{U,V}^{s}$ enters an accepted state when it computes a session key. Note that a session may terminate without ever entering into the accepted state. The information of whether a session has terminated with or without acceptance is public.

Partnering Legitimate execution of a key exchange protocol between two principals U and V makes two partnering sessions owned by U and V, respectively. Two sessions $\varPi _{U,V}^{s}$ and $\varPi _{U',V'}^{s'}$ are said to be partners if all of the following hold:

• 1. both $\varPi _{U,V}^{s}$ and $\varPi _{U',V'}^{s'}$ have computed session keys;

• 2. messages sent from $\varPi _{U,V}^{s}$ and messages received by $\varPi _{U',V'}^{s'}$ are identical;

• 3. messages sent from $\varPi _{U',V'}^{s'}$ and messages received by $\varPi _{U,V}^{s}$ are identical;

• 4. $U'=V$ and $V'=U$;

• 5. Exactly one of U and V is the initiator, and the other is the responder.

The protocol is said to be correct if two partner sessions compute identical session keys.

Adversarial powers The adversary $\mathcal {A}$ is a probabilistic polynomial time algorithm in the security parameter k that has the control over the whole network. $\mathcal {A}$ interacts with set of sessions which represent protocol instances. $\mathcal {A}$ can adaptively ask following queries.

• Send (U, V, s, m) query—This query allows $\mathcal {A}$ to run the protocol. It sends the message m to the session $\prod _{U,V}^{s}$ as coming from the session $\prod _{V,U}^{s'}$. $\prod _{U,V}^{s}$ will return to $\mathcal {A}$ the next message according to the protocol conversation so far or decision on whether to accept or reject the session. $\mathcal {A}$ can also use this query to initiate a new protocol instance with blank m. This query captures capabilities of active adversary, who can initiate sessions and modify or delay protocol messages.

• SessionKeyReveal (U, V, s) query—If a session $\prod _{U,V}^{s}$ has accepted and holds a session key, $\mathcal {A}$ gets the session key of $\prod _{U,V}^{s}$. A session can only accept a session key once. This query captures the known key attacks.

• EphemeralKeyReveal (U, V, s) query—Gives all the ephemeral keys (per session randomness) of the session $\prod _{U,V}^{s}$ to $\mathcal {A}$.

• Corrupt (U) query—$\mathcal {A}$ gets all the long-term secrets of the principal U. But this query does not reveal any session keys to $\mathcal {A}$. This query captures the key compromise impersonation (KCI) attacks, unknown key share (UKS) attacks and forward secrecy.

• Test (U, s) query—Once a session $\prod _{U,V}^{s}$ has accepted and holds a session key, $\mathcal {A}$ can attempt to distinguish it from a random key. When $\mathcal {A}$ asks the Test query, the session $\prod _{U,V}^{s}$ first chooses a random bit $b \in \{0,1\}$ and if $b=1$, the actual session key is returned to $\mathcal {A}$; otherwise, a random session key is chosen uniformly at random from the same session-key distribution and is returned to $\mathcal {A}$. This query is only allowed to be asked once.

Freshness A session $\prod _{U,V}^{s}$ is said to be fresh if and only if all of the following hold:

• 1. The session $\prod _{U,V}^{s}$ and its partner (if it exists), $\prod _{V,U}^{s'}$ have not been asked the Session- Key reveal query.

• 2. If partner $\prod _{V,U}^{s'}$ exists none of the following combinations have been asked:

  • (a) Corrupt(U) and EphemeralKeyReveal(U, V, s)

  • (b) Corrupt(V) and EphemeralKeyReveal $(V,U,s')$

• 3. If partner $\prod _{V,U}^{s'}$ does not exist, none of the following combinations have been asked

  • (a) Corrupt(V)

  • (b) Corrupt(U) and EphemeralKeyReveal(U, V, s)

Security game

• Stage 0: The challenger generates the keys by using the security parameter k.

• Stage 1: $\mathcal {A}$ is executed and may ask any of Send, SessionKeyReveal, EphemeralKeyReveal, Corrupt queries to any session at will.

• Stage 2: At some point $\mathcal {A}$ chooses a fresh session and asks the Test query.

• Stage 3: $\mathcal {A}$ continue asking Send, SessionKeyReveal, EphemeralKeyReveal,Corrupt queries. The only condition is that $\mathcal {A}$ cannot violate the freshness of the test session.

• Stage 4: At some point $\mathcal {A}$ outputs the bit $b' \in \{0,1\}$ which is its guess of the value b on the test session. $\mathcal {A}$ wins if $b'=b$.

Definition of security Let $\mathrm {Succ}_{\mathcal {A}}$ be the event that the adversary $\mathcal {A}$ wins the $\mathrm {eCK}$ game.

Definition 5

A protocol ($\pi$) is said to be secure in the eCK model if there is no PPT adversary $\mathcal {A}$ who can win the eCK game with non-negligible advantage in the security parameter k. The advantage of an adversary $\mathcal {A}$ is defined as:

$$\begin{aligned} {\mathrm {Adv}}^{\text {eCK}}_{\pi }(\mathcal {A})=|2\text {Pr}(\text {Succ}_\mathcal {A}) -1| . \end{aligned}$$

4 Generic $\mathrm {eCK}$-secure key exchange in the standard model

In this work we construct a generic $\mathrm {eCK}$-secure key exchange protocol, in the standard model, using an arbitrary $\mathrm {CCA2}$-secure public-key encryption scheme and an arbitrary pseudo-random function. We prove the security of our protocol in the standard model, assuming the hardness of the $\mathrm {DDH}$ problem.

4.1 Construction of the generic protocol $\mathrm {P1}$

The protocol $\mathrm {P1}$ shown in Table 4 is a Diffie–Hellman-style [10] key agreement protocol. Let k be the security parameter and group $\mathbb {G}$ be generated using a group generation algorithm which takes k as an input, where $\mathbb {G}$ be a group of prime order q with generator g. We use an arbitrary $\mathrm {CCA2}$-secure public-key encryption scheme $\mathrm {PKE}= (\mathrm {KG},\mathrm {Enc},\mathrm {Dec})$ to encrypt protocol messages. Given the security parameter k, $\mathrm {KG}$ computes a pair of secret/public keys. Let $sk_{\mathrm{Alice}}$, $pk_{\mathrm{Alice}}$ be the secret/public encryption keys of Alice and $sk_\mathrm{Bob}$, $pk_\mathrm{Bob}$ be the secret/public encryption keys of Bob. Let a, A and b, B are the Diffie–Hellman long-term secret and public keys of Alice and Bob, respectively, while x, X and y, Y are the Diffie–Hellman ephemeral secret and public keys of Alice and Bob, respectively. After exchanging the protocol messages ($\bar{X}\mathop {\leftarrow }\limits ^{\$}\mathrm {Enc}_{pk_\mathrm{Bob}}(X)$ and $\bar{Y}\mathop {\leftarrow }\limits ^{\$}\mathrm {Enc}_{pk_{\mathrm{Alice}}}(Y)$), both principals decrypt the incoming messages and compute a Diffie–Hellman-style shared secrets ($Y^x$, $B^a$ and $X^y$, $A^b$) and then compute the session key using a pseudo-random function $\mathrm {PRF}$.

Table 4 Protocol $\mathrm {P1}$

4.2 Security analysis of the protocol $\mathrm {P1}$

Theorem 1

If $\mathbb {G}$ is a group of a prime order q and a generator g, where the Diffie–Hellman $(\mathrm {DDH})$ assumption holds, the underlying public-key encryption scheme $\mathrm {PKE}$ is $\mathrm {CCA2}$-secure and $\mathrm {PRF}$ is a pseudo-random function, then the protocol $\mathrm {P1}$ is secure in the $\mathrm {eCK}$ model.

Let $\mathcal {U}=\{U_1,\dots ,U_{N_P}\}$ be a set of $N_P$ parties. Each party $U_i$ owns at most $N_s$ number of protocol sessions. Let $\mathcal {A}$ be any adversary against the eck challenger of the protocol $\mathrm {P1}$. Then, the advantage of $\mathcal {A}$ against the $\mathrm {eCK}$ security challenge of the protocol $\mathrm {P1}$, $\mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}$ is:

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}{(\mathcal {A})} \le N_P^2 N_s^2 \max \Big (\big (\mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C})+\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\big ),\\\big (\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})+\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {D})\big )\Big ) . \end{aligned}$$

where $\mathcal {C}$ is the algorithm against a $\mathrm {DDH}$ challenger, $\mathcal {B}$ is the algorithm against the underlying pseudo-random function $\mathrm {PRF}$ and $\mathcal {D}$ is the algorithm against the $\mathrm {CCA2}$ challenger of the underlying public-key encryption scheme $\mathrm {PKE}$.

Proof

We split the proof of Theorem 1 into two main cases: when the partner to the test session exists and when it does not. $\square$

• 1. A partner to the test session exists.

  • (a) Adversary corrupts both the owner and the partner principals to the test session—Case $\mathbf {1a}$

  • (b) Adversary corrupts neither the owner nor the partner principal to the test session—Case $\mathbf {1b}$

  • (c) Adversary corrupts the owner to the test session, but does not corrupt the partner to the test session—Case $\mathbf {1c}$

  • (d) Adversary corrupts the partner to the test session, but does not corrupt the owner to the test session—Case $\mathbf {1d}$

• 2. A partner to the test session does not exist: the adversary is not allowed to corrupt the peer to the target session.

  • (a) Adversary corrupts the owner to the test session—Case $\mathbf {2a}$

  • (b) Adversary does not corrupt the owner to the test session- Case $\mathbf {2b}$

Case 1a

Adversary corrupts both the owner and partner principals to the test session.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1}, \text {Case 1a}}(\mathcal {A}). \end{aligned}$$

(1)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random numbers $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the partner to the target session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$ or partner to the session is not $\varPi ^{t^*}_{V^*,U^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, the Game 2 is identical to the Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(2)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses $z\mathop {\leftarrow }\limits ^{\$} \mathbb {Z}^{*_{q}}$ and computes $K\leftarrow \mathrm {PRF}(g^z,\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y})$. When the adversary asks the $\mathtt {Test}(U^*,V^*,s^*)$ query, Game 3 challenger will answer with K ($\cdot$ is used as a placeholder since either $U^*$ or $V^*$ can be put there depending on the initiator and responder roles).

Note 1

Let U, V be the two long-term Diffie–Hellman public keys of the protocol principals $U^*,V^*$, respectively, such that $U=g^u, V=g^v$ and $\mathrm {CDH}(U,V)=g^{uv}$.

We construct an algorithm $\mathcal {C}$ against a $\mathrm {DDH}$ challenger, using the adversary $\mathcal {A}$ as a subroutine. $\mathcal {C}$ sets all the long-term secret/public key pairs (Diffie–Hellman and encryption key pairs) to all protocol principals. The algorithm $\mathcal {C}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$ such that $\mathcal {A}$ is interacting with either Game 2 or Game 3. The $\mathrm {DDH}$ challenger sends values $(g^{x}, g^{y}, g^z)$ such that either $z={xy}$ or $z \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}_q^{*}$, as the inputs to the algorithm $\mathcal {C}$. Algorithm $\mathcal {C}$ simulates answers to the adversarial queries as follows:

• $\mathtt {Send}(U,V,s,m)$ query:

  • If $U^*$ is the initiator, $\mathcal {C}$ sends the ciphertext $\bar{X}\mathop {\leftarrow }\limits ^{\$}(pk_{V^*},X)$ to $\mathcal {A}$ as the first message of the test session. Upon receiving the second protocol message ($\bar{Y}\mathop {\leftarrow }\limits ^{\$}(pk_{U^*},Y)$) from $V^*$ to $U^*$, $\mathcal {C}$ computes the session key $K\leftarrow \mathrm {PRF}(g^z,U^*\Vert \bar{X}\Vert V^*\Vert \bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),U^*\Vert \bar{X}\Vert V^*\Vert \bar{Y})$.

  • If $U^*$ is the responder, upon receiving the first protocol message ($\bar{X}\mathop {\leftarrow }\limits ^{\$}(pk_{U^*},X)$) from $V^*$ to $U^*$, $\mathcal {C}$ sends $\bar{Y}\mathop {\leftarrow }\limits ^{\$}(pk_{V^*},Y)$ to $\mathcal {A}$ as the second protocol message of the test session and computes the session key $K\leftarrow \mathrm {PRF}(g^z,V^*\Vert \bar{X}\Vert U^*\Vert \bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),V^*\Vert \bar{X}\Vert U^*\Vert \bar{Y})$.

Note 2

For clarity we consider $\bar{X}\mathop {\leftarrow }\limits ^{\$}(pk_{\cdot },X)$ as the first protocol message and $\bar{Y}\mathop {\leftarrow }\limits ^{\$}(pk_{\cdot },Y)$ as the second protocol message, in the target session.

• For all the other cases of $\mathtt {Send}$ queries, $\mathcal {C}$ can decrypt incoming protocol messages and execute the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or the partner of the target session. $\mathcal {C}$ can compute all the other session keys by executing the protocol normally.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $U=U^*,V=V^*,s=s^*$ and $U=V^*,V=U^*,s=t^*$ are prohibited since the adversary is allowed to corrupt both the owner and the partner to the target session. For all other $\mathtt {EphemeralKeyReveal}$ queries $\mathcal {C}$ can answer correctly, because $\mathcal {C}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: Algorithm $\mathcal {C}$ can answer all the $\mathtt {Corrupt}$ queries, since $\mathcal {C}$ has all the long-term keys.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If $\mathcal {C}$’s input is a Diffie–Hellman triple, simulation constructed by $\mathcal {C}$ is identical to Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {C}$ can answer the $\mathrm {DDH}$ challenge. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C}). \end{aligned}$$

(3)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key, or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The following describes $\mathcal {B}$?s procedure of answering queries.

• $\mathtt {Send}(U,V,s,m)$ query:

  • If $U^*$ is the initiator, upon receiving the second protocol message ($\bar{Y}$) computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(U^*||\bar{X}||V^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),U^*||\bar{X}||V^*||\bar{Y})$.

  • If $U^*$ is the responder, upon receiving the first protocol message ($\bar{X}$) computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(V^*||\bar{X}||U^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),V^*||\bar{X}||U^*||\bar{Y})$.

  • For all the other cases of $\mathtt {Send}$ queries, $\mathcal {B}$ can execute the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or its partner. $\mathcal {B}$ can compute all the session keys by executing the protocol normally.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $U=U^*,V=V^*,s=s^*)$ and $U=V^*,V=U^*,s=t^*$ are prohibited since the adversary is allowed to corrupt both the owner and the partner to the target session. For all other $\mathtt {EphemeralKeyReveal}$ queries $\mathcal {B}$ can answer correctly, because $\mathcal {B}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: $\mathcal {B}$ can answer all other $\mathtt {Corrupt}$ queries, since $\mathcal {B}$ has all the long-term secret keys.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B}). \end{aligned}$$

(4)

Semantic security of the session key in Game 4: Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(5)

Using Eqs. (1)–(5) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1a}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C})+\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\Big ). \end{aligned}$$

Case 1b

Adversary corrupts neither the owner nor the partner principals to the test session.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1}, \text {Case 1b}}(\mathcal {A}). \end{aligned}$$

(6)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random numbers $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the partner to the target session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$ or partner to the session is not $\varPi ^{t^*}_{V^*,U^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, the Game 2 is identical to the Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(7)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses $c\mathop {\leftarrow }\limits ^{\$} \mathbb {Z}^*_{q}$ and computes $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y}) \oplus \mathrm {PRF}(g^c,\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y})$. When the adversary asks the $\mathtt {Test}(U^*,V^*,s^*)$ query, Game 3 challenger will answer with K.

Note 3

Let X, Y be the two ephemeral Diffie–Hellman public keys (unencrypted) of the protocol principals in a session, such that $X=g^x, Y=g^y$ and $\mathrm {CDH}(X,Y)=g^{xy}$.

We construct an algorithm $\mathcal {C}$ against a $\mathrm {DDH}$ challenger, using the adversary $\mathcal {A}$ as a subroutine. The $\mathrm {DDH}$ challenger sends values $(g^{a}, g^{b}, g^c)$ such that either $c={ab}$ or $c \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}_q^{*}$, as the inputs to the algorithm $\mathcal {C}$. $\mathcal {C}$ sets $U\leftarrow g^a$ as the long-term Diffie–Hellman public key of $U^*$, and $V\leftarrow g^b$ as the long-term Diffie–Hellman public key of $V^*$. Moreover, $\mathcal {C}$ sets all the other long-term Diffie–Hellman secret/public key pairs and all the encryption key pairs of protocol principals. The algorithm $\mathcal {C}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$ such that $\mathcal {A}$ is interacting with either Game 2 or Game 3. Algorithm $\mathcal {C}$ simulates answers to the adversarial queries as follows:

• $\mathtt {Send}(U,V,s,m)$ query:

  • If $U^*$ is the initiator, $\mathcal {C}$ can start the protocol normally. Upon receiving the second protocol message from $V^*$ to $U^*$, $\mathcal {C}$ computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),U^*\Vert \bar{X}\Vert V^*\Vert \bar{Y}) \oplus \mathrm {PRF}(g^c,U^*\Vert \bar{X}\Vert V^*\Vert \bar{Y})$ (consider X is from the initiator and Y is from the responder, and $\bar{X}$ and $\bar{Y}$ are the encrypted X and Y, respectively, which are computed in normal protocol run).

  • If $U^*$ is the responder, upon receiving the first protocol message from $V^*$ to $U^*$, $\mathcal {C}$ executes the protocol normally, sends the second protocol message of the test session and computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),V^*\Vert \bar{X}\Vert U^*\Vert \bar{Y}) \oplus \mathrm {PRF}(g^c,V^*\Vert \bar{X}\Vert U^*\Vert \bar{Y})$.

  • For all the cases of $\mathtt {Send}$ queries, $\mathcal {C}$ can decrypt incoming protocol messages and execute the protocol normally. In the places where both $U^*$ and $V^*$ are involved, $\mathcal {C}$ uses $g^c$ in key derivation.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or the partner of the target session. $\mathcal {C}$ can compute all the other session keys by executing the protocol normally. In the places where both $U^*$ and $V^*$ are involved, $\mathcal {C}$ uses $g^c$ in key derivation.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: Algorithm $\mathcal {C}$ can answer all the other $\mathtt {EphemeralKeyReveal}$ queries, since $\mathcal {C}$ has all the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: $\mathtt {Corrupt}(U^*)$ and $\mathtt {Corrupt}(V^*)$ are prohibited since the adversary is allowed to reveal the ephemeral keys of the test session and its partner. Algorithm $\mathcal {C}$ can answer all the other $\mathtt {Corrupt}$ queries, since $\mathcal {C}$ has all the long-term keys.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If $\mathcal {C}$’s input is a Diffie–Hellman triple, simulation constructed by $\mathcal {C}$ is identical to Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {C}$ can answer the $\mathrm {DDH}$ challenge. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C}). \end{aligned}$$

(8)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The following describes $\mathcal {B}$?s procedure of answering queries.

• $\mathtt {Send}(U,V,s,m)$ query:

  • If $U^*$ is the initiator, upon receiving the second protocol message computes the session key $K \leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),U^*||\bar{X}||V^*||\bar{Y}) \oplus \text {Oracle}^{\mathrm {PRF}}(U^*||\bar{X}||V^*||\bar{Y})$.

  • If $U^*$ is the responder, upon receiving the first protocol message computes the session key $K \leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),V^*||\bar{X}||U^*||\bar{Y}) \oplus \text {Oracle}^{\mathrm {PRF}}(V^*||\bar{X}||U^*||\bar{Y})$.

  • When both $U^*$ and $V^*$ involve in a session query the Oracle$^{\mathrm {PRF}}$ to compute the session key upon receiving protocol messages.

  • For all the other cases of $\mathtt {Send}$ queries, $\mathcal {B}$ can execute the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or its partner. $\mathcal {B}$ can compute all the session keys as explained under the $\mathtt {Send}$ query description.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {B}$ can answer all $\mathtt {EphemeralKeyReveal}$ queries correctly, because $\mathcal {C}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: $\mathtt {Corrupt}(U^*)$ and $\mathtt {Corrupt}(V^*)$ are prohibited since the adversary is allowed to reveal the ephemeral keys of the test session and its partner. Algorithm $\mathcal {C}$ can answer all the other $\mathtt {Corrupt}$ queries, since $\mathcal {C}$ has all the long-term keys.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B}). \end{aligned}$$

(9)

Semantic security of the session key in Game 4: Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(10)

Using Eqs. (6)–(10) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1b}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C})+\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\Big ). \end{aligned}$$

Case 1c

Adversary corrupts the owner to the test session, but does not corrupt the partner.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1c}}(\mathcal {A}). \end{aligned}$$

(11)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random numbers $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the partner to the target session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$ or partner to the session is not $\varPi ^{t^*}_{V^*,U^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, Game 2 is identical to Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(12)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses C from the ciphertext space as encryption of the public ephemeral value X of the session $\varPi ^{s^*}_{U^*,V^*}$ and sends it to the session $\varPi ^{t^*}_{V^*,U^*}$ as having come from the session $\varPi ^{s^*}_{U^*,V^*}$.

We introduce an algorithm $\mathcal {D}$ which is constructed using the adversary $\mathcal {A}$. If $\mathcal {A}$ can distinguish the difference between Game 2 and Game 3, then $\mathcal {D}$ can be used against the $\mathrm {CCA2}$ challenger of underlying public-key cryptosystem, $\mathrm {PKE}$. The algorithm $\mathcal {D}$ uses the public key of the $\mathrm {CCA2}$ challenger as the public key of the protocol principal $V^*$ and generates all other public/secret key pairs (Diffie–Hellman and encryption keys) for protocol principals. $\mathcal {D}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$, such that it is interacting with either Game 2 or Game 3. $\mathcal {D}$ picks two random strings, $X_0, X_1 \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}^*_q$ and passes them to the $\mathrm {CCA2}$ challenger. From the $\mathrm {CCA2}$ challenger, $\mathcal {D}$ receives a challenge ciphertext C such that $C \mathop {\leftarrow }\limits ^{\$}(pk_{V^*}, X_{\theta })$ where $X_{\theta }= X_0$ or $X_{\theta } = X_1$. $\mathcal {D}$ uses $X_1$ as the decryption of C when answering queries. The following describes the procedure of answering queries:

• $\mathtt {Send}(U,V,s,m)$ query:

  • $U=U^*,V=V^*,s=s^*$:

    • If $U^*$ is the initiator, $\mathcal {D}$ sends the ciphertext C to $\mathcal {A}$ as the first message of the test session. Upon receiving the second protocol message computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X_1,Y ),U^* \Vert C \Vert V^* \Vert \bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U, V),U^* \Vert C \Vert V^* \Vert \bar{Y})$ (consider Y is from the responder, and $\bar{Y}$ is the encrypted Y).

    • If $U^*$ is the responder, upon receiving the first protocol message sends C to $\mathcal {A}$ and computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}( X_1,Y),V^*\Vert \bar{Y}\Vert U^*\Vert C) \oplus \mathrm {PRF}(\mathrm {CDH}(U, V),V^* \Vert \bar{Y}\Vert U^*\Vert C )$ (consider Y is from the initiator, and $\bar{Y}$ is the encrypted Y).

  • $U=U^*,V=V^*,s \ne s^*$: Executes the protocol normally.

  • $U=U^*,V \ne V^*$: Executes the protocol normally.

  • $U=V^*$:

    • If this is the initiator and it is the first message, then it executes the protocol normally.

    • If this is the initiator and the second protocol message, or the responder:

      • If C has come as the incoming message uses $X_1$ as the decryption of the incoming message.

      • Else uses the decryption oracle to decrypt incoming messages.

  • $U,V \ne U^*$ or $V^*$: Executes the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or the partner of the target session. $\mathcal {D}$ can compute all the session keys by executing the protocol.

  • For sessions involving the principal $V^*$, and the incoming message to $V^*$ is the same message which has come to $V^*$ in the target session, uses $X_1$ as the decryption.

  • For other sessions involving the principal $V^*$, $\mathcal {D}$ can decrypt the incoming messages to $V^*$ by using the decryption oracle.

  • Otherwise, $\mathcal {D}$ can decrypt all the other incoming messages to protocol principals by its own.

  Then compute the session key using the $\mathrm {PRF}$.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {D}$ can answer all $\mathtt {EphemeralKeyReveal}$ queries allowed in the freshness condition correctly, because $\mathcal {D}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: Except for $\mathtt {Corrupt}(V^*)$, algorithm $\mathcal {D}$ can answer all other $\mathtt {Corrupt}$ queries. In this case we consider the situation in which the adversary is not allowed to corrupt the partner principal of the target session, so in fact, $\mathcal {D}$ can answer all legitimate $\mathtt {Corrupt}$ queries.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the value C is the encryption of the value $X_1$, the simulation constructed by $\mathcal {D}$ is identical to the Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {D}$ can answer the $\mathrm {CCA2}$ challenge successfully. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PKE}}^{\mathrm {CCA2}}(\mathcal {D}). \end{aligned}$$

(13)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The following describes $\mathcal {B}$’s procedure of answering queries.

• $\mathtt {Send}(U,V,s,m)$ query:

  • $U=U^*,V=V^*,s=s^*$:

    • If $U^*$ is the initiator, upon receiving the second protocol message computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(U^*||\bar{X}||V^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),U^*||\bar{X}||V^*||\bar{Y})$ (consider X is from the initiator and Y is from the responder, and $\bar{X}$ and $\bar{Y}$ are the encrypted X and Y, respectively, which are computed in normal protocol run).

    • If $U^*$ is the responder, upon receiving the first protocol message computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(V^*||\bar{X}||U^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),V^*||\bar{X}||U^*||\bar{Y})$.

  • $U=U^*,V=V^*,s \ne s^*$: Executes the protocol normally.

  • $U=U^*,V \ne V^*$: Executes the protocol normally.

  • $U=V^*$:

    • If this is the initiator and it is the first message, then it executes the protocol normally.

    • If this is the initiator and the second protocol message, or the responder:

      • If the same message that came to $V^*$ in the test session has come as the incoming message computes the session key using the Oracle$^{\mathrm {PRF}}$.

      • Otherwise, executes the protocol normally.

  • $U,V \ne U^*$ or $V^*$: Executes the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or its partner. $\mathcal {B}$ can compute all the session keys by executing the protocol.

  • For sessions involving the principal $V^*$, and the incoming message to $V^*$ is the same message which has come to $V^*$ in the target session, $\mathcal {B}$ uses $\text {Oracle}^{\mathrm {PRF}}$ to compute the session key.

  • For all other sessions, $\mathcal {B}$ computes the session key by using the $\mathrm {PRF}$.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {B}$ can answer all $\mathtt {EphemeralKeyReveal}$ queries, which are allowed by the freshness condition, because $\mathcal {B}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: Except for $V^*$, algorithm $\mathcal {B}$ can answer all other $\mathtt {Corrupt}$ queries. In this case we consider the situation in which the adversary is not allowed to corrupt the partner principal of the target session, so in fact, $\mathcal {B}$ can answer all legitimate $\mathtt {Corrupt}$ queries.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\text {PRF}}(\mathcal {B}). \end{aligned}$$

(14)

Semantic security of the session key in Game 4: Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(15)

Using Eqs. (11)–(15) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1c}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})+\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {D})\Big ). \end{aligned}$$

Case 1d

Adversary corrupts the partner to the test session, but does not corrupt the owner.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1d}}(\mathcal {A}). \end{aligned}$$

(16)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random numbers $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the partner to the target session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$ or partner to the session is not $\varPi ^{t^*}_{V^*,U^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, Game 2 is identical to Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(17)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses C from the ciphertext space as encryption of the public ephemeral value X of the session $\varPi ^{s^*}_{U^*,V^*}$, and sends it to the session $\varPi ^{s^*}_{U^*,V^*}$ as having come from the session $\varPi ^{t^*}_{V^*,U^*}$.

We introduce an algorithm $\mathcal {D}$ which is constructed using the adversary $\mathcal {A}$. If $\mathcal {A}$ can distinguish the difference between Game 2 and Game 3, then $\mathcal {D}$ can be used against the $\mathrm {CCA2}$ challenger of underlying public-key cryptosystem, $\mathrm {PKE}$. The algorithm $\mathcal {D}$ uses the public key of the $\mathrm {CCA2}$ challenger as the public key of the protocol principal $U^*$ and generates all other public/secret key pairs (Diffie–Hellman and encryption keys) for protocol principals. $\mathcal {D}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$, such that it is interacting with either Game 2 or Game 3. $\mathcal {D}$ picks two random strings, $X_0, X_1 \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}^*_q$ and passes them to the $\mathrm {CCA2}$ challenger. From the $\mathrm {CCA2}$ challenger, $\mathcal {D}$ receives a challenge ciphertext C such that $C \mathop {\leftarrow }\limits ^{\$}(pk_{V^*}, X_{\theta })$ where $X_{\theta }= X_0$ or $X_{\theta } = X_1$. $\mathcal {D}$ uses $X_1$ as the decryption of C when answering queries. The following describes the procedure of answering queries:

• $\mathtt {Send}(U,V,s,m)$ query:

  • $U=V^*,V=U^*,s=t^*$:

    • If $V^*$ is the initiator, $\mathcal {D}$ sends the ciphertext C to $\mathcal {A}$ as the first message of the test session. Upon receiving the second protocol message computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X_1,Y),V^* \Vert C \Vert U^* \Vert \bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U, V),V^* \Vert C \Vert U^* \Vert \bar{Y})$ (consider Y is from the responder, and $\bar{Y}$ is the encrypted Y).

    • If $V^*$ is the responder, upon receiving the first protocol message sends C to $\mathcal {A}$ and computes the session key $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X_1,Y),U^*\Vert \bar{Y}\Vert V^*\Vert C) \oplus \mathrm {PRF}(\mathrm {CDH}(U, V),U^* \Vert \bar{Y}\Vert V^*\Vert C)$ (consider Y is from the initiator, and $\bar{Y}$ is the encrypted Y).

  • $U=V^*,V=U^*,s \ne t^*$: Executes the protocol normally.

  • $U=V^*,V \ne U^*$: Executes the protocol normally.

  • $U=U^*$:

    • If this is the initiator and it is the first message, then executes the protocol normally.

    • If this is the initiator and the second protocol message, or the responder:

      • If C has come as the incoming message uses $X_1$ as the decryption of the incoming message.

      • Else uses the decryption oracle to decrypt incoming messages.

  • $U,V \ne U^*$ or $V^*$: Executes the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or the partner of the target session. $\mathcal {D}$ can compute all the session keys by executing the protocol.

  • For sessions involving the principal $U^*$, and the incoming message to $U^*$ is the same message which has come to $U^*$ in the target session, uses $X_1$ as the decryption.

  • For other sessions involving the principal $U^*$, $\mathcal {D}$ can decrypt the incoming messages to $U^*$ by using the decryption oracle.

  • Otherwise, $\mathcal {D}$ can decrypt all the other incoming messages to protocol principals by its own.

  Then compute the session key using the $\mathrm {PRF}$.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {D}$ can answer all $\mathtt {EphemeralKeyReveal}$ queries allowed in the freshness condition correctly, because $\mathcal {D}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: Except for $\mathtt {Corrupt}(U^*)$, algorithm $\mathcal {D}$ can answer all other $\mathtt {Corrupt}$ queries. In this case we consider the situation in which the adversary is not allowed to corrupt the partner principal of the target session, so in fact, $\mathcal {D}$ can answer all legitimate $\mathtt {Corrupt}$ queries.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the value C is the encryption of the value $X_1$, the simulation constructed by $\mathcal {D}$ is identical to the Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {D}$ can answer the $\mathrm {CCA2}$ challenge successfully. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PKE}}^{\mathrm {CCA2}}(\mathcal {D}). \end{aligned}$$

(18)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key, or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The following describes $\mathcal {B}$’s procedure of answering queries.

• $\mathtt {Send}(U,V,s,m)$ query:

  • $U=V^*,V=U^*,s=t^*$:

    • If $V^*$ is the initiator, upon receiving the second protocol message computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(V^*||\bar{X}||U^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),V^*||\bar{X}||U^*||\bar{Y})$ (consider X is from the initiator and Y is from the responder, and $\bar{X}$ and $\bar{Y}$ are the encrypted X and Y, respectively, which are computed in normal protocol run).

    • If $V^*$ is the responder, upon receiving the first protocol message computes the session key $K \leftarrow \text {Oracle}^{\mathrm {PRF}}(U^*||\bar{X}||V^*||\bar{Y}) \oplus \mathrm {PRF}(\mathrm {CDH}(U,V),U^*||\bar{X}||V^*||\bar{Y})$.

  • $U=V^*,V=U^*,s \ne t^*$: Executes the protocol normally.

  • $U=V^*,V \ne U^*$: Executes the protocol normally.

  • $U=U^*$:

    • If this is the initiator and it is the first message, then it executes the protocol normally.

    • If this is the initiator and the second protocol message, or the responder:

      • If the same message that came to $U^*$ in the test session has come as the incoming message, computes the session key using the Oracle$^{\mathrm {PRF}}$.

      • Otherwise, executes the protocol normally.

  • $U,V \ne U^*$ or $V^*$: Executes the protocol normally.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathtt {SessionKeyReveal}$ query is not allowed to the target session or its partner. $\mathcal {B}$ can compute all the session keys by executing the protocol.

  • For sessions involving the principal $U^*$, and the incoming message to $U^*$ is the same message which has come to $U^*$ in the target session, $\mathcal {B}$ uses $\text {Oracle}^{\mathrm {PRF}}$ to compute the session key.

  • For all other sessions, $\mathcal {B}$ computes the session key by using the $\mathrm {PRF}$.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {B}$ can answer all $\mathtt {EphemeralKeyReveal}$ queries, which are allowed by the freshness condition, because $\mathcal {B}$ has the ephemeral keys.

• $\mathtt {Corrupt}(U)$ query: Except for $U^*$, algorithm $\mathcal {B}$ can answer all other $\mathtt {Corrupt}$ queries. In this case we consider the situation in which the adversary is not allowed to corrupt the partner principal of the target session, so in fact, $\mathcal {B}$ can answer all legitimate $\mathtt {Corrupt}$ queries.

• $\mathtt {Test}(U,V,s)$ query: When $U=U^*,V=V^*,s=s^*$, answers with the K which is computed as explained in the $\mathtt {Send}$ query. Otherwise aborts the game.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\text {PRF}}(\mathcal {B}). \end{aligned}$$

(19)

Semantic security of the session key in Game 4: Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(20)

Using Eqs. (16)–(20) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 1d}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})+\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {D})\Big ). \end{aligned}$$

Case 2a

Adversary corrupts the owner to the test session.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 2a}}(\mathcal {A}). \end{aligned}$$

(21)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random number $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the peer session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, Game 2 is identical to Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(22)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses C from the ciphertext space as encryption of the public ephemeral value X of the session $\varPi ^{s^*}_{U^*,V^*}$, and sends it to the session $\varPi ^{t^*}_{V^*,U^*}$ as having come from the session $\varPi ^{s^*}_{U^*,V^*}$.

We introduce an algorithm $\mathcal {D}$ which is constructed using the adversary $\mathcal {A}$. If $\mathcal {A}$ can distinguish the difference between Game 2 and Game 3, then $\mathcal {D}$ can be used against the $\mathrm {CCA2}$ challenger of underlying public-key cryptosystem, $\mathrm {PKE}$. The algorithm $\mathcal {D}$ uses the public key of the $\mathrm {CCA2}$ challenger as the public key of the protocol principal $V^*$ and generates all other public/secret key pairs (Diffie–Hellman and encryption keys) for protocol principals. $\mathcal {D}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$, such that it is interacting with either Game 2 or Game 3. $\mathcal {D}$ picks two random strings, $X_{0}, X_{1} \mathop {\leftarrow }\limits ^{\$} {{{\mathbb {Z}}^{*}}_q}$ and passes them to the $\mathrm {CCA2}$ challenger. From the $\mathrm {CCA2}$ challenger, $\mathcal {D}$ receives a challenge ciphertext C such that $C \mathop {\leftarrow }\limits ^{\$}(pk_{V^*}, X_{\theta })$ where $X_{\theta }= X_0$ or $X_{\theta } = X_1$. $\mathcal {D}$ uses $X_1$ as the decryption of C when answering queries. The way of answering the queries is the same as in the Game 3 of Case 1c.

If the value C is the encryption of the value $X_1$, the simulation constructed by $\mathcal {D}$ is identical to the Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {D}$ can answer the $\mathrm {CCA2}$ challenge successfully. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PKE}}^{\mathrm {CCA2}}(\mathcal {D}). \end{aligned}$$

(23)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key, or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The way of answering the queries is the same as in the Game 4 of Case 1c.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\text {PRF}}(\mathcal {B}). \end{aligned}$$

(24)

Semantic security of the session key in Game 4: Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(25)

Using Eqs. (21)–(25) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 2a}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})+\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {D})\Big ). \end{aligned}$$

Case 2b

Adversary does not corrupt the owner to the test session.

Game 1: This is the original game. When $\mathtt {Test}$ query is asked the Game 1 challenger will choose a random bit $b\mathop {\leftarrow }\limits ^{\$}\{0,1\}$. If $b=1$, the real session key is given to $\mathcal {A}$; otherwise, a random value chosen from the same session-key space is given. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}} (\mathcal {A})={\mathrm {Adv}}^{\mathrm {eCK}}_{\mathrm {P1}, \text {Case 2b}}(\mathcal {A}). \end{aligned}$$

(26)

Game 2: Same as Game 1 with the following exception: before $\mathcal {A}$ begins, two distinct random principals $U^*,V^*\mathop {\leftarrow }\limits ^{\$} \{U_1,\ldots ,U_{N_P}\}$ are chosen and two random numbers $s^*,t^* \mathop {\leftarrow }\limits ^{\$} \{1,\ldots N_s\}$ are chosen, where $N_P$ is the number of protocol principals and $N_s$ is the number of sessions on a principal. The session $\varPi ^{s^*}_{U^*,V^*}$ is chosen as the target session, and the session $\varPi ^{t^*}_{V^*,U^*}$ is chosen as the peer session. If the test session is not the session $\varPi ^{s^*}_{U^*,V^*}$, the Game 2 challenger aborts the game. Unless the incorrect choice happens, the Game 2 is identical to the Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A})=\frac{1}{{N_P}^2 N_s^2}\mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(27)

Game 3: Same as Game 2 with the following exception: the Game 3 challenger randomly chooses $c\mathop {\leftarrow }\limits ^{\$} \mathbb {Z}^*_{q}$ and computes $K\leftarrow \mathrm {PRF}(\mathrm {CDH}(X,Y),\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y}) \oplus \mathrm {PRF}(g^c,\cdot \Vert \bar{X}\Vert \cdot \Vert \bar{Y})$. When the adversary asks the $\mathtt {Test}(U^*,V^*,s^*)$ query, Game 3 challenger will answer with K.

Note 4

Let X, Y be the two ephemeral Diffie–Hellman public keys (unencrypted) of the protocol principals in a session, such that $X=g^x, Y=g^y$ and $\mathrm {CDH}(X,Y)=g^{xy}$.

We construct an algorithm $\mathcal {C}$ against a $\mathrm {DDH}$ challenger, using the adversary $\mathcal {A}$ as a subroutine. The $\mathrm {DDH}$ challenger sends values $(g^{a}, g^{b}, g^c)$ such that either $c={ab}$ or $c \mathop {\leftarrow }\limits ^{\$} \mathbb {Z}_q^{*}$, as the inputs to the algorithm $\mathcal {C}$. $\mathcal {C}$ sets $U\leftarrow g^a$ as the long-term Diffie–Hellman public key of $U^*$ and $V\leftarrow g^b$ as the long-term Diffie–Hellman public key of $V^*$. Moreover, $\mathcal {C}$ sets all the other long-term Diffie–Hellman secret/public key pairs and all the encryption key pairs of protocol principals. The algorithm $\mathcal {C}$ runs a copy of $\mathcal {A}$ and interacts with $\mathcal {A}$ such that $\mathcal {A}$ is interacting with either Game 2 or Game 3. The way of answering the queries is the same as in the Game 3 of Case 1b.

If $\mathcal {C}$’s input is a Diffie–Hellman triple, simulation constructed by $\mathcal {C}$ is identical to Game 2; otherwise, it is identical to Game 3. If $\mathcal {A}$ can distinguish the difference between games, then $\mathcal {C}$ can answer the $\mathrm {DDH}$ challenge. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})|\le \mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C}). \end{aligned}$$

(28)

Game 4: Same as Game 3 with the following exception: the Game 4 challenger randomly chooses $K\mathop {\leftarrow }\limits ^{\$}\{0,1\}^k$ and sends it to the adversary $\mathcal {A}$ as the answer to the $\mathtt {Test}(U^*,V^*,s^*)$ query.

If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the session-key value K is computed using the real $\mathrm {PRF}$ with a hidden key, or using a random function. The adversary $\mathcal {A}$ is given a K, such that it is computed using the $\mathrm {PRF}$ or randomly chosen from the session-key space. The way of answering the queries is the same as in the Game 4 of Case 1b.

If the oracle is using the real $\mathrm {PRF}$ with a hidden key, the simulation is identical to Game 3, whereas if the oracle is using a random function, the simulation constructed is identical to Game 4. If $\mathcal {A}$ can distinguish the difference between Game 3 and Game 4, then $\mathcal {A}$ can be used as a subroutine of an algorithm $\mathcal {B}$, which is used to distinguish whether the $\mathrm {PRF}$ challenger is real or random. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 3}}(\mathcal {A})-\mathrm {Adv}_{\text {Game 4}}(\mathcal {A})|\le \mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B}). \end{aligned}$$

(29)

Semantic security of the session key in Game 4:

Since the session key K of $\varPi ^{s^*}_{U^*,V^*}$ is chosen randomly and independently from all other values, $\mathcal {A}$ does not have any advantage in Game 4. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 4}}(\mathcal {A}) = 0. \end{aligned}$$

(30)

Using Eqs. (26)–(30) we find,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1},\text {Case 2b}}{(\mathcal {A})} \le N_P^2 {N_s}^2 \Big (\mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C})+\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\Big ). \end{aligned}$$

Combining all the above cases.

According to the analysis we can see the adversary $\mathcal {A}$’s advantage of winning against the $\mathrm {eCK}$ challenger of the protocol $\mathrm {P1}$ is:

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}{(\mathcal {A})} \le N_P^2 N_s^2 \max \Big (\big (\mathrm {Adv}_{q,g}^{\mathrm {DDH}}(\mathcal {C})+\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})\big ),\\\big (\mathrm {Adv}_{\mathrm {PRF}}(\mathcal {B})+\mathrm {Adv}^{\mathrm {CCA2}}_{\mathrm {PKE}}(\mathcal {D})\big )\Big ) . \end{aligned}$$

5 Conclusion and future works

In this paper we presented a generic $\mathrm {eCK}$-secure, NAXOS-free, standard model key exchange protocol, namely the protocol $\mathrm {P1}$. Thus, our generic protocol is a strongly secure and realistic framework for real-world instantiations. The protocol execution cost of our protocol is one encryption, one decryption, three exponentiations and two pseudo-random operations. Cramer–Shoup-based instantiation of our protocol needs relatively simple multi-exponentiations and additionally two pseudo-random functions.

As a future work authors would like to focus on leakage-resilient improvements on the protocol $\mathrm {P1}$. The essential modification would be replacing the $\mathrm {CCA2}$ public-key encryption scheme with a suitable leakage-resilient $\mathrm {CCA2}$-secure public-key encryption scheme and using a leakage-resilient mechanism to compute the exponentiation operations, in places where the long-term Diffie–Hellman secret keys are used as exponents. Several strong $\mathrm {eCK}$-style leakage-resilient security models have been introduced in the literature [1, 19], which would be useful to analyze the leakage-resilient security of the improved protocol. There are several standard model leakage-resilient $\mathrm {CCA2}$-secure public-key encryption schemes in the literature [13, 20], which can be used to replace the $\mathrm {CCA2}$ public-key encryption scheme. In order to compute the Diffie–Hellman exponentiations in leakage-resilient manner, the mechanism used by Alawatugoda et al. [2] would be appropriate, which is influenced by the leakage-resilient storage scheme of Dziembowski and Faust [12]. Thus, it is possible to improve this generic protocol to achieve leakage resiliency.