Broadcast Encryption - Encryption for Digital Content - page 67

complement of the atomic filter F(` i ) within the set system Φ. Indeed, if a
subset S is an element of Φ 0 , then S ∩{` 1 ,...,` r } = ∅ which implies that
S ∈ P ` i for any 1 ≤ i ≤ r. Similarly, for any subset S of ∩ i=1 P ` i it holds that
S ∈ Φ 0 .
We will now prove by induction on r that ∩ i=1 P ` i is a separable set. This
will show that Chop(Φ,{j 1 , j 2 ,..., j r }) constitutes a separable set system. The
r = 1 case can be proved as follows: given that Φ is factorizable, i.e. itself is
separable, we obtain that the set P ` 1 = Φ∩P ` 1 is separable as a consequence
of Lemma 2.9 and 2.31 (4). Consider now the induction hypothesis that for
any 1 ≤ s < r and ` 1 ,...,` s , it holds that ∩ i=1 P ` i is a separable set. Now,
consider r atoms over Φ.
Using the induction hypothesis, the intersection of the complement of
atomic filters of the first r−1 atoms will be a separable set, i.e., ∩ r−1

i=1 P ` i = A
where A is a separable set. The Lemma 2.31 (4) implies that the intersection
of A with P ` r is separable which concludes the statement of the theorem.

In light of the Theorems 2.29 and 2.34 , the algorithm in Figure 2.9 outputs
an optimal solution for the revocation problem for a factorizable set system
Φ using the chopping filters operation in conjunction to the PatternCover
algorithm for separable families.

Revoke(Φ,R)
1. let R = {` 1 ,...,` r } and j i be the encoding for {` i }

define Φ 0 = Chop(Φ,{j 1 ,..., j r })

2.

output PatternCover(Φ 0 ) 3.

Fig. 2.9. Optimal Solution for the revocation problem in a factorizable set system.

Theorem 2.35. Given that the fully-exclusive set system Φ is factorizable,
the algorithm in Figure 2.9 outputs an optimal solution for the revocation
problem with respect to a set of revoked users R = {` 1 ,` 2 ,...,` r }. The number
of subsets in the solution will be ord(∩ i=1 P ` i ).

Proof. Theorem 2.35 The proof follows from Theorem 2.34 and the correctness
of the PatternCover algorithm given in Figure 2.8 . As shown in Theorem 2.34 ,
Chop(Φ,{j 1 ,..., j r }), where j i is the encoding for the singleton {` i }, will be
set of disjoint principal ideals, thus the optimal solution will consist of those
principal elements. Their number will be as many as the number of ideals in
∩ i=1 P ` i which is equal to ord(∩ i=1 P ` i ).

As shown above, for a given factorizable family Φ and a set of users,
R = {` 1 ,` 2 ,...,` r }, the intersection ∩ i=1 P ` i has a lower-maximal partition
consisting of disjoint ideals. Their number would equal to the transmission
overhead for the ciphertext to be transmitted. We can provide an explicit