Pirate Evolution - Encryption for Digital Content - page 195

s X

K s = h + 1 + h 2 + 2 m−1 · (h−m) 2

m=1

Finally we obtain K s = 2 s (h−s + 1) 2 + 2 s+1 −h− 2 (an easy proof by
induction that is left as an exercise).
We finally argue about the formula for K given in the statement of the
theorem. In the case that t ≤ h + 1, we have easily that K equals (t−1)h +
h + 1 = th + 1 which settles the first case. Now suppose that 2 s (h−s + 1) <
t ≤ 2 s+1 (h−s) for some s ≥ 0. We have that the number of pirate decoders
will be equal to K s plus the number of decoders that can be produced by
the remaining t − 2 s (h − s + 1) traitors. The traitors placed in the s + 1
contribute h − s − 1 decoders therefore we have that the total number of
decoders contributed by them is (t−2 s (h−s+ 1))(h−s−1). So we obtain :

K s + (t−2 s (h−s + 1))(h−s−1) = 2 s+1 (h−s + 2) + t(h−s−1) −h−2

This completes the proof.
The maximum number of generations can be achieved following the leaking
incident of Theorem 5.16 in a configuration of the system when there is no
revoked user; in this case there is a single element in the partition, namely S
containing n users. The corollary below follows easily from theorem 5.16 .

Corollary 5.17. The pirate evolution bound for the SD method satisfies

evo[ SD ,SDDisable] ≥ t log n
for t ≤ log n. It also satisfies that for t ≤ √ n· log n
2

that

evo[ SD ,SDDisable] = Ω(t log n)

5.5 Bibliographic Notes

Pirate evolution, as an attack concept against trace and revoke schemes, was
introduced by the authors in [ 62 ]. The susceptibility of the trace and revoke
schemes of Naor, Naor and Lotspiech from [ 87 ] as it is discussed in Sections 5.3
and 5.4 of this text was also given there. Pirate evolution has practical im-
plications. For example the advanced access content system (AACS) that is
used in Blu-ray disks employs the subset difference method ( SD ) in clusters of
n = 2 23 nodes. It follows that a leaking incident as the one described in Theo-
rem 5.16 with t traitors enables an evolving pirate strategy to generate up to
23·t generations of pirate decoders. This means that key leakage incidents can
be magnified, i.e., 10 traitor keys can result in up to 230 decoders and so forth.
This was a “nightmare” scenario as described by the AACS implementers in
[ 59 ]. The suggested proposal to deal with pirate evolution is to magnify the