Broadcast Encryption - Encryption for Digital Content - page 61

be true for the revocation problem). Specifically we show that PatternCover
is NP-hard with a reduction from the the Set Cover problem. The differ-
ence between the two problems lies on the requirement that the instances of
PatternCover are fully-exclusive (as opposed to arbitrary in the case of the
Set Cover problem) and that they should admit the data structure specifica-
tion of definition 2.18 .
Theorem 2.25. PatternCover is NP-hard.
Proof. We recall that SetCover problem is NP-hard, because it is a special
case of the VertexCover problem which itself is dual to Clique . It should
be noted that VertexCover remains NP-complete even in graphs with node
degree at most 3, see [ 48 ]. We next outline a reduction of VertexCover with
node degree at most 3 to PatternCover thereby establishing its NP-hardness.
Given a graph G = (V,E) with node degree at most 3, Vertex Cover requires
a minimal set of vertices V 0 ⊆ V such that each edge in E is incident to
at least one vertex in V 0 . The decisional version of Vertex Cover is a set of
instances of the form hG(V,E),bi such that G is a graph with node degree at
most 3 and there exists b vertices in V for which any edge in E is incident to
one of these b vertices. From such a graph, we construct a fully-exclusive set
system Φ over the set of edges E. A subset in Φ consists of edges for which
there exists a vertex such that all edges are incident to it. Since nodes in G
have degree at most 3, the maximum possible number of subsets in Φ would
be 4|V|+|E| where each edge itself defines a subset and for any vertex we
have at most 4 additional subsets, i.e. all three edges (if exist) incident to
this vertex constitute a subset and all three combinations of two out of three
edges define another three subsets. It is easy to see that Φ is a fully-exclusive
set system. Further, we can describe an algorithmic specification according to
Definition 2.18 by enumerating the vertices and defining a ≤ relation between
the edges according to the vertex enumeration. Finally, we conclude that an
optimal solution of the VertexCover problem would be interchangeable to an
optimal cover in Φ over the set of users E.
Chopping Filters.
Despite the fact that revocation appears to be more general than PatternCover ,
we show that the two problems are interreducible. A reduction of PatternCover
to Revocation is immediate (by simply considering R = ∅). The other direc-
tion is the interesting one. Let us say a user u should be revoked; observe that
any subset of Φ that contains u should not be in the cover of the set N\{u}.
In other terms, finding a cover in Φ for N\{u} is equivalent to finding a cover
for N 0 = N\{u} in a new family Φ 0 where Φ 0 is constructed by deleting all
supersets of {u} in Φ which amounts to removing from Φ the filter F(u). To
capture this we introduce formally the operation of chopping filters: