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

On Formal Models for Secure Key Exchange.

Victor Shoup

Published Jan 1, 1999• 319 citations
OpenAlex

Abstract

A new formal security model for session key exchange protocols in the public key setting is proposed, and several efficient protocols are analyzed in this model. The relationship between this new model and previously proposed models is explored, and several interesting, subtle distinctions between static and adaptive adversaries are explored. We also give a brief account of anonymous users. 1 Introduction In this paper, we investigate formal models of security for authenticated key exchange protocols in a public key setting where the only trusted party is an off-line certification authority. Our work follows up on that of Bellare, Canetti, and Krawczyk [2], which is grounded in the multi-party simulatability tradition (see, e.g., [1]). This approach seems very attractive, because it formulates security in terms of the service a session key protocol should provide to a higher level protocol, rather than getting mired in the details of session key protocols themselves, many of which ar...

Related papers

Efficient eCK-secure Authenticated Key Exchange Protocols in the Standard Model.

Zheng Yang

The extended Canetti–Krawczyk (eCK) security models, are widely used to provide security arguments for authenticated key exchange protocols that capture leakage of various kinds of secret information like the long-term private key and session-specific secret state. In this paper, we study the open problem on constructing eCK secure AKE protocol without random oracles and NAXOS like trick. A generic construction GC-KKN satisfying those requirements is first given relying on standard cryptographic primitives following the guideline of efficiency. On the second 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. Both proposed schemes can be more efficiently implemented with secure device than previous eCK secure protocols in the standard model, where the secure device might be normally used to store the long-term private key and implement algorithms of protocol which require to be resilience of state leakage.

•Jan 1, 2013•0 citations

Analysis of Two Provably Secure Authenticated Key Exchange Protocols in the eCK Model

Xuexian Hu

The extended Canetti-Krawczyk(eCK) model proposed by LaMacchia et al.is currently regarded as the strongest security model for authenticated key exchange(AKE) protocols.In the eCK model,the adversary can make queries on the test session,and reveal both ephemeral private keys,both long-term keys,or one of each from the two different parties.In this paper,we analyze two AKE protocols designed in the eCK model based on the definition of eCK model.We propose ephemeral keys compromised attacks and long-term keys compromised attacks on one of them,and also propose ephemeral keys compromised attacks on the other one.The results of analysis show that both of them are insecure in the eCK model.

Journal of Wuhan University•Jan 1, 2010•0 citations

Key establishment : proofs and refutations

Kim‐Kwang Raymond Choo

We study the problem of secure key establishment. We critically examine the security models of Bellare and Rogaway (1993) and Canetti and Krawczyk (2001) in the computational complexity approach, as these models are central in the understanding of the provable security paradigm. We show that the partnership definition used in the three-party key distribution (3PKD) protocol of Bellare and Rogaway (1995) is flawed, which invalidates the proof for the 3PKD protocol. We present an improved protocol with a new proof of security. We identify several variants of the key sharing requirement (i.e., two entities who have completed matching sessions, partners, are required to accept the same session key). We then present a brief discussion about the key sharing requirement. We identify several variants of the Bellare and Rogaway (1993) model. We present a comparative study of the relative strengths of security notions between the several variants of the Bellare-Rogaway model and the Canetti-Krawczyk model. In our comparative study, we reveal a drawback in the Bellare, Pointcheval, and Rogaway (2000) model with the protocol of Abdalla and Pointcheval (2005) as a case study. We prove a revised protocol of Boyd (1996) secure in the Bellare-Rogaway model. We then extend the model in order to allow more realistic adversary capabilities by incorporating the notion of resetting the long-term compromised key of some entity. This allows us to detect a known weakness of the protocol that cannot be captured in the original model. We also present an alternative protocol that is efficient in both messages and rounds. We prove the protocol secure in the extended model. We point out previously unknown flaws in several published protocols and a message authenticator of Bellare, Canetti, and Krawczyk (1998) by refuting claimed proofs of security. We also point out corresponding flaws in their existing proofs. We propose fixes to these protocols and their proofs. In some cases, we present new protocols with full proofs of security. We examine the role of session key construction in key establishment protocols, and demonstrate that a small change to the way that session keys are constructed can have significant benefits. Protocols that were proven secure in a restricted Bellare-Rogaway model can then be proven secure in the full model. We present a brief discussion on ways to construct session keys in key establishment protocols and also prove the protocol of Chen and Kudla (2003) secure in a less restrictive Bellare-Rogaway model. To complement the computational complexity approach, we provide a formal specification and machine analysis of the Bellare-Pointcheval-Rogaway model using an automated model checker, Simple Homomorphism Verification Tool (SHVT). We demonstrate that structural flaws in protocols can be revealed using our framework. We reveal previously unknown flaws in the unpublished preproceedings version of the protocol due to Jakobsson and Pointcheval (2001) and several published protocols with only heuristic security arguments. We conclude this thesis with a listing of some open problems that were encountered in the study.

•Jan 1, 2006•17 citations

Formal Security Definition and Efficient Construction for Roaming with a Privacy-Preserving Extension

Duncan S. Wong, Guomin Yang, Xiaotie Deng

Abstract: In a secure roaming scenario, a user U travels to a foreign network and communicates with a foreign server V securely so that no one other than U and V can obtain the messages exchanged between them. U may also want to travel anonymously so that no one including V can find out its identity or trace its whereabouts except its home server H. There have been many key establishment protocols proposed for secure roaming. A typical application of these protocols is the mobile roaming service which may be deployed to interconnected WLAN and 3G networks. Despite the importance of these protocols, most of the protocols are analyzed heuristically. They are lack of formal security treatment. In this paper, we propose a formal key exchange definition and formalize secure roaming under the Canetti-Krawczyk (CK) model. We also propose a formal model for capturing the notions of user anonymity and untraceability. By using the modular approach supported by the CK-model, we construct an efficient key exchange protocol for roaming and then extend it to support user anonymity and untraceability. The protocols are efficient and each of them requires only four message flows among the three parties U, H and V. For building our protocols, we construct a one-pass counter based MT-authenticator and show its security under the assumption of a conventional MAC secure against chosen message attack.

•Jan 1, 2007•20 citations

On the Design of Key Exchange Protocol and its Variants

Susmita Mandal

With the advancement in Internet-based technologies, network applications are no longer just limited to one-to-one communication; instead, it has become a publicly accessible resource. Regardless of this growth, such applications bring specific challenges concerning authentication, integrity, and privacy. Cryptography stands as an ideal solution to overcome these issues through an interactive method of secure communication called Key Exchange. Key exchange protocols allow two or more entities to agree upon a shared secret transmitted over a public channel without revealing any information to an eavesdropper. This thesis contributes to the design and analysis of the variants of key exchange protocols along with their applications. As per the security requirements, the proposed schemes are either designed in an interactive model or a non-interactive model. Each scheme undergoes a series of formal and informal security analysis. The formal analysis provides simulation result using cryptographic models. Whereas, an informal analysis showcases the theoretical proves on known attacks where an adversary controls the network. The performance analysis maps the protocol’s efficiency based on the computation cost and communication size. The first contribution introduces an interactive two-party authenticated key exchange protocol. We begin by investigating the security flaws in an existing system such as, lack of user anonymity, trace attack, clogging attack, and failure to resist replay attack. Then proposed an authenticated self-certified key exchange protocol that overcomes the addressed issues. Also, it eliminates the requirements of a trusted certificate authority to authorize the entities. The scheme achieves anonymity during session execution, mutual authentication and enables session key agreement.Based on the ideology, an application is designed, forsecure communication between ad-hoc nodes in a mobile ad-hoc network. The second contribution contributes to the design of an Identity-based authenticated three-party key exchange protocol that overcomes the incapability of managing huge peer-to-peer communication and high computation cost faced by two-party authenticated key exchange protocols. The proposed scheme preserves user privacy by enabling the property of anonymity and ensures non-repudiation. Based on the ideology, an application is designed to establish a secure session key between two users with the help of a trusted server for an electronic payment system. The third contribution proposes an interactive pairing-free certificateless authenticated group key agreement scheme suitable for a resource constrained mobile network. The scheme allows any user to join or leave the group dynamically. The key agreement protocol devised in this scheme ensures un-deniability property by incorporating the signcryption, and unsigncryption algorithm. The final contribution presents a non-interactive Identity-based deniable authentication protocol that allows an intended receiver to identify the origin of a given message without being able to prove sender’s identity to a third party.

•Jan 1, 2018•0 citations

Modified Client-Server-Client Authenticated Key Agreement Protocols for Resource-Limited Environments

Zuowen Tan

An authenticated key agreement protocol only allows the intended parties to compute the session key. In this paper, new client-server-client authenticated key agreement protocols in the public key setting have been proposed. The new protocols are proven secure in the formal security model. Compared with the client-server-client authenticated key agreement protocols in the literature, the proposed protocols possess stronger security and higher efficiency.

網際網路技術學刊•Mar 1, 2012•0 citations
A new formal security model for session key exchange protocols in the public key setting is proposed, and several efficient protocols are analyzed in this model. The relationship between this new model and previously proposed models is explored, and several interesting, subtle distinctions between static and adaptive adversaries are explored. We also give a brief account of anonymous users. 1 Introduction In this paper, we investigate formal models of security for authenticated key exchange protocols in a public key setting where the only trusted party is an off-line certification authority. Our work follows up on that of Bellare, Canetti, and Krawczyk [2], which is grounded in the multi-party simulatability tradition (see, e.g., [1]). This approach seems very attractive, because it formulates security in terms of the service a session key protocol should provide to a higher level protocol, rather than getting mired in the details of session key protocols themselves, many of which ar...
The extended Canetti–Krawczyk (eCK) security models, are widely used to provide security arguments for authenticated key exchange protocols that capture leakage of various kinds of secret information like the long-term private key and session-specific secret state. In this paper, we study the open problem on constructing eCK secure AKE protocol without random oracles and NAXOS like trick. A generic construction GC-KKN satisfying those requirements is first given relying on standard cryptographic primitives following the guideline of efficiency. On the second 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. Both proposed schemes can be more efficiently implemented with secure device than previous eCK secure protocols in the standard model, where the secure device might be normally used to store the long-term private key and implement algorithms of protocol which require to be resilience of state leakage.
The extended Canetti-Krawczyk(eCK) model proposed by LaMacchia et al.is currently regarded as the strongest security model for authenticated key exchange(AKE) protocols.In the eCK model,the adversary can make queries on the test session,and reveal both ephemeral private keys,both long-term keys,or one of each from the two different parties.In this paper,we analyze two AKE protocols designed in the eCK model based on the definition of eCK model.We propose ephemeral keys compromised attacks and long-term keys compromised attacks on one of them,and also propose ephemeral keys compromised attacks on the other one.The results of analysis show that both of them are insecure in the eCK model.
We study the problem of secure key establishment. We critically examine the security models of Bellare and Rogaway (1993) and Canetti and Krawczyk (2001) in the computational complexity approach, as these models are central in the understanding of the provable security paradigm. We show that the partnership definition used in the three-party key distribution (3PKD) protocol of Bellare and Rogaway (1995) is flawed, which invalidates the proof for the 3PKD protocol. We present an improved protocol with a new proof of security. We identify several variants of the key sharing requirement (i.e., two entities who have completed matching sessions, partners, are required to accept the same session key). We then present a brief discussion about the key sharing requirement. We identify several variants of the Bellare and Rogaway (1993) model. We present a comparative study of the relative strengths of security notions between the several variants of the Bellare-Rogaway model and the Canetti-Krawczyk model. In our comparative study, we reveal a drawback in the Bellare, Pointcheval, and Rogaway (2000) model with the protocol of Abdalla and Pointcheval (2005) as a case study. We prove a revised protocol of Boyd (1996) secure in the Bellare-Rogaway model. We then extend the model in order to allow more realistic adversary capabilities by incorporating the notion of resetting the long-term compromised key of some entity. This allows us to detect a known weakness of the protocol that cannot be captured in the original model. We also present an alternative protocol that is efficient in both messages and rounds. We prove the protocol secure in the extended model. We point out previously unknown flaws in several published protocols and a message authenticator of Bellare, Canetti, and Krawczyk (1998) by refuting claimed proofs of security. We also point out corresponding flaws in their existing proofs. We propose fixes to these protocols and their proofs. In some cases, we present new protocols with full proofs of security. We examine the role of session key construction in key establishment protocols, and demonstrate that a small change to the way that session keys are constructed can have significant benefits. Protocols that were proven secure in a restricted Bellare-Rogaway model can then be proven secure in the full model. We present a brief discussion on ways to construct session keys in key establishment protocols and also prove the protocol of Chen and Kudla (2003) secure in a less restrictive Bellare-Rogaway model. To complement the computational complexity approach, we provide a formal specification and machine analysis of the Bellare-Pointcheval-Rogaway model using an automated model checker, Simple Homomorphism Verification Tool (SHVT). We demonstrate that structural flaws in protocols can be revealed using our framework. We reveal previously unknown flaws in the unpublished preproceedings version of the protocol due to Jakobsson and Pointcheval (2001) and several published protocols with only heuristic security arguments. We conclude this thesis with a listing of some open problems that were encountered in the study.
Abstract: In a secure roaming scenario, a user U travels to a foreign network and communicates with a foreign server V securely so that no one other than U and V can obtain the messages exchanged between them. U may also want to travel anonymously so that no one including V can find out its identity or trace its whereabouts except its home server H. There have been many key establishment protocols proposed for secure roaming. A typical application of these protocols is the mobile roaming service which may be deployed to interconnected WLAN and 3G networks. Despite the importance of these protocols, most of the protocols are analyzed heuristically. They are lack of formal security treatment. In this paper, we propose a formal key exchange definition and formalize secure roaming under the Canetti-Krawczyk (CK) model. We also propose a formal model for capturing the notions of user anonymity and untraceability. By using the modular approach supported by the CK-model, we construct an efficient key exchange protocol for roaming and then extend it to support user anonymity and untraceability. The protocols are efficient and each of them requires only four message flows among the three parties U, H and V. For building our protocols, we construct a one-pass counter based MT-authenticator and show its security under the assumption of a conventional MAC secure against chosen message attack.
With the advancement in Internet-based technologies, network applications are no longer just limited to one-to-one communication; instead, it has become a publicly accessible resource. Regardless of this growth, such applications bring specific challenges concerning authentication, integrity, and privacy. Cryptography stands as an ideal solution to overcome these issues through an interactive method of secure communication called Key Exchange. Key exchange protocols allow two or more entities to agree upon a shared secret transmitted over a public channel without revealing any information to an eavesdropper. This thesis contributes to the design and analysis of the variants of key exchange protocols along with their applications. As per the security requirements, the proposed schemes are either designed in an interactive model or a non-interactive model. Each scheme undergoes a series of formal and informal security analysis. The formal analysis provides simulation result using cryptographic models. Whereas, an informal analysis showcases the theoretical proves on known attacks where an adversary controls the network. The performance analysis maps the protocol’s efficiency based on the computation cost and communication size. The first contribution introduces an interactive two-party authenticated key exchange protocol. We begin by investigating the security flaws in an existing system such as, lack of user anonymity, trace attack, clogging attack, and failure to resist replay attack. Then proposed an authenticated self-certified key exchange protocol that overcomes the addressed issues. Also, it eliminates the requirements of a trusted certificate authority to authorize the entities. The scheme achieves anonymity during session execution, mutual authentication and enables session key agreement.Based on the ideology, an application is designed, forsecure communication between ad-hoc nodes in a mobile ad-hoc network. The second contribution contributes to the design of an Identity-based authenticated three-party key exchange protocol that overcomes the incapability of managing huge peer-to-peer communication and high computation cost faced by two-party authenticated key exchange protocols. The proposed scheme preserves user privacy by enabling the property of anonymity and ensures non-repudiation. Based on the ideology, an application is designed to establish a secure session key between two users with the help of a trusted server for an electronic payment system. The third contribution proposes an interactive pairing-free certificateless authenticated group key agreement scheme suitable for a resource constrained mobile network. The scheme allows any user to join or leave the group dynamically. The key agreement protocol devised in this scheme ensures un-deniability property by incorporating the signcryption, and unsigncryption algorithm. The final contribution presents a non-interactive Identity-based deniable authentication protocol that allows an intended receiver to identify the origin of a given message without being able to prove sender’s identity to a third party.