Cryptography Reference
In-Depth Information
such that the u-path(Steiner(T,v,v
0
)) hangs off the u
0
-path. Observe that
u
0
appears in the summation for as many traitors as its rank. We will first
compute K for the choice of t = 2
s
(h−s + 1) for s ∈ {0,1,...,h− 1} (we
denote it by K
s
for the choice of stage s):
Since the number of traitors satisfies t = 2
s
(h − s + 1), we are at the
end of the stage s for s = 0,1,...,h− 1. We make three easy observations:
(i) Other than the traitors that have path of length at least h − s, all the
remaining traitors placed according to above leaking incident have rank 0.
This is because no other traitors are placed below their path (which is shorter
than h−s). Thus, considering the summation of Theorem
5.15
, those traitors
will never appear as u
0
in the summation. (ii) On the other hand, the traitors
with non-zero rank (and their rank is the maximum possible) will appear in
the summation as a u
0
node as many as their rank (which equals to the number
of traitors hanging off the u
0
-path). For such traitors, except the traitor that
placed first, the height(top
f
(u
0
)) equals to the length of the u
0
-path. (ii) Finally,
A
u
= 0 always holds for each traitor u due to the way the traitors are placed
(recall the definition of A
u
given in Lemma
5.14
).
Based on the above we can now compute K
s
:
K
s
=
X
u∈T∩S
X
(height(top
f
(u
0
)) + A
u
) = h + 1 +
|(u
0
)-path|
u∈(T\{v})∩S
where v is the first traitor path and u
0
is a function of u that equals the
traitor such that the u-path hangs off the u
0
-path. We next arrange the above
summation with respect to u
0
, i.e. the below holds due to the relation between
u
0
and u in the above equation:
K
s
= h + 1 +
X
u
0
∈T
rank(u
0
) ·|(u
0
)-path|
Now due to the placement of the traitors |(u
0
)-path| equals to the rank of
u
0
(this is implied by the observations (i) and (ii) above); thus we obtain:
X
|(u
0
)-path|
2
K
s
= h + 1 +
u
0
∈T∧rank(u
0
)6=0
We now arrange the above summation over |u
0
-path| = h,h−1,h−2,...1.
Recall also that if |u
0
-path| < h−s then the rank of u
0
is zero and non-zero
otherwise.
s
X
|{u
0
: u
0
∈ T∧|(u
0
)-path| = h−m}|· (h−m)
2
K
s
= h + 1 +
m=0
Due to the claim we have proved above, there will be a single traitor with
path of length h and 2
m−1
traitors with path of lenght h−m for m > 0. Thus
we obtain:
