International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Yvo Desmedt
Tanja Lange
Mike Burmester
Search ePrint
Search Google
Abstract: 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.
  title={Scalable Authenticated Tree Based Group Key Exchange for Ad-Hoc Groups},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Key Distribution, Group Key Exchange, Tree based GKE, Ad-Hoc Groups, Forward Security, Authentication, Anonymity},
  note={ 13479 received 26 Nov 2006},
  author={Yvo Desmedt and Tanja Lange and Mike Burmester},