Tightly-Secure Authenticated Key Exchange, Revisited.

Tibor Jager, Eike Kiltz, Doreen Riepel, Sven Schäge

Published Jan 1, 2020• 1 citation

Abstract

We introduce new tightly-secure authenticated key exchange (AKE) protocols that are extremely efficient, yet have only a constant security loss and can be instantiated in the random oracle model both from the standard DDH assumption and a subgroup assumption over RSA groups. These protocols can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate a security loss with increased parameters and thus decreased computational efficiency.

Related papers

An Efficient Authenticated Key Exchange Protocol with a Tight Security Reduction.

Jooyoung Lee, Choon‐Sik Park

In this paper, we present a new authenticated key exchange(AKE) protocol, called NETS, and prove its security in the extended Canetti-Krawczyk model under the random oracle assumption and the gap Diffie-Hellman(GDH) assumption. Our protocol enjoys a simple and tight security reduction compared to those of HMQV and CMQV without using the Forking Lemma. Each session of the NETS protocol requires only three exponentiations per party, which is comparable to the efficiency of MQV, HMQV and CMQV.

Jan 1, 200829 citations

An RSA-Based Leakage-Resilient Authenticated Key Exchange Protocol Secure against Replacement Attacks, and Its Extensions

SeongHan Shin, Kazukuni Kobara, Hideki Imai

Secure channels can be realized by an authenticated key exchange (AKE) protocol that generates authenticated session keys between the involving parties. In [32], 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 [32] 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 [32] 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).

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20106 citations

Signed (Group) Diffie–Hellman Key Exchange with Tight Security

Jiaxin Pan, Chen Qian, Magnus Ringerud

Abstract We propose the first tight security proof for the ordinary two-message signed Diffie–Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie–Hellman assumption and the multiuser security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange. In contrast to a known tight three-message variant of the signed Diffie–Hellman protocol (Gjøsteen and Jager, in: Shacham, Boldyreva (eds) CRYPTO 2018, Part II. LNCS, Springer, Heidelberg, 2018), we do not require any modification to the original protocol, and our tightness result is proven in the “Single-Bit-Guess” model which we know can be tightly composed with symmetric cryptographic primitives to establish a secure channel. Finally, we extend our approach to the group setting and construct the first tightly secure group authenticated key exchange protocol.

Journal of CryptologySep 27, 202223 citations

Tightly Secure ID-based Authenticated Key Exchange

Takumu Mita, Kazuki Yoneyama

In CRYPTO 2021, Han et al. proposed a PKI-based authenticated key exchange (AKE) scheme that satisfies tight security in the standard model by using KEM and digital signature with multi-user security as building blocks. On the other hand, no tightly secure ID-based AKE (ID-AKE) scheme is known. ID-AKE has the advantage that certificate management is unnecessary, and the authentication can be based on the party’s public ID, such as an e-mail address. In this paper, we propose the first tightly secure ID-AKE scheme in the standard model. First, we extend the security model of Han et al.’s PKI-based AKE to the security model for ID-AKE. Next, we introduce a generic construction with multi-user secure KEM and ID-based signature (IBS) as building blocks and prove the tight security in our security model. For instantiating the underlying IBS, we also revisit the security proof of the existing generic construction of tightly secure IBS proposed by Lee et al. We point out a problem in their proof and correct it by strengthening an assumption. As an instantiation of our scheme, a tightly secure ID-AKE scheme under the MDDH assumption can be realized in the standard model.

ACM ASIA Public-Key Cryptography Workshop (APKC)Jun 28, 20240 citations

Adaptive-ID Secure Hierarchical ID-Based Authenticated Key Exchange under Standard Assumptions without Random Oracles

Ren Ishibashi, Kazuki Yoneyama

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).

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesMar 23, 20221 citation

Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices.

Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa +1 more

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

Jan 1, 20123 citations