Strongly secure authenticated key exchange from factoring, codes, and lattices

Abstract

An unresolved problem in research on authenticated key exchange (AKE) in the public-key setting is to construct a secure protocol against advanced attacks such as key compromise impersonation and maximal exposure attacks without relying on random oracles. HMQV, a state of the art AKE protocol, achieves both efficiency and the strong security proposed by Krawczyk (we call it the ${\mathrm {CK}}^+$ model), which includes resistance to advanced attacks. However, the security proof is given under the random oracle model. We propose a generic construction of AKE from a key encapsulation mechanism (KEM). The construction is based on a chosen-ciphertext secure KEM, and the resultant AKE protocol is ${\mathrm {CK}}^+$ secure in the standard model. The construction gives the first ${\mathrm {CK}}^+$ secure AKE protocols based on the hardness of integer factorization problem, code-based problems, or learning problems with errors. In addition, instantiations under the Diffie–Hellman assumption or its variant can be proved to have strong security without non-standard assumptions such as $\pi$PRF and KEA1. Furthermore, we extend the ${\mathrm {CK}}^+$ model to identity-based (called the ${\hbox {id-CK}^+}$ model), and propose a generic construction of identity-based AKE (ID-AKE) based on identity-based KEM, which satisfies ${\hbox {id-CK}^+}$ security. The construction leads first strongly secure ID-AKE protocols under the hardness of integer factorization problem, or learning problems with errors.

1 Introduction

1.1 Background

Establishing secure channels is one of the most important areas of cryptographic research. Secure channels provide secrecy and authenticity for both communication parties. When parties can share secret information via a public communication channel, secure channels would be constructed on (symmetric key) encryptions and message authentication codes with the shared secret information called session keys. Public-key cryptography can provide various solutions: one approach uses a key encapsulation mechanism (KEM) and another uses authenticated key exchange (AKE). Note that, though there are two settings (i.e., symmetric-key based and public-key based) for AKE, this paper focuses on the public-key setting.

In KEM, a receiver has public information, called a public key, and the corresponding secret information, called a secret key. The public key is expected to be certified with the receiver’s identity through an infrastructure such as a public key infrastructure (PKI). A sender who wants to share information, a session key, with the receiver sends a ciphertext of the information and, the receiver decrypts the ciphertext to extract the information. KEM can be easily constructed from public-key encryption (PKE) under the reasonable condition that the plaintext space is sufficiently large. The desirable security notion of KEM is formulated as the indistinguishability against chosen ciphertext attacks (IND-CCA).

In AKE, each party has public information, called a static public key, and the corresponding secret information, called a static secret key. The static public key is also expected to be certified with a party’s identity through an infrastructure such as PKI. A party who wants to share information with a party exchanges ephemeral public keys, generated from the corresponding ephemeral secret keys, and computes a session state from their static public keys, the corresponding static secret keys, the exchanged ephemeral public keys, and the corresponding ephemeral secret keys. Both parties then derive a session key from these values including the session state using a key derivation procedure. Many studies have investigated the security notion of AKE [5, 17, 43, 46, 61]. The first security notion of AKE based on indistinguishability was provided by Bellare and Rogaway [5] (BR model). The BR model captures basic security requirements for AKE such as known key security and impersonation resilience. However, the BR model cannot grasp more complicated situations where a static secret key or session state of a party has been exposed. Accordingly, Canetti and Krawczyk [17] defined the first security notion of AKE capturing the exposure of static secret keys and session state and called it the Canetti–Krawczyk (CK) model. Though the CK model represents exposure of information other than the target session of the adversary, some advanced attacks such as key compromise impersonation (KCI), the breaking of weak perfect forward secrecy (wPFS) and maximal exposure attacks (MEX) use secret information of the target session; thus, the CK model is not resilient to such attacks. We say that KCI is successful if given a static secret key an adversary can impersonate some honest party in order to fool the owner of the exposed secret key. wPFS implies that an adversary cannot recover a session key using static secret keys if the adversary does not modify messages of the target session and the session is executed before the static secret keys are compromised. We say that MEX is successful if an adversary can distinguish the session key from a random value under the disclosure of any pair of secret static keys and ephemeral secret keys of the initiator and the responder in the session except for both the static and ephemeral secret keys of the initiator or the responder. Resistance to MEX requires security against any exposure situation that was not presumed. For example, an implementer of AKE may pretend to generate secret keys in an insecure host machine in order to prevent the randomness generation mechanisms in a tamper-proof module such as a smart card. Additionally, if a pseudo-random number generator implemented in a system is poor, secret keys will be known to the adversary even when the generation of ephemeral secret keys is operated in a tamper-proof module. Most AKE protocols are proved in the CK model; however, it is unclear whether such protocols satisfy resistance to advanced attacks due to the limitations of the CK model. A state of the art AKE protocol HMQV [43] satisfies all known security requirements for AKE, including resistance to KCI, wPFS,¹ and MEX, as well as provable security in the CK model. In this paper, we call this security model the ${\mathrm {CK}}^+$ model; it is known to be one of the ‘strongest’ models for AKE. LaMacchia et al. [46] and Sarr et al. [61] also proposed very strong security models for AKE by re-formulating the concept of the ${\mathrm {CK}}^+$ model; they called them the eCK model and the seCK model, respectively. These models allow an adversary to pose a query that directly reveals the ephemeral secret key of the target session. However, Cremers points out that the CK model and the eCK model are incomparable [23, 24]; thus, the eCK model is not stronger than the CK model while the ${\mathrm {CK}}^+$ model is. We will briefly show the difference between the ${\mathrm {CK}}^+$ model and these models. Since MEX includes any non-trivial exposure situation, HMQV (and ${\mathrm {CK}}^+$ secure protocols) achieves surprisingly strong security.

1.2 Motivating problem

HMQV is one of the most efficient protocols and satisfies one of the strongest security models (i.e., ${\mathrm {CK}}^+$ security). However, the security proof is given in the random oracle model (ROM) under a specific number-theoretic assumption (i.e., the gap Diffie–Hellman (DH) assumption). Moreover, to prove resistance to MEX, the knowledge-of-exponent assumption (KEA1) [28] (a widely criticized assumption such as [54]) is also necessary. Hence, one of the open problems in research on AKE is to construct a secure scheme in the ${\mathrm {CK}}^+$ model without relying on random oracles under standard assumptions.

Boyd et al. [12, 13] and Gorantla et al. [34] gave a partial solution to this problem by noting that KEM and AKE are closely related and that it might be natural to construct AKE from KEM. They proposed a generic construction of AKE from KEM (BCGNP construction), and its security is proved in the CK model in the standard model (StdM). Also, the BCGNP construction is shown to satisfy resistance to KCI. However, it is unclear whether the BCGNP construction is secure when exposure of secret information occurs (i.e., resistance to MEX). In fact, the BCGNP construction fails to satisfy ${\mathrm {CK}}^+$ security when we consider the following attack scenario: Two parties exchange ciphertexts of an IND-CCA secure KEM scheme and generate a session key from these. An adversary who obtains the ephemeral secret keys (randomness used in generating ciphertexts) of the parties can compute the session key and win the game. Though the other construction which satisfies wPFS is also proposed in their paper, the construction contains specific DH values, and the security proof relies on the decisional DH assumption. It is quite restrictive because it cannot be instantiated from the hardness of something other than the DH assumption such as an integer factoring problem, code-based problem, or lattice problem. Thus, we still have no AKE protocol that is secure in the ‘strongest’ model under just a general assumption without relying on ROs.

1.3 Our contribution

We fully solve the open problem by providing a generic construction of AKE from KEM. Our construction is a generalization of the BCGNP construction. The BCGNP construction uses IND-CCA KEM, a pseudo-random function (PRF), and a key derivation function (KDF) as building blocks. Our construction effectively follows the design principle of the BCGNP construction. However, we first point out that the security proof of the BCGNP construction is not complete. Specifically, a requirement for KEM has not been formulated. KEM keys must have enough min-entropy in order to make outputs of the KDF computationally indistinguishable from a uniformly random chosen element. The IND-CCA security does not imply min-entropy of KEM keys. Thus, the assumption that the KEM scheme satisfies such a property is additionally required. Fortunately, almost all IND-CCA KEM schemes satisfy that. Also, we need an IND-CPA secure KEM in addition to the BCGNP construction. Such an additional KEM can make our scheme wPFS and resilient to MEX. Note that our construction is not one-round protocol (i.e., one-round means that the initiator and the responder can send their messages independently and simultaneously. ) in return for achieving such strong security properties. The resultant AKE protocol is ${\mathrm {CK}}^+$ secure. Its security is proved under the existence of such KEMs, a KDF, and a PRF in the StdM. IND-CCA secure KEM schemes have been shown from the hardness of integer factoring [37, 51], code-based problems [29, 50], or lattice problems [1, 2, 18, 49, 57, 59, 62]. To the best of our knowledge, our generic construction provides the first ${\mathrm {CK}}^+$ secure AKE protocols based on the hardness of the above problems. Regarding the DH assumption or its variant, our generic construction is the first protocol that achieves ${\mathrm {CK}}^+$ security in the StdM without non-standard assumptions (e.g., $\pi$PRF and KEA1).

We also rewrite the ${\mathrm {CK}}^+$ model before proving the security of our generic construction in order to simplify the original model in [43]. Specifically, the original model is defined as a mix of four definitions (i.e., the CK model, wPFS, and resistance to KCI and MEX); thus, the security proof must also be separated into four theorems, which may reduce the readability. Therefore, we reformulate the ${\mathrm {CK}}^+$ model as follows: wPFS, resistance to KCI, and resistance to MEX are integrated into the experiment of the extended model by exhaustively classifying exposure patterns. This definition is handy to prove security and rigorously captures all required properties.

Moreover, we show an extension of the above result to the ID-based setting, identity-based AKE (ID-AKE). It is natural to introduce ID-based cryptography in order to avoid the burden of key managements. Especially, ID-AKE is more suitable for mobile environment than PKI-based AKE. For example, let’s consider some P2P service for smart-phones. When a user want to securely connect to a peer with a secure channel in such a service, but he/she only knows the e-mail address or the phone number of the peer, PKI-based AKE is not available because each party must know the public-key of the peer. On the other hand, ID-AKE can easily handle this situation by dealing with the e-mail address or the phone number as the ID of the peer.

In ID-based cryptography, it is assumed that a key generate center (KGC) exists. The KGC manages system parameters and a master secret key, and generates a static secret key of each party with the master secret key. However, this means that the master key is more powerful than static secret keys of parties. We need an additional security requirement, called master-key weak forward secrecy (mFS), that the session key is protected even when the master secret key is exposed if the adversary does not modify messages of the target session and the session is executed before the master secret key is compromised. Thus, first, we formulate an ID-based version of the ${\mathrm {CK}}^+$ model (called the ${\hbox {id-CK}^+}$ model) that captures mFS. Boyd et al. [12, 13] gave a generic construction of ID-AKE based on ID-based chosen-ciphertext secure (IND-ID-CCA) ID-based KEM (IB-KEM). Next, we improve their ID-AKE construction as the same way as our generic AKE construction. IND-ID-CCA secure IB-KEM schemes have been shown from the hardness of bilinear pairing problems [9, 11], or lattice problems [1, 2, 18, 49, 57, 59, 62]. Our generic construction provides the first ${\hbox {id-CK}^+}$ secure ID-AKE protocols based on the hardness of the above problems in the StdM.

We summarize our contributions as follows:

• 1. We reformulate ${\mathrm {CK}}^+\hbox { and }{\hbox {id-CK}^+}$ models to gain readability of the security proofs.

• 2. We propose two-pass generic ${\mathrm {CK}}^+$ secure AKE and two-pass generic ${\hbox {id-CK}^+}$ secure ID-AKE constructions in the StdM.

• 3. We achieve the first ${\mathrm {CK}}^+$ secure AKE protocols based on the hardness of integer factorization problem, code-based problems, and lattice-based problems in the StdM.

• 4. We achieve the first ${\mathrm {CK}}^+$ secure AKE protocol based on the DH assumption or its variant in the StdM without knowledge assumptions.

• 5. We achieve the first ${\hbox {id-CK}^+}$ secure ID-AKE protocols based on the hardness of bilinear pairing problems, and lattice-based problems in the StdM.

The proposed generic construction can allow a hybrid instantiation; that is, the initiator and the responder can use different KEMs under different assumptions. For example, the initiator uses a factoring-based KEM while the responder uses a lattice-based KEM.

2 Security models

In this section, we recall the ${\mathrm {CK}}^+$ model that was introduced by [43]. We show a model specified to two pass protocols for simplicity. It can be trivially extended to any round protocol. Also, we show the ${\hbox {id-CK}^+}$ model as an extension of the ${\mathrm {CK}}^+$ model.

Throughout this paper we use the following notations. If $\mathsf {Set}$ is a set, then by $m \in _R \mathsf {Set}$ we denote that $m$ is sampled uniformly from $\mathsf {Set}$. If ${\mathcal {ALG}}$ is an algorithm, then by $y \leftarrow \mathcal {ALG}(x;r)$ we denote that $y$ is output by $\mathcal {ALG}$ on input $x$ and randomness $r$ (if $\mathcal {ALG}$ is deterministic, $r$ is empty).

2.1 ${\mathrm {CK}}^+$ versus eCK

As indicated in Table 1, the ${\mathrm {CK}}^+$ model captures all non-trivial patterns of exposure of static and ephemeral secret keys. The eCK model [46], which is a variant of the CK model [17], also captures all non-trivial patterns of exposure, as in Table 1. Since the ${\mathrm {CK}}^+$ model captures all non-trivial patterns of exposure of static and ephemeral secret keys, the ${\mathrm {CK}}^+$ model can theoretically be seen as a completion of the AKE security model.

Table 1 Classification of attacks and proposed ${\mathrm {CK}}^+$ model [43] and eCK model [46]

In Table 1, the six cases in Definition 2 are listed, and these six cases cover wPFS, resistance to KCI, and MEX as follows: Cases 2-(a), 2-(c), and 2-(f) capture KCI, since the adversary obtains the static secret key of one party and the ephemeral secret key of the other party of the test session. Case 2-(e) captures wPFS, since the adversary obtains the static secret keys of both parties of the test session. Cases 2-(b), 2-(d) capture MEX, since the adversary obtains the ephemeral secret keys of both parties of the test session.

The main difference between the ${\mathrm {CK}}^+$ model and the eCK model is that the ${\mathrm {CK}}^+$ model captures the session state reveal attack, but the eCK model does not. Thus, we adopt the ${\mathrm {CK}}^+$ model, which is stronger than the eCK model from the viewpoint of the session state reveal attack, in this paper.

Notice that the timing of the static and ephemeral key reveal differs in the eCK and ${\mathrm {CK}}^+$ models. In the eCK model, an adversary can issue the static and ephemeral key reveal query adaptively. In contrast, in the ${\mathrm {CK}}^+$ model, an adversary can issue a corrupt query to obtain the static key, and the ephemeral key is given to the adversary when it is determined. We summarize this in Table 2.

Table 2 Comparison of ${\mathrm {CK}}^+$ model [43] and eCK model [46]

2.2 ${\mathrm {CK}}^+$ security model

We denote a party by $U_i$, and party $U_i$ and other parties are modeled as probabilistic polynomial-time (PPT) Turing machines w.r.t. security parameter $\kappa$. For party $U_i$, we denote static secret (public) key by $s_i\,(S_i)$ and ephemeral secret (public) key by $x_i\,(X_i)$. Party $U_i$ generates its own keys, $s_i\hbox { and }S_i$, and the static public key $S_i$ is linked with $U_i$’s identity in some systems like PKI.² The maximum number of parties and sessions is polynomially bounded in the security parameter.

2.2.1 Session

An invocation of a protocol is called a session. Session activation is done by an incoming message of the forms $(\varPi ,\mathcal {I},U_A,U_B)$ or $(\varPi ,\mathcal {R},U_B,U_A,X_A)$, where we equate $\varPi$ with a protocol identifier, $\mathcal {I}\hbox { and }\mathcal {R}$ with role identifiers, and $U_A\hbox { and }U_B$ with user identifiers. If $U_A$ is activated with $(\varPi ,\mathcal {I},U_A,U_B)$, then $U_A$ is called the session initiator. If $U_B$ is activated with $(\varPi ,\mathcal {R},U_B,U_A,X_A)$, then $U_B$ is called the session responder. The initiator $U_A$ outputs $X_A$, then may receive an incoming message of the forms $(\varPi ,\mathcal {I},U_A,U_B,X_A,X_B)$ from the responder $U_B,\,U_A$ then computes the session key $SK$ if $U_A$ received the message. On the contrary, the responder $U_B$ outputs $X_B$, and computes the session key $\textit{SK}$.

If $U_A$ is the initiator of a session, the session is identified by $\mathsf {sid}=(\varPi ,\mathcal {I},U_A,U_B,\,X_A)$ or $\mathsf {sid}=(\varPi ,\mathcal {I},U_A,U_B,X_A,X_B)$. If $U_B$ is the responder of a session, the session is identified by $\mathsf {sid}=(\varPi ,\mathcal {R},U_B,U_A,\,X_A,X_B)$. We say that $U_A$ is the owner of session $\mathsf {sid}$, if the third coordinate of session $\mathsf {sid}$ is $U_A$. We say that $U_A$ is the peer of session $\mathsf {sid}$, if the fourth coordinate of session $\mathsf {sid}$ is $U_A$. We say that a session is completed if its owner computes the session key. The matching session of $(\varPi ,\mathcal {I},U_A,U_B,X_A,X_B)$ is session $(\varPi ,\mathcal {R},U_B,U_A,X_A,X_B)$ and vice versa.

2.2.2 Adversary

The adversary $\mathcal {A}$, which is modeled as a probabilistic polynomial-time Turing machine, controls all communications between parties including session activation by performing the following adversary query.

• $\mathsf {Send}(\text {message})$: The message has one of the following forms: $(\varPi ,\mathcal {I},U_A,U_B)$, $(\varPi ,\mathcal {R},U_B, U_A,X_A)$, or $(\varPi ,\mathcal {I},U_A,U_B,X_A,X_B)$. The adversary $\mathcal {A}$ obtains the response from the party.

To capture exposure of secret information, the adversary $\mathcal {A}$ is allowed to issue the following queries.

• $\mathsf {SessionKeyReveal}$($\mathsf {sid}$): The adversary $\mathcal {A}$ obtains the session key $SK$ for the session $\mathsf {sid}$ if the session is completed.

• $\mathsf {SessionStateReveal}$($\mathsf {sid}$): The adversary $\mathcal {A}$ obtains the session state of the owner of session $\mathsf {sid}$ if the session is not completed (the session key is not established yet). The session state includes all ephemeral secret keys and intermediate computation results except for immediately erased information but does not include the static secret key.

• $\mathsf {Corrupt}$($U_i$): This query allows the adversary $\mathcal {A}$ to obtain all information of the party $U_i$. If a party is corrupted by a $\mathsf {Corrupt}(U_i,S_i)$ query issued by the adversary $\mathcal {A}$, then we call the party $U_i$ dishonest. If not, we call the party honest.

2.2.3 Freshness

For the security definition, we need the notion of freshness.

Definition 1

(Freshness) Let $\mathsf {sid}^*=(\varPi ,\mathcal {I},U_A,U_B,X_A,X_B)$ or $(\varPi ,\mathcal {R},U_A,U_B,\,X_B,X_A)$ be a completed session between honest users $U_A\hbox { and }U_B$. If the matching session exists, then let $\overline{\mathsf {sid}^*}$ be the matching session of $\mathsf {sid}^*$. We say session $\mathsf {sid}^*$ is fresh if none of the following conditions hold:

• 1. The adversary $\mathcal {A}$ issues $\mathsf {SessionKeyReveal} (\mathsf {sid}^*)$, or $\mathsf {SessionKeyReveal} (\overline{\mathsf {sid}^*})$ if $\overline{\mathsf {sid}^*}$ exists,

• 2. $\overline{\mathsf {sid}^*}$ exists and the adversary $\mathcal {A}$ makes either of the following queries

  • $\mathsf {SessionStateReveal} (\mathsf {sid}^*)$ or $\mathsf {SessionStateReveal} (\overline{\mathsf {sid}^*})$,

• 3. $\overline{\mathsf {sid}^*}$ does not exist and the adversary $\mathcal {A}$ makes the following query

  • $\mathsf {SessionStateReveal} (\mathsf {sid}^*)$.

2.2.4 Security experiment

For the security definition, we consider the following security experiment. Initially, the adversary $\mathcal {A}$ is given a set of honest users and makes any sequence of the queries described above. During the experiment, the adversary $\mathcal {A}$ makes the following query.

• $\mathsf {Test}(\mathsf {sid}^*)$: Here, $\mathsf {sid}^*$ must be a fresh session. Select random bit $b \in _U \{0,1\}$, and return the session key held by $\mathsf {sid}^*$ if $b=0$, and return a random key if $b=1$.

The experiment continues until the adversary $\mathcal {A}$ makes a guess $b'$. The adversary $\mathcal {A}$ wins the game if the test session $\mathsf {sid}^*$ is still fresh and if the guess of the adversary $\mathcal {A}$ is correct, i.e., $b'=b$. The advantage of the adversary $\mathcal {A}$ in the AKE experiment with the PKI-based AKE protocol $\varPi$ is defined as

$$\begin{aligned} \text {Adv}_{\varPi }^{\text {AKE}}(\mathcal {A}) = \Pr [\mathcal {A}\ wins] - \frac{1}{2}. \end{aligned}$$

We define the security as follows.

Definition 2

(Security for PKI-based AKE) We say that a PKI-based AKE protocol $\varPi$ is secure in the ${\mathrm {CK}}^+$ model if the following conditions hold:

• 1. If two honest parties complete matching sessions, then, except with negligible probability, they both compute the same session key.

• 2. For any PPT bounded adversary $\mathcal {A},\,\text {Adv}_{\varPi }^{\text {AKE}}(\mathcal {A})$ is negligible in security parameter $\kappa$ for the test session $\mathsf {sid}^*$,

  • (a) if $\overline{\mathsf {sid}^*}$ does not exist, and the static secret key of the owner of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

  • (b) if $\overline{\mathsf {sid}^*}$ does not exist, and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

  • (c) if $\overline{\mathsf {sid}^*}$ exists, and the static secret key of the owner of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

  • (d) if $\overline{\mathsf {sid}^*}$ exists, and the ephemeral secret key of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

  • (e) if $\overline{\mathsf {sid}^*}$ exists, and the static secret key of the owner of $\mathsf {sid}^*$ and the static secret key of the peer of $\mathsf {sid}^*$ are given to $\mathcal {A}$.

  • (f) if $\overline{\mathsf {sid}^*}$ exists, and the ephemeral secret key of $\mathsf {sid}^*$ and the static secret key of the peer of $\mathsf {sid}^*$ are given to $\mathcal {A}$.

Note that the items 2.a, 2.c, and 2.f correspond to resistance to KCI, item 2.e corresponds to wPFS, and items 2.b and 2.d correspond to resistance to MEX.

2.3 ${\hbox {id-CK}^+}$ security model

The ${\hbox {id-CK}^+}$ security model for ID-AKE is similarly defined as the ${\mathrm {CK}}^+$ model. There are some differences between two models as follows:

• The KGC generates the master secret key and public parameter.

• Static secret keys of parties are generated by the KGC with the master secret key and IDs.

• An adversary may reveal the master secret key according to mFS.

Formulations of sessions, adversarial oracle queries, and freshness are not changed with the ${\mathrm {CK}}^+$ model. To capture mFS, we modify the definition of security experiment.

Definition 3

(Security for ID-AKE) We say that a ID-AKE protocol $\varPi$ is secure in the ${\hbox {id-CK}^+}$ model if the following conditions hold:

• 1. If two honest parties complete matching sessions, then, except with negligible probability, they both compute the same session key.

• 2. For any PPT adversary $\mathcal {A},\,\text {Adv}_{\varPi }^{\text {ID-AKE}}(\mathcal {A})$ is negligible in security parameter $\kappa$ for the fresh test session $\mathsf {sid}^*$,

  • (a) if $\overline{\mathsf {sid}^*}$ does not exist, and the static secret key of the owner of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

  • (b) if $\overline{\mathsf {sid}^*}$ does not exist, and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

  • (c) if $\overline{\mathsf {sid}^*}$ exists, and the static secret key of the owner of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

  • (d) if $\overline{\mathsf {sid}^*}$ exists, and the ephemeral secret key of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

  • (e) if $\overline{\mathsf {sid}^*}$ exists, and the static secret key of the owner of $\mathsf {sid}^*$ and the static secret key of the peer of $\mathsf {sid}^*$ are given to $\mathcal {A}$.

  • (f) if $\overline{\mathsf {sid}^*}$ exists, and the ephemeral secret key of $\mathsf {sid}^*$ and the static secret key of the peer of $\mathsf {sid}^*$ are given to $\mathcal {A}$.

  • (g) if $\overline{\mathsf {sid}^*}$ exists, the master secret key $msk$ is given to $\mathcal {A}$.

Note that the items 2.a, 2.c, and 2.f correspond to resistance to KCI, item 2.e corresponds to wPFS, items 2.b and 2.d correspond to resistance to MEX, and item 2.g corresponds to mFS.

3 Generic AKE construction from KEM without random oracles

In this section, we propose a generic construction of ${\mathrm {CK}}^+$-secure AKE from KEM.

3.1 Preliminaries

3.1.1 Security notions of KEM schemes

Here, we recall the definition of IND-CCA and IND-CPA security for KEM, and min-entropy of KEM keys as follows.

Definition 4

(Model for KEM Schemes) A KEM scheme consists of the following 3-tuple $(\mathsf {KeyGen},\,\mathsf {EnCap},\,\mathsf {DeCap})$:

$( ek , dk ) \leftarrow \mathsf {KeyGen}(1^\kappa ,r_g)$ ::

a key generation algorithm which on inputs $1^\kappa \hbox { and }r_g \in \mathcal {RS}_G$, where $\kappa$ is the security parameter and $\mathcal {RS}_G$ is a randomness space, outputs a pair of keys $( ek , dk )$.

$(K,CT) \leftarrow \mathsf {EnCap}_{ ek }(r_e)$ ::

an encryption algorithm which takes as inputs encapsulation key $ek \hbox { and }r_e \in \mathcal {RS}_E$, outputs session key $K \in \mathcal {KS}$ and ciphertext $CT \in \mathcal {CS}$, where $\mathcal {RS}_E$ is a randomness space, $\mathcal {KS}$ is a session key space, and $\mathcal {CS}$ is a ciphertext space.

$K \leftarrow \mathsf {DeCap}_{ dk }(CT)$ ::

a decryption algorithm which takes as inputs decapsulation key $dk$ and ciphertext $CT \in \mathcal {CS}$, and outputs session key $K \in \mathcal {KS}$.

Definition 5

(IND-CCA and IND-CPA Security for KEM) A KEM scheme is IND-CCA-secure for KEM if the following property holds for security parameter $\kappa$; For any PPT adversary $\mathcal {A} = (\mathcal {A}_1, \mathcal {A}_2),\,{\mathbf {Adv}}^\mathrm{ind-cca}=\,|\Pr [r_g \leftarrow \mathcal {RS}_G; (ek, dk) \leftarrow \mathsf {KeyGen}(1^\kappa ,r_g);\,(state) \leftarrow \mathcal {A}_1^{\mathcal {DO}(dk, \cdot )}(ek);\,b \leftarrow \{0, 1\};\,r_e \leftarrow \mathcal {RS}_E; (K^*_0, CT^*_0) \leftarrow \mathsf {EnCap}_{ek}(r_e);\,K^*_1 \leftarrow \mathcal {K};\,b' \leftarrow \,\mathcal {A}_2^{\mathcal {DO}(dk, \cdot )}(ek,\,(K^*_b, CT^*_0),\,state);\,b' = b] - 1/2 |\,\le negl$, where $\mathcal {DO}$ is the decryption oracle, $\mathcal {K}$ is the space of session key and $state$ is state information that $\mathcal {A}$ wants to preserve from $\mathcal {A}_1$ to $\mathcal {A}_2$. $\mathcal {A}$ cannot submit the ciphertext $CT = CT^*_0$ to $\mathcal {DO}$.

We say a KEM scheme is IND-CPA-secure for KEM if $\mathcal {A}$ does not access $\mathcal {DO}$.

Definition 6

(Min-Entropy of KEM Key) A KEM scheme is $k$-min-entropy KEM if for any $ek$, distribution $D_{\mathcal {KS}}$ of variable $K$ defined by $(K,CT) \leftarrow \mathsf {EnCap}_{ek}(r_e)$, distribution $D_{pub}$ of public information and random $r_e \in \mathcal {RS}_E,\,H_{\infty }(D_{\mathcal {KS}} | D_{pub}) \ge k$ holds, where $H_{\infty }$ denotes min-entropy.

3.1.2 Security notion of key derivation function

Let $\textit{KDF} : Salt \times Dom \rightarrow Rng$ be a function with finite domain $Dom$, finite range $Rng$, and a space of non-secret random salt $Salt$.

Definition 7

(Key Derivation Function [33]) We say function $\textit{KDF}$ is a KDF if the following condition holds for a security parameter $\kappa$: For any PPT adversary $\mathcal {A}$ and any distribution $D_{Rng}$ over $Rng$ with $H_{\infty }(D_{Rng}) \ge \kappa ,\,|\Pr [y\,\in _R\,Rng;\,1 \leftarrow \mathcal {A}(y)] - \Pr [x\,\in _R\,Dom;\,s \in _R Salt;\,y\,\leftarrow \,KDF(s,x);\,1\,\leftarrow \,\mathcal {A}(y)]|\,\le \,negl$.

For example, concrete constructions of such a computationally secure KDF are given in [27, 44] from a computational extractor and a PRF.

3.1.3 Security notion of pseudo-random function

Let $\kappa$ be a security parameter and $\mathsf {F}=\{F_\kappa : Dom_\kappa \times \mathcal {FS}_\kappa \rightarrow Rng_\kappa \}_{\kappa }$ be a function family with a family of domains $\{Dom_\kappa \}_{\kappa }$, a family of key spaces $\{\mathcal {FS}_\kappa \}_{\kappa }$ and a family of ranges $\{Rng_\kappa \}_{\kappa }$.

Definition 8

(Pseudo-Random Function) We say that function family $\mathsf {F}=\{F_\kappa \}_{\kappa }$ is a PRF family if for any PPT distinguisher $\mathcal {D},\,{\mathbf {Adv}}^\mathrm{prf}=\,|\Pr [1 \leftarrow \mathcal {D}^{F_\kappa (\cdot )}]\,-\,\Pr [1 \leftarrow \mathcal {D}^{\textit{RF}_\kappa (\cdot )}]|\,\le negl$, where $\textit{RF}_\kappa : Dom_\kappa \rightarrow Rng_\kappa$ is a truly random function.

3.2 Construction

Our construction $({\mathsf {GC}})$ is based on an IND-CCA secure KEM, an IND-CPA secure KEM, PRFs, and a KDF. While the requirements for the underlying building blocks are not stronger than those for the previous generic construction [12, 13], ${\mathsf {GC}}$ achieves stronger security (i.e., ${\mathrm {CK}}^+$ security) without random oracles.

3.2.1 Necessity of min-entropy of KEM key

In the BCGNP construction, a KEM scheme is only assumed to be IND-CCA. However, it is not enough to prove the security. Both parties derive the session key by applying decapsulated KEM keys to a strong randomness extractor before applying them to PRFs. This extractor guarantees to output a statistically indistinguishable value from a uniform randomly chosen element from the same space. It requires as input a (public) seed and a KEM session key with min-entropy $\kappa$, where $\kappa$ is a security parameter. IND-CCA states that no PPT adversary can distinguish the KEM key from a random element, but this does not directly guarantee min-entropy of the KEM session key. Thus, we must also assume that min-entropy of the KEM session key is equal or larger than $\kappa$. This property is not very strong; almost all IND-CCA secure schemes satisfy it. We will discuss later about this property of concrete KEM schemes.

Also, we can improve the efficiency of the session key derivation procedure of the BCGNP construction by using a KDF instead of a strong randomness extractor. On input a value having sufficient min-entropy, a strong randomness extractor outputs a value which is statistically indistinguishable from a uniformly chosen random value. Indeed, such statistical indistinguishability is not necessary to prove the security of our construction. Computational indistinguishability is sufficient, and the KDF [33] is suitable. Such a technique is also used in [64, 65].

3.2.2 Design principle

The main ideas to achieve ${\mathrm {CK}}^+$ security are to use the twisted PRF trick and session-specific key generation.

First, we have to consider resistance to MEX. The most awkward pattern of MEX is the disclosure of ephemeral secret keys of the initiator and the responder. If we use KEM naturally, all randomness used to generate ciphertexts is exposed as ephemeral secret keys; thus, the adversary can obtain encrypted messages without knowing secret keys. Hence, we have to avoid using ephemeral secret keys as randomness of KEM directly. A possible solution is to generate randomness from the static secret key as well as the ephemeral secret key by using a technique such as the ordinary NAXOS trick [46]. Though this trick leads to security against exposure of ephemeral secret keys, the trick must apply an RO to the concatenation of the static and ephemeral secret keys, and it uses the output as a quasi-ephemeral secret key. It is unsuitable for our purpose to construct secure protocols in the StdM. Thus, we use a trick to achieve the same properties as the NAXOS trick but without ROs. We call it the twisted PRF trick.³ This trick uses two PRFs $(F, F')$ with reversing keys; we choose two ephemeral keys $(r, r')$ and compute $F_{{\sigma }}(r) \oplus F'_{r'}(\sigma ')$, where $\sigma \hbox { and }\sigma '$ are static secret keys. The twisted PRF trick is especially effective in the following two scenarios: exposure of both ephemeral secret keys of the initiator and the responder, and exposure of the static secret key of the initiator and the ephemeral secret key of the responder (i.e., corresponding to KCI). If $(r, r')$ is exposed, $F_{{\sigma }}(r)$ cannot be computed without knowing $\sigma$. Similarly, if $\sigma \hbox { and }\sigma '$ are exposed, $F'_{{r'}}(\sigma ')$ cannot be computed without knowing $r'$. In our KEM-based generic construction, the output of the twisted PRF is used as randomness for the encapsulation algorithm.

Next, we have to consider the scenario in which static secret keys are exposed as the attack scenario in wPFS. We cannot achieve a ${\mathrm {CK}}^+$ secure scheme by any combination of KEMs using static secret keys as decapsulation keys against exposure of both static secret keys of the initiator and the responder because an adversary can obtain all information that the parties can obtain by using static secret keys. Our solution is to generate session-specific decapsulation and encapsulation keys. The initiator sends the temporary encapsulation key to the responder, the responder encapsulates a KEM key with the temporary encapsulation key, and the initiator decapsulates the ciphertext. Since this procedure does not depend on the static secret keys, the KEM key is hidden even if both static secret keys of the initiator and the responder are exposed. Note that security of KEM for temporary use only requires IND-CPA. The session-specific key generation is effective for achieving wPFS. Since the responder must wait the session-specific encapsulation key from the initiator, our construction is not one-round protocol (Fig. 1).

As the BCGNP construction [12, 13], we use IND-CCA secure KEM schemes to exchange ciphertexts. The CCA security is necessary to simulate $\mathsf {SessionStateReveal}$ queries in the security proof. When we prove security in the case where ephemeral secret keys are exposed, the simulator needs to embed the challenge ciphertext in the ephemeral public key in the test session. Then, the static secret key to decrypt the challenge ciphertext is not known; that is, the simulator must respond to the $\mathsf {SessionStateReveal}$ query for a session owned by the same parties as the test session without knowing the static secret key. Hence, the simulator needs the power of the decryption oracle to obtain intermediate computation results corresponding to the $\mathsf {SessionStateReveal}$ query.

Fig. 1

Generic construction ${\mathsf {GC}}$

3.2.3 Generic construction ${\mathsf {GC}}$

The protocol of ${\mathsf {GC}}$ from KEMs $(\mathsf {KeyGen},\,\mathsf {EnCap},\,\mathsf {DeCap})$ and $(\mathsf {wKeyGen},\,\mathsf {wEnCap},\, \mathsf {wDeCap})$ is as follows.

Public parameters Let $\kappa$ be the security parameter, $F, F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and $G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$ be pseudo-random functions, where $\mathcal {FS}$ is the key space of PRFs $(|\mathcal {FS}| = \kappa )$, $\mathcal {RS}_E$ is the randomness space of encapsulation algorithms, and $\mathcal {RS}_G$ is the randomness space of key generation algorithms, and let $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ be a KDF with a non-secret random salt $s \in Salt$, where $Salt$ is the salt space and $\mathcal {KS}$ is a space of KEM session keys. These are provided as some of the public parameters.

Secret and public keys Party $U_P$ randomly selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa$ and $r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$.

Key exchange Party $U_A$ with secret and public keys $((dk_{A,1},\,\sigma _A, \sigma _A'),\,ek_{A})$ as the initiator, and party $U_B$ with secret and public keys $((dk_{B,1}, \sigma _B, \sigma _B'),ek_{B})$ as the responder, perform the following two-pass key exchange protocol.

• 1. Party $U_A$ randomly chooses ephemeral secret keys $r_{A} \in _R \{0,1\}^\kappa ,\,r'_{A} \in _R \mathcal {FS}\hbox { and }r_{TA} \in \mathcal {RS}_G$. Party $U_A$ computes $(CT_{A},\,K_{A})\,\leftarrow \,\mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus F_{r'_{A}}'(\sigma _A'))$ ⁴ and $(ek_{T}, dk_{T})\,\leftarrow \,\mathsf {wKeyGen}(1^\kappa , r_{TA})$ and sends $(U_A, U_B, CT_{A},\,ek_{T})$ to party $U_B$.

• 2. Upon receiving $(U_A, U_B, CT_{A},ek_{T})$, party $U_B$ chooses the ephemeral secret keys $r_{B} \in _R \{0,1\}^\kappa ,\,r'_{B} \in _R \mathcal {FS}$ and $r_{TB} \in _R \mathcal {RS}_E$, computes $(CT_{B},\,K_{B})\,\leftarrow \,\mathsf {EnCap}_{ek_{A}}(F_{{\sigma _B}}(r_{B})\,\oplus \,F'_{{r'_{B}}}(\sigma _B'))$ and $(CT_{T},\,K_{T})\,\leftarrow \,\mathsf {wEnCap}_{ek_{T}}(r_{TB})$, and sends $(U_A, U_B, CT_{B},\,CT_{T})$ to party $U_A$. Party $U_B$ computes $K_{A} \leftarrow \mathsf {DeCap}_{dk_{B}}(CT_{A}),\,K'_{1} \leftarrow KDF(s, K_{A}),\,K'_{2} \leftarrow KDF(s, K_{B})\hbox { and }K'_{3} \leftarrow KDF(s, K_{T})$, sets the session transcript $\mathsf {ST}\,=\,(U_A, U_B,\,ek_{A},\,ek_{B},\,CT_{A},\,ek_{T},\,CT_{B},\,CT_{T})$ and the session key $\textit{SK}= G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, completes the session, and erases all session states.

• 3. Upon receiving $(U_A, U_B, CT_{B},CT_{T})$, party $U_A$ computes $K_{B}\,\leftarrow \,\mathsf {DeCap}_{dk_{A}}(CT_{B}),\,K_{T} \leftarrow \mathsf {wDeCap}_{dk_{T}}(CT_{T}),\,K'_{1}\,\leftarrow \,KDF(s, K_{A}),\,K'_{2} \leftarrow KDF(s, K_{B})$ and $K'_{3} \leftarrow KDF(s, K_{T})$, sets the session transcript $\mathsf {ST}\,=\,(U_A, U_B, ek_{A},\,ek_{B},\,CT_{A},\,ek_{T},\,CT_{B},\,CT_{T})$ and the session key $\textit{SK}= G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, completes the session, and erases all session states.

The session state of a session owned by $U_A$ contains ephemeral secret keys $(r_{A}, r_{TA})$, encapsulated KEM key $K_{A}$ and ad-hoc decryption key $dk_{T}$. Other information that is computed after receiving the message from the peer is immediately erased when the session key is established. Similarly, the session state of a session owned by $U_B$ contains ephemeral secret keys $(r_{B}, r_{TB})$ and encapsulated KEM keys $K_{B}\hbox { and }K_T$.

Other intermediate values (e.g., decapsulated KEM keys, and outputs of KDF) are not contained in session state. After receiving the message from the peer all intermediate computations are executed without stopping, and such values are immediately erased after finishing the session. Boyd et al. [12] showed that protocols based on KEM would be trivially broken if an adversary learned these values by $\mathsf {SessionStateReveal}$.

Ephemeral secret keys could be erased after generating encapsulated KEM keys. However, in our construction, it is enough to erase such information on the end of the session (i.e., on generating the session key). Hence, we deal with ephemeral secret keys as a part of session state.

If a $\mathsf {SessionStateReveal}$ query is posed to a non-completed session, $r_{A}, r_{TA},\,K_{A}$ and $dk_{T}$ (or $r_{B}, r_{TB},\,K_{B}\hbox { and }K_{T}$) are returned.

Remark 1

Obviously, we can use arbitrary combinations of KEM schemes in the generic construction. This means that each party can rely on a different assumption from the peer. Since our construction does not contain any direct operation between derivatives of KEM schemes, it is no problem that randomness spaces, public keys, or ciphertext are distinct from each other.

3.3 Security

We show the following theorem.

Theorem 1

If $(\mathsf {KeyGen}, \mathsf {EnCap}, \mathsf {DeCap})$ is IND-CCA secure KEM and is $\kappa$-min-entropy KEM, $(\mathsf {wKeyGen}, \mathsf {wEnCap},\,\mathsf {wDeCap})$ is IND-CPA secure KEM and is $\kappa$-min-entropy KEM, $F, F', G$ are PRFs, and $KDF$ is a KDF, then AKE construction ${\mathsf {GC}}$ is ${\mathrm {CK}}^+$-secure.

The proof of Theorem 1 is shown in Appendix 1. Here, we give an overview of the security proof.

We have to consider the following four exposure patterns in the ${\mathrm {CK}}^+$ security model (matching cases):

2-(c):

the static secret key of the initiator and the ephemeral secret key of the responder

2-(d):

both ephemeral secret keys

2-(e):

both static secret keys

2-(f):

the ephemeral secret key of the initiator and the static secret key of the responder

In case 2-(c), $K_{A}$ is protected by the security of $CT_{A}$ because $r'_{A}$ is not exposed; therefore, $F'_{{r'_{A}}}(\sigma _A')$ is hidden and $dk_{B}$ is not exposed. In case 2-(d), $K_{A}\hbox { and }K_{B}$ are protected by the security of $CT_{A}\hbox { and }CT_{B}$ because $\sigma _{A}\hbox { and }\sigma _{B}$ are not exposed; therefore, $F_{{\sigma _A}}(r_{A})\hbox { and }F_{{\sigma _B}}(r_{B})$ are hidden and $dk_{A}\hbox { and }dk_{B}$ are not exposed. In case 2-(e), $K_{T}$ is protected by the security of $CT_{T}$ because $dk_{T}\hbox { and }r_{TB}$ are not exposed. In case 2-(f), $K_{B}$ is protected by the security of $CT_{B}$ because $r'_{B}$ is not exposed; therefore, $F'_{{r'_{B}}}(\sigma _B')$ is hidden and $dk_{A}$ is not exposed. Then, we transform the ${\mathrm {CK}}^+$ security game since the session key in the test session is randomly distributed. First, we change part of the twisted PRF in the test session into a random function because the key of part of the twisted PRF is hidden from the adversary; therefore, the randomness of the protected KEM can be randomly distributed. Second, we change the protected KEM key into a random key for each pattern; therefore, the input of $KDF$ is randomly distributed and has sufficient min-entropy. Third, we change the output of $KDF$ into randomly chosen values. Finally, we change one of the PRFs (corresponding to the protected KEM) into a random function. Therefore, the session key in the test session is randomly distributed; thus, there is no advantage to the adversary. We can show a similar proof in non-matching cases.

3.4 Instantiations

In this section, from our generic construction ${\mathsf {GC}}$, we provide AKE protocols as concrete instantiations based on various problems.

3.4.1 Diffie–Hellman-based

We can achieve various AKE schemes as concrete instantiations based on the hardness of the DH problem and its variants. These are derived from the generic construction ${\mathsf {GC}}$ in Sect. 3. For example, we can apply efficient IND-CCA KEM schemes to ${\mathsf {GC}}$ from the decisional DH [21, 45] (DDH), computational DH [35, 36], hashed DH [41] and bilinear DH assumptions [15].

We can easily show that these schemes have $\kappa$-min-entropy KEM keys. The KEM part of the Cramer-Shoup PKE consists of $g_1^{zr} \in G$, where $G$ is a finite cyclic group of order prime $p,\,g_1^z$ is part of $ek$, and $r$ is uniformly chosen randomness, and $|r|$ is $2\kappa$. Thus, $g_1^{zr}$ has min-entropy larger than $\kappa$. Similarly, other schemes are also $\kappa$-min-entropy KEM.

The significant advantage of our instantiations in the StdM is reasonable assumption. First, HMQV satisfies the same security model as our construction. However, it requires the KEA1 assumption and relies on ROs. Since it has been criticized, in particular because the KEA1 assumption does not appear to be “efficiently falsifiable” as Naor put it [54], this assumption is quite undesirable. Also, it was shown that there exist some protocols that are secure in the ROM but are insecure if ROs are replaced by any specific function [16]. A disadvantage of our construction to HMQV is that HMQV is a one-round protocol but our scheme is not. One-round protocols mean that the initiator and the responder can send their messages independently and simultaneously. Conversely, in our scheme, the responder must wait to receive the message from the initiator. Next, the AKE scheme by Okamoto [56] is secure in the StdM. However, it is not proved in the ${\mathrm {CK}}^+$ model and needs to assume existence of $\pi$PRF. $\pi$PRF is a stronger primitive than ordinary PRF, and it is not known how to construct $\pi$PRF concretely. On the contrary, our instantiations only require the standard notions of KEM and PRF security. Moreover, the BCGNP construction [12, 13] is secure in the StdM with standard assumption. However, the security is not proved in the ${\mathrm {CK}}^+$ model.⁵ Thus, DH-based AKE schemes from ${\mathsf {GC}}$ are first ${\mathrm {CK}}^+$ secure schemes in the StdM with standard assumptions.

For example, our scheme can be instantiated with the Cramer-Shoup KEM [22] as an IND-CCA KEM, and with the ElGamal KEM as an IND-CPA KEM under the DDH assumption. Communication complexity (for two parties) of this instantiation is $8|p|$, where $|p|$ is the length of a group element. Computational complexity (for two parties) of this instantiation is $4$ multi-exponentiations and $12$ regular exponentiations (all symmetric operations such as hash function/KDF/PRF and multiplications are ignored). We show a comparison between this instantiation and previous schemes in Table 3.

Table 3 Comparison of previous DH-based schemes and an instantiation of our scheme

3.4.2 Factoring-based

We can achieve several new AKE protocols as concrete instantiations based on the hardness of integer factorization and its variants such as the RSA problem.

Some instantiations in the StdM are based on the hardness of the integer factorization problem. The Hofheinz-Kiltz PKE [37] and the Mei-Li-Lu-Jia PKE [51] are IND-CCA secure in the StdM under the factoring assumption. Furthermore, by applying the fact [38] that if a scheme is secure under the CDH assumption in $\mathbb {Z}_N^*$, it is also secure under the factoring assumption, we can obtain more efficient factoring-based KEM schemes from IND-CCA secure KEM under the CDH assumption such as [35, 36]. Thus, we can obtain first ${\mathrm {CK}}^+$ secure AKE protocols in the StdM under the integer factorization assumption. Also, we have other instantiations based on the hardness of RSA inversion. By applying the Chevallier-Mames-Joye PKE [20] and the Kiltz-Mohassel-O’Neill PKE [42], which are IND-CCA secure in the StdM under the instance-independent RSA assumption to ${\mathsf {GC}}$, we can obtain first ${\mathrm {CK}}^+$ secure AKE protocols in the StdM under the RSA-type assumption.

We can regard a message in PKE as a KEM key when the message space is larger than $\kappa$ and messages are uniformly chosen randomness. In this case, it is obvious that such a KEM scheme is $\kappa$-min-entropy KEM.

3.4.3 Code-based

We can achieve new AKE protocols as concrete instantiations based on code-based problems.

For the AKE protocol in the StdM, we can apply Dowsley et al.’s PKE [29] that is IND-CCA secure in the StdM under the McEliece and LPN assumptions to ${\mathsf {GC}}$. (See Ref. [29] for definitions of these assumptions.) This is the first ${\mathrm {CK}}^+$ secure AKE protocol without ROs based on a code-based problem.

As for factoring-based PKE, code-based PKE schemes are also $\kappa$-min-entropy KEM when the message space is larger than $\kappa$ and messages are uniformly chosen randomness.

Remark 2

Bernstein et al. [7] estimated the size of a public key of the original McEliece at about $2$ Mbits for 128-bit security. If we employ “wild” McEliece by Bernstein et al. [6] rather than the original McEliece PKE, the size of the public key is reduced to $750$K bits. Our generic construction contains the public key of the KEM from the temporary key generation in the first round message. If the randomized McEliece PKE by Nojima et al. [55] is employed as the IND-CPA secure KEM, which is IND-CPA secure and requires the same size for the public key as the original, the communication complexity of the resultant AKE scheme is high. However, the way to construct an efficient and ${\mathrm {CK}}^+$ secure AKE scheme from codes is an open problem.

3.4.4 Lattice-based

We also achieve new concrete AKE protocols based on the worst-case hardness of the (ring-)LWE problems derived from our generic constructions.

PKE schemes [1, 2, 18, 49, 52, 57, 59, 62] which are IND-CCA secure in the StdM are easily converted into IND-CCA secure KEM schemes. Also, PRFs are obtained from one-way functions [3, 48, 53, 58] and directly constructed from the (ring-)LWE assumptions with sub-exponential parameters [4]. Thus, by applying these building blocks to ${\mathsf {GC}}$, we can obtain first ${\mathrm {CK}}^+$ secure AKE protocols in the StdM under the (ring-)LWE assumption. Unfortunately, the obtained AKE protocols are still theoretical since these PKE schemes require huge keys, say, of the quadratic or cubic order of the security parameter, and thus, an efficient and direct construction of PRFs from the (ring-)LWE assumption with polynomial parameters has not yet been achieved.

As for factoring-based PKE, lattice-based PKE schemes are also $\kappa$-min-entropy KEM when the message space is larger than $\kappa$ and messages are uniformly chosen randomness.

4 Generic ID-AKE construction from IB-KEM without random oracles

In this section, we propose a generic construction of ${\hbox {id-CK}^+}$-secure ID-AKE from IB-KEM.

4.1 Preliminaries

Here, we recall the definition of IND-sID-CCA/CPA security (selective-ID IND-CCA/CPA security) for IB-KEM, and min-entropy of KEM keys as follows.

Definition 9

(Model for ID-based KEM Schemes) A IB-KEM scheme consists of the following 4-tuple $(\mathsf{MKeyGen},\mathsf {KeyDer},\mathsf {EnCap},\mathsf {DeCap})$:

$(mpk,msk) \leftarrow \mathsf{MKeyGen}(1^\kappa ,r_g)$ ::

a key generation algorithm which on inputs $1^\kappa \hbox { and }r_g \in \mathcal {RS}_G$, where $\kappa$ is the security parameter and $\mathcal {RS}_G$ is a randomness space, outputs master public key and secret key $(mpk,msk)$.

$dk \leftarrow \mathsf {KeyDer}(mpk,msk,ID,r_g)$ ::

a key derivation algorithm which on inputs master public and secret keys $(mpk,msk)$, identity string $\textit{ID}\hbox { and }r_g \in \mathcal {RS}_G$, where $\mathcal {RS}_G$ is a randomness space, outputs decapsulation key $dk$ corresponding to $\textit{ID}$.

$(K,CT) \leftarrow \mathsf {EnCap}_{mpk,ID}(r_e)$ ::

an encryption algorithm which takes as inputs master public key $mpk$, identity string $\textit{ID}$, and $r_e \in \mathcal {RS}_E$, outputs session key $K \in \mathcal {KS}$ and ciphertext $CT \in \mathcal {CS}$, where $\mathcal {RS}_E$ is a randomness space, $\mathcal {KS}$ is a session key space, and $\mathcal {CS}$ is a ciphertext space.

$K \leftarrow \mathsf {DeCap}_{dk}(CT)$ ::

a decryption algorithm which takes as inputs decapsulation key $dk$ and ciphertext $CT \in \mathcal {CS}$, outputs session key $K \in \mathcal {KS}$.

Here, we recall the definition of IND-sID-CCA/CPA security (selective-ID IND-CCA/CPA security) for IB-KEM as follows.

Definition 10

(IND-CCA/CPA security for ID-based KEM) A IB-KEM scheme is $(t, \epsilon )$-IND-ID-CCA-secure for IB-KEM if the following property holds for security parameter $\kappa$; For any adversary $\mathcal {A} = (\mathcal {A}_1, \mathcal {A}_2)$ with a time-complexity at most $t,\,{\mathbf {Adv}}^\mathrm{id-ind-cca}=\,|\Pr [(mpk,msk) \leftarrow \,\mathsf{MKeyGen}(1^\kappa ,r_g);$ $(ID^*,state) \leftarrow \,\mathcal {A}_1^{\mathcal {DO}(\cdot , \cdot ), \mathcal {KO}(msk,\cdot )}(mpk);\,b \leftarrow \{0, 1\};\,(K^*_0, CT^*_0) \leftarrow \,\mathsf {EnCap}_{mpk,ID^*}(r);\,K^*_1 \leftarrow \,\mathcal {K};\,b' \leftarrow \,\mathcal {A}_2^{\mathcal {DO}(\cdot , \cdot ), \mathcal {KO}(msk, \cdot )}\,(mpk,\,(K^*_b, CT^*_0),state);\,b' = b] - 1/2 |\,\le \epsilon$, where $\mathcal {DO}(ID,CT)$ is the decryption oracle, $\mathcal {KO}(msk,ID)$ is the key derivation oracle, $\mathcal {K}$ is the space of session key, $state$ is state information which $\mathcal {A}$ wants to preserve from $\mathcal {A}_1$ to $\mathcal {A}_2\hbox { and }\mathcal {A}$ runs in at most $t$ steps. $\mathcal {A}$ cannot make query $\mathcal {DO}(ID^*,CT^*_0)$, and cannot make query $\mathcal {KO}(msk,ID^*)$.

We say IB-KEM scheme is IND-CPA secure if adversary $\mathcal {A}$ cannot access to the decryption oracle $\mathcal {DO}$.

We say IB-KEM scheme is IND-sID-CCA/CPA secure if adversary $\mathcal {A}$ outputs target identity string $ID^*$ at the beginning of the game.

We define the notion of $k$-min-entropy for KEM keys as follows.

Definition 11

(Min-Entropy of KEM Keys) A IB-KEM scheme is $k$-min-entropy IB-KEM if for any $ID,\,mpk$, distribution $D_{\mathcal {KS}}$ of variable $K$ defined by $(K,CT) \leftarrow \mathsf {EnCap}_{mpk,ID}(r_e)$, distribution $D_{pub}$ of public information and random $r_e \in \mathcal {RS}_E,\,H_{\infty }(D_{\mathcal {KS}} | D_{pub}) \ge k$ holds, where $H_{\infty }$ denotes min-entropy.

4.2 Construction

We propose a generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ of ${\hbox {id-CK}^+}$ secure ID-AKE without ROs from IND-sID-CCA secure IB-KEM, IND-CPA secure KEM, PRFs, and a KDF.

4.2.1 Design principle

To modify the generic construction ${\mathsf {GC}}$ of PKI-based AKE, we must remove static public keys from the protocol. Thus, we use IND-sID-CCA secure IB-KEM instead of IND-CCA secure KEM. In initialization, each party receives a static secret key based on the ID from the KGC. To send $CT_A$ or $CT_B$ each party encapsulates a KEM session key with the ID of the peer by using the encapsulation algorithm of IB-KEM. Hence, static public keys are not necessary. IND-CPA secure KEM for session-specific key generation can be still used in the ID-based setting because it is not necessary to put any information to static public keys in order to generate $ek_T\hbox { and }CT_T$.

The reason that IND-sID-CCA security is enough for ID-AKE (i.e., the full-ID security is not necessary) is that our model supposes that the maximum number of parties and session is polynomially bounded in the security parameter. In the security proof (Appendix 2), the target party and session can be fixed before the hybrid experiment using IND-sID-CCA security. Hence, the ID of the target party is known to the adversary for IB-KEM, and IND-sID-CCA security is enough (Fig. 2).

4.2.2 Generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$

The protocol of ${\mathsf {ID}\text {-}\mathsf {GC}}$ from IB-KEM $(\mathsf{MKeyGen},\mathsf {KeyDer},\mathsf {EnCap},\mathsf {DeCap})$ and KEM $(\mathsf {wKeyGen},\,\mathsf {wEnCap},\mathsf {wDeCap})$ is provided as follows.

Fig. 2

Generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$

Public parameters Let $\kappa$ be the security parameter, $F, F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and $G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$ be pseudo-random functions, where $\mathcal {FS}$ is the key space of PRFs $(|\mathcal {FS}| = \kappa )$, $\mathcal {RS}_E$ is the randomness space of encapsulation algorithms, and $\mathcal {RS}_G$ is the randomness space of key generation algorithms, and let $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ be a KDF a non-secret random salt $s \in Salt$, where $Salt$ is the salt space and $\mathcal {KS}$ is a space of KEM session keys. These are provided as some of the public parameters.

Master secret and public keys The KGC randomly selects $r \in \mathcal {RS}_G$, and generates master public and secret keys $(mpk,msk) \leftarrow \mathsf{MKeyGen}(1^\kappa , r)$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf{MKeyGen}$.

Secret key For party $U_P$, the KGC randomly selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r' \in \mathcal {RS}_G$, and runs the key derivation algorithm $dk_{P} \leftarrow \mathsf {KeyDer}(mpk,msk,U_P,\,r')$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf {KeyDer}$. Party $U_P$’s static secret key is $(dk_{P},\sigma _P, \sigma _P')$.

Key exchange Party $U_A$ with secret and public keys $((dk_{A,1},\,\sigma _A, \sigma _A'),\,ek_{A})$ as the initiator, and party $U_B$ with secret and public keys $((dk_{B,1}, \sigma _B, \sigma _B'),ek_{B})$ as the responder, perform the following two-pass key exchange protocol.

• 1. Party $U_A$ randomly chooses ephemeral secret keys $r_{A} \in _R \{0,1\}^\kappa ,\,r'_{A} \in _R \mathcal {FS}\hbox { and }r_{TA} \in \mathcal {RS}_G$. Party $U_A$ computes $(CT_{A},\,K_{A})\,\leftarrow \,\mathsf {EnCap}_{mpk,U_B}(F_{{\sigma _A}}(r_{A}) \oplus F_{r'_{A}}'(\sigma _A'))$ and $(ek_{T}, dk_{T})\,\leftarrow \,\mathsf {wKeyGen}(1^\kappa , r_{TA})$ and sends $(U_A, U_B, CT_{A},\,ek_{T})$ to party $U_B$.

• 2. Upon receiving $(U_A, U_B, CT_{A},ek_{T})$, party $U_B$ chooses the ephemeral secret keys $r_{B} \in _R \{0,1\}^\kappa ,\,r'_{B} \in _R \mathcal {FS}\hbox { and }r_{TB} \in _R \mathcal {RS}_E$, computes $(CT_{B},\,K_{B})\,\leftarrow \,\mathsf {EnCap}_{mpk,U_{A}}(F_{{\sigma _B}} (r_{B})\,\oplus \,F'_{{r'_{B}}}(\sigma _B'))$ and $(CT_{T},\,K_{T})\,\leftarrow \,\mathsf {wEnCap}_{ek_{T}}(r_{TB})$, and sends $(U_A, U_B, CT_{B},\,CT_{T})$ to party $U_A$. Party $U_B$ computes $K_{A} \leftarrow \mathsf {DeCap}_{dk_{B}}(CT_{A}),\,K'_{1} \leftarrow KDF(s, K_{A}),\,K'_{2} \leftarrow KDF(s, K_{B})\hbox { and }K'_{3} \leftarrow KDF(s, K_{T})$, sets the session transcript $\mathsf {ST}\,=\,(U_A, U_B,\,ek_{A},\,ek_{B},\,CT_{A},\,ek_{T},\,CT_{B},\,CT_{T})$ and the session key $\textit{SK}= G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, completes the session, and erases all session states.

• 3. Upon receiving $(U_A, U_B, CT_{B},CT_{T})$, party $U_A$ computes $K_{B}\,\leftarrow \,\mathsf {DeCap}_{dk_{A}}(CT_{B}),\,K_{T} \leftarrow \mathsf {wDeCap}_{dk_{T}}(CT_{T}),\,K'_{1}\,\leftarrow \,KDF(s, K_{A}),\,K'_{2} \leftarrow KDF(s, K_{B})\hbox { and }K'_{3} \leftarrow KDF(s, K_{T})$, sets the session transcript $\mathsf {ST}\,=\,(U_A, U_B, ek_{A},\,ek_{B},\,CT_{A},\,ek_{T},\,CT_{B},\,CT_{T})$ and the session key $\textit{SK}= G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, completes the session, and erases all session states.

The session state of a session owned by $U_A$ contains ephemeral secret keys $(r_{A}, r_{TA})$, encapsulated KEM key $K_{A}$ and ad-hoc decryption key $dk_{T}$. Other information that is computed after receiving the message from the peer is immediately erased when the session key is established. Similarly, the session state of a session owned by $U_B$ contains ephemeral secret keys $(r_{B}, r_{TB})$ and encapsulated KEM keys $K_{B}\hbox { and }K_T$.

4.3 Security

The generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ is ${\hbox {id-CK}^+}$ secure ID-AKE without random oracles as follows.

Theorem 2

If $(\mathsf{MKeyGen},\mathsf {KeyDer},\mathsf {EnCap},\mathsf {DeCap})$ is IND-sID-CCA secure and $\kappa$-min-entropy IB-KEM, $(\mathsf {wKeyGen},\mathsf {wEnCap},\mathsf {wDeCap})$ is IND-CPA secure and $\kappa$-min-entropy KEM, $F, F', G$ are PRFs, and $KDF$ is a KDF, then ID-AKE construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ is ${\hbox {id-CK}^+}$ secure.

The proof of Theorem 2 is shown in Appendix 2. Here, we give an overview of the security proof.

In addition to the case of Theorem 1, we have to consider exposure of the master secret key according to Definition 3 in the ${\hbox {id-CK}^+}$ security model: Other cases are almost same as Theorem 1.

If $msk$ is revealed, $dk_A\hbox { and }dk_B$ are also revealed, and an adversary can know $K_A\hbox { and }K_B$. However, $K_T$ is protected by the security of $CT_{T}$ because $dk_{T}\hbox { and }r_{TB}$ are not exposed because these values are generated only from ephemeral secret keys. We can prove the case by a similar way as Theorem 1.

4.4 Instantiations

In this section, from our generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$, we provide some ID-AKE protocols as concrete instantiations based on the lattices and pairings.

4.4.1 Lattice-based instantiations

From our generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ in Sect. 4, we achieve new concrete ID-AKE protocols from the (ring-)LWE assumption.⁶

The existing IND-sID-CPA secure HIBE schemes [1, 18, 47, 49] in the StdM are easily converted into IND-sID-CCA secure IBE schemes by the CHK conversion [10] and they yield IND-sID-CCA secure IB-KEM schemes. Also, PRFs are obtained from one-way functions [3, 48, 53, 58] under the (ring-)LWE assumption with standard parameters and a direct construction [4] from the (ring-)LWE assumption with sub-exponential parameters. Applying our generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ with these building blocks, we can obtain first ${\hbox {id-CK}^+}$ secure ID-AKE protocols in the StdM under the (ring-)LWE assumption. We note that the obtained IB-KEM scheme from [47] enjoys quasi-linear-time key-generation, encapsulation, and decapsulation.

We show a comparison between this instantiation and previous schemes in Table 4. We instantiate an IND-sID-CCA secure IBE with message space $\{0,1\}^\kappa$ from the LWE (resp. ring-LWE) assumption by applying the CHK conversion to the 2-level IND-sID-CPA secure IBE scheme in [1, 52] (resp. its ring-LWE version). Here, its ciphertext length is $| CT_{\mathrm {cca},\mathrm {LWE}} |, | CT_{\mathrm {cca},\mathrm {rLWE}} | = (m+2\kappa \log _2(q)+\kappa )\log _2(q) + | \sigma | + | ovk | = \tilde{O}(\kappa )$.

We adopt the Regev encryption scheme [60] with message space $\{0,1\}^\kappa$ (resp. the LPR10 encryption scheme [49]) as an IND-CPA secure PKE from the LWE (resp. ring-LWE) assumption. $|PK_{\mathrm {cpa},\mathrm {LWE}} | = (m + \kappa ) \kappa \log _2(q) = \tilde{O}(\kappa ^2)\hbox { and }| PK_{\mathrm {cpa},\mathrm {rLWE}}| = 2\kappa \log _2(q) \tilde{O}(\kappa )$. $|CT_{\mathrm {cpa},\mathrm {LWE}} | = (m + \kappa ) \log _2(q) = \tilde{O}(\kappa )\hbox { and }| CT_{\mathrm {cpa},\mathrm {rLWE}}| = 2\kappa \log _2(q) = \tilde{O}(\kappa )$.

Table 4 Comparison of previous lattice-based schemes and an instantiation of our scheme

4.4.2 Pairing-based instantiations

From our generic construction ${\mathsf {ID}\text {-}\mathsf {GC}}$ in Sect. 4, we can achieve various ID-AKE schemes as concrete instantiations based on the hardness of the bilinear DH (BDH) problem and its variants. For example, we can apply efficient IND-sID-CCA IB-KEM schemes to ${\mathsf {ID}\text {-}\mathsf {GC}}$ from the decisional BDH (DBDH), decisional linear (DLIN) or the DBDH Inversion (DBDHI) [8] with the BCHK transformation [10].

We can easily show that these schemes are $\kappa$-min-entropy KEM. The KEM part of the Boneh-Boyen IBE consists of $e(g, \hat{g})^{\alpha \beta s} \in G_T$, where $G_T$ is a finite cyclic bilinear group of order prime $p,\,e(g, \hat{g})^{\alpha \beta }$ is part of public parameters, and $s$ is uniformly chosen randomness, and $|s|$ is larger than $\kappa$. Thus, $e(g, \hat{g})^{\alpha \beta s}$ has min-entropy larger than $\kappa$.

The significant advantage of our instantiations is security in the StdM. Most of previous ID-AKE schemes [19, 30, 31, 39] are proved in the ROM. Moreover, though the generic construction of ID-AKE in [12, 13] is secure in the StdM, its security is not proved in the ${\hbox {id-CK}^+}$ model. Thus, pairing-based ID-AKE schemes from ${\mathsf {ID}\text {-}\mathsf {GC}}$ are first ${\hbox {id-CK}^+}$ secure schemes in the StdM.

For example, our scheme can be instantiated with the Boyen-Mei-Waters ID-based KEM [15] as an IND-sID-CCA KEM under the DBDH assumption, and with the ElGamal KEM as an IND-CPA KEM under the DDH assumption. Communication complexity (for two parties) of this instantiation is $8|p|$, where $|p|$ is the length of a group element. Computational complexity (for two parties) of this instantiation is $8$ pairings and $14$ regular exponentiations (all symmetric operations such as hash function/KDF/PRF and multiplications are ignored). We show a comparison between this instantiation and previous schemes in Table 5.

Table 5 Comparison of previous pairing-based schemes and an instantiation of our scheme

Appendices

Appendix 1: Proof of Theorem 1

In the experiment of ${\mathrm {CK}}^+$ security, we suppose that $\mathsf {sid}^*$ is the session identity for the test session, and that there are $N$ users and at most $\ell$ sessions are activated. Let $\kappa$ be the security parameter, and let $\mathcal {A}$ be a PPT (in $\kappa$) bounded adversary. $Suc$ denotes the event that $\mathcal {A}$ wins. We consider the following events that cover all cases of the behavior of $\mathcal {A}$.

• Let $E_1$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the initiator and the static secret key of the initiator is given to $\mathcal {A}$.

• Let $E_2$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the initiator and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

• Let $E_3$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the responder and the static secret key of the responder is given to $\mathcal {A}$.

• Let $E_4$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the responder and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

• Let $E_5$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and both static secret keys of the initiator and the responder are given to $\mathcal {A}$.

• Let $E_6$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and both ephemeral secret keys of $\mathsf {sid}^*\hbox { and }\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

• Let $E_7$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and the static secret key of the owner of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

• Let $E_8$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and the ephemeral secret key of $\mathsf {sid}^*$ and the static secret key of the owner of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

To finish the proof, we investigate events $E_{i} \wedge Suc\,(i=1,\dots ,8)$ that cover all cases of event $Suc$.

1.1 Appendix 1.1: Event $E_{1} \wedge Suc$

We change the interface of oracle queries and the computation of the session key. These instances are gradually changed over seven hybrid experiments, depending on specific sub-cases. In the last hybrid experiment, the session key in the test session does not contain information of the bit $b$. Thus, the adversary clearly only output a random guess. We denote these hybrid experiments by $\mathbf{H}_0, \dots , \mathbf{H}_6$ and the advantage of the adversary $\mathcal {A}$ when participating in experiment $\mathbf{H}_i$ by ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_i)$.

Hybrid experiment $\mathbf{H}_0$: This experiment denotes the real experiment for ${\mathrm {CK}}^+$ security and in this experiment the environment for $\mathcal {A}$ is as defined in the protocol. Thus, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)$ is the same as the advantage of the real experiment.

Hybrid experiment $\mathbf{H}_1$: In this experiment, if session identities in two sessions are identical, the experiment halts.

When two ciphertexts from different randomness are identical and two public keys from different randomness are identical, session identities in two sessions are also identical. In the IND-CCA secure KEM, such an event occurs with negligible probability. Thus, $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)| \le negl$.

Hybrid experiment $\mathbf{H}_2$: In this experiment, the experiment selects a party $U_A$ and integer $i \in [1,\ell ]$ randomly in advance. If $\mathcal {A}$ poses $\mathsf {Test}$ query to a session except $i$-th session of $U_A$, the experiment halts.

Since guess of the test session matches with $\mathcal {A}$’s choice with probability $1/N^2\ell ,\,{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2)\,\ge 1/N^2\ell \cdot {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1)$.

Hybrid experiment $\mathbf{H}_3$: In this experiment, the computation of $(CT^*_{A},K^*_{A})$ in the test session is changed. Instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, it is changed as $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus RF(\sigma _A'))$, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct a distinguisher $\mathcal {D}$ between PRF $F^* : \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$ and a random function $RF$ from $\mathcal {A}$ in $\mathbf{H}_2$ or $\mathbf{H}_3$. $\mathcal {D}$ performs the following steps.

Setup $\mathcal {D}$ chooses PRF $F : \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E\hbox { and }G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. Also, $\mathcal {D}$ embeds $F^*$ into $F'$. These are provided as a part of the public parameters. Also, $\mathcal {D}$ sets all $N$ users’ static secret and public keys. $\mathcal {D}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$. $U_A$’s static key $(dk_{A}, \sigma _A, \sigma _A')$ is given to $\mathcal {A}$.

Next, ${\mathcal {D}}$ sets the ephemeral public key of $i$-th session of $U_A$ (i.e., the test session) as follows: $\mathcal {D}$ selects ephemeral secret keys $r^*_{A} \in \{0,1\}^\kappa ,\,r_{A}'^* \in \mathcal {FS}\hbox { and }r^*_{TA} \in \mathcal {RS}_G$ randomly. Then, $\mathcal {D}$ poses $\sigma _A'$ to his oracle (i.e., $F^*$ or a random function $RF$) and obtains $x \in \mathcal {RS}_E$. $\mathcal {D}$ computes $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r^*_{A}) \oplus x)$ and $(dk^*_{T},ek^*_{T}) \leftarrow \mathsf {KeyGen}(r^*_{TA})$, and sets the ephemeral public key $(CT^*_{A},ek^*_{T})$ of $i$-th session of $U_A$.

Simulation $\mathcal {D}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {D}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: If $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {D}$ returns the ephemeral public key $(CT^*_{A},ek^*_{T})$ computed in the setup. Otherwise, $\mathcal {D}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: $\mathcal {D}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}}, CT_{T}))$ is not recorded, $\mathcal {D}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Otherwise, $\mathcal {D}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {D}$ returns an error message.

  • (b) Otherwise, $\mathcal {D}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {D}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {D}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {D}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b' = 0,\,\mathcal {D}$ outputs that the oracle is the PRF $F^*$. Otherwise, $\mathcal {D}$ outputs that the oracle is a random function $RF$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {D}$ is same as the experiment $\mathbf{H}_2$ if the oracle is the PRF $F^*$. Otherwise, the simulation by $\mathcal {D}$ is same as the experiment $\mathbf{H}_3$. Thus, if the advantage of $\mathcal {D}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2)| \le negl$.

Hybrid experiment $\mathbf{H}_4$: In this experiment, the computation of $K^*_{A}$ in the test session is changed again. Instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus RF(\sigma _A'))$, it is changed as choosing $K^*_{A} \leftarrow \mathcal {KS}$ randomly, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct an IND-CCA adversary $\mathcal {S}$ from $\mathcal {A}$ in $\mathbf{H}_3$ or $\mathbf{H}_4$. $\mathcal {S}$ performs the following steps.

Init $\mathcal {S}$ receives the public key $ek^*$ as a challenge.

Setup $\mathcal {S}$ chooses PRF $F, F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and $G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {S}$ sets all $N$ users’ static secret and public keys except $U_B$. $\mathcal {S}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$. $U_A$’s static key $(dk_{A}, \sigma _A, \sigma _A')$ is given to $\mathcal {A}$.

Next, $\mathcal {S}$ sets $ek^*$ as the static public key of $U_B$. Also, $\mathcal {S}$ receives the challenge $(K^*, CT^*)$ from the challenger.

Simulation $\mathcal {S}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {S}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: If $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes $ek_{T}$ obeying the protocol and returns the ephemeral public key $(CT^*, ek_{T})$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: If $\bar{P} = B\hbox { and }CT_{P} \not = CT^*,\,\mathcal {S}$ poses $CT_{P}$ to the decryption oracle, obtains $K_{P}$, computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Else if $\bar{P} = B\hbox { and }CT_{P} = CT^*,\,\mathcal {S}$ sets $K_{P} = K^*$, computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi ,\,U_P,\,U_{\bar{P}},\,(CT_{P},\,ek_{T}),\,(CT_{\bar{P}},\,CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {S}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes the session key $SK$ obeying the protocol except that $K^*_{A} = K^*$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {S}$ returns an error message.

  • (b) Otherwise, $\mathcal {S}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {S}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. If the owner of $\mathsf {sid}$ is $U_B,\,\mathcal {S}$ poses ciphertexts received by $U_B$ to the decryption oracle and can simulate all intermediate computation results. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {S}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {S}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b',\,\mathcal {S}$ outputs $b'$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_3$ if the challenge is $(K^*_1, CT^*_0)$. Otherwise, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_4$. Also, both $K^*_{A}$ in two experiments have $\kappa$-min-entropy because $(\mathsf {KeyGen}, \mathsf {EnCap}, \mathsf {DeCap})$ is $\kappa$-min-entropy KEM. Thus, if the advantage of $\mathcal {S}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3)| \le negl$.

Hybrid experiment $\mathbf{H}_5$: In this experiment, the computation of $K'^*_{1}$ in the test session is changed. Instead of computing $K'^*_{1} \leftarrow KDF(s, K^*_{A})$, it is changed as choosing $K'^*_{1} \in \mathcal {FS}$ randomly.

Since $K^*_{A}$ is randomly chosen in $\mathbf{H}_4$, it has sufficient min-entropy. Thus, by the definition of the KDF, $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4)| \le negl$.

Hybrid experiment $\mathbf{H}_6$: In this experiment, the computation of $SK$ in the test session is changed. Instead of computing $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, it is changed as $SK = x\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$ where $x \in \{0,1\}^\kappa$ is chosen randomly and we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct a distinguisher $\mathcal {D'}$ between PRF $F^* : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$ and a random function $RF$ from $\mathcal {A}$ in $\mathbf{H}_5$ or $\mathbf{H}_6$. $\mathcal {D'}$ performs the following steps.

Setup $\mathcal {D'}$ chooses PRF $F: \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E,\,F' : \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, sets $G = F^*$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {D'}$ sets all $N$ users’ static secret and public keys. $\mathcal {D'}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$. $U_A$’s static key $(dk_{A}, \sigma _A, \sigma _A')$ is given to $\mathcal {A}$.

Simulation $\mathcal {D'}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {D'}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: $\mathcal {D'}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: $\mathcal {D'}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi ,\,U_P,\,U_{\bar{P}},\,(CT_{P},\,ek_{T}),\,(CT_{\bar{P}},\,CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {D'}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {D'}$ poses $\mathsf {ST}$ to his oracle (i.e., $F^*$ or a random function $RF$), obtains $x \in \{0,1\}^\kappa$, computes the session key $SK = x\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {D'}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {D'}$ returns an error message.

  • (b) Otherwise, $\mathcal {D'}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {D'}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {D'}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {D'}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b' = 0,\,\mathcal {D'}$ outputs that the oracle is the PRF $F^*$. Otherwise, $\mathcal {D'}$ outputs that the oracle is a random function $RF$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_5$ if the oracle is the PRF $F^*$. Otherwise, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_6$. Thus, if the advantage of $\mathcal {D'}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_6) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5)| \le negl$.

In $\mathbf{H}_6$, the session key in the test session is perfectly randomized. Thus, $\mathcal {A}$ cannot obtain any advantage from $\mathsf {Test}$ query.

Therefore, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_6) = 0\hbox { and }\Pr [E_{1} \wedge Suc]$ is negligible.

1.2 Appendix 1.2: Event $E_{2} \wedge Suc$

The proof in this case is essentially same as the event $E_{1} \wedge Suc$. There is a difference in the experiment $\mathbf{H}_3$. In the event $E_{1} \wedge Suc$, instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, it is changed as $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus RF(\sigma _A'))$, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session. In the event $E_{2} \wedge Suc$, it is changed as $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(RF(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$. Since $\mathcal {A}$ cannot obtain $\sigma _A$ by the freshness definition in this event, we can construct a distinguisher $\mathcal {D}$ from $\mathcal {A}$ in the similar manner in the proof of the event $E_{1} \wedge Suc$.

1.3 Appendix 1.3: Event $E_{3} \wedge Suc$

The proof in this case is essentially same as the event $E_{1} \wedge Suc$. There is differences in experiments $\mathbf{H}_3\hbox { and }\mathbf{H}_4$. In $\mathbf{H}_3$ of the event $E_{1} \wedge Suc$, instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, it is changed as $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus RF(\sigma _A'))$, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session. In $\mathbf{H}_3$ of the event $E_{3} \wedge Suc$, instead of computing $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(F_{{\sigma _B}}(r_{B}) \oplus F'_{{r'_{B}}}(\sigma _B'))$, it is changed as $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(F_{{\sigma _B}}(r_{B}) \oplus RF(\sigma _B'))$. In $\mathbf{H}_4$ of the event $E_{1} \wedge Suc$, instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus RF(\sigma _A'))$, it is changed as choosing $K^*_{A} \leftarrow \mathcal {KS}$ randomly. In $\mathbf{H}_4$ of the event $E_{3} \wedge Suc$, instead of computing $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(F_{{\sigma _B}}(r_{B}) \oplus RF(\sigma _B'))$, it is changed as choosing $K^*_{B} \leftarrow \mathcal {KS}$ randomly. Since $\mathcal {A}$ cannot obtain $\sigma _B$ by the freshness definition in this event, we can construct a distinguisher $\mathcal {D}$ from $\mathcal {A}$ in the similar manner in the proof of the event $E_{1} \wedge Suc$.

1.4 Appendix 1.4: Event $E_{4} \wedge Suc$

The proof in this case is essentially same as the event $E_{2} \wedge Suc$. There is differences in experiments $\mathbf{H}_3\hbox { and }\mathbf{H}_4$. In $\mathbf{H}_3$ of the event $E_{2} \wedge Suc$, instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(F_{{\sigma _A}}(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, it is changed as $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(RF(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session. In $\mathbf{H}_3$ of the event $E_{3} \wedge Suc$, instead of computing $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(F_{{\sigma _B}}(r_{B}) \oplus F'_{{r'_{B}}}(\sigma _B'))$, it is changed as $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(RF(r_{B}) \oplus F'_{{r'_{B}}}(\sigma _B'))$. In $\mathbf{H}_4$ of the event $E_{2} \wedge Suc$, instead of computing $(CT^*_{A},K^*_{A}) \leftarrow \mathsf {EnCap}_{ek_{B}}(RF(r_{A}) \oplus F'_{{r'_{A}}}(\sigma _A'))$, it is changed as choosing $K^*_{A} \leftarrow \mathcal {KS}$ randomly. In $\mathbf{H}_4$ of the event $E_{3} \wedge Suc$, instead of computing $(CT^*_{B},K^*_{B}) \leftarrow \mathsf {EnCap}_{ek_{A}}(RF(r_{B}) \oplus F'_{{r'_{B}}}(\sigma _B'))$, it is changed as choosing $K^*_{B} \leftarrow \mathcal {KS}$ randomly. Since $\mathcal {A}$ cannot obtain $\sigma _B$ by the freshness definition in this event, we can construct a distinguisher $\mathcal {D}$ from $\mathcal {A}$ in the similar manner in the proof of the event $E_{1} \wedge Suc$.

1.5 Appendix 1.5: Event $E_{5} \wedge Suc$

We change the interface of oracle queries and the computation of the session key. These instances are gradually changed over six hybrid experiments, depending on specific sub-cases. In the last hybrid experiment, the session key in the test session does not contain information of the bit $b$. Thus, the adversary clearly only output a random guess. We denote these hybrid experiments by $\mathbf{H}_0, \dots , \mathbf{H}_5$ and the advantage of the adversary $\mathcal {A}$ when participating in experiment $\mathbf{H}_i$ by ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_i)$.

Hybrid experiment $\mathbf{H}_0$: This experiment denotes the real experiment for ${\mathrm {CK}}^+$ security and in this experiment the environment for $\mathcal {A}$ is as defined in the protocol. Thus, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)$ is the same as the advantage of the real experiment.

Hybrid experiment $\mathbf{H}_1$: In this experiment, if session identities in two sessions are identical, the experiment halts.

By the same as the event $E_{1} \wedge Suc,\,|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)| \le negl$.

Hybrid experiment $\mathbf{H}_2$: In this experiment, the experiment selects a party $U_A$ and integer $i \in [1,\ell ]$ randomly in advance. If $\mathcal {A}$ poses $\mathsf {Test}$ query to a session except $i$-th session of $U_A$, the experiment halts.

By the same as the event $E_{1} \wedge Suc,\,{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2) \ge 1/N^2\ell \cdot {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1)$.

Hybrid experiment $\mathbf{H}_3$: In this experiment, the computation of $K^*_{T}$ in the test session is changed. Instead of computing $(CT^*_{T},K^*_{T}) \leftarrow \mathsf {wEnCap}_{ek_{T}}(r_{TB})$, it is changed as choosing $K^*_{T} \leftarrow \mathcal {KS}$ randomly, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct an IND-CPA adversary $\mathcal {S}$ from $\mathcal {A}$ in $\mathbf{H}_2$ or $\mathbf{H}_3$. $\mathcal {S}$ performs the following steps.

Init $\mathcal {S}$ receives the public key $ek^*$ as a challenge.

Setup $\mathcal {S}$ chooses PRF $F, F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and $G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {S}$ sets all $N$ users’ static secret and public keys. $\mathcal {S}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$. $U_A$’s static key $(dk_{A}, \sigma _A, \sigma _A')\hbox { and }U_B$’s static key $(dk_{B}, \sigma _B, \sigma _B')$ are given to $\mathcal {A}$.

Next, $\mathcal {S}$ receives the challenge $(K^*, CT^*)$ from the challenger.

Simulation $\mathcal {S}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {S}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: If $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes $CT_{A}$ obeying the protocol and returns the ephemeral public key $(CT_{A}, ek^*)$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: If $\bar{P} = B,\,\mathcal {S}$ computes $CT_{\bar{P}}$ and the session key $SK$ obeying the protocol except that $K_{T} = K^*$, returns the ephemeral public key $(CT_{\bar{P}},CT^*)$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {S}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes the session key $SK$ obeying the protocol except that $K^*_{T} = K^*$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {S}$ returns an error message.

  • (b) Otherwise, $\mathcal {S}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {S}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {S}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {S}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b',\,\mathcal {S}$ outputs $b'$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_2$ if the challenge is $(K^*_1, CT^*_0)$. Otherwise, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_3$. Also, both $K^*_{T}$ in two experiments have $\kappa$-min-entropy because $(\mathsf {wKeyGen}, \mathsf {wEnCap}, \mathsf {wDeCap})$ is $\kappa$-min-entropy KEM. Thus, if the advantage of $\mathcal {S}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2)| \le negl$.

Hybrid experiment $\mathbf{H}_4$: In this experiment, the computation of $K'^*_{3}$ in the test session is changed. Instead of computing $K'^*_{3} \leftarrow KDF(s, K^*_{T})$, it is changed as choosing $K'^*_{3} \in \mathcal {FS}$ randomly.

Since $K^*_{T}$ is randomly chosen in $\mathbf{H}_3$, it has sufficient min-entropy. Thus, by the definition of the KDF, $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3)| \le negl$.

Hybrid experiment $\mathbf{H}_5$: In this experiment, the computation of $SK$ in the test session is changed. Instead of computing $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, it is changed as $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$ where $x \in \{0,1\}^\kappa$ is chosen randomly and we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct a distinguisher $\mathcal {D'}$ between PRF $F^* : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$ and a random function $RF$ from $\mathcal {A}$ in $\mathbf{H}_4$ or $\mathbf{H}_5$. $\mathcal {D'}$ performs the following steps.

Setup $\mathcal {D'}$ chooses PRF $F,F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and sets $G = F^*$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {D'}$ sets all $N$ users’ static secret and public keys. $\mathcal {D'}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r \in _R \mathcal {RS}_G$, and runs $(ek_{P}, dk_{P}) \leftarrow \mathsf {KeyGen}(1^\kappa , r)$. Party $U_P$’s SSK and SPK are $((dk_{P}, \sigma _P, \sigma _P'),ek_{P})$. $U_A$’s static key $(dk_{A}, \sigma _A, \sigma _A')\hbox { and }U_B$’s static key $(dk_{B}, \sigma _B, \sigma _B')$ are given to $\mathcal {A}$.

Simulation $\mathcal {D'}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {D'}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: $\mathcal {D'}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: If $P = A$ and the session is partnered with $i$-th session of $U_A,\,\mathcal {D'}$ poses $\mathsf {ST}$ to his oracle (i.e., $F^*$ or a random function $RF$), obtains $x \in \{0,1\}^\kappa$, computes the session key $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {D'}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {D'}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {D'}$ poses $\mathsf {ST}$ to his oracle (i.e., $F^*$ or a random function $RF$), obtains $x \in \{0,1\}^\kappa$, computes the session key $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {D'}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {D'}$ returns an error message.

  • (b) Otherwise, $\mathcal {D'}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {D'}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {D'}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {D'}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b' = 0,\,\mathcal {D'}$ outputs that the oracle is the PRF $F^*$. Otherwise, $\mathcal {D'}$ outputs that the oracle is a random function $RF$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_4$ if the oracle is the PRF $F^*$. Otherwise, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_5$. Thus, if the advantage of $\mathcal {D'}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4)| \le negl$.

In $\mathbf{H}_5$, the session key in the test session is perfectly randomized. Thus, $\mathcal {A}$ cannot obtain any advantage from $\mathsf {Test}$ query.

Therefore, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5) = 0\hbox { and }\Pr [E_{5} \wedge Suc]$ is negligible.

1.6 Appendix 1.6: Event $E_{6} \wedge Suc$

The proof in this case is essentially same as the event $E_{2} \wedge Suc$. The situation that the ephemeral secret key of $\overline{\mathsf {sid}}^*$ is given to $\mathcal {A}$ is the same as $\mathsf {sid}$ has no matching session because $\mathcal {A}$ can decide arbitrary ephemeral key. Thus, the proof in this event follows that in the event $E_{2} \wedge Suc$.

1.7 Appendix 1.7: Event $E_{7} \wedge Suc$

The proof in this case is essentially same as the event $E_{1} \wedge Suc$. The situation that the ephemeral secret key of $\overline{\mathsf {sid}}^*$ is given to $\mathcal {A}$ is the same as $\mathsf {sid}$ has no matching session because $\mathcal {A}$ can decide arbitrary ephemeral key. Thus, the proof in this event follows that in the event $E_{1} \wedge Suc$.

1.8 Appendix 1.8: Event $E_{8} \wedge Suc$

The proof in this case is essentially same as the event $E_{4} \wedge Suc$. The situation that the ephemeral secret key of $\overline{\mathsf {sid}}^*$ is given to $\mathcal {A}$ is the same as $\overline{\mathsf {sid}}^*$ has no matching session because $\mathcal {A}$ can decide arbitrary ephemeral key. Thus, the proof in this event follows that in the event $E_{4} \wedge Suc$.

Appendix 2: Proof of Theorem 2

In the experiment of ${\hbox {id-CK}^+}$ security, we suppose that $\mathsf {sid}^*$ is the session identity for the test session, and that there are $N$ users and at most $\ell$ sessions are activated. Let $\kappa$ be the security parameter, and let $\mathcal {A}$ be a PPT (in $\kappa$) bounded adversary. $Suc$ denotes the event that $\mathcal {A}$ wins. We consider the following events that cover all cases of the behavior of $\mathcal {A}$.

• Let $E_1$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the initiator and the static secret key of the initiator is given to $\mathcal {A}$.

• Let $E_2$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the initiator and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

• Let $E_3$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the responder and the static secret key of the responder is given to $\mathcal {A}$.

• Let $E_4$ be the event that the test session $\mathsf {sid}^*$ has no matching session $\overline{\mathsf {sid}}^*$, the owner of $\mathsf {sid}^*$ is the responder and the ephemeral secret key of $\mathsf {sid}^*$ is given to $\mathcal {A}$.

• Let $E_5$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and both static secret keys of the initiator and the responder are given to $\mathcal {A}$.

• Let $E_6$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and both ephemeral secret keys of $\mathsf {sid}^*\hbox { and }\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

• Let $E_7$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and the static secret key of the owner of $\mathsf {sid}^*$ and the ephemeral secret key of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

• Let $E_8$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and the ephemeral secret key of $\mathsf {sid}^*$ and the static secret key of the owner of $\overline{\mathsf {sid}^*}$ are given to $\mathcal {A}$.

• Let $E_9$ be the event that the test session $\mathsf {sid}^*$ has matching session $\overline{\mathsf {sid}}^*$, and master secret key is given to $\mathcal {A}$.

To finish the proof, we investigate events $E_{i} \wedge Suc\,(i=1,\dots ,9)$ that cover all cases of event $Suc$. Though proofs of events are essentially same as the case of Theorem 1, $E_{9} \wedge Suc$ is the characteristic event for Theorem 2. Thus, we only show the proof of event $E_{9} \wedge Suc$.

1.1 Appendix 2.1: Event $E_{9} \wedge Suc$

We change the interface of oracle queries and the computation of the session key. These instances are gradually changed over six hybrid experiments, depending on specific sub-cases. In the last hybrid experiment, the session key in the test session does not contain information of the bit $b$. Thus, the adversary clearly only output a random guess. We denote these hybrid experiments by $\mathbf{H}_0, \dots , \mathbf{H}_5$ and the advantage of the adversary $\mathcal {A}$ when participating in experiment $\mathbf{H}_i$ by ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_i)$.

Hybrid experiment $\mathbf{H}_0$: This experiment denotes the real experiment for ${\hbox {id-CK}^+}$ security and in this experiment the environment for $\mathcal {A}$ is as defined in the protocol. Thus, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)$ is the same as the advantage of the real experiment.

Hybrid experiment $\mathbf{H}_1$: In this experiment, if session identities in two sessions are identical, the experiment halts.

When two ciphertexts from different randomness are identical, session identities in two sessions are also identical. In the IND-sID-CCA secure IB-KEM, such an event occurs with negligible probability. Thus, $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_0)| \le negl$.

Hybrid experiment $\mathbf{H}_2$: In this experiment, the experiment selects a party $U_A$ and integer $i \in [1,\ell ]$ randomly in advance. If $\mathcal {A}$ poses $\mathsf {Test}$ query to a session except $i$-th session of $U_A$, the experiment halts.

Since guess of the test session matches with $\mathcal {A}$’s choice with probability $1/N^2\ell ,\,{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2)\,\ge 1/N^2\ell \cdot {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_1)$.

Hybrid experiment $\mathbf{H}_3$: In this experiment, the computation of $K^*_{T}$ in the test session is changed. Instead of computing $(CT^*_{T},K^*_{T}) \leftarrow \mathsf {wEnCap}_{ek_{T}}(r_{TB})$, it is changed as choosing $K^*_{T} \leftarrow \mathcal {KS}$ randomly, where we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct an IND-CPA adversary $\mathcal {S}$ from $\mathcal {A}$ in $\mathbf{H}_2$ or $\mathbf{H}_3$. $\mathcal {S}$ performs the following steps.

Init $\mathcal {S}$ receives the public key $ek^*$ as a challenge.

Setup $\mathcal {S}$ chooses PRF $F, F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and $G : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {S}$ sets the master public and secret key, and all $N$ users’ static secret keys. $\mathcal {S}$ selects $r \in \mathcal {RS}_G$, and generates master public and secret keys $(mpk,msk) \leftarrow \mathsf{MKeyGen}(1^\kappa , r)$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf{MKeyGen}$. Then, $\mathcal {S}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r' \in \mathcal {RS}_G$, and runs the key derivation algorithm $dk_{P} \leftarrow \mathsf {KeyDer}(mpk,msk,U_P,r')$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf {KeyDer}$. Party $U_P$’s static secret key is $(dk_{P},\sigma _P, \sigma _P')$. The master key $msk$ is given to $\mathcal {A}$.

Next, $\mathcal {S}$ receives the challenge $(K^*, CT^*)$ from the challenger.

Simulation $\mathcal {S}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {S}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: If $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes $CT_{A}$ obeying the protocol and returns the ephemeral public key $(CT_{A}, ek^*)$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: If $\bar{P} = B,\,\mathcal {S}$ computes $CT_{\bar{P}}$ and the session key $SK$ obeying the protocol except that $K_{T} = K^*$, returns the ephemeral public key $(CT_{\bar{P}},CT^*)$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {S}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {S}$ computes the session key $SK$ obeying the protocol except that $K^*_{T} = K^*$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {S}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {S}$ returns an error message.

  • (b) Otherwise, $\mathcal {S}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {S}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {S}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {S}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b',\,\mathcal {S}$ outputs $b'$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_2$ if the challenge is $(K^*_1, CT^*_0)$. Otherwise, the simulation by $\mathcal {S}$ is same as the experiment $\mathbf{H}_3$. Also, both $K^*_{T}$ in two experiments have $\kappa$-min-entropy because $(\mathsf {wKeyGen}, \mathsf {wEnCap}, \mathsf {wDeCap})$ is $\kappa$-min-entropy KEM. Thus, if the advantage of $\mathcal {S}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_2)| \le negl$.

Hybrid experiment $\mathbf{H}_4$: In this experiment, the computation of $K'^*_{3}$ in the test session is changed. Instead of computing $K'^*_{3} \leftarrow KDF(s, K^*_{T})$, it is changed as choosing $K'^*_{3} \in \mathcal {FS}$ randomly.

Since $K^*_{T}$ is randomly chosen in $\mathbf{H}_3$, it has sufficient min-entropy. Thus, by the definition of the KDF, $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_3)| \le negl$.

Hybrid experiment $\mathbf{H}_5$: In this experiment, the computation of $SK$ in the test session is changed. Instead of computing $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,G_{{K'_{3}}}(\mathsf {ST})$, it is changed as $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$ where $x \in \{0,1\}^\kappa$ is chosen randomly and we suppose that $U_B$ is the intended partner of $U_A$ in the test session.

We construct a distinguisher $\mathcal {D'}$ between PRF $F^* : \{0,1\}^* \times \mathcal {FS}\rightarrow \{0,1\}^\kappa$ and a random function $RF$ from $\mathcal {A}$ in $\mathbf{H}_4$ or $\mathbf{H}_5$. $\mathcal {D'}$ performs the following steps.

Setup $\mathcal {D'}$ chooses PRF $F,F': \{0,1\}^* \times \mathcal {FS}\rightarrow \mathcal {RS}_E$, and sets $G = F^*$, where $\mathcal {FS}$ is the key space of PRFs, and a KDF $KDF : Salt \times \mathcal {KS}\rightarrow \mathcal {FS}$ with a non-secret random salt $s \in Salt$. These are provided as a part of the public parameters. Also, $\mathcal {S}$ sets the master public and secret key, and all $N$ users’ static secret keys. $\mathcal {S}$ selects $r \in \mathcal {RS}_G$, and generates master public and secret keys $(mpk,msk) \leftarrow \mathsf{MKeyGen}(1^\kappa , r)$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf{MKeyGen}$. Then, $\mathcal {S}$ selects $\sigma _P \in _R \mathcal {FS},\,\sigma _P' \in _R \{0,1\}^\kappa \hbox { and }r' \in \mathcal {RS}_G$, and runs the key derivation algorithm $dk_{P} \leftarrow \mathsf {KeyDer}(mpk,msk,U_P,r')$, where $\mathcal {RS}_G$ is the randomness space of $\mathsf {KeyDer}$. Party $U_P$’s static secret key is $(dk_{P},\sigma _P, \sigma _P')$. The master key $msk$ is given to $\mathcal {A}$.

Simulation $\mathcal {D'}$ maintains the list $\mathcal {L}_{SK}$ that contains queries and answers of $\mathsf {SessionKeyReveal}$. $\mathcal {D'}$ simulates oracle queries by $\mathcal {A}$ as follows.

• 1. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}})$: $\mathcal {D'}$ computes the ephemeral public key $(CT_{P},ek_{T})$ obeying the protocol, returns it and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}))$.

• 2. $\mathsf {Send}(\Pi , \mathcal {R}, U_{\bar{P}}, U_P, (CT_{P},ek_{T}))$: If $P = A$ and the session is partnered with $i$-th session of $U_A,\,\mathcal {D'}$ poses $\mathsf {ST}$ to his oracle (i.e., $F^*$ or a random function $RF$), obtains $x \in \{0,1\}^\kappa$, computes the session key $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {D'}$ computes the ephemeral public key $(CT_{\bar{P}},CT_{T})$ and the session key $SK$ obeying the protocol, returns the ephemeral public key, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 3. $\mathsf {Send}(\Pi , \mathcal {I}, U_P, U_{\bar{P}}, (CT_{P},ek_{T}), (CT_{\bar{P}},CT_{T}))$: If $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not recorded, $\mathcal {D'}$ records the session $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ is not completed. Else if $P = A$ and the session is $i$-th session of $U_A,\,\mathcal {D'}$ poses $\mathsf {ST}$ to his oracle (i.e., $F^*$ or a random function $RF$), obtains $x \in \{0,1\}^\kappa$, computes the session key $SK = G_{{K'_{1}}}(\mathsf {ST})\,\oplus \,G_{{K'_{2}}}(\mathsf {ST})\,\oplus \,x$, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$. Otherwise, $\mathcal {D'}$ computes the session key $SK$ obeying the protocol, and records $(\Pi , U_P, U_{\bar{P}}, (CT_{P},ek_{T}),\,(CT_{\bar{P}},CT_{T}))$ as the completed session and $SK$ in the list $\mathcal {L}_{SK}$.

• 4. $\mathsf {SessionKeyReveal}(\mathsf {sid})$:

  • (a) If the session $\mathsf {sid}$ is not completed, $\mathcal {D'}$ returns an error message.

  • (b) Otherwise, $\mathcal {D'}$ returns the recorded value $SK$.

• 5. $\mathsf {SessionStateReveal}(\mathsf {sid})$: $\mathcal {D'}$ responds the ephemeral secret key and intermediate computation results of $\mathsf {sid}$ as the definition. Note that the $\mathsf {SessionStateReveal}$ query is not posed to the test session from the freshness definition.

• 6. $\mathsf {Corrupt}(U_P)$: $\mathcal {D'}$ responds the static secret key and all unerased session states of $U_P$ as the definition.

• 7. $\mathsf {Test}(\mathsf {sid})$: $\mathcal {D'}$ responds to the query as the definition.

• 8. If $\mathcal {A}$ outputs a guess $b' = 0,\,\mathcal {D'}$ outputs that the oracle is the PRF $F^*$. Otherwise, $\mathcal {D'}$ outputs that the oracle is a random function $RF$.

Analysis For $\mathcal {A}$, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_4$ if the oracle is the PRF $F^*$. Otherwise, the simulation by $\mathcal {D'}$ is same as the experiment $\mathbf{H}_5$. Thus, if the advantage of $\mathcal {D'}$ is negligible, then $|{\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5) - {\mathbf {Adv}}(\mathcal {A},\mathbf{H}_4)| \le negl$.

In $\mathbf{H}_5$, the session key in the test session is perfectly randomized. Thus, $\mathcal {A}$ cannot obtain any advantage from $\mathsf {Test}$ query.

Therefore, ${\mathbf {Adv}}(\mathcal {A},\mathbf{H}_5) = 0\hbox { and }\Pr [E_{5} \wedge Suc]$ is negligible.