Cryptology ePrint Archive: Report 2006/284

Constant Round Group Key Exchange with Logarithmic Computational Complexity

Junghyun Nam, Youngsook Lee, and Dongho Won

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.

Category / Keywords: cryptographic protocols / Group key exchange, scalability, binary tree, provable security, DDH assumption

Date: received 20 Aug 2006

Contact author: jhnam at security re kr

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060822:141358 (All versions of this report)

Discussion forum: Show discussion | Start new discussion