Fingerprinting Codes - Encryption for Digital Content - page 24

w
x i

X ` Y

E[e −αS σ ] ≤ M x i

(1.13)

x 1 ,...,x ` =0 i=1

From this we obtain the following:

w
x

E[e −αS σ ] ≤ X
x=0

`

M x

(1.14)

We will next bound the summation on the right-hand-side. We first prove some
helpful lemmas. The first lemma deals with the expectation and variance of
C p (X) when X is a p-coin. We show that the score expectation is 0 and the
variance equals 1.
Lemma 1.23. Consider X to be a p- co in where p = sin 2 (r) and r is uni-
form over [t 0 , 2 −t 0 ] with t 0 = arcsin(

√

t) and t ∈ (0, 2 ). Then, we have that
Var[C p (X)] = 1 and for any p ∈ [t,1−t], E[C p (X) | p] = 0.

Proof. We first show the result regarding the expectation. Recall that C p (x) =
q · x − (1 − x)/q. We have E[C p (X) | p] = E[Xq − (1 − X)/q | p] = pq −

(1 −p)/q = 0, given that q = p (1−p)/p. Regarding the variance, we have
Var[C p (X)] = E[(C p (X)) 2 ] − (E[C p (X)]) 2 . Given that for any p, E[C p (X) |
p] = 0 we only need to calculate E[(C p (X)) 2 ] = E[E[(C p (X)) 2 | p]]. We have
E[(C p (X)) 2 | p] = E[q 2 X 2 +(1−X) 2 /q 2 +2X(1−X) | p] = E[pq 2 +(1−p)/q 2 ) |
p] = E[1−p + p | p] = 1.

Lemma 1.24. Let C p (w,x) = xC p (1) + (w−x)C p (0). Suppose that for some
distribution of p, it holds that E[C p (X)|p] = 0 for all p, and Var[C p (X)] = 1.
Then we have

w
x

X

·E[p x (1−p) w−x · (C p (w,x)) 2 ] = w

x=0

Proof. Consider X 1 ,...,X w independent Bernoulli trials of probability p.
Given the lemma's condition we have that:
E h P j=1 C p (X j ) 2 i = E[C p (X 1 ) 2 + ... + C p (X w ) 2 + 2 P i<j C p (X i )C p (X j )]
= w

(1.15)
To see why this holds observe that (i) E[C p (X j ) 2 ] = 1 for all j = 1,...,w,
and (ii) E[C p (X i ) · C p (X j )] = E[E[C p (X i )C p (X j ) | p]] and as X i ,X j condi-
tioned on p are independent flips we have E[C p (X i )C p (X j ) | p] = E[C p (X i ) |
p]E[C p (X j ) | p] = 0. Now, expanding the expectation on the left hand side of
equation ( 1.15 ) we have

h P x 1 ,...,x w ∈{0,1} Q `=1 p x ` (1−p) 1−x ` · ( P j=1 C p (x j )) 2 i
= E

E

h P x=0 x

p x (1−p) w−x (C p (w,x)) 2 i

(1.16)