Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, Kazuki Yoneyama

Published Jan 1, 2012• 3 citations
OpenAlex

Abstract

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.

Related papers

Strongly Secure Authenticated Key Exchange in the Standard Model

Zheng Yang

Nowadays many crucial network applications rely on the existence of a confidential channel established by authenticated key exchange (AKE) protocols over public networks.With the rapid development of cyber technology, novel attacks to cryptosystem emerge in an endless stream.This has also led to the development of AKE solutions to provide increasingly stronger security guarantees.In this thesis we focus on provision of practical constructions for AKE protocols which are provably secure in a strong sense without resorting to random oracles.We first we present three new efficient compilers to generically turn passively secure key exchange protocols (KE) into authenticated key exchange protocols (AKE) where security also holds in the presence of active adversaries.Our compilers are not only a useful tool for the design of new AKE systems with many additional security properties in a modular and less error-prone fashion, but they also help to relax the assumptions on existing, practical key exchange mechanisms which are not known to be provably secure AKE protocols.Security of our compilers is shown in a strong modified CK model where the adversary is allowed to reveal either long-term secret key or state information of the protocol participants.On the second, we study the open problem on constructing eCK secure two party AKE protocol without random oracles and NAXOS trick.A generic construction satisfying those requirements is given based on well-known cryptographic primitives following the guideline of efficiency.Then a concrete protocol is proposed which is the first eCK secure protocol in the standard model under both standard assumptions and post-specified peer setting (i.e.without knowing any cryptographic information about its communication peer).Both proposed schemes can be more efficiently implemented with secure device than previous works which are eCK secure in the standard model, where the secure device might be normally used to store the long-term private key and to implement codes of protocol which need to be resilience of state leakage.Finally, we generalize our one-round two party AKE construction to group case that yields an efficient tripartite AKE protocol based on bilinear maps and a candidate group AKE protocol (with more than three members) based on multilinear maps.Up to now they are the first solutions which can be proved secure in the g-eCK model without random oracles.Meanwhile we make first step to show how to simplify the security proof for one-round group AKE under g-eCK model.i

•Jan 1, 2013•0 citations

Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism

Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa +1 more

This paper discusses how to realize practical post-quantum authenticated key exchange (AKE) with strong security, i.e., CK+ security (Krawczyk, CRYPTO 2005). It is known that strongly secure post-quantum AKE protocols exist on a generic construction from IND-CCA secure key encapsulation mechanisms (KEMs) in the standard model.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•May 8, 2013•53 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 Sciences•Mar 23, 2022•1 citation

Compact Authenticated Key Exchange from Bounded CCA-Secure KEM

Kazuki Yoneyama

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2015•1 citation

Authenticated Key Exchange Protocol in the Standard Model under Weaker Assumptions

Janaka Alawatugoda

A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels, even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the malicious behaviors of the adversaries, there have been many efforts to define security models. Amongst them, the extended Canetti–Krawczyk (eCK) security model is considered one of the strongest security models and has been widely adopted. In this paper, we present a simple construction of a pairing-based eCK-secure AKE protocol in the standard model. Our protocol can be instantiated with a suitable signature scheme (i.e., an existentially unforgeable signature scheme against adaptive chosen message attacks). The underlying assumptions of our construction are the decisional bilinear Diffie–Hellman assumption and the existence of a pseudorandom function. Note that the previous eCK-secure protocol constructions either relied on random oracles for their security or used somewhat strong assumptions, such as the existence of strong-pseudorandom functions, target collision-resistant functions, etc., while our protocol construction uses fewer and more-standard assumptions in the standard model. Furthermore, preserving the same security argument, our protocol can be instantiated with any appropriate signature scheme that comes in the future with better efficiency.

Cryptography•Jan 5, 2023•2 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, 2024•0 citations
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.
Nowadays many crucial network applications rely on the existence of a confidential channel established by authenticated key exchange (AKE) protocols over public networks.With the rapid development of cyber technology, novel attacks to cryptosystem emerge in an endless stream.This has also led to the development of AKE solutions to provide increasingly stronger security guarantees.In this thesis we focus on provision of practical constructions for AKE protocols which are provably secure in a strong sense without resorting to random oracles.We first we present three new efficient compilers to generically turn passively secure key exchange protocols (KE) into authenticated key exchange protocols (AKE) where security also holds in the presence of active adversaries.Our compilers are not only a useful tool for the design of new AKE systems with many additional security properties in a modular and less error-prone fashion, but they also help to relax the assumptions on existing, practical key exchange mechanisms which are not known to be provably secure AKE protocols.Security of our compilers is shown in a strong modified CK model where the adversary is allowed to reveal either long-term secret key or state information of the protocol participants.On the second, we study the open problem on constructing eCK secure two party AKE protocol without random oracles and NAXOS trick.A generic construction satisfying those requirements is given based on well-known cryptographic primitives following the guideline of efficiency.Then a concrete protocol is proposed which is the first eCK secure protocol in the standard model under both standard assumptions and post-specified peer setting (i.e.without knowing any cryptographic information about its communication peer).Both proposed schemes can be more efficiently implemented with secure device than previous works which are eCK secure in the standard model, where the secure device might be normally used to store the long-term private key and to implement codes of protocol which need to be resilience of state leakage.Finally, we generalize our one-round two party AKE construction to group case that yields an efficient tripartite AKE protocol based on bilinear maps and a candidate group AKE protocol (with more than three members) based on multilinear maps.Up to now they are the first solutions which can be proved secure in the g-eCK model without random oracles.Meanwhile we make first step to show how to simplify the security proof for one-round group AKE under g-eCK model.i
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).
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.
A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels, even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the malicious behaviors of the adversaries, there have been many efforts to define security models. Amongst them, the extended Canetti–Krawczyk (eCK) security model is considered one of the strongest security models and has been widely adopted. In this paper, we present a simple construction of a pairing-based eCK-secure AKE protocol in the standard model. Our protocol can be instantiated with a suitable signature scheme (i.e., an existentially unforgeable signature scheme against adaptive chosen message attacks). The underlying assumptions of our construction are the decisional bilinear Diffie–Hellman assumption and the existence of a pseudorandom function. Note that the previous eCK-secure protocol constructions either relied on random oracles for their security or used somewhat strong assumptions, such as the existence of strong-pseudorandom functions, target collision-resistant functions, etc., while our protocol construction uses fewer and more-standard assumptions in the standard model. Furthermore, preserving the same security argument, our protocol can be instantiated with any appropriate signature scheme that comes in the future with better efficiency.
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.