Information Technology Reference
In-Depth Information
LKH
KHT
K_1^0
Node 1
Version 1
NULL
K_2^0
K_3^0
NULL
K_4^0
K_5^0
K_6^0
K_7^0
- User3
User1
User2
User3
User4
Node 1
Version 2
E(K_2^0,
K_1^1)
K_1^1
E(K_3^1,K_1^1)
E(K_7^0,K_3^1)
E(K_3^1,K_1^1)
E(K_2^0,K_1^1)
E(K_2^0,
K_1^1)
E(K_3^1,
K_1^1)
K_2^0
K_3^1
E(K_7^0,
K_3^1)
Node 3
K_4^0
K_5^0
K_6^0
K_7^0
NULL
E(K_7^0,
K_3^1)
+ User5
User4
User1
User2
User3
K_1^2= Hash(K_1^1)
Node 1
Version 2
K_1^2
K_3^2= Hash(K_3^1)
E(K_2^0,
K_1^1)
E(K_3^1,
K_1^1)
K_2^0
K_3^2
Node 3
K_4^0
K_5^0
K_6^1
K_7^0
NULL
E(K_7^0,
K_3^1)
- User2
User1
User2
User5
User4
Node 1
Version 3
E(K_2^1,
K_1^3)
E(K_3^2,K_1^3)
E(K_4^0,K_2^1)
E(K_3^2,
K_1^3)
K_1^3
E(K_2^1,K_1^3)
E(K_2^1,
K_1^3)
E(K_3^2,
K_1^3)
E(K_4^0,
K_2^1)
K_2^1
K_3^2
Node 3
Node 2
K_4^0
K_5^0
K_6^1
K_7^0
E(K_7^0,
K_3^1)
NULL
E(K_4^0,
K_2^1)
NULL
User1
User2
User5
User4
Fig. 2.
An example of a KHT
the current key regardless of how many updates he missed while off-line. It is
created and maintained by the KHT-CM, which does not have any internal
knowledge of the group structure. The KHT has the same overall structure as
the LKH tree but each node contains, for each of its descendents, the latest
multicast encrypted record of its key that uses the corresponding descendant
key for this encryption. However, since the tree has to be inferred from multicast
information, and information such as the position of a newly added member is
not multicast, it cannot exactly track the original tree. Fortunately, this is not a
serious limitation if certain conventions are followed, as we will explain later on.
Fig. 2 shows an example of how the KHT changes when, as a result of member
evictions and additions, the KHT-CM processes key updates from the LKH-KM.
In this discussion we assume a binary KHT, although it can be easily generalized
