Constant Round Group Key Exchange with Logarithmic Computational Complexity.

Junghyun Nam, Youngsook Lee, Dongho Won

Published Jan 1, 2006• 1 citation

Abstract

Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of parties communicating over a public network can come up with a common secret key. Due to their critical role in building secure multicast channels, a number of GKE protocols have been proposed over the years in a variety of settings. However despite many impressive achievements, it still remains a challenging problem to design a secure GKE protocol which scales very well for large groups. Our observation is that all provably-secure constant-round GKE protocols providing forward secrecy thus far are not fully scalable, but have a computational complexity that scales only linearly in group size. Motivated by this observation, we propose a new GKE protocol that not only offers full scalability in all directions but also attains provable security against active adversaries. Full scalability is achieved by using a complete binary tree structure where users are arranged on both internal and leaf nodes. Security is proved via reduction to the decisional Diffie-Hellman assumption in a well-defined formal model of communication and adversarial capabilities.

Related papers

Scalable Group Key Exchange for Securing Distributed Operating Systems

Junghyun Nam, Minkyu Park, Sangchul Han +2 more

Distributed operating systems are designed to run over a collection of computing nodes that are spatially disseminated and communicate through a computer network. The computing nodes interact collaboratively with each other in order to pursue a common purpose. Protecting group communication between the collaborating nodes against potential attacks is one of the major challenges faced by the designers of distributed operating systems. This challenge can be effectively addressed by a group key exchange (GKE) protocol which allows a group of communicating parties to build a secure multicast channel over an insecure network. In this work, we propose a scalable GKE protocol that achieves both constant round complexity and logarithmic computation complexity. Our GKE protocol achieves its scalability by employing a complete binary tree structure combined with a so-called ”nonce-chained authentication technique”. Besides the scalability, our protocol features provable security against active adversaries in a well-defined communication model.

Journal of information science and engineeringSep 1, 20123 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 EngineeringMar 1, 20134 citations

Scalable Protocols for Authenticated Group Key Exchange.

Jonathan I. Katz, Moti M. Yung

We consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. A number of solutions to this problem have been proposed; however, all prior provably-secure solutions do not scale well and, in particular, require O (n) rounds. Our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only O (1) \full modular exponentiations per user. Toward this goal (and adapting work of Bellare, Canetti, and Krawczyk), we first present an efficient compiler that transforms any ngroup key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and O (1) communication (per user) to the original scheme. We then prove secure | against a passive adversary | a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably-secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.

Jan 1, 20037 citations

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

Timo Brecher, Emmanuel Bresson, Mark Manulis

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.

Jan 1, 20090 citations

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 InstituteJan 1, 20101 citation

One Round Group Key Exchange with Forward Security in the Standard Model.

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

Abstract. Constructingaoneround group key exchange (GKE) protocol that provides forwardsecrecy is an open problem in the literature. In this paper, we investigate whether or not the security of one round GKE protocols can be enhanced with any form of forward secrecy without increasing the number of rounds. We apply the key evolving approach used for forward secure encryption/signature schemes and then model the notion of forward security for the first time for key exchange protocols. This notion is slightly weaker than forward secrecy, considered traditionally for key exchange protocols. We then revise an existing one round GKE protocol to propose a GKE protocol with forward security. In the security proof of the revised protocol we completely avoid reliance on the random oracle assumption that was needed for the proof of the base protocol. Our security proof can be directly applied to the base protocol, making it the most efficient one round GKE protocol secure in the standard model. Our one round GKE protocol is generically constructed from the primitive of forward secure encryption. We also propose a concrete forward secure encryption scheme with constant size ciphertext that can be used to efficiently instantiate our protocol.

Jan 1, 20104 citations