Cryptography Reference
In-Depth Information
Given a Steiner tree ST annotated by f, for any u ∈ T the u-path(ST) is
the path that is made out of all nodes that are annotated by u. Similarly, we
define ⊥-path(ST) and further we call it as the basic path of the tree ST. We
denote u-path(ST) by a vector of nodes, u-path(ST) = hv
c
1
,v
c
2
,···v
c
s
i where
v
c
i
= parent(v
c
i+1
) for 0 < i < s and u = f(v
c
i
); we also denote v
c
1
and v
c
s
in this path by top
f
(u) and bottom
f
(u) respectively.
annotation(Steiner(T,v
x
,v
y
))
Initially annotate each leaf l with its corresponding traitor u ∈ T, i.e. f(l) = u
rank(u) = 0, for each u ∈ T
f(v
y
) =⊥ and rank(⊥) = 0.
Annotate each node from bottom to top by following rule:
<
:
=
;
f(v) sibling(v) 6∈ Tree
⊥ f(v) =⊥∨ f(sibling(v)) =⊥
f(v) rank(f(v)) ≥ rank(f(sibling(v)))
f(sibling(v)) otherwise
f(parent(v)) =
if sibling(v) ∈ Tree then update rank(f(parent(v))) = rank(f(parent(v))) + 1
output f
Fig. 5.9. Computing the traitor annotation for a given Steiner tree.
Note that the rank of a traitor u is actually the number of paths hanging
off the u-path. By a bottom-top approach as described in Figure
5.9
, we make
sure that any path p with length l is annotated by a traitor u that maxi-
mizes the use of length l in such a way that the number of paths hanging
off u-path = p is maximum compared to the case another traitor v is cho-
sen to annotate p. Figure
5.10
is illustrating the annotation of Steiner Tree
Steiner({T
1
,T
2
,T
3
,T
4
},1,5) with respect to the paths dividing the tree. Note
that each path is annotated with the traitor placed on the unique leaf of
that path. According to this annotation the scheduling of traitors would be
T
4
, T
1
, T
2
and T
3
. This can be seen as follows: we choose the shortest path
hanging off the ⊥-path; this gives T
4
as the first traitor to be used; the next
path hanging off the ⊥-path is annotated by T
1
; this gives T
1
as the second
traitor to be used. After finishing T
4
,T
1
, all paths hanging off the ⊥-path are
expended and we move to choose the paths hanging off the previously cho-
sen paths that are the T
4
-path and T
1
-path (in that order). There is no path
hanging off the T
4
-path, so we choose the shortest path hanging off the T
1
-
path; this gives T
2
as the third traitor to be used. Before describing how the
master pirate box works, we will prove following lemma that will help see the
rationale behind the pirate evolution attack for the
SD
method. This lemma
tells us how the partition looks like after choosing a traitor according to the
annotation, and creating pirate boxes until the chosen traitor is entirely re-
voked. It also defines explicitly the number of pirate decoders that the master
box can spawn.
