Cryptography Reference
In-Depth Information
paths instead of nodes because of the inherent structure of the
SD
method and
the way SDDisable works by merging subsets under the condition shown in
lemma
5.12
. To illustrate how evolution for
SD
method works, let us focus on
start creating pirate boxes. In this figure, the nodes are denoted by natural
numbers in an arbitrary fashion for clarity of presentation (rather than using
the strings that correspond to the nodes).
Fig. 5.8. Two different courses for pirate evolution starting from (a): in (b) T
4
is
used; in (c) T
3
is used.
Suppose that the evolving pirate uses the keys of the traitor T
4
first;
the sequence of pirate boxes created until T
4
is entirely revoked would be
B
1
= SDBox(1,5,T
4
),B
2
= SDBox(2,5,T
4
) and B
3
= SDBox(3,5,T
4
). Due
to lemma
5.11
tracing all these boxes would end up with revoking T
4
and
GenDisable(ψ,hB
1
,B
2
,B
3
i,σ) = {users(1,2),users(2,3)}. Note that in light
of lemma
5.12
the tracing algorithm will merge these two subsets to have the
single subset users(1,3) shown in Figure
5.8
(b). This reveals the possibility
that an evolving pirate against the
SD
method may use the keys of a traitor
as many times as the height of the subset it belongs to without necessarily re-
stricting the same opportunity for other traitors that are scheduled to be used
later. Indeed, we can execute a pirate box construction using the keys of trai-
tor T
3
that would be as many as the height of the tree (the reader can compare
this to the Complete Subtree method where this is not achievable and using
the keys of one traitor strips the opportunity to use some of the keys of other
traitors scheduled later). Proceeding with our example, the master pirate box
MasterBox will now be able to create a pirate box SDBox(1,3,T
3
) (recall
that SDDisable(ψ,hB
1
,B
2
,B
3
i,σ) = {users(1,3)}) followed by another box
SDBox(1,2,T
3
) and so on until T
3
is entirely revoked. Even though we have
the opportunity now to make more boxes per traitor compared to the com-
plete subset method, special care is needed to choose the order with which we
are expending the traitor keys as we will illustrate below. This is in sharp con-
trast to the complete subset method where the scheduling of traitors makes
no difference in terms of the number of pirate box generations that the master
box can spawn.
