Broadcast Encryption - Encryption for Digital Content - page 63

Lemma 2.27. The Revocation problem is polynomial-time interreducible to
the PatternCover problem.
Proof. Lemma 2.27 First consider an instance of the PatternCover problem,
i.e., a fully exclusive set system Φ. We can form an instance of the Revocation
problem by setting R = ∅. It is clear that an optimal solution of this instance
translates immediately to an optimal solution of the original PatternCover
problem.
On the other hand, suppose that we have an instance of the Revocation
problem, i.e., a fully exclusive set system Φ as well as a set of users R for revo-
cation. We define the chopped family Φ 0 = Φ\{S ∈ Φ | S∩R 6= ∅} as in figure
2.7 . The set system Φ 0 is fully exclusive over [n]\R. An optimal solution of the
PatternCover instance Φ 0 would immediately provide an optimal solution of
the original Revocation problem.
In the next section, we will characterize su cient algebraic properties of
the underlying family Φ for solving the revocation problem optimally.
2.4.2 A su cient condition for optimal revocation
In this subsection, we will characterize a simple su cient algebraic property
for the underlying set system Φ to have an e cient optimal revocation solu-
tion.
We will first focus on solving the PatternCover problem. It is easy to
see an optimal solution of PatternCover problem defined for a set system Φ
would consist of maximal subsets in the collection. The set of all maximal
subsets might be overlapping, but if the maximal subsets of Φ are disjoint
then an optimal solution could be easily found for such set systems. Since
each subset has a corresponding principal ideal, we want to formalize the case
when there are disjoint maximal subsets in Φ in terms of ideals. We introduce
the following notion:
Definition 2.28. We say a lower set A of a poset Φ is separable if in the
lower-maximal partition hM 1 ,... M k i of A it holds that M i is ideal for i =
1,...,k.
We show next that in a separable family Φ we can easily define an optimal
solution for PatternCover . Indeed, since all ideals of Φ are principal, finding
ideals is equivalent to finding the maximal subsets in Φ. In Figure 2.8 we
present an optimal solution for a separable collection Φ; the intuition behind
the algorithm is to build one chain for each ideal and use the basic algorithms
of the collection to recover the ideals in the lower-maximal partition of Φ.
Theorem 2.29. Assuming that Φ is separable, the algorithm in Figure 2.8
outputs an optimal solution to PatternCover problem which is of size ord(Φ).