Information Technology Reference
In-Depth Information
j
i
,K
E
K
m
Algorithm 1
KHT-CM updates the KHT with
l
)
Create in KHT empty nodes in path from root to l (if not present)
Find node N in KHT at position l
IF i is even //left child {
Find E(K_iˆx,K_lˆy) the left child record of N
IF ((m > y) AND (j >= x))
Overwrite E(K_iˆx,K_lˆy) with E(K_iˆj,K_lˆm)
} else //right child
Same with the right record ...
(
j
i
, where
to n-ary trees. A node
i
of the LKH tree has a corresponding key
K
i
is
the position in the tree of that node
1
, and
is the version number of this key,
initially zero and incremented by one every time the key changes. We assume
that an encrypted key update record, such as
j
3
), where the key at node
3 with version number 1 is encrypted by the key at node 7 with version number
0, contains node and version information in clear for both keys. We also assume
a “lazy” approach to key hashing during additions, where the need for hashing
a key before using it is implied by a gap in version numbers. Moreover, we deal
with partial knowledge of the tree structure by forcing that: when a leaf splits
into two nodes, the previous leaf always occupies the leftmost position; and also,
we only prune leaves and not internal nodes with a single descendent.
When in Fig. 2 “user3” is evicted, the LKH KM changes
7
,K
E
(
K
3
to
3
and
K
K
3
with
7
, i.e., creating update
7
3
), so that “user4” can learn
encrypts
K
K
E
(
K
,K
1
to
1
and encrypts it with the new key
the new key. Then, the KM changes
K
K
3
and the key of the sibling node
2
, i.e., generating updates
3
1
) and
K
K
E
(
K
,K
2
1
), so that all group members but “user3” can learn the new root key
E
(
K
,K
1
. After receiving these encrypted key updates, the KHT-CM detects that there
is a new node 3 because of the update
K
3
), allocates a new node for it,
and stores that record as a key of a right child because 7 is an odd number. Also,
it updates the left and right child holders of the root node with
7
E
(
K
,K
2
1
) and
E
(
K
,K
E
K
3
,K
1
), respectively. Later, “user5” is added to the group, and keys
K
3
and
(
K
1
are hashed to obtain
K
3
and
K
1
, so that the disclosure of keys
K
6
,
K
3
and
K
1
. This is not immediately visible
to the KHT-CM or other group members, since they only implicitly discover
these changes by the key information attached to encrypted messages. Finally,
after the eviction of “user2”, the KHT-CM overwrites updates that refer to
1
to “user5” does not compromise
K
1
or
K
1
K
2
). Note that we
do not keep updates for older keys since an update of a key in LKH triggers an
update of its parent key.
Algorithm 1 describes in more detail the rules we use to update the KHT. In
particular, we only update when the encrypted key will be more recent and the
1
, and creates a new node 2 to capture
4
,K
instead of
K
E
(
K
1
Our node numbering scheme assigns
id
(
root
)=1,and
id
(
n
)=2
∗
id
(
parent
(
n
)), if
n
is a left child, or else
id
(
n
)=2
∗
id
(
parent
(
n
))+1.
