Information Technology Reference
In-Depth Information
key used to encrypt that key is not older than the current one. All other cases
can be safely ignored because either they break the basic LKH rule of updating
keys bottom up or they do not add new information.
Algorithm 2
Client C obtains the group key from a set of updates S
FOR EACH update E(K_iˆj,K_lˆm) in S using post-order tree traversal {
IF (i in path from C to Root){
Find K_lˆr in local store
IF (r <m){
Find K_iˆn in local store
Obtain candidate K_iˆj by hashing K_iˆn for (j-n) times
Obtain K_lˆm by decrypting E(K_iˆj,K_lˆm) with candidate K_iˆj
IF (K_lˆm is OK) {
Add K_lˆm to local store
}}}}
Algorithm 2 describes the processing done by a client to update his local
state after receiving a set of key updates from the KHT-CM. First, he has to
filter the relevant updates based on his position in the tree and order them so
that updates lower in the tree are processed first. Then, he must discard updates
that do not produce newer keys and try to decrypt the others using the keys
he already holds. However, in certain cases the decryption key that he holds
might be an older version, which needs to be hashed multiple times to obtain
the actual key. In cases where the whole KHT is sent as an update, then it is
guaranteed that the client will obtain all the needed decryption keys just by
hashing. Unfortunately, if only a subset of the KHT is sent, and the KHT-CM
has mis-predicted the working set, it could happen that the client cannot obtain
a correct decryption key just by hashing. Therefore, he always has to validate
the key obtained after decryption before adding it to his local store.
3.3
Pruning the KHT
The process of updating the KHT described in Section 3.2 can only grow the
tree and this is likely to make it too large to be eciently distributed by the
KHT-CM. However, the benefit is that a client could keep as state its original
key, i.e., it is a stateless client, and derive the current session key from the KHT
and this key (see [11]).
To avoid the “growing tree problem” we focus on cases where clients are
updating local state every time they can, like in Algorithm 2, and we introduce
the notion of KHT Working Set (KHT-WS). The KHT-WS is the minimal subset
of the KHT that will allow
all
valid clients to recover the current session key.
This subset is also a tree with the same root as the KHT, since in LKH a change
of a key triggers a change in its parent key. Each leaf of this tree corresponds to
the lower node in the KHT, mapping a key that a relevant client cannot derive
