Cryptography Reference
In-Depth Information
Definition 2.3. Consider a family of subsets Φ = {S
j
}
j∈J
defined over
[n] where J denotes the set of encodings for the elements in Φ over an al-
phabet Σ with length of at most l(n) for some length function l(·). We say
Φ is (n,r,t)-exclusive if for any subset R ⊆ [n] with |R| ≤ r, we can write
[n] \R = ∪
i=1
S
j
i
where s ≤ t and S
j
i
∈ Φ for 1 ≤ i ≤ s.
Having defined exclusive-set systems, we will now give a construction for
broadcast encryption schemes based on exclusive-set systems. We note that
the recovery of j
1
,..., j
s
given R should be done e
ciently for a system to
be useful. For this reason when one proposes a set system it is imperative
to include a description of how the covering algorithm would work (that is
at the heart of the revocation algorithm). The goal of this algorithm would
be to produce the indices j
i
, i = 1,...,s of the subsets that cover the set of
enabled users [n] \R. A trivial covering algorithm for revocation that works
with any set system would be to search for the pattern in a brute force manner.
Given that in an exclusive set system the target pattern is postulated to exist,
the exhaustive search algorithm is guaranteed to find a solution. Nevertheless
this will not lead to an e
cient implementation for any but entirely trivial
set systems. In the rest of the chapter we will be concerned with the design of
exclusive set systems with e
cient revocation algorithms and in fact we will
present a generic revocation algorithm given any set system that satisfies a
simple algebraic property.
In Figure
2.2
we present a template for a broadcast encryption system
based on exclusive set systems. We assume a family of exclusive set systems
indexed by n as well as an underlying symmetric encryption scheme (
E
,
D
)
that uses as keys elements of K.
The characteristics of the scheme given in figure
2.2
that make it a template
are as follows:
1. The exclusive set system Φ is not explicitly specified but used in a black-
box fashion. It is assumed that an exclusive set system can be found for
any number of users n. To specify this we may use the notation {Φ
n
}
n∈
N
to denote the collection of exclusive set systems produced for each number
of users n, or simply write Φ overloading the set-system notation (in such
case there an implicit reference to the number of users n will be assumed).
2. The exact mechanism that KeyGen uses to sample the keys {k
j
}
j∈J
is
not specified. The only restriction is that each key belongs to the set K.
3. The underlying encryption scheme (
E
,
D
) is not specified but used in a
black box fashion.
Comments on the Template Construction.
For any exclusive set system Φ and an encryption scheme (
E
,
D
) we can instan-
tiate the template of Figure
2.2
by having the KeyGen procedure sample the
keys {k
j
}
j∈J
independently at random from the set of keys for the encryption
scheme (
E
,
D
). We will refer to this scheme as :
BE
basic
. As we will see later
