We would like to present the ideas on which Wallner's scheme
is based, and then describe it and provide a reference to it.
The first idea is to assign a manager M to maintain the group key and assume all the re-keying responsibilities. As we previously mentioned, to achieve user revocation, M will need to change the group key K to a new key K' upon deletion of a user u. After this change, M must to communicate K' somehow to the remaining group members. If M sends them K' encrypted with K, u will "understand" the message because it has K, and hence will get K'. Thus we need some secret channel of communication between M and every individual user that would not be known to other users. This way, after a deletion, K' can be communicated to every legitimate user using the secret channel. To achieve this, M can share with every user ui a secret key Ki in addition to K. Thus, in its setup package, ui will receive the group key K and another key Ki. Now when a user is deleted, M can communicate the new group key K' encrypted for each legitimate ui with its individual key Ki. Since the deleted user knows only K and its own individual key, it won't "understand" anything from the re-keying messages. Here's the picture of this idea:
Here we have 8 users, u0
through u7. When we delete u7,
M changes K to K'
and communicates K' to each legitimate user ui
(i.e., with 0 £
6, in this case) encrypted with this user's private key Ki.
(Note that every message is broadcasted to the whole group. Only users who have
the appropriate keys for each message will be able to decrypt it.)
This approach indeed achieves our goal of user revocation, since u7 only knows K7 and K. As you can see, for n users, one deletion costs n - 1 transmissions. And this is a very large re-keying overhead. The problem here is that we are communicating K' to only one user per transmitted message. To improve on the overhead, we need to be able to deal with more than one user per message. Hence the next idea:
Keep everything the same as above and divide the group into two subgroups A and B. Let M share with each subgroup an additional key, say KA with subgroup A, and KB with subgroup B, as follows:
Note that this is just a virtual tree to show you who knows
(stores) what keys. The machines here are only the leaves (the users) and the
root (the manager). In this scenario, if 0 £
3, ui knows (stores) Ki,
KA, and K;
if 4 £
7, ui stores Ki,
KB, and K.
In other words, every user (leaf) stores all the keys on the path from itself to
the root. As we shall see, this will cut on the re-keying overhead. The
immediate advantage here is that if M wants to
delete a user in subgroup A or B,
it can deal with all the members in the other subgroup in one single message,
encrypted with this subgroup's key. For example, if M
wants to delete u7 (in subgroup B),
it can deal with the whole subgroup A in one single
All it needs to do is transmit the new group key K' encrypted with KA, i.e., EKA(K'), and it will be sure that each of u0, u1, u2 and u3 (the whole group A) is all set [*]. And of course, nothing will be comprehensible to u7 since it does not know KA.
Note that in this approach, it is not enough anymore to change only the group key K upon deletion of u7 (or any other user, but we're using u7 for the sake of this example). A rule of thumb in user revocation schemes is the following: upon departure of a user ui, the keys that need to be changed are all the keys that ui used to share with other users [**]. When we deleted u7 in the previous idea (above), it was enough to change the group key K because this was the only piece of information that u7 shared with other users. But in this idea here, u7 not only shares K with other users, but also KB. Thus, if we do not change KB upon deletion of u7, any future re-keying messages using KB (similar to [*] above) will be comprehensible to u7. Hence, KB needs to be changed to KB' and communicated to u4, u5 and u6.encryped with K4, K5 and K6, respectively. And then, K' can be communicated to the whole subgroup B encrypted with KB'. Note that since u7 does not know any of its sibling leaves' keys (with which we have encrypted KB'), it can in no way get KB' . Recall that u7 does not know KA either. Hence, u7 can in no way get K', since we have encrypted it with KB' and KA. Also note that K7 does not need to be changed because u7 does not share it with other users.
Here's the picture of the messages sent upon deletion of u7:
Notice that the keys that have been changed (KB and K) are the keys on the path from the deleted node (u7) to the root.
Keep in mind that all the messages are broadcasted to the whole group. But we drew them only on the tree links on which they are relevant. Also recall that this is a virtual tree just to show you who has which keys, and that the machines are only the leaves (users) and the root (manager).
Note that the leaf keys are never changed. No deletion will ever cause the manager to change a leaf key. Why? Well, who knows a leaf key? A leaf key is shared only by the user at this leaf and the manager, and is not known by any other user. The changing/non-changing of a leaf's key is only relevant when the user at this leaf is deleted. When the user at this leaf is deleted, we need to change the keys that it shares with other users (see [**]) and hence not the key at this leaf.
Also note that M stores all the keys in the tree.
The re-keying overhead is indeed reduced to n/2 + 1 messages per deletion, where n is the number of users.
What Wallner's scheme does is reducing the re-keying overhead to 2log n - 1 messages per deletion, where n is the number of users. It uses exactly the last idea we have just discussed. What Wallner does is taking this idea to the extreme, optimizing it by using a full binary tree. The users are the leaves of this binary tree and the manager is the root. Everything we discussed in the previous idea still holds. Every user (leaf) stores all the keys on the path from itself to the root, that is, log n + 1 keys. M stores all the keys as we said, that is, 2n keys. Upon deletion of a user, the exact same mechanism we used above is applied, but generalized. In other words, when a leaf is deleted, all the keys on the path from this leaf to the root are changed, and the messages sent are as follows:
For the parent node of the deleted
Encrypt its new key with the key of its other child (i.e. the remaining child), if any.
[Cost: 1 message]
For any other node on the path to
(Note that such a node has one child that is on the path from itself to the deleted leaf, and one child that is not.)
Encrypt its new key:
1) with the new key of the child on the path to the deleted leaf.
2) with the key of the other child.
[Cost: 2(log n -1) messages = 2log n - 2 messages]
[Total cost: 2log n - 2 + 1 messages = 2log n -1 messages]
This might sound complicated, but actually it is not. This is
exactly a generalization for a binary tree of what we did above. Compare this to
the messages drawn on the tree above, and you'll
see that this is exactly what we did.
Here too, every message is broadcasted to the whole group. Only users who have the appropriate keys for each message will be able to decrypt it..
This should be enough to fully understand Wallner's scheme. However if you feel that you need more on it, check out Issues in Multicast Security.