Understanding and Constructing AKE via Double-Key Key Encapsulation Mechanism(cid:63) Haiyang Xue1,2,3, Xianhui Lu1,2,3, Bao Li1,2,3, Bei Liang4, and Jingnan He1,2,3 1 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China. [email protected],[email protected] 2 Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing, China. 3 School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China. 4 Chalmers University of Technology, Gothenburg, Sweden Abstract. Motivatedbyabstractingthecommonideabehindseveralimplicitlyauthenticatedkey exchange (AKE) protocols, we introduce a primitive that we call double-key key encapsulation mechanism(2-keyKEM).ItisaspecialtypeofKEMinvolvingtwopairsofsecret-publickeysand satisfying some function and security property. Such 2-key KEM serves as the core building block andprovidesalternativeapproachestosimplifytheconstructionsofAKE.Toseetheusefulnessof 2-keyKEM,weshowhowseveralexistingconstructionsofAKEcanbecapturedas2-keyKEMand understood in a unified framework, including widely used HMQV, NAXOS, Okamoto-AKE, and FSXY12-13 schemes. Then, we show 1) how to construct 2-key KEM from concrete assumptions, 2) how to adapt the classical Fujisaki-Okamoto transformation and KEM combiner to achieve the security requirement of 2-key KEM, 3) an elegant Kyber-AKE over lattice using the improved Fujisaki-Okamoto technique. Keywords: Authenticated Key Exchange, CK Model, Key Encapsulation Mechanism 1 Introduction Key exchange (KE), which enables two parties to securely establish a common session key while com- municating over an insecure channel, is one of the most important and fundamental primitives in cryp- tography. After the introduction of Diffie-Hellman key exchange in [DH76], cryptographers have devised a wide selection of the KE with various use-cases. One important direction is authenticated key ex- change (AKE). The main problems that the following works focus on are specified as security models [BR93,CK01,LLM07,Cre09,FSXY12], efficient and provably-secure realizations and their improvements [MTI86,MQV95,CK01,Kra03,LLM07,Oka07,BCG+08,FSXY12,FSXY13,YZ13,Pei14,BCN+14,ZZD+15]. InanAKEprotocol,eachpartyhasapairofsecret-publickeys,astatic/long-term public key andthe corresponding static/long-term secret key. The static public key is interrelated with a party’s identity, whichenablestheotherpartiestoverifytheauthenticbindingbetweenthem.Apartywhowantstoshare information with another party generates ephemeral one-time randomness which is known as ephemeral secret keys, computes session state (which is originally not explicitly defined [CK01], but nowadays it is generally agreed [LLM07,FSXY12] that the session state should at least contain ephemeral secret keys) from ephemeral and static secret keys and incoming message, then outputs corresponding ephemeral 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 shared session key. ManystudieshaveinvestigatedthesecuritynotionofAKEincludingBRmodelandCanetti-Krawczyk (CK) model [CK01]. Fujioka et al. [FSXY12] re-formulated the desirable security notion of AKE in [Kra05],includingresistancetoKCI(keycompromiseimpersonationattack),wPFS(weakperfectforward attack) and MEX (maximal exposure attack), as well as provable security in the CK model, and called (cid:63) This is the full version of a preliminary form as Understanding and Constructing AKE via Double-Key Key Encapsulation Mechanism in ASIACRYPT 2018 [XLL+18] it the CK+ security model. LaMacchia et al. [LLM07] also proposed a very strong security model, called the eCK model. The CK model and the eCK model are incomparable [Cre09], and the eCK model is not stronger than the CK model while the CK+ model is [FSXY12]. 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 primi- tives i.e., signature or MAC to combine with the underlying KE, such as IKE [CK02], SIGMA [Kra03], TLS [Kra01,BCN+14] etc.; while the solution of implicit AKE initiated by [MTI86], 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 [MQV95,Kra05], Okamoto [Oka07,Oka07a], NAXOS [LLM07], OAKE [YZ13], FSXY variants [BCG+08,FSXY12,FSXY13,Yon12], and AKE from lattice assumptions [ZZD+15,BDK+17]. Motivation. In this paper, we focus on the second class, i.e., constructions of implicit AKE. Based on different techniques and assumptions, many implicit AKE protocols have been proposed in recent years [Kra05,LLM07,Oka07,Oka07a,FSXY12,FSXY13,YZ13]. However, the constructing techniques and methods of the existing implicit AKE protocols are some- what 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 buildingblocksandcapturethecommonideaandtechniquebehindtheconstructionsandsecurityproofs of AKE. On the contrary, with respect to explicit AKE Canetti and Krawcayk [Kra03,CK02] gave the frame of “SIGin-and-MAc” (later extended by [Pei14]) which provides a good guideline for designing explicit AKE. Infact,Boydetal.[BCG+08]andFujiokaetal.[FSXY12,FSXY13]initiatedtheresearchonstudying frameworksofimplicitAKE.Boydet al.firstlynoticedtheconnectionbetweenAKEandkeyencapsula- tionmechanism(KEM),thenFujiokaet al.providedCK+ secureAKEprotocolsfromchosenciphertext (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 [Kra05,YZ13] which are built on the challenge-respond signature; AKE protocol in [Oka07] which results from universal hash proof [CS02]; as well as NAXOS [LLM07]. Hence, one of the important problems on AKE is to give an even more general framework for con- structing AKE that is able to not only unify and encompass 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 structure under a unified framework, not only with some well- studied cryptographic primitive as building block but also with simple formal functionality and security requirements rather than heuristic ideas and techniques. MainObservation.Inordertofindoutwhatkindofthefundamental/essentialbuildingblockisexactly needed for CK+ secure AKE, let’s go back to the original KE, and show insight on how to augment the requirements or capability of adversary so as to achieve CK+ secure AKE from KE step by step. In fact, KEM is a KE naturally. The initiator U sends ephemeral public key pk to responder U . A B U computes encapsulated key and ciphertext under pk and returns ciphertext to U . By decapsulating B A ciphertext using sk, U obtains the agreed key encapsulated by U . A B Step 1. Authentication. To make a KE be authenticated, we take unilaterally authenticating U A for example. It is required that U has static secret-public keys (ssk ,spk ), ephemeral secret key esk A A A A and ephemeral public outgoing message epm . In light of using KEM with one pair of secret-public key A to realize KE naturally, one simple and natural approach to authenticate U with one pair of static A key as well as one pair of ephemeral secret key and ephemeral public message is to extend the KEM with one pair of key to a KEM with two pairs of secret-public key. More specifically, for example, to authenticate U , U sends ephemeral public key epk to U , and U computes encapsulated key and A A A B B ciphertext under two public keys spk and epk . Only with both secret keys ssk and esk , can U A A A A A 2 extract encapsulated key. Equipped with the 2-key KEM, the authentication property of AKE comes down to some proper security notions of such 2-key KEM. We analyze its security notion in step 2. Step2.Security.OnesecurityconsiderationinAKEistomaintainthesecrecyofsharedsessionkey even if the adversary is allowed to query session state and key of non-target session and send message by controlling the communications. The capability imparted to adversary with permission of querying session state and key of non-target session directly corresponds to the adversary’s capability of having access to strong1 CCA decryption queries of 2-key KEM. The adversary’s capability of sending message correspondstothepowerofadversarytoadaptivelychoosetheephemeralpublickeysepk (underwhich A the challenge ciphertext is computed). Another security consideration in AKE is the forward security, in which case the adversary has the static secret key ssk . This forward security comes down to the A (chosen plaintext attack) CPA security of such 2-key KEM if ssk is leaked to adversary. A 1.1 Our Contributions – Basedontheabovemotivationsandobservations,weintroducedouble-key key encapsulation mecha- nism (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 construction- s and security proof of AKE, including well-known HMQV[Kra05], NAXOS [LLM07], Okamoto- AKE[Oka07,Oka07a], and FSXY12[FSXY12], FSXY13[FSXY13]. – We investigate the constructions of 2-key KEM based on concrete assumptions. We also show the failure of implying [IND/OW-CCA,IND/OW-CPA] secure 2-key KEM from KEM combiner and the classicalFujisaki-Okamoto(FO)transformation.Hence,withaslightbutvitalmodificationbytaking publickeyasinputtothehashstepweprovideimprovedKEMcombinerandimprovedFOtoadapt them in our 2-key KEM setting. – Equippedwith2-keyKEMandourframeabove,weproposeapost-quantumAKEbasedonModule- LWE assumption, which consumes less communications than Kyber [BDK+17] using frame of F- SXY13 [FSXY13]. 2-key Key Encapsulation Mechanism. Generally, the 2-key KEM scheme is a public key encapsula- tionwithtwopairsofpublicandsecretkeys,butthemaindistinctionsarethefunctionalityandsecurity. Theencapsulationanddecapsulationalgorithms:insteadoftakingasinputsinglepublickeytogenerate a random key K and a ciphertext C and single secret key to decapsulate ciphertext C, each algorithm takes two public keys (pk ,pk ) to generate (C,K) and only with both two secret keys (sk ,sk ) the 1 0 1 0 decapsulation algorithm can decapsulate C. Wedefinethesecuritynotionof2-keyKEM/PKEintheattackingmodel[IND/OW-CCA,IND/OW-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 [IND/OW-CCA,·] denotes the securitymodelwhereadversaryAaimstoattacktheciphertextunderpk andpk∗ (withitscontrolover 1 0 the generation of pk∗), and it is allowed to query a strong decapsulation oracle that will decapsulate 0 the ciphertext under pk and arbitrary pk(cid:48) (generated by challenger); while [·,IND/OW-CPA] denotes 1 0 the security model where adversary B aims to attack the ciphertext under pk and pk∗ (with its control 0 1 over the generation of pk∗). We say a 2-key KEM is [IND/OW-CCA,IND/OW-CPA] secure if it is both 1 [IND/OW-CCA,·] and [·,IND/OW-CPA] secure. Compared with classical definition of CCA security, the [CCA,·] adversary of 2-key KEM has two main enhancements: 1) one of the challenge public keys pk∗, under which the challenge ciphertext is 0 computed,isgeneratedbytheadversary;2)theadversaryisallowedtoqueryastrongdecryptionoracle, and get decapsulation of the ciphertext under arbitrary public keys (pk∗,pk(cid:48)) where pk(cid:48) is generated by 1 0 0 the challenger. 1 ComparewithclassicaldecryptionqueriesofCCAsecurity,“strong”meansadversarycouldquerydecryption oracle with ciphertext under several other public keys. 3 AKE from 2-key KEM. Equipped with [IND/OW-CCA, IND/OW-CPA] 2-key KEM, by taking pk as 1 static public key and pk as ephemeral public key, we give several general frames of CK+ secure AKE, 0 AKE,AKE andAKE ,dependingondifferenttricks.TheCK+ securityofourAKEisdecomposed ro-pkic-lr std to the [IND/OW-CCA,·] security (corresponding to KCI and MEX security) and [·,IND/OW-CPA] secu- rity (corresponding to wPFS) of 2-key KEM. Furthermore, to resist the leakage of partial randomness, a function f(ssk ,esk ) is required so that if one of ssk and esk is leaked f(ssk ,esk ) is still B B B B B B computationally indistinguishable with a random string. In Fig. 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 [Kra05], NAXOS [LLM07], Okamoto [Oka07], FSXY12[FSXY12], and FSXY13 [FSXY13]. FrameworksModels Concrete AKEs Assumptions Tricks RO FSXY13 [FSXY13],Kyber[BDK+17] OW-CCA Modified KEM Comb. AKE RO AKE-2Kyber(Sec.7) M-LWE Modified FO RO HMQV [Kra05] OAKE [YZ13] GDH, KEA1 Remark 1-3 AKE ro-pkic-lr RO NAXOS [LLM07] GDH Remark 1, 2 Std FSXY12 [FSXY12] IND-CCA Modified KEM Comb. AKE std Std Okamoto [Oka07a] DDH, πPRF Twisted PRF Table 1. The unification of AKEs. Comb. is the abbreviation for combiner. GDH is the Gap-DH assumption. ROdenotesthenotionofrandomoracle.Stdistheshortenedformofstandardmodel.πPRFmeansthepairwise- independent random source PRF [Oka07a]. ByconsideringanAKEprotocolinsuchaframeworkbasedon2-keyKEM,thecomplicatedsecurity 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 a post-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. PuttingPublicKeyintheHashingorPRFstep.TheFujisaki-Okamoto(FO)[FO99,FO13,HHK17]trans- formation 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.2 Strong Point of the AKE via 2-Key KEM Themainadvantageofourcontributionsisthatweuseanon-interactiveprimitivetohandlethecomplex requirement of interactive protocols. The functionality and security requirements of [CCA, CPA] secure 2-keyKEMarerelativelyeasiertoworkwithandunderstand.Asitisknown,inAKEwehavetoconsider complexanddiverseadversaries.However,whenconsideringtheAKEunderourunifiedframeworkbased on 2-key KEM, all the attacking strategies in CK+ model can be simplified to the singular security of 2-keyKEM.Furthermore,combinedwiththeimprovedFujisaki-OkamototransformationinSection6.2, the construction of AKE can be deduced to that of [CPA, CPA] secure 2-key KEM in the random oracle model. 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 [CS98], there have been a number of CCA se- curePKE/KEMschemesbasedonbothconcreteassumptions[CS98,Kil07,Wee10,BDK+17]andgeneral 4 cryptographic primitives [DDN91,CHK04,Kil06,PW08]. Therefore, it is possible for us to employ the established and nature technique of classical KEM to construct 2-key KEM, and further AKE. 1.3 Open Problem and Following Works OurmainAKEreliestheassumptionofclassicalrandomoracle.Weleaveitasanopenproblemtoprove the security in the quantum random oracle model. Recently, Xu et al. [XXW+18] proposed SIAKE based on the supersingular isogeny with the in- spiration of double-key KEM. The SIAKE dramatically improved the efficiency and communication of supersingular isogeny based AKE. 2 Preliminary For a variable x, if x is a bit string, denote [x] as the i-th bit of x; if x is a polynomial, denote [x] as i i the i-th coefficient of x; if x is a sets of vectors (with string or number) denote [x] as the sets of all i-th i element of vectors in x; 2.1 CK+ Security Model We recall the CK+ model introduced by [Kra05] and later refined by [FSXY12,FSXY13], which is a CK [CK01] model integrated with the weak PFS, resistance to KCI and MEX properties. Since we focus on two-pass protocols in this paper, for simplicity, we show the model specified to two pass protocols. In AKE protocol, U denotes a party indexed by i, who is modeled as probabilistic polynomial time i (PPT) interactive Turing machines. We assume that each party U owns a static pair of secret-public i keys (ssk ,spk ), where spk is linked to U ’s identity, using some systems i.e. PKI, such that the other i i i i 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 a session. A party can be activated to initiate the session by an incoming message of the forms (Π,I,U ,U ) or respond to an incoming A B message of the forms (Π,R,U ,U ,X ), where Π is a protocol identifier, I and R are role identifiers B A A correspondingtoinitiator andresponder.Activatedwith(Π,I,U ,U ),U iscalledthesessioninitiator. A B A Activated with (Π,R,U ,U ,X ), U is called the session responder. B A A B According to the specification of AKE, the party creates randomness which is generally called ephemeral secret key, computes and maintains a session state, generates outgoing messages, and com- pletes the session by outputting a session key and erasing the session state. Note that Canetti-Krawczyk [CK01]definessessionstateassession-specificsecretinformationbutleavesituptoaprotocoltospecify which information is included in session state; LaMacchia et al. [LLM07] explicitly set all random coins used by a party in a session as session-specific secret information and call it ephemeral secret key. Here 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 creates a session A state and outputs X , then may receive an incoming message of the forms (Π,I,U ,U ,X ,X ) from A A B A B the responder U , then may computes the session key SK. On the contrary, the responder U outputs B B X , and may compute the session key SK. We say that a session is completed if its owner computes the B session key. Asessionisassociatedwithitsowner,apeer,andasessionidentifier.IfU istheinitiator,thesession A identifier is sid = (Π,I,U ,U , X ) or sid = (Π,I,U ,U ,X ,X ), which denotes U as an owner A B A A B A B A and U as a peer. If U is the responder, the session is identified by sid = (Π,R,U ,U ,X ,X ), B B B A A B which denotes U as an owner and U as a peer. The matching session of (Π,I,U ,U ,X ,X ) is B A A B A B (Π,R,U ,U ,X ,X ) and vice versa. B A A B Adversary. The adversary A is modeled in the following to capture real attacks in open networks, including the control of communication and the access to some of the secret information. 5 – Send(message): A could send message in one of the forms: (Π,I,U ,U ), (Π,R,U ,U ,X ), or A B B A A (Π,I,U ,U ,X ,X ), and obtains the response. A B A B – SessionKeyReveal(sid): if the session sid is completed, A obtains the session key SK for sid. – SessionStateReveal(sid): The adversary A obtains the session state of the owner of sid 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 ): By this query, A learns all information of U (including the static secret, session states i A and session keys stored at U ); in addition, from the moment U is corrupted all its actions may be A A controlled by A. Freshness.Letsid∗ =(Π,I,U ,U ,X ,X )or(Π,I,U ,U ,X ,X )beacompletedsessionbetween A B A B A B A B honestusersU andU .Ifthematchingsessionofsid∗exists,denoteitbysid∗.Wesaysessionsid∗isfresh A B if A does not queries: 1) SessionStateReveal(sid∗), SessionKeyReveal(sid∗), and SessionStateReveal(sid∗), SessionKeyReveal(sid∗) if sid∗ exists; 2) SessionStateReveal(sid∗) and SessionKeyReveal(sid∗) if sid∗ does not exist. Security Experiment. The adversary A could make a sequence of the queries described above. During the experiment, A makes the query of Test(sid∗), where sid∗ must be a fresh session. Test(sid∗) select random bit b ∈ {0,1}, and return the session key held by sid∗ if b = 0; and return a random key if U b=1. The experiment continues until A returns b(cid:48) as a guess of b. The adversary A wins the game if the test session sid∗ is still fresh and b(cid:48) = b. The advantage of the adversary A is defined as Advck+(A) = Π Pr[A wins]− 1. 2 Definition 1. We say that a AKE protocol Π 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 adversary A, Advck+(A) is negligible for the test session sid∗, Π 1. the static secret key of the owner of sid∗ is given to A, if sid∗ does not exist. 2. the ephemeral secret key of the owner of sid∗ is given to A, if sid∗ does not exist. 3. the static secret key of the owner of sid∗ and the ephemeral secret key of sid∗ are given to A, if sid∗ exists. 4. the ephemeral secret key of sid∗ and the ephemeral secret key of sid∗ are given to A, if sid∗ exists. 5. the static secret key of the owner of sid∗ and the static secret key of the peer of sid∗ are given to A, if sid∗ exists. 6. the ephemeral secret key of sid∗ and the static secret key of the peer of sid∗ are given to A, if 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 Definition 1, and these ten cases cover wPFS, resistance to KCI, and MEX as follows: E and E capture KCI, since the adversary obtains the static secret key of one party 1 4 of the test session and pretends to be the other party. E captures wPFS. E , E , E , E , E , E 5 2 3 6 7-1 7-2 8-1 and E capture MEX, since the adversary obtains either the static secret key of one party or both the 8-2 static secret key of one party and the ephemeral secret key of the other party of the test session. 3 2-Key Key Encapsulation Mechanism In this section, we introduce the notions of double-key encapsulation and define the security of KEM in double-key setting. We also give some analysis and show differences with previous similar definitions. 6 EventCase sid∗ sid∗ ssk esk esk ssk Security √A A B B E 1 A No × - × KCI 1 √ E 2 A No × - × MEX 2 √ E 2 B No × - × MEX 3 √ E 1 B No × - × KCI 4 √ √ E 5 A or B Yes × × wPFS 5 √ √ E 4 A or B Yes × × MEX 6 √ √ E 3 A Yes × × MEX 7-1 √ √ E 3 B Yes × × MEX 7-2 √ √ E 6 A Yes × × MEX 8-1 √ √ E 6 B Yes × × MEX 8-2 Table 2. The behavior of AKE adversary in CK+ model. sid∗ is the matching session of sid∗, if it exists. “Yes” means that there exists sid∗, “No” means do not. ssk (ssk ) means the static secret key of A(B). esk (esk ) A B √ A B is the ephemeral secret key of A(B) in sid∗ or sid∗ if there exists. “ ” means the secret key may be revealed to adversary, “×” means the secret key is not revealed. “-” means the secret key does not exist. 3.1 2-Key Key Encapsulation Mechanism Generally, a double-key (2-key) KEM is a public key encapsulation with two pairs of public and se- cret keys. Formally, a 2-key KEM 2KEM=(KeyGen1, KeyGen0, Encaps, Decaps) is a quadruple of PPT algorithms together with a key space K. – KeyGen1(λ,pp): on inputs security parameter λ, and public parameters pp, output a pair of public- secret keys (pk ,sk ). In order to show the randomness that is used, we denote key generation 1 1 algorithm as KeyGen1(λ,pp;r). For simplicity, sometimes we omit the input security parameter λ and public parameter pp and denote it as KeyGen1(r) directly. – KeyGen0(λ): on inputs security parameter λ output a pair of public and secret keys (pk ,sk ). 0 0 – Encaps(pk ,pk ;aux ) : on input public keys pk ,pk and auxiliary input aux (if there is), output 1 0 e 1 0 e ciphertext c and encapsulated key k in key space K. Sometimes, we explicitly add the randomness r and denote it as Encaps(pk ,pk ,r;aux ). 1 0 e – Decaps(sk ,sk ,c;aux ):oninputsecretkeyssk ,sk ,auxiliaryinputaux (ifthereis)andc,output 1 0 d 0 1 d key k. Correctness.For(pk ,sk )←KeyGen1(λ,pp),(pk ,sk )←KeyGen0(λ,pp)and(c,k)←Encaps(pk ,pk ), 1 1 0 0 1 0 we require that Decaps(sk ,sk ,c)=k holds with all but negligible probability. 1 0 Security. We consider two kinds of security i.e., indistinguishability and one-wayness in the attacking model [ATK ,ATK ]. More precisely, in our [ATK ,ATK ] security model for 2KEM, we consider two 1 0 1 0 adversaries, i.e., A = (A ,A ) attacking pk (controlling the generation of pk∗) and B = (B ,B ) 1 2 1 0 1 2 attacking pk (controlling the generation of pk∗). In Figure 1 below we show the security games of 0 1 one-wayness and indistinguishable security corresponding to [IND/OW-ATK ,·] and [·,IND/OW-ATK ] 1 0 respectively. Tobeclear,theauxiliaryinputsaux andaux maycontainpublicpart,calledpublicauxiliaryinput, e d 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 aux and aux in the security games. e d On the i-th query of O , the challenger generates (pki,ski) ← KeyGen0(ri), sets L = L ∪ leak0 0 0 0 0 0 {(pki,ski,ri)} and returns (pki,ski,ri) to adversary A. On the i-th query of O , the challenger 0 0 0 0 0 0 leak1 generates(pki,ski)←KeyGen1(ri),setsL =L ∪{(pki,ski,ri)}andreturns(pki,ski,ri)toadversary 1 1 1 1 1 1 1 1 1 1 1 B. Depending on the definition of oracle O the adversary A accesses, and O that the adversary ATK1 ATK0 B accesses, we get CPA and CCA notions respectively. – if O =−, it implies CPA notion; ATK1(pk0(cid:48),c(cid:48)) 7 Game [IND-ATK1, ·] on pk Game [·, IND-ATK0] on pk 1 0 01 (pk ,sk )←KeyGen1(pp); 14 (pk ,sk )←KeyGen0(pp) 1 1 0 0 02 L ={(−,−,−)} 15 L ={(−,−,−)} 0 1 03 (state,pk∗)←AOATK1,Oleak0(pk ) 16 (state,pk∗)←BOATK0,Oleak1(pk ); 0 1 1 1 1 0 04 b←{0,1}; 17 b←{0,1}; 05 (c∗,k∗)←Encaps(pk ,pk∗),k∗ ←K;18 (c∗,k∗)←Encaps(pk∗,pk ),k∗ ←K; 0 1 0 1 0 1 0 1 06 b(cid:48) ←AOATK1,Oleak0(state,c∗,k∗); 19 b(cid:48) ←BOATK0,Oleak1(state,c∗,k∗); 2 b 2 b 07 return b(cid:48) =? b 20 return b(cid:48) =? b Game [OW-ATK1, ·] on pk Game [·, OW-ATK0] on pk 1 0 08 (pk ,sk )←KeyGen1(pp); 21 (pk ,sk )←KeyGen0(pp) 1 1 0 0 09 L ={(−,−,−)} 22 L ={(−,−,−)} 0 1 10 (state,pk∗)←AOATK1,Oleak0(pk ) 23 (state,pk∗)←BOATK0,Oleak1(pk ); 0 1 1 1 1 0 11 (c∗,k∗)←Encaps(pk ,pk∗); 24 (c∗,k∗)←Encaps(pk∗,pk ); 1 0 1 0 12 k(cid:48) ←AOATK1,Oleak0(state,c∗); 25 k(cid:48) ←BOATK0,Oleak1(state,c∗); 2 2 13 return k(cid:48) =? k∗ 26 return k(cid:48) =? k∗ Fig.1. The [ATK1,·], and [·,ATK0] games of 2KEM for adversaries A and B. The oracles O , O , O , leak0 ATK1 leak1 and O are defined in the following. ATK0 – if O (cid:54)= −, it works as following: If pk(cid:48) ∈ [L ] ∧(c(cid:48) (cid:54)= c∗ ∨pk(cid:48) (cid:54)= pk∗), compute k(cid:48) ← DecaApTsK(1s(kpk0(cid:48),,sc(cid:48)k)(cid:48),c(cid:48)), and return the correspondin0g k(cid:48), o0t1herwise return ⊥0. This0case implies CCA 1 0 notion. – if O =−, it implies CPA notion; – if OATK0(pk1(cid:48),c(cid:48)) (cid:54)= −, it works as following: If pk(cid:48) ∈ [L ] ∧(c(cid:48) (cid:54)= c∗ ∨pk(cid:48) (cid:54)= pk∗), compute k(cid:48) ← DecaApTsK(0s(kpk(cid:48)1(cid:48),,sc(cid:48)k) ,c(cid:48)), and return the correspondin1g k(cid:48), o1t1herwise return ⊥1. This1case implies CCA 1 0 notion. Let A = (A ,A ) be an adversary against pk of 2KEM. We define the advantage of A winning in 1 2 1 (cid:12) (cid:12) the game IND-ATK1 and OW-ATK1 respectively as: Adv[IND-ATK1,·](A)=(cid:12)Pr[IND-ATK1A ⇒1]− 1(cid:12), and 2KEM (cid:12) 2(cid:12) Adv[OW-ATK1,·](A) = Pr[OW-ATK1A ⇒ 1], where game [IND-ATK1,·] and [OW-ATK1,·] are described in 2KEM Figure 1. Wesaythat2KEMis[IND-ATK1,·]secure,ifAdv[IND-ATK1,·](A)isnegligible;that2KEMis[OW-ATK1,·] 2KEM secure, if Adv[OW-ATK1,·](A) is negligible, for any PPT adversary A. The [·,IND-ATK0] and [·,OW-ATK0] 2KEM security can be defined in the same way. Here to avoid repetition we omit their description. [ATK1,ATK0] security. The scheme 2KEM is called [ATK1,ATK0] secure if it is both [ATK1,·] and [·,ATK0] secure for any PPT algorithms A and B. By the combination of adversaries A and 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- waynesssetting.Forsimplicityinthefollowingpartsweabbreviatethesecuritymodelas[IND/OW-CCA, IND/OW-CPA]. 3.2 Differences between [CCA,·] Security and Previous Definitions In order to avoid confusion, we re-clarify the definition of [IND/OW-CCA,·] security and analyze its difference with previous similar notions, including classical CCA security, KEM combiner [GHP18], and completely non-malleable scheme[Fis05]. ComparedwithclassicalCCAadversary,the[CCA,·]adversaryof2-keyKEM1)hasthecapabilityof choosingoneofthechallengepublickeypk∗;2)couldqueryastrongdecryptionoracle,whichdecapsulates 0 the ciphertext under several public keys (pk∗,pk(cid:48)) where pk(cid:48) is generated by the challenger. While in 1 0 0 8 the classical definition of decapsulation oracle the adversary could only query decapsulation oracle with ciphertext under the challenge public keys (pk∗,pk∗). 1 0 Very recently, Giacon et. al [GHP18] study combiners for KEMs. That is, given a set of KEMs, an unknown subset of which might be arbitrarily insecure, Giacon et. 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 Giacon et. al have a parallel structure: If the number of KEMs to be combined is n, a public keyoftheresultingKEMconsistsofavectorofnpublickeys;likewiseforsecretkeys.Theencapsulation procedure performs n 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 Section 6.1, we show there exists [CCA,·] adversary to attack a CCA secure two KEM combiner. Aimingtoconstructnon-malleablecommitments,Fischlin[Fis05]consideredcompletelynon-malleable (NM)schemes.ThecompleteNMschemeislaterextendedtoindistinguishabilitysettingbyBarbosaand Farshim [BF10] with a strong decryption oracle, which allows the adversary to queries with ciphertext under arbitrary public key of its choice. Note that our [CCA,·] 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 [CCA,·] is. Basedontheaboveobservations,wegivecomparisonamongthesedifferentdefinitionsbyconsidering 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 ,pk ) and let KEM combiner be two combiner 1 0 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. Definitions Cha. PK (pk∗,pk∗) Cha. ciphertext c∗ O ((pk ,pk ),c(cid:48)) 1 0 Dec 1 0 Classical CCA (pk∗,pk∗)←C c∗ under (pk∗,pk∗) (pk ,pk )=(pk∗,pk∗) 1 0 1 0 1 0 1 0 KEM Combiner [GHP18](pk∗,pk∗)←C, A(sk∗)c∗||c∗, c∗ under pk∗ (pk ,pk )=(pk∗,pk∗) 1 0 0 1 0 i i 1 0 1 0 Complete NM [Fis05] (pk∗,pk∗)←C c∗ under (pk∗,pk∗) (pk ,pk )←A 1 0 1 0 1 0 [CCA,·] pk∗ ←C,pk∗ ←A c∗ under (pk∗,pk∗) pk =pk∗, pk ←C 1 0 1 0 1 1 0 Table 3.Thedifferencesofrelateddefinitions.“Cha.”istheabbreviationof“challenge”.C denotethechallenger andAdenotetheadversary.WeuseA(sk∗)todenotethatAbreakstheKEMunderpk∗.InbothClassicalCCA 0 0 and KEM combiner the decapsulation oracle only returns when (pk ,pk ) = (pk∗,pk∗), while in Complete NM 1 0 1 0 (pk ,pk ) could be arbitrary public keys chosen by adversary, and in [CCA,·], pk could be arbitrary public key 1 0 0 chosen by challenger. 3.3 Basic Definitions and Results related to 2-Key KEM [CCA,·] security with non-adaptive adversary We can define a weak [CCA,·] adversary, who is not able to adaptively choose the challenge public key. In this case, taking the adversary A attacking pk as an example, the challenge public key pk∗ is generated by challenger instead of A, which means 1 0 pk∗ ∈[L ] . 0 0 1 PublicKeyIndependentCiphertext.Theconceptofpublic-key-independent-ciphertext(PKIC)was firstproposedin[Yon12].Weextenditto2-keyKEMsetting.ThePKIC2-keyKEMallowsaciphertext 9 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)←Encaps(pk ,pk ,r) can be realized in two steps: in step 1, ciphertex c is generated from pk and 1 0 1 randomness r. We precisely denote it as c←Encaps0(pk ,-,r); in step 2, the encapsulated key k in c is 1 generated from r, pk , and pk . We precisely denote it as k ←Encaps1(pk ,pk ,r). 1 0 1 0 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 = -. However given any classical 0 one-key KEM, it can be seen as a 2-key KEM with KeyGen0 not in use and pk = -. At that time, 0 the [OW/IND-CCA,·] security of this 2-key KEM return to the classical OW/IND-CCA security of the underlying KEM. Min-Entropy.Incaseof2-keyKEMwithPPTadversaryA,for(pk ,sk )←KeyGen1andpk ←Aor 1 1 0 (pk ,sk ) ← KeyGen0 and pk ← A, we define the min-entropy of Encaps(pk ,pk ) by γ(pk ,pk ,A) = 0 0 1 1 0 1 0 −logmax Pr[c = Encaps(pk ,pk )]. We say that KEM is γ-spread if for every (pk ,sk ) ← KeyGen1 c∈C 1 0 1 1 and pk ← A or (pk ,sk ) ← KeyGen0 and pk ← A, γ(pk ,pk ,A) ≥ γ, which means for every 0 0 0 1 1 0 ciphertext c∈C, it has Pr[c=Encaps(pk ,pk )]≤2−γ. 1 0 4 Authenticated Key Exchange from 2-Key KEM Inthissection,weproposeCK+ secureAKEsfrom[CCA,CPA]secure2-keyKEMinbothrandomoracle 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 ×D → R be a sk b function from domain D ×D to R. Denote KeyGen → D ×D as key generation algorithm for sk b sk pk some KEM. Let D ,R be the uniformly distributions over D ,R. It is called (ε ,ε ) hl-RF with respect b b 1 2 to KeyGen, if for (pk,sk)←KeyGen, the following distributions are computational indistinguishable with advantage ε ,ε . 1 2 {(pk,sk,f(sk,b))|b←D }= {(pk,sk,U)|U ←R}; b ε1 {(pk,b,f(sk,b))|b←D }= {(pk,b,U)|b←D ,U ←R}. b ε2 b The hk-RF can be achieved in both random oracle model and standard model. – In the random oracle model, if f is a hash function, without the knowledge of b, the output of f is totally random; if KEM with respect to KeyGen is secure, without the knowledge of sk the output of f is computational indistinguishable with a random string (otherwise the adversary must query random oracle with sk which against the security of KEM) given pk. Then equation 2 holds. This structure is known as NAXOS trick [LLM07]. – Let F(cid:48) : D ×{0,1}λ → R and F(cid:48)(cid:48) : D ×D → R be two pseudo random functions (PRFs). If b sk b assume KeyGen outputs an additional string s ← {0,1}λ, after obtaining (pk,sk), set sk = (sk||s). If f(sk,b) = F(cid:48)(1λ)⊕F(cid:48)(cid:48)(b), then even given pk, without the knowledge of s or b, f(sk,b) is com- b s putational indistinguishable with random distribution over R. This is known as twisted PRF trick [FSXY12][Oka07]. 4.1 AKE 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 2KEM = (KeyGen1,KeyGen0,Encaps,Decaps) be a [OW-CCA, OW-CPA] secure 2-key KEM with secret key space D × D , random space R. Let H : {0,1}∗ → {0,1}λ be hash function, f : sk1 sk0 A D ×{0,1}∗ →Randf :D ×{0,1}∗ →Rbehl-RFs.TheCK+ secureAKEispresentedinFigure sk1 B sk1 2. 10