Broadcast Encryption - Encryption for Digital Content - page 89

2. Replace the i-th leaf of the set system Φ BS s that corresponds to the user-
index i ∈ [d], for s ∈{1,...,d} x , 0 ≤ x ≤ k−1, with the top subset of the
set system Φ BS d

si .
We denote the output of k-layering by LTrans k (BS d ).
It is very intuitive in the key-poset framework to reflect the above trans-
formation as depicted in the Figure 2.18 .

Fig. 2.18. Graphical depiction of the key-poset of the k-layering of a basic set
system BS for d users.

The computational specification of the new set system LTrans k (Φ BS d )
in the KP framework can be defined based on the specification of the basic
set system BS d . Recall that LTrans k (Φ BS d ) consists of d k −1

d−1 copies of the
set system Φ BS d . The labeling of each copy can be comprehensible in the
construction figure 2.18 by traversing the set systems top-down: the root set
system of the figure is labeled by , the label of an i-th child set system
is constructed by appending i to its parent's label. An encoding for the set
system LTrans k (Φ BS d ) is a pair (s, j) where j ∈ J BS d and s ∈ {1,...,d} x ,
0 ≤ x ≤ k−1, is the label of the set system the subset corresponding to the
encoding (s, j) is located in. The algorithmic specification of the set system
LTrans k (BS d ) can be defined based on the specification of Φ BS d by taking
the labels of the encodings into account: If the labels of two encodings are
comparable, i.e. one is strict prefix of another, then the subset with longer
label contains the other; if the labels are same, then whatever rules within the
basic set system hold would be effective; if the labels are not comparable then
the subsets corresponding to the encodings are disjoint. Since all six algorithms
that we require in Definition 2.18 can be constructed without much effort, we
will not explicitly state the descriptions in here and leave them as an exercise
for the reader.