Broadcast Encryption - Encryption for Digital Content - page 76

Regarding the coverage of the set family by the trees, consider a subset
encoded as j = (L,R) where R is a string of length at least 1 starting with
b ∈ {0,1}. It is easy to see that this node is located in the binary tree F Lb
and not in any other binary tree.
Finally, the degree of the key-forest is 3 since the key forest consists of
only binary trees.

Since the above key-forest has a degree of three, we can apply the key-
assignment of Definition 2.21 by employing 3-fold key extender f 3 : K 7→ K 3 .
It is easy to see that each of trees in the forest has height less than log n
and hence the computation overhead for key decompression would be bounded
by log n. The key storage for a user u is the number of trees in the forest
|F SD ∩ F(u)| where F(u) refers to the filter of the user u in the key-poset
(see Figure 2.14 for graphical illustration). Recall that user u is given a local
value for the root of each tree in the intersection forest |F SD ∩F(u)|. In order
to find the number of trees in the intersection forest, we need to consider
for each L ∈ {0,1} x ,b ∈ {0,1} the number of trees that are produced when
intersecting the tree F Lb with the nodes of the filter F(u). We will denote this
forest by F Lb ∩F(u). We distinguish the following three cases.
Case 1: if L is not a prefix of u; then F Lb ∩F(u) is empty.
Case 2: if L is a prefix of u, but Lb is not; then the intersection F Lb ∩F(u)
is the tree F Lb itself, meaningly all nodes in that tree is already included in
the filter.
Case 3: If Lb is a prefix of u; then the intersection would have log n−|Lb|
disjoint trees.
The second case happens for log n different choices of L as a prefix of u, (L
can not be equal to u). The third case also happens for log n different choices
of Lb as a prefix of u, with each case resulting log n−|Lb| disjoint trees. Also
the user would need the one key for the unit-size tree F . Based on the above,
the key storage required by a user would be equal to

log X

(log n−i) = 1 + log n· (log n + 1)
2

1 + log n +

i=1

Factorizability of the subset difference set system.

We now prove that the subset difference set system satisfies the factorizability
property and hence it inherits the optimal revocation algorithm of Figure 2.9 .

Proposition 2.42. The set system Φ SD is a factorizable set system.

Proof. Our proof will take advantage of the alternative characterization for
factorizability, the diamond property given in definition 2.32 which is shown
to be equivalent with factorizability (see Theorem 2.33 ).
Consider two subsets encoded by j 1 = (L 1 ,R 1 ) and j 2 = (L 2 ,R 2 ) that are
intersecting. We will have to show that their union is in the set system. Since