Broadcast Encryption - Encryption for Digital Content - page 53

a ∈ M 2 . It follows M 1 ⊆ M 2 a contradiction. It follows that I has as a lower
maximal partition just itself.
It is interesting to note though that ord(A) = 1 is not a su cient condition
to make A an ideal. This is due to the fact that the directed property is not
implied by ord(A) = 1.
In the definition below we define the set of maximal elements of a subset
A of a poset.
Definition 2.14. Given a nonempty subset A of a partially ordered set (Φ,≤)
we say h m 1 ,..., m k i is the set of maximal-elements of A if the following holds:
1. m i ∈ A for i = 1,...,k.
2. For any a ∈ A,i ∈ {1,...,k}, it holds that either a ≤ m i or it is not
possible to compare a with m i .
We will denote the number of maximal-subsets of a lower set A by
maxnum(A) (the maximal-order of A).
We next prove an important property elaborating on the relations between
the maximal elements of a lower set with an order 1 : a maximal element in
such a lower set can not be disjoint from other maximal elements.
Lemma 2.15. Given that h m 1 ,..., m k i is the set of maximal elements of a
lower set A that satisfies ord(A) = 1, for each m i there exists another maximal
element m j that they share a common atom, i.e. there exists an atom a ∈ A
such that a ≤ m i and a ≤ m j hold.
Proof. of Lemma 2.15 : Consider now a maximal element m i and suppose that
m i does not share a common atom with any other maximal element. We will
derive a contradiction.
We denote the set of atoms dominated by m i by A i . Consider the set
D = { b ∈ A |∃a ∈ A i s.t. a ≤ b }.
The set D is lower: suppose x ≤ y with y ∈ D. We will first prove that
y ≤ m i . Suppose the converse is true, y 6≤ m i and recall that atomicity implies
that there exists an atom a with a ≤ y and a 6≤ m i . We know that there exists
a maximal element m j such that y ≤ m j . Hence, we obtain m j ∈ D which is a
contradiction with the fact that m i shares no common element with any other
maximal element. Given now that y ≤ m i , we have by transitivity that also
x ≤ m i . This implies that there is an atom a ∈ A i such that a ≤ x, i.e. x ∈ D.
We next show that the set D is maximal with respect to A. Consider some
y ∈ A with x ≤ y and x ∈ D. Since x ∈ D then there exists an atom a ∈ A i
with a ≤ x and by transitivity we have a ≤ y. This shows that y ∈ D and
thus D is maximal with respect to A.
Now it holds that trivially, A is lower and maximal with respect to itself
and thus by Lemma 2.11 we have that A\D is a lower set and maximal with
respect to set A. Then, the pair hD,A\Di satisfies the properties (1-3) of a
lower maximal partition which contradicts with the fact that ord(A) = 1.