Broadcast Encryption - Encryption for Digital Content - page 54

The following proposition sets the stage for our investigation of fully ex-
clusive set systems as posets.
Proposition 2.16. Any fully-exclusive set system Φ ⊆ 2 [n] forms a finite
atomistic poset ordered by subset inclusion whose ideals are all principal.
Proof. Proposition 2.16 Suppose that Φ = {S j } j∈J . Φ indeed forms a poset
ordered by subset inclusion as the reflexive, antisymmetric and transitive prop-
erties hold for subset inclusion. This poset would be atomistic due to the fact
that Φ is a fully-exclusive set system, i.e. any user, itself, should be a valid
subset in the set system which is equivalent to a corresponding atom. Con-
sider any lower-directed set (an ideal) I of Φ, this ideal would have a single
maximal element. This maximal element, itself, is a subset S in Φ, and the
ideal I would be the smallest ideal that contains S. Hence, any ideal I turns
out to be a principal ideal.
A useful observation we make finally is that in a fully exclusive set system
disjoint ideals are made out of disjoint sets of atoms.
Lemma 2.17. Consider any two disjoint ideals I 1 , I 2 of a fully exclusive set
system Φ. It holds for any S 1 ∈ I 1 and S 2 ∈ I 2 that S 1 ∩S 2 = ∅.
Proof. Lemma 2.17 Suppose the converse; i.e. u ∈ S 1 ∩ S 2 . Because Φ forms
a finite atomistic poset, there exists an atom corresponding to the element
u. That atom is subset of both S 1 and S 2 , thus, it is an element of both
ideals due to the lower property. This contradicts with the definition of being
disjoint.
In general we may use the notation Φ to refer the corresponding poset
(Φ,⊆) interchangeably depending on the context. Similarly, we use the term
“subset” in a set system interchangeably with the term “node” or member
in the poset. When drawing diagrams of posets, we will always draw the
transitive-reduction of the key-poset unless stated otherwise.
2.3.2 Computational Specification of Set Systems
So far we have avoided explaining what is the exact data structure that rep-
resents a set system Φ. While it is possible to think of a representation of Φ
as a collection of sets this is not the most e cient way that an algorithm can
interact with Φ. Representing an explicit data structure that packages Φ will
help in the design as well as the exact complexity analysis of the algorithms
that operate on a set system.
The formal specification of a set system Φ that we lay out below is com-
prised by six basic functions. Henceforth it will be possible to design algo-
rithms that employ these basic functions in black-box fashion and hence they
can be “family-independent.”