Cryptography Reference
In-Depth Information
Transmission Overhead
As the theorem
2.36
illustrates the transmission overhead depends on the
order of the lower maximal partition of an intersection (S) ∩P
u
. For the set
system Φ
CS
we have the following:
Proposition 2.38. For any subset S ∈ Φ
CS
and an atom u, it holds that
ord((S) ∩P
u
) ≤ log|S|
Proof. In the key-poset of the complete subtree set system, (S) ∩P
u
consists
of the subtrees hanging from the path from u to the node corresponding to the
subset S. Hence, there would be log|S| ideals in the lower-maximal partition
of the intersection (S) ∩P
u
.
The above result combined with Theorem
2.36
gives an upper bound for
the transmission overhead that equals r(log n−1) +1 ≤ r log n. We will show
next a slightly more refined analysis that brings this bound further down.
Theorem 2.39. The transmission overhead of the optimal revocation algo-
rithm given in Figure
2.9
for the factorizable set system Φ
CS
is bounded by
r(log n/r−1) where r is the number of revoked users.
Proof. Observe that the chopped set system Chop(Φ,{j
1
,..., j
r
}) is con-
structed by chopping the filter of the subset {`
i
} encoded by j
i
one by one
starting from i = 1. For each user, the chopping takes an intersection of the
filter of the user with an ideal containing it (recall Theorem
2.35
for more
details on how the revocation algorithm operates). In the light of proposi-
is transmission overhead) as many as elements as its height. It follows that
in each revocation the subset S that contains the revoked user in question
contributes log|S|−1 subsets in the broadcast pattern.
It remains to find the maximum size that a subset in each revocation can
have. Let i = 1,...,r denote the revocation index and m
i
be the maximum
size a subset can have when revoking the i-th user. We have that m
1
= n,
m
2
= n/2, m
3
= m
4
= n/4 and in general m
i
= n/2
l
where 2
l−1
< i ≤ 2
l
.
Using this series, the upper bound on the broadcast pattern would then
be given by the summation
r
X
log m
i
− (r−1)
i=1
where we subtract r−1 since at each revocation we will be picking up an
existing subset and substituting with the ones that result from the intersection
with the subsets in the atomic filter of the user.
Let k be such that 2
k
≤ r < 2
k+1
. We analyze the above summation to
obtain the following upper bound
