Cryptography Reference
In-Depth Information
underlying key poset that we introduce called chopping filters. This observa-
tion is advantageous since in case we can solve PatternCover optimally we
also have an optimal solution for the revocation problem.
In section 2.4.2 , we introduce the property of factorizability for posets
that characterizes a wide class of key posets for which we can optimally solve
PatternCover . Specifically, we first observe that if a poset satisfies a property
we call separable then PatternCover can be solved optimally. Building on this
simple observation we then define factorizability for posets and we show that
the operation of chopping filters when applied to a factorizable poset results
to a separable poset. This provides the design of an optimal and e cient
revocation algorithm.
2.4.1 Revocation in the key-poset framework: Definitions
Let Φ be a set system over the set [n]. Note that since Φ is a fully-exclusive
set system, there exists a trivial revocation algorithm that searches for a
broadcast pattern that covers [n]\R in a brute-force manner. Moreover, if one
does not wish to spend the time required to brute-force the optimal solution,
there is a way to find a feasible cover that consists simply of all the individual
elements in the set [n]\R; this is due to the fact that Φ is fully exclusive and
thus all singletons should be present in Φ. Clearly these two approaches are
undesirable as either ine cient or grossly wasteful in terms of communication
overhead. In this section we will be interested in finding the shortest pattern
in an e cient way. We will next define the revocation problem formally as
the problem of finding a broadcast pattern for a set of enabled users that is
minimal in size.
Definition 2.23. Revocation Problem (Optimization Version).
Input: A fully-exclusive set system Φ over set [n] and a set of users R
Output: A minimal sized set P = {S j 1 ,...,S j m } of disjoint subsets in Φ, such
that [n] \R = S i=1 S j i .
As we will show the revocation problem is a natural extension to the
problem of PatternCover that we define next. PatternCover is the problem
of finding an optimal cover for a family Φ.
Definition 2.24. PatternCover Problem (Optimization Version).
Input: A fully-exclusive set system Φ over set [n]
Output: A minimal sized set P = {S j 1 ,...,S j m } of disjoint subsets in Φ, such
that [n] = S i=1 S j i .
Hardness of Pattern Cover for General Families.
We next discuss the hardness of PatternCover problem in the general case,
something that shows that without imposing any special structure on the
family there is no way to solve this problem e ciently (and the same would
 
Search WWH ::




Custom Search