Broadcast Encryption - Encryption for Digital Content - page 93

over M 0 = {1,...,2 2m }. The construction for the new key-poset will be as
follows:
1. Generate 2 m copies of Φ. We enumerate and denote the copies by
Φ 1 ,Φ 2 ,...,Φ 2 m . We say Φ i is defined over the set M i = {(i−1)2 m +1,..., (i−
1)2 m + 2 m } while Φ will be called as the 'body' of the transformation.
2. For i = 1,...,2 m generate a copy of F Φ i and F Φ i , and denote them by F i
and F i respectively. These collections should be thought as graphs, while their
subset content will be determined in the remaining steps of the transformation.
Constructing the 'feet' of the transformation:
3. Replace the leaf {v} ∈ Φ that corresponds to the user v ∈ M with the
leading subset of the set system Φ v . We will name these parts as the feet of
the new set system.
Constructing the 'head' of the transformation:
4. Remove the edges outgoing from the leading subset of Φ.
5. For any v ∈ M, add edges C v ⊂ F v and C v ⊂ F v . (here F v and F v
represent the roots of the corresponding binary trees)
6. Connect the leading subset of Φ with the leaves of binary tree F v for all
v ∈M and b ∈{1,2}.
Finally :
7. For any v ∈ M and b ∈ {1,2}, add an edge between S and S 0 where
S 0 ∈ F v is the copy of the subset S ∈ F b Φ v . Recall that F v and F b Φ v are isomorphic
to each other.
We denote the output of the X-Transformation by XTrans(Φ).

The above transformation is illustrated in Figure 2.19 . Note that the depic-
tion lacks the representation of step 7 (as the inclusion would make it rather
hard to read - for a complete example the reader is referred to the example
in the end of this section).
We will now prove that the transformation preserves the X−property.

Theorem 2.53. The transformation XTrans described in definition 2.52
preserves the X−property.

Proof of Theorem 2.53 : To begin with, it is easy to observe that the new set
system Φ 0 is defined over the set M 0 = {1,2,...,2 2m } and it is fully-exclusive;
indeed, the new key poset is connected and for each u ∈ M 0 there exists a
corresponding node in the key poset. It also holds that the subsets in the
head of the new key poset are valid subsets in the new set system since each
has an incoming edge from a subset in the feet of the key poset.
We prove next that the new key-poset satisfies the two properties required
in Definition 2.51 . We will use the following argument: if a subset S in the
has incoming edges from s different subsets S 1 ,...,S s , then it holds that

S = S i=1 S i .
1. Recall that there exist two elements S 1 ∈ Φ and S 2 ∈ Φ such that F(S 1 )
and F(S 2 ) are disjoint full binary trees of height m− 1 so that C v is a leaf
of one of these binary trees for any v ∈ M (this is ensured by the second