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

Fully Robust Tree-Diffie-Hellman Group Key Exchange (Full Version)

Timo Brecher, Emmanuel Bresson, Mark Manulis

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

We extend the well-known Tree-Diffie-Hellman technique used for the design of group key exchange (GKE) protocols with robustness, i.e. with resistance to faults resulting from possible system crashes, network failures, and misbehavior of the protocol participants. We propose a fully robust GKE protocol using the novel tree replication technique: our basic protocol version ensures security against outsider adversaries whereas its extension addresses optional insider security. Both protocols are proven secure assuming stronger adversaries gaining access to the internal states of participants. Our security model for robust GKE protocols can be seen as a step towards unification of some earlier security models in this area.

Related papers

Design and analysis of group key exchange protocols

M. Choudary Gorantla

A group key exchange (GKE) protocol allows a set of parties to agree upon a common secret session key over a public network. In this thesis, we focus on designing efficient GKE protocols using public key techniques and appropriately revising security models for GKE protocols. For the purpose of modelling and analysing the security of GKE protocols we apply the widely accepted computational complexity approach. The contributions of the thesis to the area of GKE protocols are manifold. We propose the first GKE protocol that requires only one round of communication and is proven secure in the standard model. Our protocol is generically constructed from a key encapsulation mechanism (KEM). We also suggest an efficient KEM from the literature, which satisfies the underlying security notion, to instantiate the generic protocol. We then concentrate on enhancing the security of one-round GKE protocols. A new model of security for forward secure GKE protocols is introduced and a generic one-round GKE protocol with forward security is then presented. The security of this protocol is also proven in the standard model. We also propose an efficient forward secure encryption scheme that can be used to instantiate the generic GKE protocol. Our next contributions are to the security models of GKE protocols. We observe that the analysis of GKE protocols has not been as extensive as that of two-party key exchange protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for GKE protocols. We model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure against KCI attacks. A new proof of security for an existing GKE protocol is given under the revised model assuming random oracles. Subsequently, we treat the security of GKE protocols in the universal composability (UC) framework. We present a new UC ideal functionality for GKE protocols capturing the security attribute of contributiveness. An existing protocol with minor revisions is then shown to realize our functionality in the random oracle model. Finally, we explore the possibility of constructing GKE protocols in the attribute-based setting. We introduce the concept of attribute-based group key exchange (AB-GKE). A security model for AB-GKE and a one-round AB-GKE protocol satisfying our security notion are presented. The protocol is generically constructed from a new cryptographic primitive called encapsulation policy attribute-based KEM (EP-AB-KEM), which we introduce in this thesis. We also present a new EP-AB-KEM with a proof of security assuming generic groups and random oracles. The EP-AB-KEM can be used to instantiate our generic AB-GKE protocol.

Faculty of Science and Technology; Information Security Institute•Jan 1, 2010•1 citation

Provably secure authenticated group Diffie-Hellman key exchange

Emmanuel Bresson, Olivier Chevassut, David Pointcheval

Authenticated key-exchange protocols allow two participants A and B , communicating over a public network and each holding an authentication means to exchange a shared secret value. Methods designed to deal with this cryptographic problem ensure A (resp. B ) that no other participants aside from B (resp. A ) can learn any information about the agreed value and often also ensure A and B that their respective partner has actually computed this value. A natural extension to this cryptographic method is to consider a pool of participants exchanging a shared secret value and to provide a formal treatment for it. Starting from the famous two-party Diffie--Hellman (DH) key-exchange protocol and from its authenticated variants, security experts have extended it to the multiparty setting for over a decade and, in the past few years, completed a formal analysis in the framework of modern cryptography. The present paper synthesizes this body of work on the provably-secure authenticated group DH key exchange.

ACM Transactions on Information and System Security•Jul 1, 2007•87 citations

Securing group key exchange against strong corruptions and key registration attacks

Emmanuel Bresson, Mark Manulis

In Group Key Exchange (GKE) protocols, users usually extract the group key using some auxiliary (ephemeral) secret information generated during the execution. Strong corruptions are attacks by which an adversary can reveal these ephemeral secrets, in addition to the possibly used long-lived keys. Undoubtedly, security impact of strong corruptions is serious, and thus specifying appropriate security requirements and designing secure GKE protocols appears an interesting yet challenging task – the aim of our article. We start by investigating the current setting of strong corruptions and derive some refinements like opening attacks that allow to reveal ephemeral secrets of users without their long-lived keys. This allows to consider even stronger attacks against honest, but 'opened' users. Further, we define strong security goals for GKE protocols in the presence of such powerful adversaries and propose a 3-round GKE protocol, named TDH1, which remains immune to their attacks under standard cryptographic assumptions. Our security definitions allow adversaries to register users and specify their long-lived keys, thus, in particular capture attacks of malicious insiders for the appropriate security goals such as Mutual Authentication, key confirmation, contributiveness, key control and key-replication resilience.

International Journal of Applied Cryptography•Jan 1, 2008•13 citations

Scalable group key exchange protocol with provable security

Chengbang Li, Chunxiang Xu

Purpose The purpose of this paper is to introduce a scalable group key exchange (GKE) protocol with provable security, which is used to establish a confidential channel. Design/methodology/approach The protocol in this paper uses line structure, rather than formal ring structure or tree structure, to reduce the amount of calculation and communication. Findings In the protocol, every participant just need send two messages. The security can be proved under the Decisional Diffie‐Hellman (DDH) problem. Originality/value Using the protocol provides an efficient and secure method to allow group users to share a common key.

COMPEL The International Journal for Computation and Mathematics in Electrical and Electronic Engineering•Mar 1, 2013•5 citations

Contributory group key exchange in the presence of malicious participants

Emmanuel Bresson, Mark Manulis

In a group key exchange (GKE) protocol, the resulting group key should be computed by all participants such that none of them can gain any advantage concerning the protocol's output: misbehaving participants might have personal advantage in influencing the value of the group key. In fact, the absence of trust relationship is the main feature of GKE (when compared with group key transport) protocols. The existing notions of security are enlarged by identifying limitations in some previously proposed security models while taking into account different types of corruptions (weak and strong). To illustrate these notions, two efficient and provably secure generic solutions, compilers, are presented.

IET Information Security•Aug 30, 2008•23 citations

Flexible Robust Group Key Agreement

Stanisław Jarecki, Jihye Kim, Gene Tsudik

A robust group key agreement protocol (GKA) allows a set of players to establish a shared secret key, regardless of network/node failures. Current constant-round GKA protocols are either efficient and nonrobust or robust but not efficient; assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, nonrobust group key agreement can be achieved with each player broadcasting just constant-sized messages. We propose a novel 2-round group key agreement protocol, which tolerates up to T node failures, using O(T)-sized messages for any T. We show that the new protocol implies a fully-robust group key agreement with logarithmic-sized messages and expected round complexity close to 2, assuming random node faults. The protocol can be extended to withstand malicious insiders at small constant factor increases in bandwidth and computation. The proposed protocol is secure under the (standard) Decisional Square Diffie-Hellman assumption.

IEEE Transactions on Parallel and Distributed Systems•Jul 1, 2010•41 citations
We extend the well-known Tree-Diffie-Hellman technique used for the design of group key exchange (GKE) protocols with robustness, i.e. with resistance to faults resulting from possible system crashes, network failures, and misbehavior of the protocol participants. We propose a fully robust GKE protocol using the novel tree replication technique: our basic protocol version ensures security against outsider adversaries whereas its extension addresses optional insider security. Both protocols are proven secure assuming stronger adversaries gaining access to the internal states of participants. Our security model for robust GKE protocols can be seen as a step towards unification of some earlier security models in this area.
A group key exchange (GKE) protocol allows a set of parties to agree upon a common secret session key over a public network. In this thesis, we focus on designing efficient GKE protocols using public key techniques and appropriately revising security models for GKE protocols. For the purpose of modelling and analysing the security of GKE protocols we apply the widely accepted computational complexity approach. The contributions of the thesis to the area of GKE protocols are manifold. We propose the first GKE protocol that requires only one round of communication and is proven secure in the standard model. Our protocol is generically constructed from a key encapsulation mechanism (KEM). We also suggest an efficient KEM from the literature, which satisfies the underlying security notion, to instantiate the generic protocol. We then concentrate on enhancing the security of one-round GKE protocols. A new model of security for forward secure GKE protocols is introduced and a generic one-round GKE protocol with forward security is then presented. The security of this protocol is also proven in the standard model. We also propose an efficient forward secure encryption scheme that can be used to instantiate the generic GKE protocol. Our next contributions are to the security models of GKE protocols. We observe that the analysis of GKE protocols has not been as extensive as that of two-party key exchange protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for GKE protocols. We model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure against KCI attacks. A new proof of security for an existing GKE protocol is given under the revised model assuming random oracles. Subsequently, we treat the security of GKE protocols in the universal composability (UC) framework. We present a new UC ideal functionality for GKE protocols capturing the security attribute of contributiveness. An existing protocol with minor revisions is then shown to realize our functionality in the random oracle model. Finally, we explore the possibility of constructing GKE protocols in the attribute-based setting. We introduce the concept of attribute-based group key exchange (AB-GKE). A security model for AB-GKE and a one-round AB-GKE protocol satisfying our security notion are presented. The protocol is generically constructed from a new cryptographic primitive called encapsulation policy attribute-based KEM (EP-AB-KEM), which we introduce in this thesis. We also present a new EP-AB-KEM with a proof of security assuming generic groups and random oracles. The EP-AB-KEM can be used to instantiate our generic AB-GKE protocol.
Authenticated key-exchange protocols allow two participants A and B , communicating over a public network and each holding an authentication means to exchange a shared secret value. Methods designed to deal with this cryptographic problem ensure A (resp. B ) that no other participants aside from B (resp. A ) can learn any information about the agreed value and often also ensure A and B that their respective partner has actually computed this value. A natural extension to this cryptographic method is to consider a pool of participants exchanging a shared secret value and to provide a formal treatment for it. Starting from the famous two-party Diffie--Hellman (DH) key-exchange protocol and from its authenticated variants, security experts have extended it to the multiparty setting for over a decade and, in the past few years, completed a formal analysis in the framework of modern cryptography. The present paper synthesizes this body of work on the provably-secure authenticated group DH key exchange.
In Group Key Exchange (GKE) protocols, users usually extract the group key using some auxiliary (ephemeral) secret information generated during the execution. Strong corruptions are attacks by which an adversary can reveal these ephemeral secrets, in addition to the possibly used long-lived keys. Undoubtedly, security impact of strong corruptions is serious, and thus specifying appropriate security requirements and designing secure GKE protocols appears an interesting yet challenging task – the aim of our article. We start by investigating the current setting of strong corruptions and derive some refinements like opening attacks that allow to reveal ephemeral secrets of users without their long-lived keys. This allows to consider even stronger attacks against honest, but 'opened' users. Further, we define strong security goals for GKE protocols in the presence of such powerful adversaries and propose a 3-round GKE protocol, named TDH1, which remains immune to their attacks under standard cryptographic assumptions. Our security definitions allow adversaries to register users and specify their long-lived keys, thus, in particular capture attacks of malicious insiders for the appropriate security goals such as Mutual Authentication, key confirmation, contributiveness, key control and key-replication resilience.
Purpose The purpose of this paper is to introduce a scalable group key exchange (GKE) protocol with provable security, which is used to establish a confidential channel. Design/methodology/approach The protocol in this paper uses line structure, rather than formal ring structure or tree structure, to reduce the amount of calculation and communication. Findings In the protocol, every participant just need send two messages. The security can be proved under the Decisional Diffie‐Hellman (DDH) problem. Originality/value Using the protocol provides an efficient and secure method to allow group users to share a common key.
In a group key exchange (GKE) protocol, the resulting group key should be computed by all participants such that none of them can gain any advantage concerning the protocol's output: misbehaving participants might have personal advantage in influencing the value of the group key. In fact, the absence of trust relationship is the main feature of GKE (when compared with group key transport) protocols. The existing notions of security are enlarged by identifying limitations in some previously proposed security models while taking into account different types of corruptions (weak and strong). To illustrate these notions, two efficient and provably secure generic solutions, compilers, are presented.
A robust group key agreement protocol (GKA) allows a set of players to establish a shared secret key, regardless of network/node failures. Current constant-round GKA protocols are either efficient and nonrobust or robust but not efficient; assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, nonrobust group key agreement can be achieved with each player broadcasting just constant-sized messages. We propose a novel 2-round group key agreement protocol, which tolerates up to T node failures, using O(T)-sized messages for any T. We show that the new protocol implies a fully-robust group key agreement with logarithmic-sized messages and expected round complexity close to 2, assuming random node faults. The protocol can be extended to withstand malicious insiders at small constant factor increases in bandwidth and computation. The proposed protocol is secure under the (standard) Decisional Square Diffie-Hellman assumption.