Paper 2006/443

Scalable Authenticated Tree Based Group Key Exchange for Ad-Hoc Groups

Yvo Desmedt, Tanja Lange, and Mike Burmester


Task-specific groups are often formed in an ad-hoc manner within big structures, like companies. Take the following typical scenario: A high rank manager decides that a task force group for some project needs to be built. This order is passed down the hierarchy where it finally reaches a manager who calls some employees to form a group. The members should communicate in a secure way and for efficiency reasons symmetric systems are the common choice. To establish joint secret keys for groups, group key exchange (GKE) protocols were developed. If the users are part of e.g. a Public Key Infrastructure (PKI), which is usually the case within a company or a small network, it is possible to achieve authenticated GKE by modifying the protocol and particularly by including signatures. In this paper we recall a GKE due to Burmester and Desmedt which needs only $O(\log n)$ communication and computation complexity per user, rather than $O(n)$ as in the more well-known Burmester-Desmedt protocol, and runs in a constant number of rounds. To achieve authenticated GKE one can apply compilers, however, the existing ones would need $O(n)$ computation and communication thereby mitigating the advantages of the faster protocol. Our contribution is to extend an existing compiler so that it preserves the computation and communication complexity of the non-authenticated protocol. This is particularly important for tree based protocols.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Key DistributionGroup Key ExchangeTree based GKEAd-Hoc GroupsForward SecurityAuthenticationAnonymity
Contact author(s)
tanja @ hyperelliptic org
2006-12-04: received
Short URL
Creative Commons Attribution


      author = {Yvo Desmedt and Tanja Lange and Mike Burmester},
      title = {Scalable Authenticated Tree Based Group Key Exchange for Ad-Hoc Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2006/443},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.