Cryptography Reference
In-Depth Information
Similar to the algorithmic specification, the key-forest of the new set sys-
tem can trivially be constructed by retrieving the key-forests of the set systems
Φ
BS
s
for s ∈{1,...,d}
x
with 0 ≤ x ≤ k−1. The union of all these key forests
constitutes the key forest of the new set system LTrans
k
(BS
d
).
Factorizability of the layering transformation.
Provided that the set system Φ
BS
d
is factorizable, the layering transformation
preserves the factorizability property for n = d
k
receivers. Hence, the new set
system is accompanied with an e
cient and optimal revocation algorithm due
to the Theorem
2.35
. We prove this in the next theorem.
Theorem 2.49. Given that the fully exclusive set system Φ
BS
d
defined over
{1,...,d} is factorizable, then the transformation LTrans described in Defi-
set system defined over {1,...,d
k
}.
set system by showing that it satisfies the diamond property, i.e. given any
two intersecting subsets we will show that their union is in the new set system.
Our proof will be based on the location of subsets that are intersecting:
Suppose, now, we have two subsets S
1
∈ LTrans
k
(Φ
BS
d
) and S
2
∈
LTrans
k
(Φ
BS
d
) so that S
1
∩ S
2
6= ∅. If S
1
and S
2
are located in the same
set system Φ
BS
s
for some string s ∈ {1,...,d}
x
with 0 ≤ x ≤ k − 1, then
it will hold that (S
1
∪S
2
) ∈ LTrans
k
(Φ
BS
d
) due to the factorizability of the
set system Φ
BS
s
. Otherwise, given that they are overlapping, it must be the
case that one is covering the other and hence again their union is in the set
system.
E
ciency parameters of the transformation.
We now come to the point to discuss the transmission overhead of a set system
constructed by the layering transformation. Even though the transformation
defines a new set system that increases by an exponential factor of k the
size of the receiver population, it turns out that it increases the transmission
overhead and the key storage by only a multiplicative factor of k. This will be
observed in the following theorem that bounds the order of a lower-maximal
partition for the intersection of any ideal with the complement of an atomic-
filter. In the same theorem we also argue that the storage overhead will only
suffer a multilplicative factor of k independently of the method that is used
to assign the keys.
Theorem 2.50. Suppose that a fully-exclusive set system Φ defined over a set
[d] = {1,...,d} is factorizable.
(i) If for any subset S ∈ Φ and an atom u ∈ Φ it satisfies that ord((S) ∩
P
u
) ≤ t(d) within the poset Φ for some function t(·), then it holds that
