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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Compact Authenticated Key Exchange from Bounded CCA-Secure KEM

Kazuki Yoneyama

Published Jan 1, 2015• 1 citation
Publisher

Abstract

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.

DOI
10.1587/transfun.e98.a.132

Related papers

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, 2012•3 citations

Generic Construction of Two-Party Round-Optimal Attribute-Based Authenticated Key Exchange without Random Oracles

Kazuki Yoneyama

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2013•11 citations

Attribute-based Authenticated Key Exchange.

M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto

Abstract. We introduce the concept of attribute-based authenticated key exchange (AB-AKE) within the framework of ciphertext policy attribute-based systems. A notion of AKE-security for AB-AKE is presented based on the security models for group key exchange protocols and also taking into account the security requirements generally considered in the ciphertext policy attribute-based setting. We also extend the paradigm of hybrid encryption to the ciphertext policy attribute-based encryption schemes. A new primitive called encapsulation policy attribute-based key encapsulation mechanism (EP-AB-KEM) is introduced and a notion of chosen ciphertext security is defined for EP-AB-KEMs. We propose an EP-AB-KEM from an existing attribute-based encryption scheme and show that it achieves chosen ciphertext security in the generic group and random oracle models. We present a generic one-round AB-AKE protocol that satisfies our AKE-security notion. The protocol is generically constructed from any EP-AB-KEM that satisfies chosen ciphertext security. Instantiating the generic AB-AKE protocol with our EP-AB-KEM will result in a concrete one-round AB-AKE protocol also secure in the generic group and random oracle models.

•Jan 1, 2010•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

Chosen-Ciphertext Secure Key Encapsulation Mechanism in the Standard Model

Shengfeng Xu, Xiangxue Li

Key Encapsulation Mechanism (KEM) is a foundational cryptography primitive, which can provide secure symmetric cryptographic key material for transmission by using public key algorithms. Until now, many Chosen-Ciphertext (IND-CCA) secure KEM schemes are constructed from Chosen-Plaintext (IND-CPA) or One-Way (OW-CPA) secure PKE via the generic Fujisaki-Okamoto (FO) transformations (TCC 2017). However, the security relies on the Random Oracle Model (ROM). To the best of our knowledge, there are no IND-CCA secure KEM schemes based on Learning Parity with Noise (LPN) assumption that can against post quantum attacks in the standard model. In this work, we propose the first direct construction of LPN-based KEM, which is secure in the standard model. In particular, we use double-trapdoor technique to answer adversary’s decryption queries correctly and a Target Collision Resistant (TCR) hash function to check the validity of the ciphertext. The encapsulated key is determined by a special LPN problem (with no random oracle required). The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight. Compared with previous schemes on 128-bit security level, our CCA-secure scheme only holds 50.78MB public keys, 62.50MB secret keys and 4.54KB ciphertexts, which is more efficient than the schemes of Döttlinget al.(ASIACRYPT 2012), Kiltzet al.(PKC 2014) and Yuet al.(CRYPTO 2016) ((7.27GB, 7.24GB, 7.03KB), (80.89MB, 46.23MB, 6.80KB) and (70.95MB, 70.65MB, 86.50KB) respectively).

IEEE Access•Jan 1, 2021•7 citations

One-Round Authenticated Key Exchange without Implementation Tricks

Kazuki Yoneyama

Fujioka et al. proposed the first generic construction (FSXY construction) of exposure-resilient authenticated key exchange (AKE) from a key encapsulation mechanism (KEM) without random oracles. However, the FSXY construction implicitly assumes that some intermediate computation result is never exposed though other secret information can be exposed. This is a kind of physical assumption, and an implementation trick (i.e., some on-line computation is executed in a special tamper-proof module) is necessary to achieve the assumption. Such a trick is very costly and may be missed by human errors in implementation. From the viewpoint of the human factor, it is desirable to avoid using complicated implementation tricks. In this paper, we introduce a new generic construction without implementation tricks. Our construction satisfies the same security model as the FSXY construction without increasing communication complexity. Moreover, it has another advantage that the protocol can be executed in one-round while the FSXY construction is a sequential two-move protocol. Our key idea is to use KEM with public-key-independent-ciphertext, which allows parties to be able to generate a ciphertext without depending on encryption keys.

Journal of Information Processing•Jan 1, 2016•2 citations
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.
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.
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.
Abstract. We introduce the concept of attribute-based authenticated key exchange (AB-AKE) within the framework of ciphertext policy attribute-based systems. A notion of AKE-security for AB-AKE is presented based on the security models for group key exchange protocols and also taking into account the security requirements generally considered in the ciphertext policy attribute-based setting. We also extend the paradigm of hybrid encryption to the ciphertext policy attribute-based encryption schemes. A new primitive called encapsulation policy attribute-based key encapsulation mechanism (EP-AB-KEM) is introduced and a notion of chosen ciphertext security is defined for EP-AB-KEMs. We propose an EP-AB-KEM from an existing attribute-based encryption scheme and show that it achieves chosen ciphertext security in the generic group and random oracle models. We present a generic one-round AB-AKE protocol that satisfies our AKE-security notion. The protocol is generically constructed from any EP-AB-KEM that satisfies chosen ciphertext security. Instantiating the generic AB-AKE protocol with our EP-AB-KEM will result in a concrete one-round AB-AKE protocol also secure in the generic group and random oracle models.
Key Encapsulation Mechanism (KEM) is a foundational cryptography primitive, which can provide secure symmetric cryptographic key material for transmission by using public key algorithms. Until now, many Chosen-Ciphertext (IND-CCA) secure KEM schemes are constructed from Chosen-Plaintext (IND-CPA) or One-Way (OW-CPA) secure PKE via the generic Fujisaki-Okamoto (FO) transformations (TCC 2017). However, the security relies on the Random Oracle Model (ROM). To the best of our knowledge, there are no IND-CCA secure KEM schemes based on Learning Parity with Noise (LPN) assumption that can against post quantum attacks in the standard model. In this work, we propose the first direct construction of LPN-based KEM, which is secure in the standard model. In particular, we use double-trapdoor technique to answer adversary’s decryption queries correctly and a Target Collision Resistant (TCR) hash function to check the validity of the ciphertext. The encapsulated key is determined by a special LPN problem (with no random oracle required). The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight. Compared with previous schemes on 128-bit security level, our CCA-secure scheme only holds 50.78MB public keys, 62.50MB secret keys and 4.54KB ciphertexts, which is more efficient than the schemes of Döttlinget al.(ASIACRYPT 2012), Kiltzet al.(PKC 2014) and Yuet al.(CRYPTO 2016) ((7.27GB, 7.24GB, 7.03KB), (80.89MB, 46.23MB, 6.80KB) and (70.95MB, 70.65MB, 86.50KB) respectively).
Fujioka et al. proposed the first generic construction (FSXY construction) of exposure-resilient authenticated key exchange (AKE) from a key encapsulation mechanism (KEM) without random oracles. However, the FSXY construction implicitly assumes that some intermediate computation result is never exposed though other secret information can be exposed. This is a kind of physical assumption, and an implementation trick (i.e., some on-line computation is executed in a special tamper-proof module) is necessary to achieve the assumption. Such a trick is very costly and may be missed by human errors in implementation. From the viewpoint of the human factor, it is desirable to avoid using complicated implementation tricks. In this paper, we introduce a new generic construction without implementation tricks. Our construction satisfies the same security model as the FSXY construction without increasing communication complexity. Moreover, it has another advantage that the protocol can be executed in one-round while the FSXY construction is a sequential two-move protocol. Our key idea is to use KEM with public-key-independent-ciphertext, which allows parties to be able to generate a ciphertext without depending on encryption keys.