Authenticated Key Exchange (AKE) is a cryptographic protocol to share a common session key among multiple parties. Usually, PKI-based AKE schemes are designed to guarantee secrecy of the session key and mutual authentication. However, in practice, there are many cases where mutual authentication is undesirable such as in anonymous networks like Tor and Riffle, or difficult to achieve due to the certificate management at the user level such as the Internet. Goldberg et al. formulated a model of anonymous one-sided AKE which guarantees the anonymity of the client by allowing only the client to authenticate the server, and proposed a concrete scheme. However, existing anonymous one-sided AKE schemes are only known to be secure in the random oracle model. In this paper, we propose generic constructions of anonymous one-sided AKE in the random oracle model and in the standard model, respectively. Our constructions allow us to construct the first post-quantum anonymous one-sided AKE scheme from isogenies in the standard model.

Hierarchical ID-based authenticated key exchange (HID-AKE) is a cryptographic protocol to establish a common session key between parties with authentication based on their IDs with the hierarchical delegation of key generation functionality. All existing HID-AKE schemes are selective ID secure, and the only known standard model scheme relies on a non-standard assumption such as the q-type assumption. In this paper, we propose a generic construction of HID-AKE that is adaptive ID secure in the HID-eCK model (maximal-exposure-resilient security model) without random oracles. One of the concrete instantiations of our generic construction achieves the first adaptive ID secure HID-AKE scheme under the (standard) k-lin assumption in the standard model. Furthermore, it has the advantage that the computational complexity of pairing and exponentiation operations and the communication complexity do not depend on the depth of the hierarchy. Also, the other concrete instantiation achieves the first HID-AKE scheme based on lattices (i.e., post-quantum).

Almost all existing password-based authenticated key exchange (PAKE) schemes achieve concurrent security in the standard model by relying on the common reference string (CRS) model. A drawback of the CRS model is to require a centralized trusted authority in the setup phase; thus, passwords of parties may be revealed if the authority ill-uses trapdoor information of the CRS. There are a few secure PAKE schemes in the plain model, but, these are not achievable in a constant round (i.e., containing a linear number of rounds). In this paper, we discuss how to relax the setup assumption for (constant round) PAKE schemes. We focus on the multi-string (MS) model that allows a number of authorities (including malicious one) to provide some reference strings independently. The MS model is a more relaxed setup assumption than the CRS model because we do not trust any single authority (i.e., just assuming that a majority of authorities honestly generate their reference strings). Though the MS model is slightly restrictive than the plain model, it is very reasonable assumption because it is very easy to implement. We construct a (concurrently secure) three-move PAKE scheme in the MS model (justly without random oracles) based on the Groce-Katz PAKE scheme. The main ingredient of our scheme is the multi-string simulation-extractable non-interactive zero-knowledge proof that provides both the simulation-extractability and the extraction zero-knowledge property even if minority authorities are malicious. This work can be seen as a milestone toward constant round PAKE schemes in the plain model.

By using Password-based Authenticated Key Exchange (PAKE), a server can authenticate a user who has only the same password shared with the server in advance and establish a session key with the user simultaneously. However, in the real applications, we may have a situation where a user needs to share a session key with server A, but the authentication needs to be done by a different server B that shares the password with the user. Further, to achieve higher security on the server side, it may be required to make PAKE tolerant of a server breach by having multiple authentication servers. To deal with such a situation, Abdalla et al. proposed a variant of PAKE called Gateway Threshold PAKE (GTPAKE) where a gateway corresponds to the aforementioned server A being an on-line service provider and also a potential adversary that may try to guess the passwords. However, the schemes of Abdalla et al. turned out to be vulnerable to Undetectable On-line Dictionary Attack (UDonDA). In this paper, we propose the first GTPAKE provably secure against UDonDA, and in the security analysis, we prove that our GTPAKE is secure even if an adversary breaks into parts of multiple authentication servers.

Although password-only authenticated key exchange (PAKE) in the three-party setting has been widely studied in recent years, it remains a challenging area of research. A key challenge in designing three-party PAKE protocols is to prevent insider dictionary attacks, as evidenced by the flaws discovered in many published protocols. In this letter, we revisit Abdalla and Pointcheval's three-party PAKE protocol from FC 2005 and demonstrate that this protocol, named 3PAKE, is vulnerable to a previously unpublished insider offline dictionary attack. Our attack is dependant on the composition of 3PAKE and the higher-level protocol that uses the established session key.

How to reduce communication complexity is a common important issue to design cryptographic protocols. This paper focuses on authenticated key exchange (AKE). Several AKE schemes have been studied, which satisfy strong security such as exposure-resilience in the standard model (StdM). However, there is a large gap on communication costs between schemes in the StdM and in the random oracle model. In this paper, we show a generic construction that is significantly compact (i.e., small communication cost) and secure in the StdM. We follow an existing generic construction from key encapsulated mechanism (KEM). Our main technique is to use a bounded chosen-ciphertext secure KEM instead of an ordinary chosen-ciphertext secure KEM. The communication cost can be reduced to half by this technique, and we achieve the most compact AKE scheme in the StdM. Moreover, our construction has instantiations under wider classes of hardness assumptions (e.g., subset-sum problems and multi-variate quadratic systems) than existing constructions. This work pioneers the first meaningful application of bounded chosen-ciphertext secure KEM.

This paper studies Tripartite Key Exchange (3KE) which is a special case of Group Key Exchange. Though general one-round GKE satisfying advanced security properties such as forward secrecy and maximal-exposure-resilience (MEX-resilience) is not known, it can be efficiently constructed with the help of pairings in the 3KE case. In this paper, we introduce the first one-round 3KE which is MEX-resilient in the standard model, though existing one-round 3KE schemes are proved in the random oracle model (ROM), or not MEX-resilient. Each party broadcasts 4 group elements, and executes 14 pairing operations. Complexity is only three or four times larger in computation and communication than the existing most efficient MEX-resilient 3KE scheme in the ROM; thus, our protocol is adequately practical.

ID-based authenticated key exchange (ID-AKE) is a cryptographic tool to establish a common session key between parties with authentication based on their IDs. If IDs contain some hierarchical structure such as an e-mail address, hierarchical ID-AKE (HID-AKE) is especially suitable because of scalability. However, most of existing HID-AKE schemes do not satisfy advanced security properties such as forward secrecy, and the only known strongly secure HID-AKE scheme is inefficient. In this paper, we propose a new HID-AKE scheme which achieves both strong security and efficiency. We prove that our scheme is eCK-secure (which ensures maximal-exposure-resilience including forward secrecy) without random oracles, while existing schemes is proved in the random oracle model. Moreover, the number of messages and pairing operations are independent of the hierarchy depth; that is, really scalable and practical for a large-system.

In this paper, we propose a generic construction of one-round attribute-based (implicitly) authenticated key exchange (ABAKE). The construction is based on a chosen-ciphertext (CCA) secure attribute-based KEM and the decisional Diffie-Hellman (DDH) assumption. If an underlying attribute-based KEM scheme allows expressive access controls and is secure in the standard model (StdM), an instantiated ABAKE scheme also achieves them. Our scheme enjoys the best of both worlds: efficiency and security. The number of rounds is one (optimal) while the known secure scheme in the StdM is not one-round protocol. Our scheme is comparable in communication complexity with the most efficient known scheme that is not proved in the StdM. Also, our scheme is proved to satisfy security against advanced attacks like key compromise impersonation.

Forward secrecy (FS) is a central security requirement of authenticated key exchange (AKE). Especially, strong FS (sFS) is desirable because it can guarantee security against a very realistic attack scenario that an adversary is allowed to be active in the target session. However, most of AKE schemes cannot achieve sFS, and currently known schemes with sFS are only proved in the random oracle model. In this paper, we propose a generic construction of AKE protocol with sFS in the standard model against a constrained adversary. The constraint is that session-specific intermediate computation results (i.e., session state) cannot be revealed to the adversary for achieving sFS, that is shown to be inevitable by Boyd and González Nieto. However, our scheme maintains weak FS (wFS) if session state is available to the adversary. Thus, our scheme satisfies one of strongest security definitions, the CK+ model, which includes wFS and session state reveal. The main idea to achieve sFS is to use signcryption KEM while the previous CK+ secure construction uses ordinary KEM. We show a possible instantiation of our construction from Diffie-Hellman problems.

In this paper, we propose an identity-based authenticated key exchange (ID-AKE) protocol that is secure in the identity-based extended Canetti-Krawczyk (id-eCK) model in the random oracle model under the gap Bilinear Diffie-Hellman assumption. The proposed ID-AKE protocol is the most efficient among the existing ID-AKE protocols that is id-eCK secure, and it can be extended to use in asymmetric pairing.

This paper examines two-pass authenticated key exchange (AKE) protocols that are secure without the NAXOS technique under the gap Diffie-Hellman assumption in the random oracle model: FHMQV [18], KFU1 [21], SMEN- [13], and UP [17]. We introduce two protocol, biclique DH protocol and multiplied biclique DH protocol, to analyze the subject protocols, and show that the subject protocols use the multiplied biclique DH protocol as internal protocols. The biclique DH protocol is secure, however, the multiplied biclique DH protocol is insecure. We show the relations between the subject protocols from the viewpoint of how they overcome the insecurity of the multiplied biclique DH protocol: FHMQV virtually executes two multiplied biclique DH protocols in sequence with the same ephemeral key on two randomized static keys. KFU1 executes two multiplied biclique DH protocols in parallel with the same ephemeral key. UP is a version of KFU1 in which one of the static public keys is generated with a random oracle. SMEN- can be thought of as a combined execution of two multiplied biclique DH protocols. In addition, this paper provides ways to characterize the AKE protocols and defines two parameters: one consists of the number of static keys, the number of ephemeral keys, and the number of shared secrets, and the other is defined as the total sum of these numbers. When an AKE protocol is constructed based on some group, these two parameters indicate the number of elements in the group, i.e., they are related to the sizes of the storage and communication data.

LaMacchia, Lauter and Mityagin [19] proposed a novel security definition for authenticate key exchange (AKE) that gives an adversary the power to obtain ephemeral information regarding a target test session. To demonstrate feasibility of secure protocols in the new definition, henceforth called eCK, the authors described a protocol called NAXOS. NAXOS combines an ephemeral private key x with a static private key a to generate an ephemeral public key X (more precisely in what we call the NAXOS' approach X = gH(x,a)). Thus no one is able to query the discrete logarithm of X without knowing both the ephemeral and static private keys. This idea is crucial in the security argument to guard against leaked ephemeral secrets belonging to the test session. Another important assumption is the gap assumption that allows the protocol to remain secure even in the presence of malicious insiders. Both ideas have been successfully used in creating various protocols secure in the eCK model. In this paper, we construct two eCK-secure protocols without the above mentioned ideas. KFU1 is secure under the GDH assumption without using the NAXOS' approach. KFU2 builds upon KFU1 and drops the gap requirement, thus it is secure under the CDH assumption. Efficiency and security of the proposed protocols are comparable to the well-known HMQV [15] protocol. Furthermore, unlike HMQV and NAXOS the use of the random oracle in KFU1 and KFU2 is restricted to the key derivation function making them more suitable for practical applications.

An anonymous password-authenticated key exchange (PAKE) protocol is designed to provide both password-only authentication and client anonymity against a semi-honest server, who honestly follows the protocol. In INDOCRYPT2008, Yang and Zhang [26] proposed a new anonymous PAKE (NAPAKE) protocol and its threshold (D-NAPAKE) which they claimed to be secure against insider attacks. In this paper, we first show that the D-NAPAKE protocol [26] is completely insecure against insider attacks unlike their claim. Specifically, only one legitimate client can freely impersonate any subgroup of clients (the threshold t > 1) to the server. After giving a security model that captures insider attacks, we propose a threshold anonymous PAKE (called, TAP+) protocol which provides security against insider attacks. Moreover, we prove that the TAP+ protocol has semantic security of session keys against active attacks as well as insider attacks under the computational Diffie-Hellman problem, and provides client anonymity against a semi-honest server, who honestly follows the protocol. Finally, several discussions are followed: 1) We also show another threshold anonymous PAKE protocol by applying our RATIONALE to the non-threshold anonymous PAKE (VEAP) protocol [23]; and 2) We give the efficiency comparison, security consideration and implementation issue of the TAP+ protocol.

In this paper, we propose two authenticated key exchange(AKE) protocols and prove their security in the extended Canetti-Krawczyk model. The first protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin [15]. We prove its security under the Computational Diffie-Hellman (CDH) assumption by using the trapdoor test introduced in [6]. To the authors' knowledge, this is the first AKE protocol which is secure under the CDH assumption in the eCK model. The second protocol, called NETS, enjoys a simple and tight security reduction compared to existing schemes including HMQV and CMQV without using the Forking Lemma. Since each session of the NETS protocol requires only three exponentiations per party, its efficiency is also comparable to MQV, HMQV and CMQV.

Secure channels can be realized by an authenticated key exchange (AKE) protocol that generates authenticated session keys between the involving parties. In, Shin et al., proposed a new kind of AKE (RSA-AKE) protocol whose goal is to provide high efficiency and security against leakage of stored secrets as much as possible. Let us consider more powerful attacks where an adversary completely controls the communications and the stored secrets (the latter is denoted by "replacement" attacks). In this paper, we first show that the RSA-AKE protocol is no longer secure against such an adversary. The main contributions of this paper are as follows: (1) we propose an RSA-based leakage-resilient AKE (RSA-AKE2) protocol that is secure against active attacks as well as replacement attacks; (2) we prove that the RSA-AKE2 protocol is secure against replacement attacks based on the number theory results; (3) we show that it is provably secure in the random oracle model, by showing the reduction to the RSA one-wayness, under an extended model that covers active attacks and replacement attacks; (4) in terms of efficiency, the RSA-AKE2 protocol is comparable to in the sense that the client needs to compute only one modular multiplication with pre-computation; and (5) we also discuss about extensions of the RSA-AKE2 protocol for several security properties (i.e., synchronization of stored secrets, privacy of client and solution to server compromise-impersonation attacks).

An anonymous password-authenticated key exchange (anonymous PAKE) protocol is designed to provide both password-only authentication and user anonymity against a semi-honest server, who follows the protocol honestly. Very recently, Yang and Zhang have proposed a new anonymous PAKE (NAPAKE) protocol that is claimed efficient compared to the previous constructions. In this paper, we propose a very-efficient anonymous PAKE (called, VEAP) protocol that provides the most efficiency among their kinds in terms of computation and communication costs. The VEAP protocol guarantees semantic security of session keys in the random oracle model under the chosen target CDH problem, and unconditional user anonymity against a semi-honest server. If the pre-computation is allowed, both the user and the server are required to compute only one modular exponentiation, respectively. Surprisingly, this is the same computation cost of the well-known Diffie-Hellman protocol that does not provide authentication at all. In addition, we extend the VEAP protocol in two ways: the first is designed to reduce the communication costs of the VEAP protocol and the second shows that stripping off anonymity parts from the VEAP protocol results in a new PAKE protocol.

In this paper, we raise a question about existence of secure password-based authenticated key exchange against leakage of internal states (i.e., the passwords and session-specific private information). Toward this question, first, we classify six models of adversary's capabilities about leakage. Next, as a result of considerations for 2-party PAKE, we find two negative answers, but also find a positive answer. More specifically, we show that there exists no scheme which is secure in strong leakage models, but we also show that there exists a scheme which is secure in weak leakage models. Also, we consider the case of 3-party setting which is a special setting of password-based authenticated key exchange, and we find similar impossibilities as 2-party setting.

Both mutual authentication and generation of session keys can be accomplished by an authenticated key exchange (AKE) protocol. Let us consider the following situation: (1) a client, who communicates with many different servers, remembers only one password and has insecure devices (e.g., mobile phones or PDAs) with very-restricted computing power and built-in memory capacity; (2) the counterpart servers have enormous computing power, but they are not perfectly secure against various attacks (e.g., virus or hackers); (3) neither PKI (Public Key Infrastructures) nor TRM (Tamper-Resistant Modules) is available. The main goal of this paper is to provide security against the leakage of stored secrets as well as to attain high efficiency on client's side. For those, we propose an efficient and leakage-resilient RSA-based AKE (RSA-AKE) protocol suitable for the above situation whose authenticity is based on password and another secret. In the extended model where an adversary is given access to the stored secret of client, we prove that its security of the RSA-AKE protocol is reduced tightly to the RSA one-wayness in the random oracle model. We also show that the RSA-AKE protocol guarantees several security properties (e.g., security of password, multiple sever scenario with only one password, perfect forward secrecy and anonymity). To our best knowledge, the RSA-AKE protocol is the most efficient, in terms of both computation costs of client and communication costs, over the previous AKE protocols of their kind (using password and RSA).

Password-based authenticated key exchange protocols are more convenient and practical, since users employ human-memorable passwords that are simpler to remember than cryptographic secret keys or public/private keys. Abdalla, Fouque, and Pointcheval proposed the password-based authenticated key exchange protocol in a 3-party model (GPAKE) in which clients trying to establish a secret do not share a password between themselves but only with a trusted server. On the other hand, Canetti presented a general framework, which is called universally composable (UC) framework, for representing cryptographic protocols and analyzing their security. In this framework, the security of protocols is maintained under a general protocol composition operation called universal composition. Canetti also proved a UC composition theorem, which states that the definition of UC-security achieves the goal of concurrent general composition. A server must manage all the passwords of clients when the 3-party password-based authenticated key exchange protocols are realized in large-scale networks. In order to resolve this problem, we propose a hierarchical hybrid authenticated key exchange protocol (H2AKE). In H2AKE, forwarding servers are located between each client and a distribution server, and the distribution server sends the client an authentication key via the forwarding servers. In H2AKE, public/private keys are used between servers, while passwords are also used between clients and forwarding servers. Thus, in H2AKE, the load on the distribution server can be distributed to the forwarding servers concerning password management. In this paper, we define hierarchical hybrid authenticated key exchange functionality. H2AKE is the universal form of the hierarchical (hybrid) authenticated key exchange protocol, which includes a 3-party model, and it has the characteristic that the construction of the protocol can flexibly change according to the situation. We also prove that H2AKE is secure in the UC framework with the security-preserving composition property.