Broadcast Encryption - Encryption for Digital Content - page 58

derive a key at the leaf-level. The maximum key-storage on the other hand is
the number of trees in the forest max u∈[n] (|F∩F(u)|) and thus it depends on
the structure of the key-poset and the choice of F.
Note that, if the key-forest of a set system consists of single nodes, i.e. any
node in the key-poset defines a tree of size 1, the key compression procedure
defined above would yield an independent key for each subset, i.e. all subsets
are assigned unique keys randomly and independently from each other (and
in essence no compression would be achieved in this case).
Illustration.
Below we present an illustration of our key-compression strategy. Consider the
set system Φ of figure 2.6 ( a). In this system that applies to 4 users there is a
total of 11 encryption key (one for each subset) and it is possible to transmit to
any subset of users using just two ciphertexts. Following an independent key
assignment as the one suggested in the basic scheme BE basic we will require
from each user the storage of 5 keys. Consider now the forest F given in
figure 2.6 (b). This forest has 5 trees (two of height 2 and 3 of height 0); it is
a degree 3 forest. Using the key assignment of BE F,f c we have that each user
would need to store at most 3 keys.
Fig. 2.6. An illustration of the key-compression strategy.
More specifically, observe that based on the key compression strategy on
the given forest, we will choose at random the labels l {1} ,l {2} ,l {3} ,l {4} ,l {1,2,3,4} .
The remaining labels will be calculated based on a key-extender function
f 3 . User 2, for example, will receive the following data as her key material
l {2} ,l {1,2} = f 3 (l {1} ),l {1,2,3,4} . It is easy to see that user 2 based on her in-
formation can recover all necessary keys. For example the key of the subset
{1,2,3} is calculated as k {1,2,3} = f 3 (f 3 (l {1,2} )).
We will next prove the key-indistinguishability property (see Definition 2.6 )
of the key compression technique as given above in Definition 2.21 .
Theorem 2.22. The broadcast encryption BE F,f c satisfies the key indistin-
guishability property with distinguishing probability h F · ε where F is a key