Cryptography Reference
In-Depth Information
(ii) In this case it holds that the leaves corresponds to the indices u and
LbR are on the different half of the subtree rooted at v
L
.
Suppose first that b = 1. If u is not the leftmost leaf in the subtree rooted
at v
L
, the subset S
j
1
with an interval [str2int(s
1
),u−1] (with s
1
= L0
log n−|L|
)
contains all leaves located on the left of the leaf encoded by u. If u + 1
has a prefix of L1 then the subset S
j
2
= {str2int(s
2
),... str2int(LbR)} where
s
2
= L10
log n−|L|−1
, will be enough to cover all remaining atoms in the inter-
section (S)∩P
u
. Otherwise we also define the subset S
j
3
= {u+1, str2int(s
3
)}
where s
3
= L01
log n−|L|−1
. We observe that none of these three subsets are
intersecting and they all belong to the set system.
The case b = 0 is symmetric. If u is not the rightmost leaf in the subtree
rooted at v
L
, the subset S
j
1
= {u + 1,..., str2int(s
1
)} where s
1
= L1
log n−|L|
,
contains all leaves located on the right of the leaf encoded by u. If u−1 has
a prefix of L0 then the subset S
j
2
= {str2int(LbR),... str2int(s
2
)} where s
2
=
L01
log n−|L|−1
, will be enough to cover all remaining atoms in the intersection
(S) ∩ P
u
. Otherwise we also define the subset S
j
3
= {str2int(s
3
),...,u − 1}
where s
3
= L10
log n−|L|−1
. As before it is easy to see that none of these three
subsets are intersecting and that they all belong to the set system.
Applying Theorem
2.36
gives an upper bound on the transmission over-
head for the key chain tree method, which yields an overhead of 2r + 1.
A direct revocation algorithm.
An direct revocation algorithm is also possible as follows. First we determine
the contiguous sets of enabled users. Given R = {`
1
,...,`
r
}, we will get
at most r + 1 contiguous subsets of enabled users. One of them is possibly
starting with the leftmost user and another one is possibly ending with the
rightmost user. It is possible to cover any other consecutive set of users with
at most 2 subsets of the key-chain tree set system. To see this consider a set
of consecutive users S = {u
1
,...,u
t
}, and denote the least common ancestor
of u
1
and u
t
by node v of the binary tree of the set system. If u
1
is leftmost
leaf or u
t
is rightmost leaf of the subtree rooted at v, then it is already the
case that S belongs to the set system. Otherwise, say u
i
is the rightmost leaf
of the left child of the node v for some i; this is guarranteed to exist due to
the choice of v. It holds that u
i+1
will be the leftmost leaf of the right-child
of the node v. Hence, both {u
1
,...,u
i
} and {u
i+1
,...,u
t
} belong to the set
system and they cover the initial subset S. This revocation algorithm yields a
broadcast pattern with size at most 2r.
2.6 Generic Transformations for Key Posets
A generic transformation for key posets is a technique of deriving a new key
poset from an existing one. Such transformations have frequently the capabil-
ity to improve the performance characteristics of the underlying set-systems.
In this section we will see two such transformation techniques.
