Information Technology Reference
In-Depth Information
Key History Tree: E
cient Group Key
Management with Off-Line Members
Antonio Lain and Viacheslav Borisov
HP Labs, Bristol, UK
Abstract.
We present a new approach to deal with off-line members
that are part of a secure dynamic group, where all the group members
share a secret key, and this key is continuously changed to match cur-
rent membership. Instead of re-negotiating keys when members become
off-line or forcing direct interaction with the key manager, we propose a
safe caching mechanism particularly suited for LKH (Logical Key Hier-
archy) schemes. The basis of our approach is that in many applications,
members that are back on-line just need to know the current key and
not all the intermediate keys negotiated while they were off-line. We have
devised a compact representation for that purpose called KHT (Key His-
tory Tree). A KHT is built using only publicly available information, so it
can be safely replicated over the network, and its operation is transparent
to clients and key managers. We use as an example of the benefits of our
approach a web-based subscription service that anonymizes customer in-
teractions while enforcing membership payments. Extensive simulations
show the advantage of our approach over more conventional schemes.
1
Introduction
Many applications require an ecient and secure mechanism to distribute infor-
mation to a dynamically changing trusted community. Mechanisms that satisfy
this requirement form a secure group that share a secret key. This key is up-
dated when a new member joins the group (backward confidentiality) or leaves
it (forward confidentiality). We will assume in the rest of this paper that there is
a Key Manager (KM) responsible for controlling this shared key, and therefore,
the membership of the group. A trivial implementation of a member eviction will
require a private communication of the KM with each of the remaining members,
so that they can learn the new key. However, in order to make this rekeying op-
eration more scalable, there are well-known techniques that combine a multicast
transport with a Logical Key Hierarchy (LKH) [1], reducing the complexity of
this operation to logarithmic with the size of the group.
Unfortunately, robust key management in these schemes requires that mem-
bers are always on-line to reliably receive key updates on a timely manner. This
can limit the applicability of these schemes when the community is large and
Borisov's research was done under a HP Labs student placement program in Bristol.
Currently, he is at St. Petersburg Technical University.
