Cryptography Reference
In-Depth Information
in [n]\R iteratively by modifying the Steiner Tree at each step. We set initially
T = Steiner(R) and repeat the following until the tree is empty.
1. Find a node v in the tree T that has two children v
L
and v
R
with each
one being an ancestor of a single leaf. Denote the leaf that is a descendent
of v
L
by v
i
and the leaf that is a descendent of v
R
by v
j
. If no such node
exists, i.e., there is only one leaf left in the tree, then set the nodes v
i
= v
j
to the leaf, set v to be the root and v
L
= v
R
= v.
2. If v
L
6= v
i
, then add the subset S
j
1
with encoding j
1
= (v
L
,v
i
) to the
broadcast pattern. Likewise, if v
R
6= v
j
, then add the subset S
j
2
with
encoding j
2
= (v
R
,v
j
) to the broadcast pattern.
3. Remove from T all the descendents of v and make v a leaf.
We next show that the the size of the broadcast pattern is at most 2r−1
in the worst case scenario and 1.38r in the average case.
Theorem 2.44. The size of the broadcast pattern output by the above revoca-
tion algorithm is at most 2r− 1 and 1.38r on average where r is the size of
the revoked set R.
Proof. In each step of the above algorithm, the number of leaves is decreasing
by 1. Indeed, v
i
and v
j
are replaced by a single node v, and at most two new
subsets are included in the broadcast pattern. This continues until the last
leaf which yields a single subset. Hence, it is quite easy to observe that the
transmission overhead is bounded by 2(r−1) + 1 = 2r−1.
Note that it is possible that v
i
is left child of v, or v
j
is right child of v.
These cases do not generate a subset to be included in the broadcast pattern.
As a result the transmission overhead can be much smaller than 2r−1.
We will now discuss the average-case for randomly chosen r users to be re-
voked, i.e. the expected number of subsets generated by the above revocation
algorithm. First, we mark the nodes that are set as leaves during the revoca-
tion algorithm. As mentioned before, in each step two leaves are revoked and
an ancestral node is set as a new leaf. Hence, there are r− 1 of those nodes
that are marked and both left and right children of these nodes are included
in the Steiner(R). Denoting the children of the marked leaves as v
1
,...,v
2r−2
,
a possible subset is generated for each of them depending on how the revoked
users are located beneath each node v
i
, for i = 1,...,2r−2.
If v
i
has an outdegree 2 in the Steiner Tree, then no subset will be gen-
erated, otherwise, if the outdegree is 1, a single subset will be generated.
Assuming that there are k
i
revoked users rooted at this node the probability
that a subset is generated is 1/2
k
i
−1
. This comes from the event that the users
are either placed all on the left subtree of the node or on the right subtree of
the node. The expected number of subsets over the values of k
i
is thus given
by the summation:
2r−
X
1
2
k
i
−1
i=1
