Cryptography Reference
In-Depth Information
C = {c
1
,...,c
n
} is an (`,n,q) code with q = 2w.
Consider now a Forging adversary that is subject to the marking as-
sumption as is described in Definition
1.4
. The adversary chooses a traitor
coalition with index-set T which satisfies |T|≤ w. The adversary is given the
traitor codewords C
T
= {c
j
| j ∈ T} and finally outputs a pirate codeword
p ∈ desc(C
T
).
Regardless of the choice of T and p ∈ desc(C
T
) there exists some u ∈ T
such that I(c
u
,p) ≥
w
. We will now compute the probability for the existence
some j ∈ [n] \ T such that I(c
j
,p) ≥
w
(which would cause ambiguity in
identification). If we can bound such probability, this would also be an upper
bound on the failure of identification. Indeed, if there does not exist any such j
then the identification algorithm Identify
TA
will return an index from T as it
happens that u ∈ T already satisfies I(c
u
,p) ≥
w
> I(c
j
,p) for any j ∈ [n]\T.
We consider a fixed coalition T
0
⊆ [n] of size at most w and a receiver index
j
0
∈ [n] \T
0
; the corresponding w + 1 codewords are strings of length ` over
the alphabet Q that are sampled uniformly and independently. Lemma
1.17
suggests that independently of the adversary strategy that is employed for
constructing a pirate codeword p it happens that I(c
j
0
,p) ≥
w
with probability
at most
n
. Given that we would like this to hold true for all receiver indices,
the overall failure probability will be bounded by n·
n
≤ ε.
So we showed in this section that we can get quite close to the optimal
alphabet for fingerprinting codes as suggested in Theorem
1.14
via a proba-
bilistic construction. Nevertheless an alphabet proportional to w is still quite
high for many reasonable settings. In the coming section we show how the w
barrier can be broken and constant alphabets can be achieved.
1.4.3 The Boneh-Shaw Fingerprinting Codes
Code Generation. Given an integer n, the length of the code is determined
as ` = d · (n − 1) where d = 2n
2
(λ + ln 2n) for some λ = log(1/ε) that
will be relatedto the failure probability in the identification algorithm. The
CodeGen
`
BS
algorithm, where ` = d·(n−1), first constructs a master-matrix
M
d
of size n×d(n−1) such that M
d
(i,j) = 1 if j > (i−1)d and M
d
(i,j) = 0
permutation π ∈
R
Perm(d(n−1)) and permutes the columns of M
d
according
to the permutation π. The resulting matrix M
d,π
would satisfy the following:
M
d,π
(i,j) = 1 if π
−1
(j) > (i−1)d and M
d,π
(i,j) = 0 otherwise. A codeword
w
i
for 1 ≤ i ≤ n is defined as an d(n − 1)-tuple where w
j
= M
d,π
(i,j).
The CodeGen
`
BS
algorithm outputs the tracing key tk = π as well as the
(d(n−1),n,2)-code C = {w
1
,...,w
n
}.
Identifying Algorithm. Given a pirate codeword p ∈ {0,1}
d(n−1)
and π,
it first applies the inverse permutation π
−1
on p so that the resulting vector
