Cryptography Reference
In-Depth Information
Let the total Hamming weight of the pirate codeword as projected on the
blocks B
s−1
and B
s
be k (after the application of π
−1
). Denote the random
variable X that is the weight k
s−1
conditioning on the event that the total
Hamming weight is k. The probability that X = r equals:
r
d
k−r
Prob[X = r] =
2
k
Consider a random variable Y which is a binomial distribution of k successive
experiments with success probability 1/2, hence Prob[Y = r] =
(
r
)
2
k
. It is easy
to see the following(just substitute and do regular computation):
Prob[X = r] ≤ 2·Prob[Y = r]
have the following for some 0 < α < k/2.
Prob[Y < k/2−α] ≤ e
−2α
2
/k
q
k(λ+ln 2n)
2
Substituting α =
, w
e will see
with what probability a pirate
q
k(λ+ln 2n)
2
codeword puts a weight ≤ k/2−
on block B
s−1
while at the same
time user s is innocent.
q
k(λ+ln 2n)
2
q
k(λ+ln 2n)
2
Prob[X ≤ k/2−
] ≤ 2·Prob[Y ≤ k/2−
]
≤ 2·e
−
k
·
k(λ+ln 2n)
2
= 2· (
e
−λ
2n
)
=
e
−λ
n
Summing the above failure probability for each user will result to an upper
bound of e
−λ
= ε on framing one of the innocent users. This completes the
proof of Theorem
1.20
1.4.4 The Tardos Fingerprinting Codes
Code generation. The Tardos code generation uses a distribution of values
p over [0,1] that is based on a parameter t ∈ (0,
2
) and is defined as follows:
p = sin
2
(r) where r
is
a random variable uniformly distributed over [t
0
,π/2−t
0
]
where t
0
= arcsin(
√
t). Note that the range of p as defined is [t,1−t].
Given the number of users n, the length of the code ` is determined (the
choice will be made explicit in the analysis) as a function of the bound on
coalition size w and the security parameter λ = log(
1
). The values p
1
,...,p
`
are sampled independently as defined above and subsequently the code C =
