Traitor Tracing - Encryption for Digital Content - page 137

2. Provided that σ > 10qε p + 1

|M| , lemma 3.20 implies that the key material
k w j ,j belongs to the traitor coalition.
3. Assuming that the codeword p = hw 1 ,...,w ` i is in the descendant set of
the traitor coalition it holds that Identify(tk,p) ∈ C with probability at
least 1−ε f .

The traceability proof of the statement follows directly from the above
arguments. Regarding the tracing overhead the result follows easily by the
fact that K experiments need to be performed for each of the q symbols along
the whole length of the code `.

A slightly different line of reasoning is required for the Boneh-Naor scheme
since depending on the choice of l ←{1,...,`}, the decoder possibly decrypts
the transmission with different success rates. One simple way to deal with this
problem is to boost the required σ bound for the adversary to be above `−1
`
(it is worth noting that there are alternative - albeit more complex - strategies
for dealing with this matter; the reader is referred to the bibliographic notes
discussion in the end of the chapter).

Theorem 3.22. Consider the multiuser encryption scheme ME BN[ F ] that em-
ploys a symmetric encryption scheme that is ε p -insecure in the sense of Def-
inition 2.5 and an (`,n,q) fingerprinting code F that is (ε f ,t)-identifier.
For any n ∈ N, > 0, ME BN[ F ] is a black box traitor tracing scheme for
t-coalitions with success probability 1 − ε − ε f against resettable σ-pirates
with σ > ` (` − 1 + 10qε p +

1

|M| ). It further holds that trover[ ME BN[ F ] ] =

`q 3 ·ln(`/ε)
(`σ−`+1−1/|M|) 2 ).

O(

Proof. We apply the same reasoning as in the case of Theorem 3.21 . The only
obstacle is to find a lower bound on the success probability of the adversary's
decryption success in queries that are sampled from Transmit 0,j

BN[ F ] (ek,m)
for each j ∈ {1,...,`} (note that such issue did not arise in the case of
Theorem 3.21 as that bound was trivially σ).
Towards computing the lower bound we let A j be the event that j ∈
{1,,...,`} is selected for transmission. It is immediate that the events
{A j } j=1,...,` partition the space of the normal transmissions and each one
has likelihood 1/`. Considering the success probabilities σ j of the adversary
that are conditional to the events A j we have that

P j∈[`] σ j = σ. This im-

1
`

plies that for all j, P j∈[`] σ j > `−1 + 10q p + 1

|M| , which implies that for all

j ∈ [`], σ j > 10q p + 1

|M| .
Now, we can apply the same reasoning as in Theorem 3.21 within each
conditional space to locate a value w j ∈ {0,1,...,q}, for any j = 1,...,`,
such that |p w j −1,j −p w j ,j | ≥ σ j −1/|M|

5q holds with probability at least 1 −ε
where p i,j is the probability that the predicate R B returns true on the response
of the adversary when it receives a query of type (i,j).