Cryptography Reference
In-Depth Information
To see the importance of scheduling the traitors appropriately, suppose
that we use the traitor T
3
first instead of T
4
; then, the sequence of pirate
boxes created until T
3
is entirely revoked would be B
1
= SDBox(1,5,T
3
),B
2
=
SDBox(1,2,T
3
),B
3
= SDBox(8,9,T
3
) and B
4
= SDBox(10,12,T
3
) (refer to fig-
ure
5.8
(b) for the node numbering). Tracing all these boxes would end up with
revoking T
3
and SDDisable(ψ,hB
1
,B
2
,B
3
,B
4
i,σ) = {users(2,5),users(8,10),
users(10,11)}. Note that this subset collection will also be merged by tracing
algorithm, resulting to the partition given in figure
5.8
(c). The pirate then will
be able to create a pirate box SDBox(2,5,T
4
) and so on until T
4
is revoked.
Observe that now T
4
is isolated in its own subtree, and the master pirate box
will be able to make fewer boxes using the keys of T
4
. Thus, it would have
been preferable to start the pirate evolution with traitor T
4
.
This example shows the effect of scheduling in the number of decoders
that the master pirate box can produce. In particular, it shows that the or-
der of using the traitor keys in pirate evolution affects the number of pirate
decoder generations PE
R,SDDisable
P,Leaking
(t). We observe that starting with T
4
pro-
duces more pirate boxes than T
3
because the subtree(users(3,5)) containing
T
4
that is hanging off the path 1 − 5 is shorter than the one corresponding
T
3
. This will be used as our criterion to choose which traitor to start with;
applying it recursively will induce a scheduling of the traitors for the master
pirate box to use that we will formalize below.
We observe that the evolving pirate strategy can be based on a representa-
tion of the Steiner tree by means of paths hanging off each other hierarchically
such that each path stems from an internal node to a traitor placed on a leaf.
Each time we choose a traitor, we actually choose a path to walk on to
construct pirate boxes. We observe two criteria to maximize the number of
pirate decoders. (1) Once a traitor is revoked, we choose a shortest path
hanging off the path containing the recently revoked traitor. (2) If there are
more than one shortest paths, a path with large number of paths hanging
off itself would be preferable. Choosing a traitor amounts to choosing a path
according to this criteria (in a recursive way). In the next paragraphs we
formalize these observations.
We next introduce a special annotation of a Steiner Tree Steiner(T,u,v),
where users(u,v) is one of the subsets in the partition, that will enable us to
choose the best ordering of the traitors.
Definition 5.13. A traitor annotation of a Steiner tree Steiner(T,v
x
,v
y
) is
that the annotation of parent(v) is computed symmetrically regardless of the
choice of v or its sibling.
We say Steiner(T,v
x
,v
y
) is annotated by f. Denote the parent of a node v
by parent(v), the sibling by sibling(v), the height by height(v).
We define the rank of a traitor u given an annotation f as the number of
nodes with 2 children that are annotated by u. We denote the rank of u ∈ T
by rank
f
(u).
