Broadcast Encryption - Encryption for Digital Content - page 95

with the node corresponding to the subset C v = M\{v}. Recall that in the
5-th step of the transformation, we connected the set C v with the filters F v
and F v . Observe now that the path within the body that excludes v and the
path in the extension (the one denoted by {u v∗ ,...,u v∗ }) on the head are
connected and all corresponding subsets exclude u. This results to a unique
path of length 2m in the transformed set system.
The computational specification of the resulting set system XTrans(Φ) in
the KP framework can be described based on the specifications of the basic
set system Φ defined over {1,...,2 m }. Recall that XTrans(Φ) generates 2 m
copies of the set system Φ. An encoding for the set system XTrans(Φ) is a
triple (b,s, j) where j ∈J Φ and s ∈{}∪{0,1} m is the label of the set system
the node corresponding to the encoding j is located in while b ∈{0,1}. In case,
b = 0 then the subset j is located in one of the set systems Φ,Φ 1 ,...,Φ 2 m , while
in case b = 1 then the subset encoded by j ∈J Φ is a copy of a subset in the
filter and it is located on the head of the transformed set system. Note that not
all triples (b,s, j) correspond to a legal subset. The algorithmic specification
of the set system XTrans(Φ) can be defined based on the specification of Φ
by taking the labels of the encodings into account. Since all six algorithms we
require in Definition 2.18 can be constructed without so much effort, we will
not explicitly state the algorithms in here and leave this task as an exercise
for the reader.
An important characteristic of X transformation is that, it is respecting
the key-forest key compression approach as it was defined in Section 2.3.3 .
Given that the underlying set system Φ has a key-forest F Φ , the key forest
of the set system Φ 0 = XTrans(Φ) is the union of the key-forests of the
underlying building set systems while the binary trees on the head can be
appended to corresponding trees of the key-forest defined for the body of the
extended family Φ 0 . This means that it is possible to maintain a small overall
number of trees in the key-forest as the transformation is applied repetitively.
For an example of this the reader is referred to the explicit instantiation of
an X-transformation shown in the end of this section.
Factorizability of the X-Transformation.
We will prove next that the transformation described in definition 2.52 pre-
serves the factorizability of the underlying set system.
Theorem 2.54. Given that the fully exclusive set system Φ defined over
{1,...,2 m } is factorizable and further satisfies the X−property, then it holds
that the set system XTrans(Φ) defined over {1,...,2 2m } is also factorizable.
Proof of Theorem 2.54 : We will prove that XTrans(Φ) is a factorizable set
system by showing that it satisfies the diamond property, i.e. given any two
intersecting subsets we will show that their union is in the new set system.
Our proof will be based on the location of subsets that are intersecting: