Pirate Evolution - Encryption for Digital Content - page 177

of Steiner trees {Steiner(T,S) | S ∈ ψ}. More specifically, it recursively runs a
procedure called makeboxes on each Tree S = Steiner(T,S) which first creates
a pirate box Box by using the unique key assigned to the node root(Tree S ). It
then splits the Tree S into two trees. The splitting is needed because tracing Box
will result in the partition of the subset S. Thus the splitting procedure is based
on the partition of subset S into two equal subsets (recall that in CS , tracing
works by splitting into the two subtrees rooted at the children of root(Tree S )).
The master box MasterBox then runs makeboxes independently on both
of the trees resulting from the partition. Figure 5.3 is the summary of the
evolving pirate strategy. The number of generations that can be produced
equals the number of nodes in the forest of Steiner trees {Steiner(T,S) | S ∈
ψ}.

1. For each S ∈ ψ run makeboxes(Steiner(T,S)) till the `-th box is produced.
makeboxes(Tree)
1. Take any user u placed on a leaf of Tree
2. Retrieve the encoding j for the node of the Complete Subtree that corresponds
to root(Tree).
3. Output CSBox j as the key for S j is available to the pirate through sk u
4.

Let Tree L and Tree R be respectively the left and right subtrees of Tree.

5. run makeboxes(Tree L )

6. run makeboxes(Tree R )

Fig. 5.3. The master box program MasterBox(1 t+log n ,`) parameterized by
ψ,T,sk u for u ∈ T that is produced by the evolving pirate for the complete subtree
method.

In figure 5.4 , we illustrate the generations of pirate boxes for the set of
traitors in the Figure 5.2 . Each key assigned to a node in the forest of the
trees is used to construct a pirate box. The order that the pirate boxes are
released is actually the order of their construction (that is walking from top
to bottom).
Theorem 5.6 is deals with the correctness of the above procedure, i.e. the
next generation should be able to decrypt the message encrypted after tracing
has disabled all previous boxes. This will be shown against the GenDisable
algorithm of figure 4.1 .

Theorem 5.6. Consider the revocation instruction ψ = Revoke(Φ CS ,R)
that encodes the set R where Revoke is the algorithm described in Figure 2.9 .
Let 0 < σ ≤ 1 and B 1 ,B 2 ,···,B v+1 be a sequence of pirate boxes constructed
by the evolving pirate strategy described in Figure 5.3 parameterized by ψ and
T. Suppose ψ 0 = GenDisable(ψ,hB 1 ,...,B v i,σ), then it holds that

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