Trace and Revoke Schemes - Encryption for Digital Content - page 165

Upon constructing the pirate codeword as described above, the underlying
identification algorithm returns an index w ∈ [s]. The tracer then splits the
subset S j w , denoting the output by (S j l ,S j r ) = spt(S j w ), returns the broadcast
pattern ψ 0 = {S j 1 ,...,S j w−1 ,S j l ,S j r ,S j w+1 ,...,S j s }. It is easy to observe that
for any u ∈ [n] \ (R ∪ C) it holds that Decrypt(sk u ,c) = M where c ←
Encrypt(ek,M,ψ 0 ) and ψ encodes the set R to be revoked. It further holds
that (C,ψ) SC (C,ψ 0 ) which completes the proof of the theorem.
Picking a Fingerprinting Code.
The choice of the underlying fingerprinting code is flexible. It is even pos-
sible to pick totally different codes in a series of tracing transmissions, i.e.,
the broadcast encryption scheme is not necessarily attached to a single type
of fingerprinting. Moreover, this choice will be reflected in the deciphering
process within the content transmission, hence the choice of fingerprinting
code is independent from the keys stored by the receiver. The code is used to
simply restructure the marking-assignment logically, by reassigning a subset
to a new codeword.
A crucial difference regarding the selection of the fingerprinting code in the
present section when compared to other applications of fingerprinting codes
we have seen earlier is that in the present section we only need codes with a
number of codewords proportional to the number of revoked users and active
traitors as opposed to the whole population. Due to this important charac-
teristic, one can employ fingerprinting codes that allow for arbitrary traitor
collusions such as Boneh-Shaw and Tardos codes presented in Chapter 1 with-
out hurting the e ciency of the above scheme and thus an unbounded number
of traitors can be traced.
Recall that the basic process given in the revocation game will be repeated
recursively until all the traitors are identified or the rebroadcast ceases. It is
worth noting here that our formulation of tracing and revoking pirate re-
broadcasts (as it is the case for trace and revoke schemes in Section 4.1 ) only
suggests that the tracer does progress towards the ultimate revocation of the
traitor coalition. We refer the reader to figure 4.4 for an illustration of how
the above scheme works in combination with the subset-difference method.
4.4 On the effectiveness of Trace and Revoke schemes
Given that Definition 4.3 does not suggest the immediate revocation of the
pirate decoder it is important to consider how eventually the traitors are
revoked in such schemes. Based on the formulation, the tracer will progress
and walk along a chain of the relation changing revocation instructions till it
reaches a maximal point (or the pirate decoder stops working). Given that the
end points of all chains ensure that the traitors are revoked, the formulation
of traceability ensures that the tracer advances to the right direction. As