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

One-round strongly secure key exchange with perfect forward secrecy and deniability

Cas J. F. Cremers, Michèle Feltz

Published Jun 1, 2011• 35 citations
Publisher

Abstract

Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead. We show that by reintroducing signatures, it is possible to satisfy both a strong key-exchange security notion as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e. g., the extended CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e. g., the SIGMA protocol. We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties and efficiency

DOI
10.3929/ethz-a-006519221

Related papers

A practical strongly secure one‐round authenticated key exchange protocol without random oracles

Zheng Yang, Yang Wu

Abstract Most recently, a variant of extended Canetti–Krawczyk model called aseCKwis introduced to provide stronger security than previous eCK models. NamelyeCKwmodels formulate a stronger notion regarding weak perfect forward secrecy than other eCK models. In particular, anyeCKwsecure protocols can be generally transformed to achieve full provide perfect forward secrecy without requiring additional round. So far, there is no protocol which has been proven secure in theeCKwmodel without random oracles. In this paper, we study the open problem on constructingeCKwsecure AKE protocol in the standard model. A new one‐round AKE protocol is introduced relying on standard cryptographic primitives and a variant of bilinear decisional Diffie–Hellman assumption. The main advantage of our proposal is its high efficiency in key exchange in contrast to the previous eCK secure protocols without random oracles and under post‐specified peer setting. Copyright © 2014 John Wiley & Sons, Ltd.

Security and Communication Networks•Sep 9, 2014•4 citations

eCK Secure Single Round ID-based Authenticated Key Exchange Protocols with Master Perfect Forward Secrecy (Extended Version)

Tapas Pandit, Rana Barua, Somanath Tripathy

Recently, LaMacchia, Lauter and Mityagin proposed the extended Canetti-Krawczyk (eCK) model for Authenticated Key Exchange (AKE) protocols that covers many attacks on existing models. An ID-based AKE protocol with Perfect Forward Secrecy (PFS) (respectively Master Perfect Forward Secrecy (MPFS)) ensures that revelation of the static keys of the parties (respectively the master secret key of the private key generator), must not compromise even a single bit of the session keys of the past sessions between the parties. Currently, to the best of our knowledge, there is no ID-based eCK secure single round AKE protocol with either PFS or MPFS. In our preliminary version [18] we have proposed, without proofs, ID-based eCK secure single round AKE protocols with PFS and MPFS in the random oracle model. To achieve this, we also have constructed ID-based eCK secure single round AKE protocols, one without Master Forward Secrecy (MFS) and one with MFS, almost at the same computational cost as the existing efficient ID-based eCK Secure Single Round AKE protocols. In this full version, we provide proofs to show that all of our protocols are secure under the Gap Bilinear Diffie-Hellman (GBDH) problem.

Journal of Wireless Mobile Networks Ubiquitous Computing and Dependable Applications•Jan 1, 2014•1 citation

Strongly Secure One Round Authenticated Key Exchange Protocol with Perfect Forward Security.

Hai Huang

Abstract. This paper investigates the two-pass authenticated key exchange protocol in the enhanced Canetti-Krawczyk (eCK) with perfect forward security. Currently, there exist no authenticated key exchange protocols which are provably secure in eCK model and meanwhile achieve perfect forward security against active adversary in one round. We propose a new two-pass authenticated key exchange protocol which enjoys following desirable properties. First, our protocol is shown secure in the eCK model under the gap Diffie-Hellman (GDH) assumption. Moreover, our protocol does not use the NAXOS transformation, the drawback of which will be discussed in the introduction. Second, under the same assumption, we prove that our protocol achieves perfect forward security against active adversary in one round. To the best of our knowledge, our proposal is first two-pass (one round) AKE protocol provably secure in the eCK model and achieving perfect forward security against active adversary.

•Jan 1, 2011•0 citations

One-Round Authenticated Key Exchange with Strong Forward Secrecy in the Standard Model against Constrained Adversary

Kazuki Yoneyama

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.

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

Unified security model of authenticated key exchange with specific adversarial capabilities

Weiqiang Wen, Libin Wang, Jiaxin Pan

The most widely accepted models in the security proofs of authenticated key exchange protocols are the Canetti–Krawczyk (CK) and extended CK models that admit different adversarial queries with ambiguities and incomparable strength. It is desirable to incorporate specific and powerful adversarial queries into a single unified security model and establish a more practical oriented security notion. Concerning the security of one‐round implicitly authenticated Diffie–Hellman (DH) key exchange protocols, the authors present a unified security model that has many advantages over the previous ones. In the model, a system environment is set up, all of adversarial queries are practically interpreted and definitely characterised through physical environment, and some rigorous rules of secret leakage are also specified. To demonstrate usability of their model, a new protocol based on the OAKE protocol is proposed, which satisfies the presented strong security notion and attains high efficiency. The protocol is proven secure in random oracle model under gap DH assumption.

IET Information Security•Jul 22, 2015•8 citations

One-round Protocols for Two-Party Authenticated Key Exchange

Ik-Rae Jeong, Donghoon Lee

Abstract. Cryptographic protocol design in a two-party setting has often ignored the possibility of simultaneous message transmission by each of the two parties (i.e., using a duplex channel). In particular, most protocols for two-party key exchange have been designed assuming that parties alternate sending their messages (i.e., assuming a bidirectional half-duplex channel). However, by taking advantage of the communication characteristics of the network it may be possible to design protocols with improved latency. This is the focus of the present work. We present a number of provably-secure protocols for two-party authenticated key exchange (AKE) which require only a single round. Our first protocol provides key independence only, and is analyzed in the random oracle model. This scheme matches the most efficient AKE protocols among those found in the literature. Our second scheme additionally provides forward secrecy, and is also analyzed in the random oracle model. Our final protocol provides the same strong security guarantees, but is proven secure in the standard model. This scheme is only slightly less efficient (from a computational perspective) than the previous ones. These last two schemes are the first provably-secure one-round protocols for authenticated 2-party key exchange which provide forward secrecy.

Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon•Jan 1, 2006•1 citation
Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead. We show that by reintroducing signatures, it is possible to satisfy both a strong key-exchange security notion as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e. g., the extended CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e. g., the SIGMA protocol. We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties and efficiency
Abstract Most recently, a variant of extended Canetti–Krawczyk model called aseCKwis introduced to provide stronger security than previous eCK models. NamelyeCKwmodels formulate a stronger notion regarding weak perfect forward secrecy than other eCK models. In particular, anyeCKwsecure protocols can be generally transformed to achieve full provide perfect forward secrecy without requiring additional round. So far, there is no protocol which has been proven secure in theeCKwmodel without random oracles. In this paper, we study the open problem on constructingeCKwsecure AKE protocol in the standard model. A new one‐round AKE protocol is introduced relying on standard cryptographic primitives and a variant of bilinear decisional Diffie–Hellman assumption. The main advantage of our proposal is its high efficiency in key exchange in contrast to the previous eCK secure protocols without random oracles and under post‐specified peer setting. Copyright © 2014 John Wiley & Sons, Ltd.
Recently, LaMacchia, Lauter and Mityagin proposed the extended Canetti-Krawczyk (eCK) model for Authenticated Key Exchange (AKE) protocols that covers many attacks on existing models. An ID-based AKE protocol with Perfect Forward Secrecy (PFS) (respectively Master Perfect Forward Secrecy (MPFS)) ensures that revelation of the static keys of the parties (respectively the master secret key of the private key generator), must not compromise even a single bit of the session keys of the past sessions between the parties. Currently, to the best of our knowledge, there is no ID-based eCK secure single round AKE protocol with either PFS or MPFS. In our preliminary version [18] we have proposed, without proofs, ID-based eCK secure single round AKE protocols with PFS and MPFS in the random oracle model. To achieve this, we also have constructed ID-based eCK secure single round AKE protocols, one without Master Forward Secrecy (MFS) and one with MFS, almost at the same computational cost as the existing efficient ID-based eCK Secure Single Round AKE protocols. In this full version, we provide proofs to show that all of our protocols are secure under the Gap Bilinear Diffie-Hellman (GBDH) problem.
Abstract. This paper investigates the two-pass authenticated key exchange protocol in the enhanced Canetti-Krawczyk (eCK) with perfect forward security. Currently, there exist no authenticated key exchange protocols which are provably secure in eCK model and meanwhile achieve perfect forward security against active adversary in one round. We propose a new two-pass authenticated key exchange protocol which enjoys following desirable properties. First, our protocol is shown secure in the eCK model under the gap Diffie-Hellman (GDH) assumption. Moreover, our protocol does not use the NAXOS transformation, the drawback of which will be discussed in the introduction. Second, under the same assumption, we prove that our protocol achieves perfect forward security against active adversary in one round. To the best of our knowledge, our proposal is first two-pass (one round) AKE protocol provably secure in the eCK model and achieving perfect forward security against active adversary.
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.
The most widely accepted models in the security proofs of authenticated key exchange protocols are the Canetti–Krawczyk (CK) and extended CK models that admit different adversarial queries with ambiguities and incomparable strength. It is desirable to incorporate specific and powerful adversarial queries into a single unified security model and establish a more practical oriented security notion. Concerning the security of one‐round implicitly authenticated Diffie–Hellman (DH) key exchange protocols, the authors present a unified security model that has many advantages over the previous ones. In the model, a system environment is set up, all of adversarial queries are practically interpreted and definitely characterised through physical environment, and some rigorous rules of secret leakage are also specified. To demonstrate usability of their model, a new protocol based on the OAKE protocol is proposed, which satisfies the presented strong security notion and attains high efficiency. The protocol is proven secure in random oracle model under gap DH assumption.
Abstract. Cryptographic protocol design in a two-party setting has often ignored the possibility of simultaneous message transmission by each of the two parties (i.e., using a duplex channel). In particular, most protocols for two-party key exchange have been designed assuming that parties alternate sending their messages (i.e., assuming a bidirectional half-duplex channel). However, by taking advantage of the communication characteristics of the network it may be possible to design protocols with improved latency. This is the focus of the present work. We present a number of provably-secure protocols for two-party authenticated key exchange (AKE) which require only a single round. Our first protocol provides key independence only, and is analyzed in the random oracle model. This scheme matches the most efficient AKE protocols among those found in the literature. Our second scheme additionally provides forward secrecy, and is also analyzed in the random oracle model. Our final protocol provides the same strong security guarantees, but is proven secure in the standard model. This scheme is only slightly less efficient (from a computational perspective) than the previous ones. These last two schemes are the first provably-secure one-round protocols for authenticated 2-party key exchange which provide forward secrecy.