Fingerprinting Codes - Encryption for Digital Content - page 27

In order to simplify the analysis of this section we will assume that the
exact values p 1 ,...,p ` are known to the adversary. Moreover we will impose
no restriction on how the adversarial coalition decides to output a value {0,1}
as the i-th letter of a descendant codeword.
Observe that the i-th position of the codeword of an innocent user is
determined by a p-biased coin. For this case, we can determine the following
useful expectation relating to the random variable C p (X) (where β ∈ R + to
be determined below and X is a p-biased 0/1 random variable). Suppose that
the coalition digit is y ∈{0,1}; we have:

E[e β·(2y−1)·C p (X) |y] = E[e β(2y−1)(Xq−(1−X)/q) |y] ≤ e β 2

The above is justified as follows: first observe that e u ≤ 1+u+u 2 provided tha t
u < 1.7. We have that for any x ∈{0,1}, it holds that β·C p (x) ≤ βq ≤ β/

√

t

and thus by constraining β to satisfy
β < 1.7· √ t (1.23)

for the case y ∈ {0,1} we can apply the bound on the exponential and
lemma 1.23 to obtain

E[e β(2y−1)C p (X) |y] ≤ 1±βE[C p (X) | y] + β 2 E[C p (X) 2 | y] = 1 + β 2 ≤ e β 2

We next observe that the score accumulated by an innocent user will be equal

to S = P i=1 (2y i −1)C p i (X i ) where y i ∈{0,1}. Based on the above we have
the following bound on the expectation for any strategy of the adversary:

E[e β·S ] ≤ e β 2 ·`

We are interested in obtaining an upper bound on the probability that S ≥ Z,
i.e., the event that an innocent user is accused. We have the following:

Prob[S ≥ Z] = Prob[e βS ≥ e βZ ] ≤ e β 2 `−βZ

To bound the above by , it su ces to choose Z,` that satisfy

β − log( 1 )

` ≤ Z (1.24)

β 2

By combining the upper bound on `, equation ( 1.24 ) with the lower bound
on `, equation ( 1.22 ) we obtain the bound on Z,
Z ≥ (1−3·wβ) −1 3· β

log( 1

α + 1 )

(1.25)

β

which requires the upper bound on β as follows:

β < 1
3w

(1.26)