Pirate Evolution - Encryption for Digital Content - page 192

Prob[B k+1 (Encrypt(ek,m,ψ k )) = m] ≥ σ

The second case: Let the box B k+1 be produced as the first box on a
call of makeboxes(Steiner(T,x,y), f). The box then would be of the form
SDBox(x,y,u) for some u ∈ T that is the annotation of the shortest path
hanging of the ⊥-path of the tree Steiner(T,x,y).
The call for makeboxes(Steiner(T,x,y), f) is either a call on a set
users(x,y) that is present in ψ (line 2 of the MasterBox program in Fig-
ure 5.11 ) or it is a call in a stack of recursive calls (lines 9-10 of the
makeboxes procedure in Figure 5.11 ). The first subcase would trivially imply
that users(x,y) ∈ ψ k as no previous calls have changed the set users(x,y) in
the original revocation instruction ψ. For the second subcase, the Lemma 5.14
ensures that the set users(x,y) is formed due to the parent invocation of
makeboxes; hence again we obtain users(x,y) ∈ ψ k . In both of the cases it
holds:

Prob[B k+1 (Encrypt(ek,m,ψ k )) = m] ≥ σ

This completes the induction proof.
We next study classes of leaking incidents and the number of pirate gen-
erations they allow. For the polynomial time evolving pirate P described in
Figure 5.11 , the value of PE R,SDDisable

P,Leaking (t) follows from theorem 5.15 . We next
give a lower bound on this quantity by suitably constructing a class of leaking
incidents in the following theorem.

Theorem 5.16. Let n ∈ N be the number of receivers. For a given R, there
exists a leaking incident Leaking corrupting t users in a single subset S ∈
Revoke(Φ SD ,R) where we assume for simplicity that S is a complete subset,
and thus log|S| is an integer, that enables an evolving pirate with respect to
Leaking so that K = PE R,SDDisable
P,Leaking

(t) satisfies:

t log|S|+ 1,

t ≤ log|S|+ 1

K =

|S| |S|

2 s−2 ) − log|S|−2, 2 s+1 ) + 2 s+1 log(

t log(

n o

,0 < s < log|S|

2 s log( |S|

2 s−1 ) + 1,...,2 s+1 log( |S|

t ∈

2 s )

Proof of Theorem 5.16 :
Consider the following leaking incident Leaking: the first traitor is placed
in an arbitrary leaf; its initial rank is 0; then, h stages follow (easing the
notation we will use h in place of log|S|): in stage s (where s = 0,...,h−1),
a number of new traitors will be placed as follows: for each already placed
traitor u that has rank 0 and path length h−s we will add h−s new traitors
in the disjoint subtrees that are hanging off the u-path. Observe this makes