Cryptography Reference
In-Depth Information
r
(k
s−1
+ k
s
)(λ + ln 2n)
2
k
s−1
≥
k
s−1
+ k
s
2
−
By combining the above two, we will have:
q
(k
s−1
+k
s
)(λ+ln 2n)
2
≤ (s−1)
2
(λ + ln 2n) +
2
≤
k
s−1
k
s
+
2
q
(2(s−1)
2
(λ+ln 2n)+k
s
)(λ+ln 2n)
2
Suppose that k
s
= 2r
2
(λ + ln 2n) holds for some positive r.
2r
2
(λ+ln 2n)
2
≤ (s−1)
2
(λ + ln 2n)+
q
(2(s−1)
2
(λ+ln 2n)+2r
2
(λ+ln 2n))(λ+ln 2n)
2
r
2
(λ + ln 2n) ≤ (s−1)
2
(λ +
ln 2n) + (λ +
ln 2n)
p
(s−1)
2
+ r
2
r
2
≤ (s
−1)
2
+
p
r
2
+ (s−1)
2
(r−s + 1)(r + s−1) ≤
p
r
2
+ (s−1)
2
(r−s + 1)(r + s−1) ≤ r + s−1
r−s + 1 ≤ 1
r ≤ s
It follows that k
s
≤ 2s
2
(λ + ln 2n) for all s = 1,...,n−1. Now we return
to the statement of the theorem. Suppose that the Identify
`
BS
algorithm fails
to return a user index. In such case k
n−1
≥ d ≥ 2n
2
(λ + ln 2n) holds since
there is no output, but on the other hand, the above inductive claim implies
that k
n−1
≤ 2(n− 1)
2
(λ + ln 2n). This two statements contradict hence the
algorithm will not fail.
We will now state the basic theorem on the effectiveness of the Boneh-Shaw
fingerprinting code.
Theorem 1.20. The Boneh-Shaw binary fingerprinting code (CodeGen
`
BS
,
Identify
`
BS
) is (ε,n)-identifier for ` ≥ 2n
2
(n−1)(ln(
ε
) + ln 2n).
Identify
`
BS
algorithm outputs a user due to Lemma
1.19
. If that user is the
first or the last, the marking assumption ensures that these users are indeed
traitors.
Otherwise, k
s−1
<
k
s−1
+k
s
2
q
(k
s−1
+k
s
)(λ+ln 2n
2
holds for some s ∈
{2,...,n − 1}, and so the user assigned the codeword w
s
is considered to
be a traitor. Suppose to the contrary that the s-th user is innocent.
If the user-codeword w
s
is not available to the traitor coalition, then the
traitors will not be able to differentiate the blocks B
s−1
and B
s
. Hence, |k
s−1
−
k
s
| is expected to be close to 0, in other terms k
s−1
cannot be substantially
different than the expectation
k
s−1
+k
s
2
−
. We will, now, compute the probability
q
(k
s−1
+k
s
)(λ+ln 2n)
2
of k
s−1
to be less than
k
s−1
+k
s
2
−
.
