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).
 
Search WWH ::




Custom Search