Key exchange (KE), which enables two parties to securely establish a common session key while communicating over an insecure channel, is one of the most important and fundamental primitives in cryptography. After the introduction of Diffie-Hellman key exchange in [12], cryptographers have devised a wide selection of the KE with various use-cases. One important direction is authenticated key exchange (AKE). The main problems that the following works focus on are specified as security models [5,6,7,15,24], efficient and provably-secure realizations [1,2,3,7,15,16,22,24,25,26,27,29,34,35].

In an AKE protocol, each party has a pair of secret-public keys, astatic/long-term public key and the correspondingstatic/long-term secret key. The static public key is interrelated with a party’s identity, which enables the other parties to verify the authentic binding between them. A party who wants to share information with another party generates ephemeral one-time randomness which is known asephemeral secret keys, computessession state (which is originally not explicitly defined [7], but nowadays it is generally agreed [15,24] that the session state should at least contain ephemeral secret keys) from ephemeral and static secret keys and incoming message, then outputs correspondingephemeral public outgoing message. Then each party uses their static secret keys and the ephemeral secret keys along with the transcripts of the session to compute a sharedsession key.

Many studies have investigated the security notion of AKE including BR model and Canetti-Krawczyk (CK) model [7]. Fujiokaet al. [15] re-formulated thedesirable security notion of AKE in [23], including resistance to KCI (key compromise impersonation attack), wPFS (weak perfect forward attack) and MEX (maximal exposure attack), as well as provable security in the CK model, and called it the CK\(^+\) security model. LaMacchiaet al. [24] also proposed a very strong security model, called the eCK model. The CK model and the eCK model are incomparable [6], and the eCK model is not stronger than the CK model while the CK\(^+\) model is [15]. However, each of these two models, eCK and CK\(^+\) can be theoretically seen as a strong version of the AKE security model.

To achieve a secure AKE in one of the above security models (CK, CK\(^+\), eCK), the solutions are divided into two classes: explicit AKE and implicit AKE. The solution of explicit AKE is to explicitly authenticate the exchanged messages between the involved parties by generally using additional primitivesi.e., signature or MAC to combine with the underlying KE, such as IKE [8], SIGMA [22], TLS [2,21] etc.; while the solution of implicit AKE initiated by [25], is to implicitly authenticate each party by its unique ability so as to compute the resulted session key. These kinds of implicit AKE schemes include (H)MQV [23,26], Okamoto [27,28], NAXOS [24], OAKE [34], FSXY variants [1,15,16,33], and AKE from lattice assumptions [3,35].

Motivation. In this paper, we focus on the second class,i.e., constructions ofimplicit AKE. Based on different techniques and assumptions, many implicit AKE protocols have been proposed in recent years [15,16,23,24,27,28,34].

However, the constructing techniques and methods of the existing implicit AKE protocols are somewhat separate and the study on the highly accurate analysis of AKE’s requirement for the building block is critically in a shortage, especially for the exact underlying primitives that serve as fundamental building blocks and capture the common idea and technique behind the constructions and security proofs of AKE. On the contrary, with respect to explicit AKE Canetti and Krawcayk [8,22] gave the frame of “SIGin-and-MAc” (later extended by [29]) which provides a good guideline for designing explicit AKE.

In fact, Boydet al. [1] and Fujiokaet al. [15,16] initiated the research on studying frameworks of implicit AKE. Boydet al. firstly noticed the connection between AKE and key encapsulation mechanism (KEM), then Fujiokaet al. provided CK\(^+\) secure AKE protocols from chosen ciphertext (CCA) secure KEM in the random oracle and standard models. Although the paradigm of connecting the AKE with KEM is of great significance, it can not be applied to explain many widely-used and well-known constructions of AKE such as HMQV and its variant [23,34] which are built on the challenge-respond signature; AKE protocol in [27] which results from universal hash proof [10]; as well as NAXOS [24].

Hence, one of the important problems on AKE is to give an even more general framework for constructing AKE that is able to not only unify the existing structures of AKE protocol as much as possible, but also to systemize and simplify the construction and analysis methods of AKE protocol. It will be useful and helpful for understanding the existing works and future studying on formalization of the AKE construction under a unified framework with some well-studied and simple cryptographic primitive as building block.

1.1Our Contributions

• Based on the above motivations and observations, we introducedouble-key key encapsulation mechanism (2-key KEM) and its secure notions,i.e., [IND/OW-CCA,IND/OW-CPA] security. We also show its distinction with previous similar notions.

• Based on the [IND/OW-CCA,IND/OW-CPA] secure 2-key KEM, we present unified frames of CK\(^+\) secure AKE, which in turn conceptually capture the common pattern for the existing constructions and security proof of AKE, including well-known HMQV [23], NAXOS [24], Okamoto-AKE [27,28], and FSXY12 [15], FSXY13 [16].

• We investigate the constructions of 2-key KEM based on concrete assumptions. We also show the failure of implying\([\textsf {IND/OW\text {-}CCA}, \textsf {IND/OW\text {-}CPA}]\) secure 2-key KEM from KEM combiner and the classical Fujisaki-Okamoto (FO) transformation. Hence, with a slight but vital modification by taking public key as input to the hash step we provide improved KEM combiner and improved FO to adapt them in our 2-key KEM setting.

• Equipped with 2-key KEM and our frame above, we propose a post-quantum AKE based on Module-LWE assumption, which consumes less communications than Kyber [3] using frame of FSXY13 [16].

2-Key Key Encapsulation Mechanism. Generally, the 2-key KEM scheme is a public key encapsulation with two pairs of public and secret keys, but the main distinctions are the functionality and security.

The encapsulation and decapsulation algorithms: instead of taking as input single public key to generate a random keyK and a ciphertextC and single secret key to decapsulate ciphertextC, each algorithm takes two public keys\((pk_1, pk_0)\) to generate (C, K) and only with both two secret keys\((sk_1, sk_0)\) the decapsulation algorithm can decapsulateC.

We define the security notion of 2-key KEM/PKE in the attacking model\([\textsf {IND/OW\text {-}CCA},\textsf {IND/OW\text {-}CPA}]\) which captures the idea that the 2-key KEM is secure under one secret-public key pair even if another pair of secret-public key is generated by the adversary. Informally, the\([\textsf {IND/OW\text {-}CCA}, \cdot ]\) denotes the security model where adversary\(\mathcal {A}\) aims to attack the ciphertext under\(pk_1\) and\(pk^*_0\) (with its control over the generation of\(pk^*_0\)), and it is allowed to query a strong decapsulation oracle that will decapsulate the ciphertext under\(pk_1\) and arbitrary\(pk'_0\) (generated by challenger); while\([\cdot , \textsf {IND/OW\text {-}CPA}]\) denotes the security model where adversary\(\mathcal {B}\) aims to attack the ciphertext under\(pk_0\) and\(pk^*_1\) (with its control over the generation of\(pk^*_1\)). We say a 2-key KEM is\([\textsf {IND/OW\text {-}CCA},\textsf {IND/OW\text {-}CPA}]\) secure if it is both\([\textsf {IND/OW\text {-}CCA}, \cdot ]\) and\([\cdot , \textsf {IND/OW\text {-}CPA}]\) secure.

Compared with classical definition of CCA security, the\([\textsf {CCA}, \cdot ]\) adversary of 2-key KEM has two main enhancements: (1) one of the challenge public keys\(pk^*_0\), under which the challenge ciphertext is computed, is generated by the adversary; (2) the adversary is allowed to query a strong decryption oracle, and get decapsulation of the ciphertext under arbitrary public keys\((pk^*_1, pk'_0)\) where\(pk'_0\) is generated by the challenger.

AKE from 2-Key KEM. Equipped with [IND/OW-CCA,IND/OW-CPA] 2-key KEM, by taking\(pk_1\) as static public key and\(pk_0\) as ephemeral public key, we give several general frames of CK\(^+\) secure AKE,\(\mathsf {AKE}\),\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) and\(\mathsf {AKE}_{\textsf {std}}\), depending on different tricks. The CK\(^+\) security of our AKE is decomposed to the\([\textsf {IND/OW\text {-}CCA}, \cdot ]\) security (corresponding to KCI and MEX security) and\([\cdot , \textsf {IND/OW\text {-}CPA}]\) security (corresponding to wPFS) of 2-key KEM. Furthermore, to resist the leakage of partial randomness, a function\(f(ssk_B, esk_B)\) is required so that if one of\(ssk_B\) and\(esk_B\) is leaked\(f(ssk_B, esk_B)\) is still computationally indistinguishable with a random string.

In Table 1 we summarize which one of our general frames is used to explain which one of the existing AKE protocols by employing the specific tricks and assumptions. Our general protocols capture the common idea of constructing CK\(^+\) secure AKE. And depending on 2-key KEM and different tricks, it facilitates a number of instantiations, including HMQV [23], NAXOS [24], Okamoto [27], FSXY12 [15], and FSXY13 [16].

By considering an AKE protocol in such a framework based on 2-key KEM, the complicated security proofs of existing AKE is decomposed into several smaller cases each of which is easier to work with. Moreover, this general scheme not only explains previous constructions, but also yields efficient AKE from lattice problems. After giving [IND-CPA,IND-CPA] twin-kyber under Module-LWE assumption, we obtain apost-quantum AKE with less communications.

Constructions of 2-Key KEM. In addition to show that existing AKEs imply [CCA,CPA] secure 2-key KEM, we investigate the general constructions.

Putting Public Key in the Hashing or PRF step. The Fujisaki-Okamoto (FO) [14,18] transformation and KEM combiner are general techniques of classical CCA security for one-key KEM. We show the failure of implying [IND/OW-CCA,IND/OW-CPA] secure 2-key KEM from KEM combiner and the classical FO transformation by giving particular attacks on concrete schemes. Hence, we show that with a slight but vital modification, when extracting encapsulated key, by taking public key as input to the hash or PRF step, the modified KEM combiner and FO transformation work for 2-key KEM.

1.2Strong Point of the AKE via 2-Key KEM

The main advantage of our contributions is that we use a non-interactive primitive to handle the complex requirement of interactive protocols. The functionality and security requirements of [CCA,CPA] secure 2-key KEM are relatively easier to work with and understand. As it is known, in AKE we have to consider complex and diverse adversaries. However, when considering the AKE under our unified framework based on 2-key KEM, all the attacking strategies in CK\(^+\) model can be simplified to the singular security of 2-key KEM.

The non-interactive 2-key KEM helps us to highly simplify the constructions for AKE as well as to understand the essential working mechanism. In fact, KEM is relatively well-studied and intensively analyzed. Following the first practical CCA secure PKE [9], there have been a number of CCA secure PKE/KEM schemes based on both concrete assumptions [3,9,30,31] and general cryptographic primitives [11,19,30]. Therefore, it is possible for us to employ the established and nature technique of classical KEM to construct 2-key KEM, and further AKE.

For a variablex, ifx is a bit string, denote\([x]_i\) as thei-th bit ofx; ifx is a polynomial, denote\([x]_i\) as thei-th coefficient ofx; ifx is a sets of vectors (with string or number) denote\([x]_i\) as the sets of alli-th element of vectors inx;

2.1CK\(^+\) Security Model

We recall the CK\(^+\) model introduced by [23] and later refined by [15,16], which is a CK [7] model integrated with the weak PFS, resistance to KCI and MEX properties. Since we focus ontwo-pass protocols in this paper, for simplicity, we show the model specified to two pass protocols.

In AKE protocol,\(U_i\) denotes a party indexed byi, who is modeled as probabilistic polynomial time (PPT) interactive Turing machines. We assume that each party\(U_i\) owns a static pair of secret-public keys\((ssk_i, spk_i)\), where the static public key is linked to\(U_i\)’s identity, using some systems i.e. PKI, such that the other parties can verify the authentic binding between them. We do not require the well-formness of static public key, in particular, a corrupted party can adaptively register any static public key of its choice.

Session. Each party can be activated to run an instance called asession. A party can be activated to initiate the session by an incoming message of the forms\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B})\) or respond to an incoming message of the forms\((\mathrm {\Pi },\mathcal {R}, U_{B},U_{A},X_{A})\), where\(\mathrm {\Pi }\) is a protocol identifier,\(\mathcal {I}\) and\(\mathcal {R}\) are role identifiers corresponding toinitiator andresponder. Activated with\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B})\),\(U_A\) is called the sessioninitiator. Activated with\((\mathrm {\Pi },\mathcal {R}, U_{B},U_{A},X_{A})\),\(U_B\) is called the sessionresponder.

According to the specification of AKE, the party creates randomness which is calledephemeral secret key, computes and maintains asession state, and completes the session by outputting a session key and erasing the session state. Note that Canetti-Krawczyk [7] defines session state as session-specific secret information but leaves it up to a protocol to specify which information is included in session state; LaMacchia et al. [24] explicitly set all random coins used by a party in a session as session-specific secret information and call itephemeral secret key. We require that the session state at least contains the ephemeral secret key.

A session may also be aborted without generating a session key. The initiator\(U_A\) creates a session state and outputs\(X_A\), then may receive an incoming message of the forms\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B},X_A,X_B)\) from the responder\(U_B\), then may computes the session keySK. On the contrary, the responder\(U_B\) outputs\(X_B\), and may compute the session keySK. We say that a session iscompleted if its owner computes the session key.

A session is associated with its owner, a peer, and a session identifier. If\(U_A\) is the initiator, the session identifier is\(\mathsf {sid}=(\mathrm {\Pi },\mathcal {I},U_{A}, U_{B},\)\(X_A)\) or\(\mathsf {sid}=(\mathrm {\Pi },\mathcal {I},U_{A},U_{B},X_A,X_B)\), which denotes\(U_A\) as an owner and\(U_B\) as a peer. If\(U_B\) is the responder, the session is identified by\(\mathsf {sid}=(\mathrm {\Pi },\mathcal {R}, U_{B},U_{A},X_{A},X_{B})\), which denotes\(U_B\) as an owner and\(U_A\) as a peer. Thematching session of\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B}, X_A, X_B)\) is\((\mathrm {\Pi },\mathcal {R}, U_{B},U_{A},X_{A}, X_B)\) and vice versa.

Adversary. The adversary\(\mathcal {A}\) is modeled in the following to capture real attacks in open networks.

• Send(message):\(\mathcal {A}\) could send message in one of the forms:\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B})\),\((\mathrm {\Pi },\mathcal {R}, U_{B},U_{A},X_{A})\), or\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B},X_A,X_B)\), and obtains the response.

• SessionKeyReveal(sid): if the sessionsid is completed,\(\mathcal {A}\) obtains the session keySK forsid.

• SessionStateReveal(sid): The adversary\(\mathcal {A}\) obtains the session state of the owner ofsid if the session is not completed. 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.

• Corrupt(\(U_i\)): By this query,\(\mathcal {A}\) learns all information of\(U_A\) (including the static secret, session states and session keys stored at\(U_A\)); in addition, from the moment\(U_A\) is corrupted all its actions may be controlled by\(\mathcal {A}\).

Freshness. Let\(\mathsf {sid}^*=(\mathrm {\Pi },\mathcal {I},U_{A},U_{B},X_A,X_B)\) or\((\mathrm {\Pi },\mathcal {I},U_{A},U_{B},X_A,X_B)\) be a completed session between honest users\(U_A\) and\(U_B\). If the matching session of\(\mathsf {sid}^*\) exists, denote it by\(\overline{\mathsf {sid}^{*}}\). We say session\(\mathsf {sid}^*\) is fresh if\(\mathcal {A}\) does not queries: (1)SessionStateReveal(\(\mathsf {sid}^*\)),SessionKeyReveal(\(\mathsf {sid}^*\)), andSessionStateReveal(\(\overline{\mathsf {sid}^*}\)),SessionKeyReveal(\(\overline{\mathsf {sid}^*}\)) if\(\overline{\textsf {sid}^*}\) exists; (2)SessionStateReveal(\(\mathsf {sid}^*\)) andSessionKeyReveal(\(\mathsf {sid}^*\)) if\(\overline{\textsf {sid}^*}\) does not exist.

Security Experiment. The adversary\(\mathcal {A}\) could make a sequence of the queries described above. During the experiment,\(\mathcal {A}\) makes the query of\(\mathsf {Test(sid^*)}\), where\(\mathsf {sid}^*\) must be a fresh session.\(\mathsf {Test(sid^*)}\) 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\(\mathcal {A}\) returns\(b^\prime \) as a guess ofb. The adversary\(\mathcal {A}\) wins the game if the test session\(\mathsf {sid}^*\) is still fresh and\(b^\prime = b\). The advantage of the adversary\(\mathcal {A}\) is defined as\(\mathsf {Adv}_{\mathrm {\Pi }}^{ck+}(\mathcal {A})=\Pr \left[ \mathcal {A}~\mathrm {wins}\right] -\frac{1}{2}.\)

Definition 1

We say that a AKE protocol\(\mathrm {\Pi }\) is secure in the\(CK^+\) model if the following conditions hold:

(Correctness:) if two honest parties complete matching sessions, then they both compute the same session key except with negligible probability.

(Soundness:) for any PPT\(\mathcal {A}\),\(\mathsf {Adv}_{\mathrm {\Pi }}^{ck+}(\mathcal {A})\) is negligible for the test session\(\mathsf {sid}^*\),

1. 1.

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

2. 2.

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

3. 3.

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

4. 4.

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

5. 5.

   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}\), if\(\overline{\mathsf {sid}^{*}}\) exists.

6. 6.

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

As indicated in Table 2, the CK\(^+\) model captures all non-trivial patterns of exposure of static and ephemeral secret keys listed in Definition1, and these ten cases cover wPFS, resistance to KCI, and MEX.

3.12-Key Key Encapsulation Mechanism

Generally, a double-key (2-key) KEM is a public key encapsulation with two pairs of public and secret keys. Formally, a 2-key KEM\(\mathsf {2KEM=(KeyGen1, KeyGen0, Encaps, Decaps)}\) is a quadruple of PPT algorithms together with a key space\(\mathcal {K}\).

• \(\textsf {KeyGen1}(\lambda , pp){:}\) on inputs security parameter\(\lambda \), and public parameterspp, output a pair of public-secret keys\((pk_1, sk_1)\). In order to show the randomness that is used, we denote key generation algorithm as\(\textsf {KeyGen1}(\lambda , pp; r)\). For simplicity, sometimes we omit the input security parameter\(\lambda \) and public parameterpp and denote it as\(\textsf {KeyGen1}(r)\) directly.

• \(\textsf {KeyGen0}(\lambda ){:}\) on inputs security parameter\(\lambda \) output a pair of public and secret keys\((pk_0, sk_0)\).

• \(\textsf {Encaps}(pk_1, pk_0; \mathsf {aux}_{\textsf {e}}){:}\) on input public keys\(pk_1, pk_0\) and auxiliary input\(\mathsf {aux}_{\textsf {e}}\) (if there is), output ciphertextc and encapsulated keyk in key space\(\mathcal {K}\). Sometimes, we explicitly add the randomnessr and denote it as\(\textsf {Encaps}(pk_1, pk_0, r; \mathsf {aux}_{\textsf {e}})\).

• \(\textsf {Decaps}(sk_1, sk_0, c; \mathsf {aux}_{\textsf {d}}){:}\) on input secret keys\(sk_0, sk_1\), auxiliary input\(\mathsf {aux}_{\textsf {d}}\) (if there is) andc, output keyk.

Correctness. For\((pk_1, sk_1) \leftarrow \mathsf {KeyGen1}(\lambda , pp)\),\((pk_0, sk_0) \leftarrow \mathsf {KeyGen0}(\lambda , pp)\) and\((c, k) \leftarrow \mathsf {Encaps}(pk_1, pk_0)\), we require that\(\mathsf {Decaps}(sk_1, sk_0, c) = k\) holds with all but negligible probability.

Security. We consider two kinds of securityi.e., indistinguishability and one-wayness in the attacking model\([\mathsf {ATK}_1,\mathsf {ATK}_0]\). More precisely, in our\([\mathsf {ATK}_1, \mathsf {ATK}_0]\) security model for\(\textsf {2KEM}\), we consider two adversaries,i.e.,\(\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)\) attacking\(pk_1\) (controlling the generation of\(pk_0^*\)) and\(\mathcal {B}=(\mathcal {B}_1, \mathcal {B}_2)\) attacking\(pk_0\) (controlling the generation of\(pk_1^*\)). In Fig. 1 below we show the security games of one-wayness and indistinguishable security corresponding to\([\textsf {IND/OW\text {-}}\mathsf {ATK}_1, \cdot ]\) and\([\cdot , \textsf {IND/OW\text {-}}\mathsf {ATK}_0]\) respectively.

To be clear, the auxiliary inputs\(\mathsf {aux}_{\textsf {e}}\) and\(\mathsf {aux}_{\textsf {d}}\) may contain public part, called public auxiliary input, and secret part, called secret auxiliary input. In the security games, both the challenger and adversary have public auxiliary input, while only the challenger has the secret auxiliary input. For simplicity, we do not explicitly show\(\mathsf {aux}_{\textsf {e}}\) and\(\mathsf {aux}_{\textsf {d}}\) in the security games.

The\([\textsf {ATK1}, \cdot ]\), and\([\cdot , \textsf {ATK0}]\) games of2KEM for adversaries\(\mathcal {A}\) and\(\mathcal {B}\). The oracles\(\mathcal {O}_{\mathsf {leak_0}}\),\(\mathcal {O}_{\mathsf {ATK_1}}\),\(\mathcal {O}_{\mathsf {leak_1}}\), and\(\mathcal {O}_{\mathsf {ATK_0}}\) are defined in the following

Full size image

On thei-th query of\(\mathcal {O}_{\mathsf {leak_0}}\), the challenger generates\((pk^i_0, sk^i_0) \leftarrow \mathsf {KeyGen0}(r_0^i)\), sets\(L_0=L_0\cup \{(pk^i_0, sk^i_0, r_0^i)\}\) and returns\((pk^i_0, sk^i_0, r_0^i)\) to adversary\(\mathcal {A}\). On thei-th query of\(\mathcal {O}_{\mathsf {leak_1}}\), the challenger generates\((pk^i_1, sk^i_1) \leftarrow \mathsf {KeyGen1}(r^i_1)\), sets\(L_1=L_1\cup \{(pk^i_1, sk^i_1, r^i_1)\}\) and returns\((pk^i_1, sk^i_1, r^i_1)\) to adversary\(\mathcal {B}\).

Depending on the definition of oracle\(\mathcal {O}_{\mathsf {ATK_1}}\) the adversary\(\mathcal {A}\) accesses, and\(\mathcal {O}_{\mathsf {ATK_0}}\) that the adversary\(\mathcal {B}\) accesses, we get\(\mathsf {CPA}\) and\(\mathsf {CCA}\) notions respectively.

• if\(\mathcal {O}_{\mathsf {ATK_1}(pk_0', c')}=-\), it implies\(\mathsf {CPA}\) notion;

• if\(\mathcal {O}_{\mathsf {ATK_1}(pk_0', c')}\ne -\), it works as following: If\(pk'_0\in [L_0]_1 \wedge (c'\ne c^*\vee pk'_0\ne pk_0^*)\), compute\(k'\leftarrow \textsf {Decaps}(sk_1, sk'_0, c')\), and return the corresponding\(k'\), otherwise return\(\bot \). This case implies\(\mathsf {CCA}\) notion.

• if\(\mathcal {O}_{\mathsf {ATK_0}(pk_1', c')}=-\), it implies\(\mathsf {CPA}\) notion;

• if\(\mathcal {O}_{\mathsf {ATK_0}(pk_1', c')}\ne -\), it works as following: If\(pk'_1\in [L_1]_1 \wedge (c'\ne c^*\vee pk'_1\ne pk_1^*)\), compute\(k'\leftarrow \textsf {Decaps}(sk'_1, sk_0, c')\), and return the corresponding\(k'\), otherwise return\(\bot \). This case implies\(\mathsf {CCA}\) notion.

Let\(\mathcal {A} = (\mathcal {A}_1, \mathcal {A}_2)\) be an adversary against\(pk_1\) of2KEM. We define the advantage of\(\mathcal {A}\) winning in the game\(\textsf {IND\text {-}ATK1}\) and\(\textsf {OW\text {-}ATK1}\) respectively as:\(\text {Adv}^{[\textsf {IND\text {-}ATK1}, \cdot ]}_{\textsf {2KEM}}(\mathcal {A}) = \left| \Pr [\textsf {IND\text {-}ATK1}^\mathcal {A}\Rightarrow 1] - \frac{1}{2}\right| \), and\(\text {Adv}^{[\textsf {OW\text {-}ATK1}, \cdot ]}_{\textsf {2KEM}}(\mathcal {A}) = \Pr [\textsf {OW\text {-}ATK1}^\mathcal {A}\Rightarrow 1]\), where game\([\textsf {IND\text {-}ATK1}, \cdot ]\) and\([\textsf {OW\text {-}ATK1}, \cdot ]\) are described in Fig. 1.

We say that2KEM is\([\textsf {IND\text {-}ATK1}, \cdot ]\) secure, if\(\text {Adv}^{[\textsf {IND\text {-}ATK1}, \cdot ]}_{\textsf {2KEM}}(\mathcal {A})\) is negligible; that2KEM is\([\textsf {OW\text {-}ATK1}, \cdot ]\) secure, if\(\text {Adv}^{[\textsf {OW\text {-}ATK1}, \cdot ]}_{\textsf {2KEM}}(\mathcal {A})\) is negligible, for any PPT adversary\(\mathcal {A}\). The\([\cdot , \textsf {IND\text {-}ATK0}]\) and\([\cdot , \textsf {OW\text {-}ATK0}]\) security can be defined in the same way. Here to avoid repetition we omit their description.

[ATK1,ATK0]Security. The scheme\(\textsf {2KEM}\) is called\([\textsf {ATK1}, \textsf {ATK0}]\) secure if it is both\([\textsf {ATK1}, \cdot ]\) and\([\cdot , \textsf {ATK0}]\) secure for any PPT algorithms\(\mathcal {A}\) and\(\mathcal {B}\). By the combination of adversaries\(\mathcal {A}\) and\(\mathcal {B}\) attacking different security (i.e., indistinguishability and one-wayness), we could get 16 different definitions of security for 2-key KEM. What we concern in this paper is the [CCA,CPA] security in both indistinguishability and one-wayness setting. For simplicity, we abbreviate the security model as [IND/OW-CCA,IND/OW-CPA].

3.2Differences Between\([\textsf {CCA}, \cdot ]\) Security and Previous Definitions

In order to avoid confusion, we re-clarify the definition of\([\textsf {IND/OW\text {-}CCA}, \cdot ]\) security and analyze its difference with previous similar notions, including classical CCA security, KEM combiner [17], and completely non-malleable scheme [13].

Compared with classical CCA adversary, the\([\text {CCA}, \cdot ]\) adversary of 2-key KEM (1) has the capability of choosing one of the challenge public key\(pk^*_0\); (2) could query a strong decryption oracle, which decapsulates the ciphertext under several public keys\((pk^*_1, pk'_0)\) where\(pk'_0\) is generated by the challenger. While in the classical definition of decapsulation oracle the adversary could only query decapsulation oracle with ciphertext under the challenge public keys\((pk^*_1, pk^*_0)\).

Very recently, Giaconet. al [17] study combiners for KEMs. That is, given a set of KEMs, an unknown subset of which might be arbitrarily insecure, Giaconet. al investigate how they can be combined to form a single KEM that is secure if at least one ingredient KEM is. The KEM combiners treated by Giaconet al. have a parallel structure: If the number of KEMs to be combined isn, a public key of the resulting KEM consists of a vector ofn public keys; likewise for secret keys. The encapsulation procedure performsn independent encapsulations, one for each combined KEM. The ciphertext of the resulting KEM is simply the concatenation of all generated ciphertexts. The session key is obtained as a function of keys and ciphertexts. Although from the literature our 2-key KEM looks like the two KEM combiner, the security requirement and concrete constructions between them are completely different. Since the two KEM combiner considers the problem that if one of two KEMs is insecure and the other one is CCA secure, how to combine them to obtain a CCA secure single KEM. In fact, the adversary of KEM combiner security model is the classical CCA adversary (it can only query the decryption oracle under certain public keys). Actually, in Sect. 6.1, we show there exists\([\text {CCA}, \cdot ]\) adversary to attack a CCA secure two KEM combiner.

Aiming to construct non-malleable commitments, Fischlin [13] considered completely non-malleable (NM) schemes. The complete NM scheme is later extended to indistinguishability setting by Barbosa and Farshim [4] with a strong decryption oracle, which allows the adversary to queries with ciphertext underarbitrary public key of its choice. Note that our\([\text {CCA}, \cdot ]\) is also modeled to allow the adversary to query a strong (but weaker than complete NM) decapsulation oracle with ciphertext under several public keys that are chosen by challenger instead of by adversary. On the other hand, the complete NM adversary is not allowed to choose part of challenge public key, while\([\text {CCA}, \cdot ]\) is.

Based on the above observations, we give comparison among these different definitions by considering two public keys in Table 3. For convenience, we consider classical CCA and complete NM schemes in which public keys are expressed as two public keys\((pk_1, pk_0)\) and let KEM combiner be two combiner of KEM. The differences among security requirements are the capability of adversary, namely, whether the adversary is allowed to choose part of the challenge public keys, or under which public keys the ciphertexts that adversary is allowed to query decryption oracle with are computed.

3.3Basic Definitions and Results Related to 2-Key KEM

[CCA,\(\cdot ]\)Security with Non-adaptive Adversary. We can define a weak\([\textsf {CCA}, \cdot ]\) adversary, who is not able to adaptively choose the challenge public key. In this case, taking the adversary\(\mathcal {A}\) attacking\(pk_1\) as an example, the challenge public key\(pk^*_0\) is generated by challenger instead of\(\mathcal {A}\), which means\(pk^*_0\in [L_0]_1\).

Public Key Independent Ciphertext. The concept of public-key-independent-ciphertext (PKIC) was first proposed in [33]. We extend it to 2-key KEM setting. The PKIC 2-key KEM allows a ciphertext to be generated independently from one of two public keys, while the encapsulated key underlay in such ciphertext to be generated with the randomness and both two public keys. More precisely, algorithm\((c, k)\leftarrow \mathsf {Encaps}(pk_1, pk_0, r)\) can be realized in two steps: in step 1, ciphertexc is generated from\(pk_1\) and randomnessr. We precisely denote it as\(c\leftarrow \mathsf {Encaps0}(pk_1, \text {-}, r)\); in step 2, the encapsulated keyk inc is generated fromr,\(pk_1\), and\(pk_0\). We precisely denote it as\(k\leftarrow \mathsf {Encaps1}(pk_1, pk_0, r)\).

Classical One-Key KEM and 2-Key KEM. Note that given a concrete 2-key KEM, usually it is not obvious and natural to regress to one-key KEM by setting\(pk_0=\text {-}\). However given any classical one-key KEM, it can be seen as a 2-key KEM with\(\textsf {KeyGen0}\) not in use and\(pk_0=\text {-}\). At that time, the\([\textsf {OW/IND\text {-}CCA}, \cdot ]\) security of this 2-key KEM return to the classicalOW/IND-CCA security of the underlying KEM.

Min-Entropy. In case of 2-key KEM with PPT adversary\(\mathcal {A}\), for\((pk_1, sk_1)\leftarrow \textsf {KeyGen1}\) and\(pk_0\leftarrow \mathcal {A}\) or\((pk_0, sk_0)\leftarrow \textsf {KeyGen0}\) and\(pk_1\leftarrow \mathcal {A}\), we define themin-entropy of\(\mathsf {Encaps}(pk_1, pk_0)\) by\(\gamma (pk_1, pk_0, \mathcal {A})=-\log \text {max}_{c\in \mathcal {C}}\Pr [c=\mathsf {Encaps}(pk_1, pk_0)]\). We say that KEM is\(\gamma \)-spread if for every\((pk_1, sk_1)\leftarrow \textsf {KeyGen1}\) and\(pk_0\leftarrow \mathcal {A}\) or\((pk_0, sk_0)\leftarrow \textsf {KeyGen0}\) and\(pk_1\leftarrow \mathcal {A}\),\(\gamma (pk_1, pk_0, \mathcal {A})\ge \gamma \), which means for every ciphertext\(c\in \mathcal {C}\), it has\(\text {Pr}[c=\mathsf {Encaps}(pk_1, pk_0)]\le 2^{-\gamma }\).

In this section, we propose CK\(^+\) secure AKEs from\([\textsf {CCA}, \textsf {CPA}]\) secure 2-key KEM in both random oracle and standard models. Before showing our AKEs, we need a primitive of random function with half of leakage, that is used by several existing AKEs.

Definition 2

(Random Function with half of leakage (hl-RF)). Let\(f:D_{sk}\times D_b\rightarrow R\) be a function from domain\(D_{sk}\times D_b\) toR. Denote\(\textsf {KeyGen}\rightarrow D_{sk}\times D_{pk}\) as key generation algorithm for some KEM. Let\(\mathcal {D}_b, \mathcal {R}\) be the uniformly distributions over\(D_b, R\). It is called\((\varepsilon _1, \varepsilon _2)\) hl-RF with respect to\(\textsf {KeyGen}\), if for\((pk, sk)\leftarrow \textsf {KeyGen}\), the following distributions are computational indistinguishable with advantage\(\varepsilon _1, \varepsilon _2\).

The hk-RF can be achieved in both random oracle model and standard model.

• In the random oracle model, iff is a hash function, without the knowledge ofb, the output off is totally random; if KEM with respect to\(\textsf {KeyGen}\) is secure, without the knowledge ofsk the output off is computational indistinguishable with a random string (otherwise the adversary must query random oracle withsk which against the security of KEM) givenpk. Then Eq. 2 holds. This structure is known as NAXOS trick [24].

• Let\(F': D_{b}\times \{0, 1\}^\lambda \rightarrow R\) and\(F'': D_{sk}\times D_b\rightarrow R\) be two pseudo random functions (PRFs). If assume\(\textsf {KeyGen}\) outputs an additional string\(s\leftarrow \{0, 1\}^\lambda \), after obtaining (pk, sk), set\(sk=(sk||s)\). If\(f(sk, b)=F'_{b}(1^\lambda )\oplus F''_s(b)\), then even givenpk, without the knowledge ofs orb,f(sk, b) is computational indistinguishable with random distribution overR. This is known as twisted PRF trick [15,27].

4.1AKE from 2-Key KEM in Random Oracle Model

Roadmap: We first give a basic AKE from two [OW-CCA,OW-CPA] secure 2-key KEMs. Utilizing extra properties of 2-key KEM, like PKIC or resistance of leakage of partial randomness, we then present two elegant AKEs based on 2-key KEM with different property.

Let\(\textsf {2KEM}=(\textsf {KeyGen1}, \textsf {KeyGen0}, \textsf {Encaps}, \textsf {Decaps})\) be a [OW-CCA,OW-CPA] secure 2-key KEM with secret key space\(D_{sk_1}\times D_{sk_0}\), random spaceR. Let\(H:\{0, 1\}^*\rightarrow \{0, 1\}^{\lambda }\) be hash function,\(f_A: D_{sk_1}\times \{0, 1\}^*\rightarrow R\) and\(f_B: D_{sk_1}\times \{0, 1\}^*\rightarrow R\) be hl-RFs. The CK\(^+\) secure AKE is presented in Fig. 2.

Stage 0: static secret-public key pair and public parameters. Each user’s static secret-public key pair is generated using\(\textsf {KeyGen1}\). Sample one pair of key\((cpk_0, csk_0)\leftarrow \textsf {KeyGen0}\) (which need not to be randomly generated). Set\(cpk_0\) as the predetermined ephemeral public key which will be used by initiator afterwards and\(csk_0\) as the predetermined ephemeral secret key that will be used by responder. Let\((cpk_0, csk_0)\) be parts of public parameters.

Stage 1: Initiator\(U_A\) generates two randomness\(r_A, r_{A0}\); it computes\((C_B, K_B)\) under public key\(pk_B\) and predetermined\(cpk_0\) with randomness\(f_A(sk_A, r_A)\), and generates ephemeral secret-public key\((pk_{A0}, sk_{A0})\leftarrow \textsf {KeyGen0}(r_{A0})\). Then it sends\(C_B, pk_{A0}\) to\(U_B\).

Stage 2: Responder\(U_B\) generates randomness\(r_B\); it computes\((C_A, K_A)\) under public keys\(pk_A\) and\(pk_{A0}\) with randomness\(f_B(sk_B, r_B)\);\(U_B\) sends\(C_A\) to\(U_A\) and de-encapsulates\(C_B\) using\(sk_B\) and predetermined\(csk_0\) to obtain\(K'_B\); it then computes\(SK=H(U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A, K_A, K'_B)\), and erases\(K'_B\).

Stage 3:\(U_A\) de-encapsulates\(C_A\) using\(sk_A\) and\(sk_{A0}\) to obtain\(K'_A\) and computes\(SK=H(U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A, K'_A, K_B)\).

The session state of\(\textsf {sid}\) owned by\(U_A\) consists of ephemeral secret key\(r_{A0}, r_{A}\), decapsulated key\(K'_A\) and encapsulated key\(K_B\); The session state of\(\textsf {sid}\) owned by\(U_B\) consists of ephemeral secrete key\(r_{B}\) and encapsulated key\(K_A\).

\(\mathsf {AKE}\) from [OW-CCA,OW-CPA] secure2KEM in random oracle model.\(cpk_0, csk_0\) are predetermined and default ephemeral keys and they are part of the public parameters.si here is\((U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A)\)

Full size image

Theorem 1

If the underlying2KEM is\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) secure and\(\gamma \)-spread,\(f_A, f_B\) are\((\varepsilon _1, \varepsilon _2)\) hl-RFs, and there areN users in the AKE protocol and the upbound of sessions between two users isl, for any PPT adversary\(\mathcal {A}\) against AKE with totallyq times of CK\(^+\) queries, there exists\(\mathcal {S}\) s.t.,

Proof of Theorem1. Let\(\textsf {Succ}\) be the event that the guess of\(\mathcal {A}\) against freshed test session is correct. Let\(\textsf {AskH}\) be the event that\(\mathcal {A}\) poses\((U_A, U_B, pk_A, pk_B, C_B\),\(pk_{A0}, C_A, K_A, K_B)\) toH, where\(C_B, pk_{A0}, C_A\) are the views of the test session and\(K_A, K_B\) are the keys encapsulated in the test session. Let\(\overline{\textsf {AskH}}\) be the complement of\(\textsf {AskH}\). Then,

where the probability is taken over the randomness used in CK\(^+\) experiment.

We then show that\(\text {Pr}[\textsf {Succ}\wedge \overline{\textsf {AskH}}]\le 1/2\) (as in Lemma1) and\(\text {Pr}[\textsf {AskH}]\) is negligible (as in Lemma2) in all the events (listed in Table 2) of CK\(^+\) model. Followed by Lemmas1 and2, we acheive the security of AKE in CK\(^+\) model. Thus, we only need to prove Lemmas1 and2.

Lemma 1

IfH is modeled as a random oracle, we have\(\text {Pr}[\textsf {Succ}\wedge \overline{\textsf {AskH}}]\le 1/2.\)

Proof of Lemma1. If\(\text {Pr}[\overline{\textsf {AskH}}]=0\) then the claim is straightforward, otherwise we have\( \text {Pr}[\textsf {Succ}\wedge \overline{\textsf {AskH}}] = \text {Pr}[\textsf {Succ}| \overline{\textsf {AskH}}]\text {Pr}[\overline{\textsf {AskH}}] \le \text {Pr}[\textsf {Succ}| \overline{\textsf {AskH}}]. \) Let\(\textsf {sid}\) be any completed session owned by an honest party such that\(\textsf {sid}\ne \textsf {sid}^*\) and\(\textsf {sid}\) is not matching\(\textsf {sid}^*\). The inputs to\(\textsf {sid}\) are different from those to\(\textsf {sid}^*\) and\(\overline{\textsf {sid}^*}\) (if there exists the matching session of\(\textsf {sid}^*\)). If\(\mathcal {A}\) does not explicitly query the view and keys to oracle, then\(H(U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A, K_A, K_B)\) is completely random from\(\mathcal {A}\)’s point of view. Therefore, the probability that\(\mathcal {A}\) wins whenAskH does not occur is exactly 1 / 2.

Lemma 2

If the underlying2KEM is\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) secure, the probability of eventAskH defined above is negligible. Precisely,

Please refer the full version [32] for the formal proof. we give a sketch of proof here. In the following, to bound\(\Pr [\textsf {AskH}]\), we work with the events in Table 4.

Due to the\([\textsf {OW\text {-}CCA}, \cdot ]\) security of\(\textsf {2KEM}\) with\(pk_1=pk_A\) and\(pk_0^*\) generated by\(\mathcal {A}\), the probability of events\(\textsf {AskH}\wedge E_3\) and\(\textsf {AskH}\wedge E_4\) is negligible; Due to the\([\textsf {OW\text {-}CCA}, \cdot ]\) security of\(\textsf {KEM}\) with\(pk_1=pk_B\) and\(pk_0^*=cpk_0\), the probability of events\(\textsf {AskH}\wedge E_1\),\(\textsf {AskH}\wedge E_2\),\(\textsf {AskH}\wedge E_{7\text {-}1}\) and\(\textsf {AskH}\wedge E_{\text {8-2}}\) is negligible; Due to the\([\textsf {OW\text {-}CCA}, \cdot ]\) security of\(\textsf {2KEM}\) with\(pk_1=pk_A\) and\(pk_0^*\in [L_0]_1\), the probability of events\(\textsf {AskH}\wedge E_6\),\(\textsf {AskH}\wedge E_{\text {7-2}}\) and\(\textsf {AskH}\wedge E_{\text {8-1}}\) is negligible. Due to the\([\cdot , \textsf {OW\text {-}CPA}]\) security with\(pk_1^*\in [L_1]_1\), the probability of event\(\textsf {AskH}\wedge E_{5}\) is negligible.

Here, we only take\(\textsf {AskH}\wedge E_3\) as an example to explain in detail. For the other cases we can deal with them in a similar way. In the event\(E_3\), the test session\(\mathsf {sid}^*\) has no matching session, and the ephemeral secret keys\(r_B\) of\(U_B\) is given to\(\mathcal {A}\). In case of\(\mathsf {AskH}\wedge E_3\), the\([\textsf {OW\text {-}CCA}, \cdot ]\) adversary\(\mathcal {S}\) performs as follows. It simulates the CK\(^+\) games, and transfers the probability that the event\(\textsf {AskH}\) performed by\(\mathcal {A}\) occurs to the advantage of attacking\([\textsf {OW\text {-}CCA}, \cdot ]\) security.

In order to simulate the random oracles,\(\mathcal {S}\) maintains two lists forH oracle andSessionKeyReveal respectively.H-oracle andSessionKeyReveal are related, which means the adversary may askSessionKeyReveal without the encapsulated keys at first, and then may askH-oracle with the encapsulated keys. Thus, the reduction must ensure consistency with the random oracle queries toH andSessionKeyReveal. The decryption oracle for\([\textsf {OW\text {-}CCA}, \cdot ]\) game would help to maintain the consistency ofH-oracle andSessionKeyReveal.

On receiving the public key\(pk_1\) from the\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger, to simulate the CK\(^+\) game,\(\mathcal {S}\) randomly chooses two parties\(U_A, U_B\) and thei-th session as a guess of the test session with success probability\(1/N^2l\).\(\mathcal {S}\), picks one preset\((cpk_0, csk_0)\leftarrow \textsf {KeyGen0}\) as public parameters, runs\(\textsf {KeyGen1}\) to set all the static secret and public key pairs\((pk_P, sk_P)\) for allN users\(U_P\) except for\(U_A\). Specially,\(\mathcal {S}\) sets the static secret and public key pairs\((pk_B, sk_B)\) for\(U_B\), and sets\(pk_A=pk_1\).

Without knowing the secret key of\(U_A\),\(\mathcal {S}\) chooses totally random\(r_A\) as part of ephemeral secret key and totally random\(R_A\) for\(\textsf {Encaps}\). Since\(f_A\) is\((\varepsilon _1, \varepsilon _2)\) hl-RF, the difference between simulation with modification of\(r_A\) and real game is bounded by\(\varepsilon _1\). When a ephemeral public key\(pk_{P0}\) is needed,\(\mathcal {S}\) queries\((pk_0^i, sk_0^i, r_0^i)\leftarrow \mathcal {O}_{\mathsf {leak}_0}\) and sets\(pk_{P0}=pk^i_0\). When a session state revealed to a session owned by\(U_A\), is queried,\(\mathcal {S}\) returns\(r_A\) and\(r_0^i\) of this session as part of ephemeral secret key.

On receiving thei-th session\((C'_B, pk_0^*)\) from\(U_A\) (that is sent by\(\mathcal {A}\) in the CK\(^+\) games),\(\mathcal {S}\) returns\(pk_0^*\) to the\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger and receives the challenge ciphertext\(C^*\) under public key\(pk_1\) and\(pk_0^*\). Then\(\mathcal {S}\) returns\(C^*\) to\(U_A\) as the response ofi-th session from\(U_B\).\(\mathcal {S}\) chooses a totally independent randomness\(r_B\) as the ephemeral secret key of\(U_B\) for\(C^*\) and leaks it to adversary\(\mathcal {A}\). Since\(f_B\) is\((\varepsilon _1, \varepsilon _2)\) hl-RF, the difference between simulation with modification of\(r_B\) and real game is bounded by\(\varepsilon _2\).

\(\mathcal {S}\) simulates the oracle queries of\(\mathcal {A}\) and maintains the hash lists. Specially, when\(\textsf {AskH}\) happens, which means\(\mathcal {A}\) poses\((U_A, U_B, pk_A, pk_B, C'_B, pk_0^*, C^*, K_A, K_B)\) toH, where\(C'_B, pk_0^*, C^*\) are the views of the test session and\(K_B\) is the key encapsulated in\(C'_B\),\(\mathcal {S}\) returns\(K_A\) as the guess of\(K^*\) encapsulated in\(C^*\), which contradicts with the\([\textsf {OW\text {-}CCA}, \cdot ]\) security for\(pk_1=pk_A\),\(pk^*_0\leftarrow \mathcal {A}\).\(\square \)

4.1.1If 2-Key KEM Is PKIC

As we notice in\(\textsf {AKE}\), the session state of\(\textsf {sid}\) owned by\(U_B\) does not contain decapsulated key\(K'_B\). If the underlying 2-key KEM is PKIC (which is defined in Sect.3.3), and\(U_B\) also sends ephemeral public key\(pk_{B0}\) out in every session,\(K'_B\) is encapsulated under two public keys\(pk_B\) and\(pk_{B0}\), then\(K'_B\) could be included in session state, and the predetermined ephemeral public key\(cpk_0\) can be omitted. Let\(\mathsf {2KEM}_{\textsf {pkic}}=(\textsf {KeyGen1}, \textsf {KeyGen0}, \textsf {Encaps0}, \textsf {Encaps1}, \textsf {Decaps})\) be PKIC and\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) secure 2-key KEM. The\(\textsf {AKE}\) can be modified to include\(K'_B\) as session state by (1) replacing2KEM with\(\mathsf {2KEM}_{\textsf {pkic}}\); (2) requiring\(U_B\) to generate a fresh\((pk_{B0}, sk_{B0})\leftarrow \textsf {KeyGen0}\) and send out ephemeral public key\(pk_{B0}\); (3) encapsulating and separating\((C_B, K_B)\leftarrow \textsf {Encaps}(pk_B, pk_{B0}, R_A)\) in two steps and computing\(C_B \leftarrow \mathsf {Encaps0}(pk_{B}, \text {-}, R_A)\) and\(K_B \leftarrow \mathsf {Encaps1}(pk_{B}, pk_{B0}, R_A)\). The modified protocol\(\mathsf {AKE}_{\textsf {ro\text {-}pkic}}\) is shown in Fig. 3.

Note that the encapsulation algorithm of PKIC 2-key KEM can be split into two steps. Since the generation of ciphertext\(C_B\) does not require\(pk_{B0}\), we denote it as\(C_B\leftarrow \textsf {Encaps0}(pk_B, \text {-}, R_A)\). The computation of encapsulated key\(K_B\) requires\(pk_{B0}\), and we denote it as\(K_B\leftarrow \textsf {Encaps1}(pk_B, pk_{B0}, R_A)\).

\(\mathsf {AKE}_{\textsf {ro\text {-}pkic}}\) from PKIC [OW-CCA,OW-CPA] secure2KEM. Here\(si=(U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A, pk_{B0})\). The boxed argument is the difference withAKE

Full size image

Since the proof mainly follows that of Theorem1, we only show the difference here. The main difference is the analysis of\(\Pr [\textsf {AskH}]\) in Lemma2. Now, the probability of events\(\textsf {AskH}\wedge E_1\),\(\textsf {AskH}\wedge E_2\),\(\textsf {AskH}\wedge E_{7\text {-}1}\),\(\textsf {AskH}\wedge E_{\text {8-2}}\) is bounded by the\([\textsf {OW\text {-}CCA}, \cdot ]\) security of\(\mathsf {2KEM}_{\textsf {pkic}}\) with\(pk^*_0\) chosen by\(\mathcal {A}\) rather than the predetermined\(cpk_0\). Precisely, in those events, when the adversary queries the session state of\(U_B\) whose secret key is unknown to simulator\(\mathcal {S}\), in\(\textsf {AKE}\),\(\mathcal {S}\) queries the decryption oracle of2KEM with\(cpk_0\) and\(C_B\) (when adversary queries\(\textsf {Send}(\Pi , R, U_B, U_P, C_B, pk_{A0})\)), while in\(\mathsf {AKE}_{\textsf {pkic}}\),\(\mathcal {S}\) queries the decryption oracle of\(\mathsf {2KEM}_{\textsf {pkic}}\) with\((pk_{B0}, C_B)\) chosen by\(\mathcal {A}\). This modification does not affect the proof of security.

4.1.2If PKIC 2-Key KEM Is Even Secure with Leakage of Partial Randomness

We can further refine the framework\(\mathsf {AKE}_{\textsf {ro-pkic}}\) based on two observations: (1) From the proof of Theorem1 (especially Lemma2), we can see that the only purpose of\(f_A\) and\(f_B\) is to preserve the\([\textsf {OW\text {-}CCA}, \cdot ]\) security with\(pk_1=pk_A\) and the\([\cdot , \textsf {OW\text {-}CPA}]\) security with\(pk_0=pk_{A0}\) even if part of randomness,\(r_B\) or\(sk_B\) is leaked to the adversary. If the underlying 2-key KEM itself is strong enough to preserve the\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) security with respect tosome function\(f_A(sk_A, r_A)\) (resp.\(f_B(sk_B, r_A)\)), and leakage of\(sk_A\) or\(r_A\) for fixed\(pk_A\) (resp.\(sk_B\) or\(r_B\) for fixed\(pk_B\)), the functions\(f_A\) and\(f_B\) don’t have to be hl-RFs. (2) if the 2-key KEM is strong enough to preserve security even when the randomness\(r_{B0}\) used to generate\(pk_{B0}\) is generated from\(f_{B0}(sk_B, r_B)\) for some function\(f_{B0}\), then we could regard\(f_{B0}(sk_B, r_B)\) as a random string using to compute\(pk_{B0}\). The same holds when\((pk_{A0}, sk_{A0})\leftarrow \textsf {KeyGen0}(r_{A0})\) where\(r_{A0}=f_{A0}(sk_A, r_A)\) for some function\(f_{A0}\).

Therefore, the problem comes down to study the security of 2-key KEM when\(C_A\) (under public keys\(pk_A\) and\(pk_{A0}\)) shares the randomness of\(pk_B\) and\(pk_{B0}\).

Definition 3

We say 2-key KEM isleakage resistant of partial randomness with respect to\(f_B\) and\(f_{B0}\) (they need not to be hl-RFs), if the following property holds. Under public key\(pk_A\) and\(pk_{A0}\), the\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) security still holds where the ciphertext is computed as\(\textsf {Encaps}(pk_A, pk_{A0}, f_B(sk_B, r_{B}))\) for some fixed\(pk_B\) (where\((pk_B, sk_B)\leftarrow \textsf {KeyGen1}\)), when either\(r_{B}\) and\(pk_{B0}\) or\(sk_B\) and\(pk_{B0}\) are given to adversary, where\((pk_{B0}, sk_{B0})\leftarrow \textsf {KeyGen0}(f_{B0}(sk_B, r_{B}))\).

Equipped with PKIC 2-key KEM that resists to the leakage of partial randomness with respect to\(f_B\) and\(f_{B0}\), we set\(f_{A0}(sk_A, r_A)\) and\(f_{B0}(sk_B, r_B)\) as the randomness for\(\textsf {KeyGen0}\), and denote the result AKE as\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) in Fig. 4. The session state ofsid owned by\(U_A\) consists of\(r_A\),\(K'_A\) and\(K_B\), the session state ofsid owned by\(U_B\) consists of\(r_B\),\(K_A\) and\(K'_B\).

\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\). Here\(si=(U_A, U_B, pk_A, pk_B, C_B, pk_{A0}, C_A, pk_{B0})\). The boxed argument is the main difference with\(\mathsf {AKE}_{\textsf {ro\text {-}pkic}}\)

Full size image

Remark 1

As in the definition of 2-key KEM, both\(\textsf {Encaps}\) and\(\textsf {Decaps}\) allow to have auxiliary input\(\mathsf {aux}_{\textsf {e}}\) or\(\mathsf {aux}_{\textsf {d}}\). In\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) (AKE and\(\mathsf {AKE}_{\textsf {ro\text {-}pkic}}\)), the static public keys are generated by\(\textsf {KeyGen1}\) during the registration phase (i.e., Stage 0) and publicly available. Thus, in the protocol, it makes sense that\(\textsf {Encaps}\) and\(\textsf {Decaps}\) algorithms take the static public keys as public auxiliary input. And for user\(U_A\) (resp.\(U_B\)), it is also reasonable that\(\textsf {Encaps}\) executed by\(U_A\) (resp.\(U_B\)) takes his static secret key\(sk_A\) (resp.\(sk_B\)) as auxiliary input. In this sense, one couple of2KEM is really “coupled” with each other.

Remark 2

Since\(C_A\) share the randomness of\(pk_{B0}\) and secret key of\(pk_{B}\), if the 2-key KEM and function\(f_B/f_{B0}\) further satisfy that\(C_A\) is publicly computable from\(pk_B\) and\(pk_{B0}\), we can omit\(C_A\) in the communications. The same holds for\(C_B\), if it is publicly computable from\(pk_A\) and\(pk_{A0}\), we can omit\(C_B\).

Remark 3

Note that the computation of\(f_B\) is part of\(\textsf {Encaps}(pk_A, pk_{A0}, R_B)\) algorithm.\(f_B\) may take\(pk_A\) as input. At that time, to be clear, we denote\(f_B(sk_B, r_B)\) as\(f_B(sk_B, r_B, pk_A)\). It is similar in the case of\(f_A\).

With these modifications, we should handle the proof more carefully. The main challenge is that the ciphertext\(C_A\), static public key\(pk_B\), ephemeral public key\(pk_{B0}\) are correlated (the same holds for\(C_B\),\(pk_A\), and\(pk_{A0}\)). We should handle the problem that, since\(C_A\) shares the randomness with\(pk_{B0}\) and secret key of\(pk_{B}\), when applying the\([\textsf {OW\text {-}CCA}, \cdot ]\) security of 2-key KEM with\(pk_1=pk_A\) in event\(\textsf {AskH}\wedge E_3\),\(\textsf {AskH}\wedge E_6\), not only\(sk_A\) but also\(sk_B\) is unknown to simulator\(\mathcal {S}\). (The same situation occurs when applying\([\textsf {OW\text {-}CCA}, \cdot ]\) security of 2-key KEM with\(pk_1=pk_B\) in event\(\textsf {AskH}\wedge E_2\)).

The way to solving this problem is to bring in another\([\textsf {OW\text {-}CCA}, \cdot ]\) challenge. As an example, we sketch the proof of event\(\textsf {AskH}\wedge E_3\) to show how this resolves the above problem. The main modification is for the proof of Lemma2. In case of\(\mathsf {AskH}\wedge E_3\), the\([\textsf {OW\text {-}CCA}, \cdot ]\) adversary\(\mathcal {S}\) performs as follows. On receiving the public key\(pk_1\) from the\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger, to simulate the CK\(^+\) game,\(\mathcal {S}\) randomly chooses two parties\(U_A, U_B\) and thei-th session as a guess of the test session.\(\mathcal {S}\) runs\(\textsf {KeyGen1}\) to generate all static public keys except\(U_A\) and\(U_B\).\(\mathcal {S}\) queries the first\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger to get\(pk_1\), and sets\(pk_A=pk_1\).\(\mathcal {S}\) queries the second\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger again to get another\(pk'_1\) and sets\(pk_B=pk'_{1}\).

Note that now\(\mathcal {S}\) does not know the secret key of both\(pk_A\) and\(pk_B\). Here\(\mathcal {S}\) generates\((pk^*_{B0}, sk^*_{B0})\) by itself.\(\mathcal {S}\) sends\(pk^*_{B0}\) to the second challenge to get challenge ciphertext\(C^*_{B}\) and keeps both\(pk^*_{B0}\) and\(C^*_{B}\) secret to CK\(^+\) adversary\(\mathcal {A}\). On receiving thei-th session\((C'_B, pk_{A0}^*)\) from\(U_A\) (that is sent by\(\mathcal {A}\) in the CK\(^+\) games),\(\mathcal {S}\) queries the first\([\textsf {OW\text {-}CCA}, \cdot ]\) challenger with\(pk_{A0}^*\) and obtains\(C^*_A\),\(pk_{B0}\) and its randomness\(r_{B0}\).\(\mathcal {S}\) returns\(C^*_A\) and\(pk_{B0}\) to\(U_A\) as the response ofi-th session from\(U_B\), and sets\(pk_{A0}^*\) as the public key under which\(C^*_A\) is encrypted.\(\mathcal {S}\) also leaks\(r_{B0}\) to adversary as the ephemeral secret key.

With the first\([\textsf {OW\text {-}CCA}, \cdot ]\) challenge,\(\mathcal {S}\) could partially maintain the hash list and\(\textsf {SessionStateReveal}\) and\(\textsf {SessionKeyReveal}\) with strong decapsulation oracle when\(U_B\) is not involved. When\(U_B\) is involved, the second\([\textsf {OW\text {-}CCA}, \cdot ]\) challenge is needed. Note that since 2-key KEM is\(\gamma \)-spread, the probability that\(\mathcal {A}\) queries a message with\(C_B=C^*_B\) is bounded by\(q\times 2^{-\gamma }\). The simulation is perfect and the other part of proof proceeds the same with Lemma2.

4.2AKE from 2-Key KEM in Standard Model

The protocol\(\textsf {AKE}/\mathsf {AKE}_{\textsf {ro\text {-}pkic}}\) in random oracle model can be easily extended to one that is secure in the standard model, denoted by\(\mathsf {AKE}_{\textsf {std}}/\mathsf {AKE}_{\textsf {std\text {-}pkic}}\), via the following steps:

1. 1.

   replacing the\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CPA}]\) secure 2-key KEM in random oracle model with the\([\textsf {IND\text {-}CCA}, \textsf {IND\text {-}CPA}]\) secure 2-key KEM in standard model;

2. 2.

   instantiating the hl-RF functions\(f_A, f_B\) in standard model instead of the random oracle model. As noted after the definition, the instantiation of hl-RF in standard model require PRF and extra randomness. Thus every user holds extra random secret\(s_P\leftarrow \{0, 1\}^\lambda \) as part of the static secret key and\(R_A=f_A(sk_A||s_A, r_A)\),\(R_B=f_B(sk_B||s_B, r_B)\).

3. 3.

   replacing the random oracle\(H(si, K_A, K_B)\) with\(F_{K_A}(si)\oplus \hat{F}_{K_B}(si)\), to extract session key, whereF and\(\hat{F}\) are PRFs.

Actually, converting a scheme in the random oracle model into that in the standard model is generally not trivial, and there are many negative results. However, without taking advantage of strong property of random oracle, our step 2 and 3 just use the property that if the input is unknown then the output is totally random. The difficult part is step 1. Once the 2-key KEM in random oracle model is replaced by\([\textsf {IND\text {-}CCA}, \textsf {IND\text {-}CPA}]\) secure 2-key KEM in standard model, the proof of security for AKE in standard model is straightforward.

In this section, we show that existing AKEs, HMQV [23], NAXOS [24], Okamoto [27], and FSXY framework [15,16], can be explained in our unified frameworks.

5.1HMQV-AKE

In HMQV [23], the 2-key KEM is initiated by\(\mathsf {2KEM_{HMQV}}\) in Fig. 5. Leth and\(\hat{H}\) be hash functions. LetG be a group of prime orderp withg as a generator. Both\(\textsf {Encaps}\) andDecaps algorithms have auxiliary input\(\mathsf {aux}_{\textsf {e}}=(B, b)\) where\(B=g^b\) and\(\mathsf {aux}_{\textsf {d}}=B\). Note that, here,B is the public auxiliary input andb is the secret auxiliary input. By applying\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\), Remarks1–3, we present how the HMQV scheme is integrated in our unified framework of AKE and how it is built from the view of 2-key KEM in Fig. 6.

The [OW-CCA,OW-CCA] secure\(\mathsf {2KEM_{HMQV}}\) implied by HMQV.

Full size image

Theorem 2

Under the Gap-DH and KEA1 assumptions^Footnote1,\(\mathsf {2KEM_{HMQV}}\) in Fig. 5 is [OW-CCA,OW-CCA] secure with the resistance to the leakage of partial randomness with respect to\(f_B(b, y, A)=y+b\cdot h(g^y, A)\) and\(f_{B0}(b, y)=y\) in the random oracle model.

Please refer the full version [32] for the proof of Theorem2.

As said in Remark3,\(f_B\) takesA as input and\(f_B(b, y, A)=y+b\cdot h(g^y, A)\). By Theorem2,\(\mathsf {2KEM_{HMQV}}\) is [OW-CCA,OW-CCA] secure even if partial randomness (b ory) is leaked with respect to\(f_B(b, y, A)=y+b\cdot h(g^y, A)\) and\(f_{B0}(b, y)=y\). By changing the role ofA andB,X andY, we also get a dual scheme of\(\mathsf {2KEM_{HMQV}}\), with respect to\(f_A(a, x, B)=x+a\cdot h(g^x, B)\) and\(f_{A0}(a, x)=x\). Obviously,\(\mathsf {2KEM_{HMQV}}\) is PKIC, which means that the ciphertext is independent of the public key\(pk_0\). Thus the\(\textsf {Encaps}\) algorithm can be split into two stepsEncaps0 andEncaps1. However, when integrating\(\mathsf {2KEM_{HMQV}}\) into\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) to reproduce HMQV, one may doubt that whether\(\textsf {aux}_e=(B, b)\) or (A, a) required by\(\textsf {Encaps}\) and\(\text {aux}_d=B\) orA required by\(\text {Decaps}\) influence the reconstruction. As explained in Remark2, sinceB andA are the static public keys and generated during the registration phase, they can be used as the public auxiliary input by any user during the execution phase. As a static secret key,b can be used by\(U_B\) as secret auxiliary input during the execution phase. Based on the above analysis, applying\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) and Remarks1–3 to\(\mathsf {2KEM_{HMQV}}\), HMQV is reconstructed in Fig. 6.

Moreover,A,B are static public keys, andd,e are publicly computable,\(C_A\),\(C_B\) can be publicly computed from\(pk_{B0}=Y\) and\(pk_{A0}=X\). Thus, we can apply Remark1 to omit\(C_B=XA^d\) and\(C_A=YB^d\) in the communications.

Understanding HMQV with\(\mathsf {2KEM}_{\textsf {HMQV}}\) in the frame\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) where\(si=(U_A, U_B, A, B, C_B, X, C_A, Y)\).

Full size image

5.2NAXOS-AKE

In [24], the 2-key KEM is initiated by\(\mathsf {2KEM_{NAXOS}}\) in Fig. 7. LetG be a group of prime orderp withg as a generator. Let\(h:\mathbb {Z}_p\times \mathbb {Z}_p\rightarrow \mathbb {Z}_p\) and\(\hat{H}: \mathbb {Z}_p\times \mathbb {Z}_p\rightarrow \{0, 1\}^\lambda \) be hash functions. By applying\(\mathsf {AKE}_{\textsf {ro-pkic-lr}}\) and Remarks1–2, in Fig. 8, we present how the NAXOS scheme is integrated in our unified framework of AKE and how it is built from the view of 2-key KEM.

The [OW-CCA,OW-CCA] secure\(\mathsf {2KEM_{NAXOS}}\) implied by NAXOS

Full size image

Theorem 3

Under the Gap-DH assumption,\(\mathsf {2KEM_{NAXOS}}\) is\([\textsf {OW\text {-}CCA}, \textsf {OW\text {-}CCA}]\) secure even with the leakage of one of\(y_0\) andb where\(f_B(b, y_0)=h(b, y_0)\) and\(f_{B0}(b, y_0)=h(b, y_0)\) in the random oracle model.

By Theorem3,\(\mathsf {2KEM_{NAXOS}}\) is [OW-CCA,OW-CCA] secure even if partial randomness (b or\(y_0\)) is leaked with respect to\(f_B(b, y_0)=h(b, y_0)\) and\(f_{B0}(b, y_0)=h(b, y_0)\). Obviously,\(\mathsf {2KEM_{NAXOS}}\) is PKIC. We split\(\textsf {Encaps}\) algorithm into two stepsEncaps0 andEncaps1. As explained in Remark2, sinceb is static secret key and generated by\(U_B\), in the execution phase\(U_B\) takes it as secret auxiliary input. Based on the above analysis, applying\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) and Remarks1–2 to\(\mathsf {2KEM_{NAXOS}}\), NAXOS is reconstructed in Fig. 8.

Moreover,\(C_A\) is equal to\(pk_{B0}=Y\) and\(C_B\) is equal to\(pk_{A0}=X\). Thus we can apply Remark2 to omit\(C_B=X\) and\(C_A=Y\) in the communications.

Understanding NAXOS with\(\mathsf {2KEM}_{\textsf {naxos}}\) in the frame\(\mathsf {AKE}_{\textsf {ro\text {-}pkic\text {-}lr}}\) where\(si=(U_A, U_B, A, B, X, Y)\).

Full size image

5.3Okamoto-AKE

In Okamoto-AKE [27], the 2-key KEM is initiated by\(\mathsf {2KEM_{Oka}}\) in Fig. 9. In\(\mathsf {2KEM_{Oka}}\), the computation is proceeded over groupG of prime orderp with generatorg,\(h_{tcr}\) is a target-collision resistant (TCR) hash function and\(\bar{F}\) is a pairwise-independent random source PRF. (Please refer [27] for the formal definition of pairwise-independent random source PRFs.)

The [IND-CCA,IND-CPA] secure\(\mathsf {2KEM}_{\textsf {Oka}}\) implied by Okamato-AKE.

Full size image

LetG be a group of orderp with the generatorg. Let\(1_G=g^p\) be the identity element. The DDH assumption states that\(\{(G, g^a, g^b, g^{ab})\}_{\lambda }\) is computationally indistinguishable from\(\{(G, g^a, g^b, g^{c})\}_{\lambda }\), wherea, b, c are randomly and independently chosen in\(\mathbb {Z}_{p}\). If\(c=ab\),\((g, g^a, g^b, g^c)\) is called a DDH tuple, otherwise it’s called a non-DDH tuple. Denote the advantage of any PPT algorithm\(\mathcal {B}\) solving DDH problem as\(\text {Adv}^{\textsf {ddh}}_{\mathcal {B}}=|\Pr [\mathcal {B}(g^a, g^b, g^{ab})=1]-\Pr [\mathcal {B}(g^a, g^b, g^{c})=1]|\).

Theorem 4

Under the DDH assumption, if\(h_{tcr}\) is a TCR hash function and\(\bar{F}\) is a pairwise-independent random source PRF, then\(\mathsf {2KEM_{Oka}}\) in Fig. 9 is [IND-CCA,IND-CPA] secure in the standard model.

Please refer the full version [32] for the formal proof of Theorem4.

By applying\(\mathsf {AKE_{std}}\), in Fig. 10, we present how the Okamato scheme is integrated in our unified framework of AKE and how it is built from the view of 2-key KEM. Let\(F':\{0, 1\}^\lambda \times \{0, 1\}^\lambda \rightarrow \mathbb {Z}_p\) and\(F'':\mathbb {Z}_p\times \{0, 1\}^\lambda \rightarrow \mathbb {Z}_p\) be PRFs. In the frame of\(\mathsf {AKE_{std}}\), by setting\(s_A=a_0, s_B=b_0\),\(r_A=x'_1||x'_2, r_{A0}=x_3\),\(r_B=y'_1||y'_2\), choosing\(cpk_0=1_G, csk_0=p\), initiating\(f_A\) and\(f_B\) as\(F'_{x'_1}(1^k)\oplus F''_{\sum _0^4 a_i}(x'_2)\) and\(F'_{y'_1}(1^k)\oplus F''_{\sum _0^4 b_i}(y'_2)\), and applying\(\mathsf {2KEM}_{\textsf {Oka}}\) as 2-key KEM, we will get Okamoto AKE in Fig. 10.

Understanding Okamoto-AKE from\(\mathsf {2KEM}_{\textsf {Oka}}\) where\(si=(U_A, U_B, C_B, X_3, C_A)\) in frame\(\mathsf {AKE_{std}}\). Some notions are borrowed from\(\mathsf {2KEM}_{\textsf {Oka}}\)

Full size image

5.4FSXY12-AKE and FSXY13-AKE

Fujiokaet al. in PKC 12 (called FSXY12 [15]) proposed a construction of AKE from IND-CCA secure KEM and IND-CPA secure KEM in the standard model. In FSXY12 [15],\(U_B\) sends a ciphertext of IND-CCA secure KEM and a ciphertext of IND-CPA secure KEM, and the session key is computed from these two encapsulated keys, public key of IND-CPA secure KEM, and ciphertext in the PRF functions. As we point out in Sect. 6.1, the FSXY12 scheme implies a trivial\([\textsf {IND\text {-}CCA},\textsf {IND\text {-}CPA}]\) secure 2-key KEM from the improved KEM combiner in the standard model. More precisely, in\(\mathsf {AKE_{std}}\),\(cpk_0\) and\(csk_0\) is set to be empty;\(C_B\) is just\(c_{B1}||\text {-}\), where\(c_{B1}\) is the ciphertext of IND-CCA secure one-key KEM under\(pk_B\);\(C_A\) is replaced by the concatenation of\(c_{A1}||c_{A0}\), where\(c_{A1}\) is the ciphertext of IND-CCA secure one-key KEM under\(pk_A\) with encapsulated key\(k_{A1}\) and\(c_{A0}\) is the ciphertext of IND-CPA secure one-key KEM under\(pk_{A0}\) with encapsulated key\(k_{A0}\); and\(K_A\) is replaced by\(F_{k_{A1}}(pk_{A0}, c_{A1}||c_{A0})\oplus F_{k_{A0}}(pk_{A0}, c_{A1}||c_{A0})\). To make it clearer, in Sect. 6.1 we explain why we should put public key in PRFs when combining two KEMs. Note that FSXY12 implicitly did it in the same way by putting\(\textsf {sid}\) in PRF. Thus, due to this observation, our frame of\(\mathsf {AKE_{std}}\) with improved KEM combiner can be used to explain the FSXY12 scheme.

Considering efficiency, Fujiokaet al. in AsiaCCS 13 (called FSXY13 [16]) proposed AKE from OW-CCA secure KEM and OW-CPA secure KEM in the random oracle model. In FSXY13 [16],\(U_B\) sends a ciphertext of OW-CCA secure KEM and a ciphertext of OW-CPA secure KEM. The session key is computed from these two encapsulated keys, public key of CPA secure KEM, and ciphertext in the hashing step. As we point out in Sect. 6.1, the FSXY13 scheme implies a trivial\([\textsf {OW\text {-}CCA},\textsf {OW\text {-}CPA}]\) secure 2-key KEM from the improved KEM combiner in the random oracle model. Precisely, in\(\mathsf {AKE}\),\(cpk_0\) and\(csk_0\) is set to be empty;\(C_B\) is just\(c_{B1}||\text {-}\), where\(c_{B1}\) is the ciphertext of OW-CCA secure one-key KEM under\(pk_B\);\(C_A\) is replaced by the concatenation of\(c_{A1}||c_{A0}\), where\(c_{A1}\) is the ciphertext of OW-CCA secure one-key KEM under\(pk_A\) with encapsulated key\(k_{A1}\) and\(c_{A0}\) is the ciphertext of OW-CPA secure one-key KEM under\(pk_{A0}\) with encapsulated key\(k_{A0}\); and\(K_A\) is replaced by\(\hat{H}(pk_{A0}, k_{1}||k_{A0}, c_{A1}||c_{A0})\). In Sect. 6.1 we explain why we should put public key in hashing step when combining two KEMs. Note that FSXY13 implicitly did it in the same way by putting\(\textsf {sid}\) in hashing step. Thus, our frame of\(\mathsf {AKE}\) with improved KEM combiner works for explaining the FSXY13 scheme.

In this section we investigate how to improve the KEM combiner [17] and Fujisaki-Okamoto transformation [14,18] so as to yield more general constructions of 2-key KEM, which are much more well-suited for lattice assumptions.

6.1Improved Combiner of Two KEMs

Giaconet al. [17] propose two KEM combiner and yield a new single KEM that is classical CCA secure as long as one of the ingredient KEMs is. We show that the simple KEM combiner does not work for our 2-key KEM. Furthermore, we show that with a slight but vital modification the combiner could work.

6.1.1The Failure to Imply\([\textsf {OW\text {-}CCA}, \cdot ]\) Secure 2key KEM from KEM Combiner

We give a scheme that is a CCA secure two KEM combiner but is not\([\textsf {OW\text {-}CCA}, \cdot ]\) secure.

Leth andH be hash functions. Let\(G=<g>\) be a group with prime orderp. Let\(pk_1=(g_1, g_2=g_1^a), sk_1=a\), the ciphertext be\(c_1=(g_1^r, g_2^r\cdot m)\) where\(r=h(m)\) and the encapsulated key be\(k_1=H(m)\). By the FO transformation [14] and DDH assumption, the first KEM is one-way-CCA secure. Let\(pk_0=(h_1, h_2=h_1^b), sk_0=b\), the ciphertext be\(c_0=h_1^x\) and the encapsulated key be\(k_0=H(h_2^x)\); and obviously the second KEM is IND-CPA secure.

Let the combined ciphertext be\((c_1||c_0)\) and combined encapsulated key be\(K=\hat{H}(k_1||k_0, c_1||c_0)\), by the KEM combiner [17] (Lemma 6 and Example 3 in [17]), the combined KEM is CCA secure. However, such combined KEM is not\([\textsf {OW\text {-}CCA}, \cdot ]\) secure which means there exists an adversary\(\mathcal {A}\) that can break\([\textsf {OW\text {-}CCA}, \cdot ]\) game.

Note that\(c_0=h_1^x\) encapsulates the key\(k^*_0=H(h_2^x)\) under public key\(pk_0=(h_1, h_2)\) while it encapsulates the same key\(k^*_0=H(h_2^x)\) under public key\(pk_0=(h_1^c, h_2^c)\) for some\(c\in \mathbb {Z}_p\). The\([\textsf {OW\text {-}CCA}, \cdot ]\) adversary\(\mathcal {A}\) first queries the\(\mathcal {O}_{\textsf {leak}}\) oracle and gets\(pk_0=(h_1, h_2)\). Then it randomly chooses\(c\in \mathbb {Z}_p\) and sets\(pk^*_0=(h_1^c, h_2^c)\). After receiving\(c_1^*||c^*_0\) under public keys\(pk_1\) and\(pk^*_0\),\(\mathcal {A}\) queries the decryption oracle with\((pk_1, pk_0, c^*_1||c^*_0)\), and would receive exactly\(K^*=\hat{H}(k^*_1||k^*_0, c^*_1||c^*_0)\).

6.1.2Improvement on KEM Combiner to Achieve\([\textsf {CCA}, \textsf {CPA}]\) Secure 2-Key KEM

Inspired by the attacks above, we propose a improved combiner of CCA secure and CPA secure KEMs to achieve\([\textsf {CCA}, \textsf {CPA}]\) secure 2-key KEM. Let\(\mathsf {KEM_{cca}}=(\mathsf {KeyGen_{cca}}, \mathsf {Encaps_{cpa}}, \mathsf {Decaps_{cca}})\) be IND-CCA secure KEM,\(\mathsf {KEM_{cpa}}=(\mathsf {KeyGen_{cpa}}, \mathsf {Encaps_{cpa}}, \mathsf {Decaps_{cpa}})\) be IND-CPA secure KEM. Let\(\hat{H}\) be a hash function andF be a PRF. The improved combiner is shown in Fig. 11, where function\(f(pk_0, k_1||k_0, c)\) can be initiated by\(\hat{H}(pk_0, k_1||k_0, c)\) or\(F_{k_1}(pk_0, c)\oplus F_{k_0}(pk_0, c)\). Our main modification is to take public key as input to the hash function or PRF when generating encapsulated key.

The [CCA,CPA] secure\(\mathsf {2KEM}_{f}\) in random oracle or standard model depending on the instantiation of\(f(pk_0, k_1||k_0, c)\).

Full size image

Theorem 5

Let the underlying two KEMs be IND-CCA and IND-CPA secure. If\(f(pk_0, k_1||k_0, c)=\hat{H}(pk_0, k_1||k_0, c)\) for a hash function\(\hat{H}\),\(\mathsf {2KEM}_{f}\) in Fig. 11 is [OW-CCA,OW-CCA] secure in random oracle model; if\(f(pk_0, k_1||k_0, c)=F_{k_1}(pk_0, c)\oplus F_{k_0}(pk_0, c)\) for PRFF,\(\mathsf {2KEM}_{f}\) in Fig. 11 is [IND-CCA,IND-CPA] secure in standard model.

Please refer the full version [32] for the proof.

6.2Modified FO Transformation

In this section, we investigate the constructions of passively 2-key PKE and give a modified FO transformation which can be used to transform a passively secure 2-key PKE to an adaptively secure 2-key KEM.

6.2.1Passively Secure 2-Key PKE

As the preparation for realizing adaptively secure 2-key KEM and the modified FO transformation, similar to the notion of 2-key KEM, we can also provide the notion of 2-key (public key encryption) PKE.

Informally, a 2-key PKE\(\textsf {2PKE=(KeyGen0, KeyGen1, Enc, Dec)}\) is a quadruple of PPT algorithms together with a plaintext space\(\mathcal {M}\) and a ciphertext space\(\mathcal {C}\), whereKeyGen1 outputs a pair of public and secret keys\((pk_1, sk_1)\),KeyGen0 outputs a pair of keys\((pk_0, sk_0)\),\(\textsf {Enc}(pk_1, pk_0, m)\) outputs the ciphertext\(C\in \mathcal {C}\), and\(\textsf {Dec}(sk_1, sk_0, C)\) outputs a plaintextm. Sometimes, we explicitly add the randomnessr toEnc and denote it as\(\textsf {Enc}(pk_1, pk_0, m, r)\). Here we only describe the\([\textsf {IND\text {-}CPA}, \textsf {IND\text {-}CPA}]\) security game in Fig. 12. For more concrete and full definition of 2-key PKE please refer the full version [32].

The\([\textsf {IND\text {-}CPA}, \cdot ]\), and\([\cdot , \textsf {IND\text {-}CPA}]\) games of\(\mathsf {2PKE}\) for adversaries\(\mathcal {A}\) and\(\mathcal {B}\).

Full size image

Passively Secure Twin-ElGamal from DDH Assumption. Our construction is actually a conjoined ElGamal encryption. Let’s call it twin-ElGamal. The\([\textsf {IND\text {-}CPA}, \textsf {IND\text {-}CPA}]\) secure twin-ElGamal\(\mathsf {2PKE}_{\textsf {cpaddh}}=(\textsf {KeyGen1}, \textsf {KeyGen0}, \textsf {Enc}, \textsf {Dec})\) is presented in detail in Fig. 13.

The [IND-CPA,IND-CPA] secure\(\mathsf {2PKE}_{\textsf {cpaddh}}\) under DDH assumption

Full size image

Theorem 6

Under the DDH assumption, the twin-ElGamal\(\mathsf {2PKE}_{\textsf {cpaddh}}\) scheme shown in Fig. 13 is\([\textsf {IND\text {-}CPA}, \textsf {IND\text {-}CPA}]\) secure.

Please refer the full version [32] for the proof.

6.2.2Modified FO Transformation from Passive to Adaptive Security

In the random oracle model, the FO [14,18] technique is able to transform a passively secure one-key encryption scheme to an adaptively secure scheme. We show that the classical FO transformation does not work for our 2-key encryption scheme. Then we show that with a slight but vital modification the FO transformation could work.

The Failure of Classical FO Transform on 2-key KEM. We give a novel twin-ElGamal scheme by injecting redundant public keys, and show that such twin-ElGamal scheme after FO transformation is still OW-CCA secure, but not [OW-CCA,\(\cdot \)] secure.

The\(\textsf {KeyGen0}\) algorithm of\(\mathsf {2PKE}_{\textsf {cpaddh}}\) chooses a random\(z\leftarrow \mathbb {Z}_p\), and sets\(pk_0=(g, h_0, g_0=g^z), sk_0=(a_0, z)\). The algorithm\(\textsf {KeyGen1}, \textsf {Enc}, \textsf {Dec}\) are the same as in\(\mathsf {2PKE}_{\textsf {cpaddh}}\). Obviously this novel twin-ElGamal scheme is IND-CPA secure under DDH assumption. Let\(\mathsf {2PKE}^{\textsf {fo}}_{\textsf {cpaddh}}\) be the scheme by applying classical FO transform on the novel twin-Elgamal. It is OW-CCA secure. Note that the encapsulated key is\(K=H(m, c)\) whereH is a hash function.

However, there exists an\([\textsf {IND\text {-}CCA}, \cdot ]\) attacker\(\mathcal {A}\) of\(\mathsf {2PKE}^{\textsf {fo}}_{\textsf {cpaddh}}\) that works as follows:\(\mathcal {A}\) first queries the\(\mathcal {O}_{\mathsf {leak}_0}\) and gets\(pk^{1}_0=(g, h_0, g_0=g^z), sk^{1}_0=(a_0, z)\). Then\(\mathcal {A}\) chooses\(g'_0\ne g_0\in \mathbb {G}\), and sets\(pk^*_0=(g, h_0, g'_0)\) as challenge public key. On receiving challenge ciphertext\(c^*\) under\((pk_1, pk^*_0)\),\(\mathcal {A}\) queries\(\mathcal {O}_{\textsf {ow\text {-}cca}}\) with\((pk^{1}_0, c^*)\). Since\(pk^1_0\ne pk^*_0\),\(\mathcal {O}_{\textsf {ow\text {-}cca}}\) would return\(K'\).\(\mathcal {A}\) just outputs\(K'\). Since\(c^*\) encapsulated the same key\(K^*=H(m ,c^*)\) under both public keys\((pk_1, pk^1_0)\) and\((pk_1, pk^*_0)\).\(\mathcal {A}\) will succeed with probability 1.

Modification on FO Transform to Achieve [\({\mathbf {\mathsf{{IND\text {-}CCA}}}}, {\mathbf {\mathsf{{IND\text {-}CCA}}}}\)] Secure 2-Key KEM from 2-Key PKE. Motivated by the above attacks, we give a modified FO transform by a slight but vital modification from “Hashing” in [18] to “Hashing with public key as input”. Actually, taking the public keys as input to hash function is also motivated by the fact that: from the perspective of proof, “Hashing with public key as input” would help to preserve the consistency of strong decryption oracle and hashing list.

Since we take the decryption failure into account, let’s firstly recall and adapt the definition of correctness for decryption in [18] to our 2-key setting. When\(\mathsf {2PKE}=\mathsf {2PKE}^G\) is defined with respect to a random oracleG, it is said to be\(\delta _{q_G}\)-correct if for adversary\(\mathcal {A}\) making at most\(q_G\) queries to random oracleG, it holds that\(\text {Pr}[\textsf {COR\text {-}RO}^{\mathcal {A}_{\textsf {2PKE}}}\Rightarrow 1]\le \delta _{q_G}\), where the correctness gameCOR-RO is defined as following:\((pk_1, sk_1) \leftarrow \mathsf {KeyGen1}(pp)\),\((pk_0, sk_0) \leftarrow \mathsf {KeyGen0}(pp)\),\(m \leftarrow \mathcal {A}^{G(\cdot )}(pk_1, sk_1, pk_0, sk_0)\),\(c \leftarrow \mathsf {Enc}(pk_1, pk_0, m)\). Return\(\mathsf {Dec}(sk_1, sk_0, c){\mathop {=}\limits ^{?}}m\).

Let\(\mathsf {2PKE}=(\mathsf {KeyGen1', KeyGen0', Enc, Dec})\) be a [IND-CPA,IND-CPA] secure 2-key PKE with message space\(\mathcal {M}\). The [IND-CCA,IND-CCA] secure\(\mathsf {2KEM}=(\mathsf {KeyGen1, KeyGen0, Encaps, Decaps})\) are described as in Fig. 14.

The [IND-CCA,IND-CCA] secure 2-key KEM\(\mathsf {2KEM}\) by modified FO

Full size image

Theorem 7

For any\([\textsf {IND\text {-}CCA}, \cdot ]\) adversary\(\mathcal {C}\), or\([\cdot , \textsf {IND\text {-}CCA}]\) adversary\(\mathcal {D}\) against\(\textsf {2KEM}\) with at most\(q_D\) queries to decapsulation oracleDECAPS,\(q_H\) (resp.\(q_G\)) queries to random oracleH (resp.G), there are\([\textsf {IND\text {-}CPA}, \cdot ]\) adversary\(\mathcal {A}\), or\([\cdot , \textsf {IND\text {-}CPA}]\) adversary\(\mathcal {B}\) against\(\textsf {2PKE}\), that make at most\(q_H\) (resp.\(q_G\)) queries to random oracleH (resp.G) s.t.

Please refer the full version [32] for the proof.

With the above analysis and tools, we give a more compact AKE from Module-LWE assumption with less communications than Kyber [3]. The roadmap is that we first give a [IND-CPA,IND-CPA] secure 2-key PKE from Module-LWE, by applying the modified FO transform in Sect. 6.2.2 and theAKE in Sect. 4.1 step by step, and we finally obtain a AKE scheme.

Letq be a prime and\(R_q\) denote the ring\(\mathbb {Z}_q[x]/(x^n+1)\). Define the centered binomial distribution\(B_{\eta }\) for positive integer\(\eta \) as: sample\((a_1, \cdots , a_{\eta }, b_1, \cdots , b_\eta )\) uniformly from\(\{0, 1\}\), and output\(\sum _{i=1}^\eta (a_i-b_i)\). Denote\(\mathbf {\mathrm s}\leftarrow \beta _\eta \) as that each of\(\mathbf {\mathrm s}\)’s coefficient is generated according to\(B_{\eta }\). Letk, m be a positive integer parameter. For PPT adversary\(\mathcal {A}\), the advantage\(\mathbf Adv ^{mlwe}_{m, k, \eta }(\mathcal {A})\) of solving Module-LWE problem is the advantage of distinguishing two distributions\(\{(\mathbf A \leftarrow R_q^{m\times k}, \mathbf A \mathbf {\mathrm s}+\mathbf {\mathrm e})| (\mathbf {\mathrm s}, \mathbf {\mathrm e})\leftarrow \beta ^k_{\eta }\times \beta ^k_{\eta }\}\) and\(\{(\mathbf A \leftarrow R_q^{m\times k}, \mathbf {\mathrm b}\leftarrow R_q^m)\}\).

Let\(d_{t_1}, d_{t_0}, d_{u_1}, d_{u_0}, d_v\) be positive numbers, depending on the special choice of the parameters settings, and\(n=256\). Every message in\(\mathcal {M}=\{0, 1\}^{n}\) can be seen as a polynomial in\(R_q\) with coefficients in\(\{0, 1\}\). Let\(\mathbf A \) be a random\(k\times k\) matrix in\(R_q\). Let\(\lceil x \rfloor \) be the rounding ofx to the closest integer. For distributionX, let\(\sim X=\textsf {Samp}(r)\) be sample algorithm with randomnessr according to distributionX.

For an even (resp. odd) positive integer\(\alpha \), we define\(r'=r \mod ^{\pm } \alpha \) to be the unique element\(r'\) in the range\(-\frac{\alpha }{2}<r'\le \frac{\alpha }{2}\) (resp.\(-\frac{\alpha -1}{2}\le r'\le \frac{\alpha -1}{2}\)) such that\(r'=r\mod \alpha \). For any positive integer\(\alpha \), define\(r'= r \mod ^+ \alpha \) to be the unique element\(r'\) in the range\(0< r'< \alpha \) such that\(r'=r\mod \alpha \). When the exact representation is not important, we simplify it as\(r \mod \alpha \). For\(x\in \mathbb {Q}\),\(d\le \log _2 q\), define the compress function as\(\mathsf {Comp}_q(x, d)=\lceil (2^d)/q\cdot x \rfloor \mod ^+ 2^d\), and the decompress function as\(\mathsf {Decomp}_q(x, d)=\lceil q/(2^d)\cdot x \rfloor \). And when applying theComp andDecomp function to\(\mathbf {\mathrm x}\), the procedure is applied to coefficient.

Twin-Kyber. Our construction, called twin-kyber, is an extension of kyber scheme [3] in the same conjoined way for our twin-ElGamal scheme. With the parameters above, twin-kyber\(\mathsf {2PKE_{\textsf {mlwe}}}=(\textsf {KeyGen1, KeyGen0, Enc, Dec})\) is shown in Fig. 15.

The [IND-CPA,IND-CPA] secure\(\mathsf {2PKE_{\textsf {mlwe}}}\) under Module-LWE assumption.

Full size image

Theorem 8

If there is a PPT adversary\(\mathcal {A}\) against\([\textsf {IND\text {-}CPA}, \textsf {IND\text {-}CPA}]\) security of\(\mathsf {2PKE}_{\textsf {mlwe}}\), there exists\(\mathcal {B}\) such that,\(\mathbf Adv ^{[\textsf {IND\text {-}CPA}, \textsf {IND\text {-}CPA}]}_{\mathsf {2PKE}_{\textsf {mlwe}}}(\mathcal {A}) \le 2\mathbf Adv ^{mlwe}_{k+1, k, \eta }(\mathcal {B})\).

Please refer the full version [32] for the analysis of decryption failure and proof. By applying the modified FO transformation to\(\mathsf {2PKE}_{\textsf {mlwe}}\), we obtain a\([\textsf {OW\text {-}CCA}\),\(\textsf {OW\text {-}CCA}]\) secure\(\mathsf {2KEM}_{\textsf {mlwe}}\). Then by setting\(cpk_0=(0)^k\) and\(csk_0=(0)^k\), and integrating\(\mathsf {2KEM}_{\textsf {mlwe}}\) to\(\textsf {AKE}\) in Sect. 4, a novel and efficient post-quantum AKE from Module-LWE assumption is constructed.

The parameter setting and comparison are given in Tables 5 and6. Note that by setting\(d_{t_1}=d_{t_0}=\lceil \log q \rceil \) we actually do not apply compress on public keys. (which fix one bug of the security proof in [3]). One may doubt that with\(q=3329\) we can not apply NTT technique to accelerate the multiplications of two polynomials\(f(x)\times g(x)\) over\(R_q\), since\(512\not \mid 3328\). Actually, we can fix this gap. Separate\(f(x)=f_B(x^2)+xf_A(x^2)\),\(g(x)=g_2(x^2)+xg_1(x^2)\) into a series of odd power and a series of even power, then\(f(x)\times g(x)=f_B(x^2)g_2(x^2)+(f_A(x^2)g_2(x^2)+f_B(x^2)g_1(x^2))x+f_A(x^2)g_1(x^2)x^2\). Then we can apply NTT to\(f_i(y)g_j(y)\) over\(Z_q[y]/(y^{128}+1)\) by setting\(y=x^2\) since 256|3328.