Fingerprinting Codes - Encryption for Digital Content - page 26

27
Next observe that P x=0 Z x = 1 independently of the distribution of p and by
applying lemma 1.24 and lemma 1.25 , as well as the fact that |a−b|≤ a + b
for positive a,b we have
P x=0 x

M x ≤ 1−α 2γ · (2(1−t) w −2t w −1) −α·w
≤ e −α(2γ(2(1−t) w −2t w −1)−α·w)

(1.19)

1

where γ =

π−4t 0 . We apply the above inequality 1.19 to the bound of equa-
tion 1.14 to obtain:

−α·`· (2γ · (1−2wt−2t w ) −α·w
|

E[e −αS σ ] ≤ exp )

{z }

ρ

Next we constrict α,t to show that the expression ρ has a positive lower
bound. In particular, under the conditions:

α ≤ 1
6w

(1.20)

1
300w

t ≤ (1.21)

we obtain that 2γ(1 − 2wt− 2t w ) ≥ 1/2 and α·w ≤ 1/6. Utilizing the fact
that γ ≥ 4 we obtain that under the conditions placed on α,t we have that
ρ ≥ 1/3 which implies that:

E[e −αS σ ] ≤ e −α`/3

We are now ready to obtain an upper bound on the probability that the
malicious coalition accumulates a score of at most wZ.

Prob[S σ ≤ wZ] = Prob[e −αS σ ≥ e −αwZ ] ≤ E[e −αS σ ]/e −αwZ ≤ e −α`/3+αwZ

where the penultimate inequality follows from Markov's inequality. Bounding
the probability by we have to select `,Z so that they satisfy
` ≥ 3· log( 1 )
α

+ wZ (1.22)

It follows that if `,Z are selected so that the above lower bound on ` holds we
have that with probability at least 1− the output of the tracing algorithm
will contain at least one member of the traitor coalition.

We next turn our attention to the requirement that the output of the trac-
ing algorithm does not contain any innocent users. This will provide another
condition on `,Z, an upper bound on `. We will take advantage of the fact
that, given that the code C is private, the codeword assigned to any innocent
user can be assumed to be selected after the traitor coalition is formed.