Cryptography Reference
In-Depth Information
Recall that the Theorem
2.36
relates the transmission overhead of a set
system with the upper bound on the lower maximal partition order for the
intersection of an ideal with a complement of an atomic filter. Hence, we obtain
the transmission overhead for the ciphertext revoking r users is bounded by
r(2k+t(d)−1)+1. That would conclude the case when k is a constant. While
on the other hand, if d is a constant then we obtain r(log log n).
Regarding the key storage and the computation overhead, we successively
apply the bounds given in theorem
2.55
to obtain for i = 1,...,k:
s
i
= 2s
i−1
+ 2
i−1
log d
where s
0
= s(d). By applying a telescopic sum over i values we will obtain
s
k
= 2
k
s(d) + k2
k−1
log d = 2
k
s(d) +
k log
2
. That would conclude the case
when k is a constant. In case d is constant we have k = log log n, hence the
key storage is O(log log n· log n).
4
Fig. 2.20. The X-transformation over the set system Φ
4
= AS
Φ
{1,2}
.
We will next give an example of an AS set system and an application
of the transformation technique above. We first start with a set system
Φ
{1,2}
= {{1,2},{1},{2}} that is the power set (without the empty set) of
the set {1,2}. Observe that this basic set system satisfies the X− property
and it is factorizable set system. Hence, the transformation described in de-
finition
2.52
will yield factorizable set systems over exponentially growing
receiver populations that satisfy the statement of the corollary
2.57
. Observe
that the resulting set system AS
Φ
{1,2}
is defined over a receiver population of
size 16. The figure
2.20
illustrates the resulting set system after applying the
transformation twice on the above simple set system.
