Cryptography Reference
In-Depth Information
Fig. 5.12. Maximizing the number of pirate generations for the evolving pirate in
the subset difference method.
the rank of traitor u maximum. We continue in this fashion until all traitors
are placed.
Claim. In the beginning of stage s > 0, there will be exactly 2
s−1
traitors
of rank 0 each one with a traitor path of length h−s.
We prove this by induction; the base case of s = 1, is easy to see: in
stage 1 there is a single traitor of traitor path length h−1 (this is the traitor
prove the induction step. From stage 0 we have a single traitor of length h
that contributes a single traitor with path length h−s. Similarly, from stage 1
we have a single traitor of traitor length h−1 that contributes a single traitor
with path length h−s. From stage 2 we have 2 traitors of length h−2 that
each one contributes a single traitor of path length h−s. In general in stage
m < s we have 2
m−1
traitors that contribute each one a single traitor of path
length h−s. In total we have
s−
X
2
m−1
= 2
s−1
1 +
m=1
which completes the proof of the claim.
Based on the claim, at the end of stage s > 0 there will be a total of
2
s−1
(h−s) new traitors placed. Therefore, the total number of traitors that
will be placed by the end of stage s > 0 is equal to
s
X
2
m−1
(h−m) = 2
s
(h−s + 1)
1 + h +
m=1
We, next, compute the number of decoders that can be produced by the
traitors placed according to the above leaking incident. Recall that corrupting
t users from T ⊂ S with respect to the above leaking incident, the evolving
pirate P annotates the traitors in Steiner tree Steiner(T,S) to apply the
strategy of Figure
5.11
.
Define K = PE
R,SDDisable
P,Leaking
(t) is to be the summation over height(top
f
(u
0
))+
A
u
as stated in Theorem
5.15
where u
0
is defined as the traitor (possibly ⊥)
