Cryptography Reference
In-Depth Information
The lower-maximal partition of a lower set is uniquely determined as we
show next.
Theorem 2.13. Any lower set A of poset (Φ,≤) has a unique lower-maximal
partition.
Proof. Theorem
2.13
Suppose that A has two different lower-maximal parti-
tions, i.e. hM
1
,...,M
k
i = hM
0
1
,...,M
0
k
0
i are satisfying the conditions listed in
both the largest integers that satisfy the first three conditions, thus the order
of A is unique.
Suppose now that there is a set M
0
j
that is not equal to any of M
1
,...,M
k
.
Without loss of generality let us consider j = 1. Consider the sets L
i
= M
i
∩M
0
1
and D
i
= M
0
1
\M
i
. If there is some i for which it holds that both L
i
,D
i
are
non empty then we derive a contradiction as we could form a lower-maximal
partition longer than k. Indeed, say this holds for i = 1, then the collection
L
1
,D
1
,M
0
2
\ L
1
,...,M
0
k
\ L
1
satisfies the properties (1-3) of a lower-maximal
partition and has k + 1 subsets.
It follows that for all i, either there is no intersection between M
i
and M
0
1
or M
0
1
is a strict subset of M
i
. Suppose that there is an i for which M
0
1
is a
strict subset of M
i
. This means that there is some atom a ∈ M
i
for which it
holds that it is not in M
0
1
. Indeed, for the sake of contradiction, suppose that
all atoms of M
i
are in M
0
1
. Then if x ∈M
i
, by the fact that M
i
is lower, we can
build a chain connecting x to an atom of M
i
, which is also an atom of M
0
1
and
by the fact that M
0
1
is maximal with respect to A we have that x ∈ M
0
1
, i.e.,
M
0
1
= M
i
, a contradiction to the fact that the former is a strict subset. We
derive from this that there is some other set M
0
j
that includes those atoms of
M
i
that are excluded from M
0
1
. Then, it follows that M
0
j
∩M
i
is a strict non-
empty subset of M
i
and we can apply the same reasoning as before to derive
a longer lower-maximal partition. This is a contradiction and as a result it
cannot be that there is some i for which M
0
1
is a strict subset of M
i
. It follows
that for all i, M
0
1
has no intersection with M
i
which is also a contradiction
as some overlap is guarranteed by the fact that M
0
1
is a non-empty lower set
that must contain at least one atom of A. This contradiction is against our
initial assumption that there is a set among M
0
1
,...M
0
k
that is not equal to
any of M
1
,...,M
k
. From this we derive the equality of the two lower-maximal
partitions.
In the context of broadcast encryption we will restrict our attention to
finite and atomistic posets. In this domain it is easy to see that all ideals
have a single maximal element and thus are principal. Further observe that
for any ideal I it holds that ord(I) = 1. Indeed, if it happens that we have
a lower maximal partition M
1
,...,M
k
of I with k > 1, for any two elements
a ∈ M
1
,b ∈ M
2
it holds that a ≤ m and b ≤ m where m is the maximal
element of I. Due to the maximality of M
1
,M
2
with respect to I we also obtain
that m ∈ M
1
∩M
2
. But due to the fact that M
2
is lower it also holds that
