Cryptography Reference
In-Depth Information
Lemma 2.31. Let Φ be a factorizable fully exclusive set system defined over
[n].
1. For any S ∈ Φ, it holds that (S) = ∩
u∈[n]\S
P
u
.
2. For any S ∈ Φ, it holds that Φ\F(S) = ∪
u∈S
P
u
.
3. For any S ∈ Φ, (S) is a fully exclusive factorizable set system over S.
4. For any u ∈ [n], and a separable set A ⊆ Φ, the set P
u
∩A is separable.
Proof. Lemma
2.31
1. If a subset S
1
∈ (S), then it holds for any u ∈ [n] \S that S
1
∈ P
u
; hence
S
1
∈ ∩
u∈[n]\S
P
u
. For the opposite direction, if S
2
∈ ∩
u∈[n]\S
P
u
, then it
holds that S
2
∩ ([n] \S) = ∅; hence S
2
⊆ S.
2. If S
1
∈ Φ\ F(S), then it holds that there exists u ∈ S such that u ∈ S
1
;
hence S
1
∈ ∪
u∈S
P
u
. For the opposite direction, if S
2
∈ ∪
u∈S
P
u
, then it
holds that there exists u ∈ S such that u ∈ S
2
; hence S
2
∈ F(S), i.e.
S
2
∈ Φ\F(S).
3. It is easy to observe that (S) is fully-exclusive over the elements of S.
Now consider a subset S
1
∈ (S) and an atom u ∈ S; we will check the set
(S
1
) ∩ P
0
u
, where P
0
u
= (S) \ F(u). First if u 6∈ S
1
then (S
1
) ∩ P
0
u
= (S
1
)
and we are done since (S
1
) is ideal. Now suppose u ∈ S
1
. We will show
that (S
1
) ∩P
0
u
= (S
1
) ∩P
u
where P
u
= Φ\ F(u); this will establish that
(S
1
)∩P
0
u
is separable. If S
2
∈ (S
1
)∩P
0
u
, then it follows that S
2
∈ (S
1
)∩P
u
as P
0
u
⊆ P
u
. For the opposite direction, consider a subset S
3
∈ (S
1
) ∩P
u
,
then it holds that S
3
∈ (S
1
) \F(u) ⊆ P
0
u
; hence S
3
∈ (S
1
) ∩P
0
u
.
4. Given that A is separable, by definition, the lower-maximal partition of
A consists of ideals. We have A = ∪
j=1
I
j
. By Lemma
2.17
u belongs to
only one of these ideals, say {u} ∈ I
s
. Thus, for any j 6= s,1 ≤ j ≤ k,
I
j
∩P
u
= ∅. On the other hand, since Φ is factorizable, the lower maximal
partition of I
s
∩P
u
consists of disjoint ideals and thus P
u
∩A is a separable
set.
Interestingly, the property of being factorizable has an alternative charac-
terization that is of a more local nature:
Definition 2.32. We say a fully-exclusive set system Φ has the diamond prop-
erty if for any S
1
,S
2
∈ Φ such that S
1
∩S
2
6= ∅, then it holds that S
1
∪S
2
∈ Φ.
We prove the following:
Theorem 2.33. A fully-exclusive set system Φ that is an ideal satisfies the
following: Φ is factorizable if and only if Φ has the diamond property.
Proof. Theorem
2.33
Suppose that Φ has the diamond property. We will prove
that Φ is factorizable by showing that for any ideal I and any atom u ∈ I, the
lower set P
u
inside I, i.e. I∩P
u
, is a separable set. Consider the lower-maximal
partition hM
1
,...,M
k
i of I ∩ P
u
and suppose the converse is true, I ∩ P
u
