Cryptography Reference
In-Depth Information
Consider now an arbitrary strategy σ. Recall that S
σ
is the cumulative
score that the whole coalition will amass; we will show that S
σ
with very high
probability will be greater than w·Z and thus at least one guilty user will be
included in the list of users returned by the tracing algorithm Identify.
We consider the random variable e
−αS
σ
for a suitable parameter α to be
determined below and we will provide an upper bound on its expectation. In
the light of lemma
1.22
we can restrict ourselves in bounding the expectation
for orthodox strategies. In particular,
X
`
Y
E[e
−αS
σ
] =
E[p
x
i
(1−p)
w−x
i
·e
−α·(2σ
i
(X)−1)·C
p
(w,x
i
)
]
(1.12)
i=1
X∈{0,1}
w×`
where σ(·) depends only on the column weights of X. Recall that C
p
(w,x) =
(q ·x− (w −x)/q) and q =
p
(1−p)/p. Note that in the above expression
the matrix X determines x
1
,...,x
n
. Moreover, the likelihood of a particular
matrix X is only dependent on the values x
1
,...,x
`
and the number of 1's
in the i-th column follows a Binomial distribution with success probability p
where p is distributed independently for each column i.
Given that we want to quantify over all possible (orthodox) strategies, it
will be helpful to introduce some notations to be used as upper bounds on
the expectations. We define the following for all values w ∈ N, x = 0,...,w,
α ∈ R
+
,
Z
x
= E[p
x
(1−p)
w−x
]
H
x
= E[p
x
(1−p)
w−x
·C
p
(w,x)]
Q
x
= E[p
x
(1−p)
w−x
· (C
p
(w,x))
2
]
U
x
= E[p
x
(1−p)
w−x
·e
−α·C
p
(w,x)
]
P
x
= E[p
x
(1−p)
w−x
·e
α·C
p
(w,x)
]
8
<
max{U
x
,Z
x
,P
x
} x ∈{1,...,w−1}
P
0
M
x
=
x = 0
:
U
c
x = w
We make first the following handy observation: For any α ∈ R
+
, w ∈ N,
we have U
x
= P
w−x
for x ∈ {0,1,...,w}. Similarly, Z
0
= Z
w
. This follows
from the symmetry of the range of p. Note that P
w−x
= E[p
w−x
(1 − p)
x
·
e
αC
p
(w,w−x)
]. We have that C
p
(w,w −x) = q(w −x) −x/q = −C
1−p
(w,x)
and given that p ∈ [t,1−t] we obtain the desired result by substituting p for
1−p.
Using the above notations and the fact that the strategy σ is orthodox (i.e.,
it depends only on column Hamming weights) we can bound the summation
X):
