Cryptography Reference
In-Depth Information
Suppose, now, we have two subsets S
1
∈XTrans(Φ) and S
2
∈XTrans(Φ)
so that S
1
∩ S
2
6= ∅. If S
1
and S
2
are in the same Φ component of the new
key-poset, it will hold that (S
1
∪S
2
) ∈ XTrans(Φ) due to the factorizability
of the set system Φ. Otherwise, we have three cases:
1. S
1
is located on the head, and S
2
is located in the body. It holds that
S
1
extends C
i
∈ Φ for some i ∈ {1,...,2
m
}. Let S
2
be the subset of Φ that
corresponds to S
2
. If i ∈ S
2
, this means that S
2
contains all atoms of Φ
i
while
on the other hand S
1
contains all other atoms (as it extends C
i
). It follows
that S
1
∪ S
2
= M
0
, hence their union is the top subset of the set system
which belongs to XTrans(Φ). On the other hand, if i ∈ S
2
then it holds that
S
2
⊂ S
1
.
2. S
1
is located on the head, and S
2
is located on the feet. It holds that S
1
is in a binary tree that extends C
i
∈ Φ for some i ∈ {1,...,2
m
}. If S
2
∈ Φ
i
,
then there is a corresponding copy of S
1
within Φ
i
say called S
3
∈ Φ
i
. It is easy
to see that S
2
,S
3
are also intersecting and hence the union of S
3
∪ S
2
exists
within Φ
i
. The union is also in the filter of S
3
, hence it holds that there would
be a corresponding element of the union-subset on the head of new key-poset
XTrans(Φ) that will contain S
1
. On the other hand, if S
2
is located on the
set system Φ
i
0
for some leaf i
0
6= i, then it holds that S
2
⊂ S
1
.
3. S
1
is located in the body, and S
2
is located on the feet: it holds that S
2
is located on the set system Φ
i
for some leaf {i}∈ Φ. Let S
1
be the subset of
Φ that corresponds to S
1
. Since S
1
∩ S
2
6= ∅ then it holds that i ∈ S
1
. This
suggests that S
2
⊂ S
1
.
E
ciency parameters of the transformation.
We now come to the point to discuss the transmission overhead of the set
system constructed by the X-transformation. Provided that the set system
satisfies the X−property, even though the transformation defines a new set
system that squares the size of the receiver population, it increases the trans-
mission overhead by a constant factor only. This can be observed by the
following theorem on bounding the order of a lower-maximal partition for the
intersection of any ideal with the complement of an atomic-filter. At the same
time we show how the key storage and computation overhead are affected by
the transformation.
Theorem 2.55. Suppose that a fully-exclusive set system Φ defined over a set
M = {1,...,2
m
} is factorizable and further satisfies the X−property.
(i) If for any subset S ∈ Φ and an atom u ∈ Φ it holds that ord((S)∩P
u
) ≤
t(m) within the poset Φ for some function t(·), then it holds that ord((S
0
) ∩
P
u
0
) ≤ t(m) + 2 for any S
0
∈XTrans(Φ) and any atom u
0
∈XTrans(Φ).
(ii) If there exists a key-assignment technique for Φ such that the key-
storage for each user is bounded by s(m) for some function s(·) and the com-
putation overhead is bounded by c(m) for some function c(·), then there is a
key-assignment technique so that the key-storage in XTrans(Φ) is bounded by
2s(m) + m and computation overhead is bounded by max(c(m),m).