Cryptography Reference
In-Depth Information
The last property is required to defend against traitors leaking their key
materials which we will discuss more in Chapter
4
.
In general, we will represent a subset-cover scheme by a pair hΦ,Revokei
where Φ = {S
j
}
j∈J
is a fully-exclusive set system defined over [n] that satis-
fies the above properties. Later in this chapter, we will start designing fully-
exclusive set systems that are accompanied with an e
cient revocation algo-
rithm. We found imperative to see the set system as a partial order over a
'subset' relation. This will enable us to define a generic revocation algorithm
for set systems that satisfy the necessary requirements we put forth. Sec-
tion
2.4.2
will elaborate on the actual algorithm after we build the necessary
notions and definitions in the following section.
2.3 The Key-Poset Framework for Broadcast Encryption
In this section we will introduce an algebraic perspective for the study of
broadcast encryption based on exclusive set systems that we call the Key-
Poset (KP) framework. Recall that every key in the construction template for
broadcast encryption in Figure
2.2
can be viewed as a set of users (the users
that own it or can derive it) and thus the set of keys forms a partially ordered
set (or poset) which is a sub-poset of the powerset of {1,...,N}, the set of
all users. This is based on the fact that if a user owns (or can derive) a key
corresponding to a set of users S it should own (or be able to derive) all keys
that dominate S in the key poset.
The rest of the section is structured as follows. In section
2.3.1
we discuss
some basic elements of partial order theory that we need. Next we introduce
a more careful formalization of the representation of exclusive set families in
to compress the information in the secret key-material sk
u
available to each
user u ∈ [n]. We will provide a generic key compression technique over the
key-poset in Section
2.3.3
that satisfies the key indistinguishability property
2.3.1 Viewing Set Systems as Partial Orders
A partial order set (or poset) is a set Φ equipped with a relation ≤ that is
reflexive, antisymmetric and transitive. A nonempty subset A of a partially
ordered set (Φ,≤) is called a directed set if for any two elements a,b ∈ A, there
exists c in A such that a ≤ c and b ≤ c. It is called a lower set if for every
x ∈ A, y ≤ x implies that y is in A. An atom in a poset Φ is an element that
is minimal among all elements. A poset would be called atomistic if x 6≤ y
implies that there is an atom a such that a ≤ x and a 6≤ y.
A nonempty subset I of a partially ordered set (Φ,≤) is called an ideal if
I is lower and directed. The smallest ideal that contains a given element p if
it exists is called a principal ideal and p is said to be a principal element of
