Cryptography Reference
In-Depth Information
We also have (C
out
,tk
out
) ← CodeGen
out
(1
n
) where C
out
= {o
1
,...,o
n
}
is an (`
2
,n,n
1
) outer code for which Identify
out
satisfies the following:
∀T
2
⊆ [n
1
] s.t. |T
2
|≤ w Prob[∅ * Identify
out
(tk
out
,p
out
) ⊆ T
2
] ≥ 1−ε
2
(1.29)
where p
out
∈ Q
`
out
is an output of any probabilistic polynomial time
Forging adversary, that is bounded by the marking assumption of Defini-
tion
1.4
, given the set of codewords (C
out
)
T
2
.
Let T ⊆ [n] be a traitor coalition with size less than or equal to w, and
suppose that the Forging algorithm, on input (C
con
)
T
, outputs p ∈ Q
`
1
·`
2
in
.
According to the identification algorithm for the concatenated code, we chop
the pirate codeword p = hp
1
,...,p
`
1
`
2
i into `
2
blocks of size `
1
, and denote
the j-th block as p
j
= hp
`
1
(j−1)+1
,p
`
1
(j−1)+2
,...,p
`
1
(j−1)+`
1
i. We will prove
that Identify
con
returns an index from T with a failure probability at most
ε
2
+ `
2
ε
1
.
Due to the code concatenation, a user receives an inner-codeword for each
block. Hence, the traitor coalition T amounts to a different set of traitor
coalitions for each block within the formalization of inner fingerprinting code.
For each block j = 1,...,`
2
we define T
j
= {v ∈ [n
1
] : ∃u ∈ T s.t. i
v
=
f
−1
(o
j
)}. It further holds that p
j
∈ desc((C
in
)
T
j
).
Identify
in
(tk
in
,p
j
) = ind
j
∈ [n
1
] and the symbol q
j
= f(i
ind
j
) ∈{a ∈ Q
out
|
∃u ∈ T s.t. a = o
j
}.
Summing the error probability over j ∈{1,...,`
2
} we obtain the fact that
p
∗
= hq
1
,...,q
`
2
i∈ desc(Cout
T
) with probability at least 1−`
2
ε
1
.
1−ε
2
.
The proof completes with a failure probability at most ε
2
+ `
2
ε
1
.
An example of concatenating fingerprinting codes. As the concatena-
tion asks for a fully-collusion resistant inner code, we can either employ the
Boneh-Shaw fingerprinting code (CodeGen
`
BS
,Identify
`
BS
) or the Tardos
fingerprinting code (CodeGen
T
,Identify
T
). Both of these codes are over
binary alphabets which suits the purpose of code concatenation, i.e., an in-
ner code with a smaller alphabet. On the other hand, the traceability codes
based on error correcting codes or Chor-Fiat-Naor construction can be used
in the place of the outer code. None of those combinations provides asymp-
totically good results. Still, an interesting combination is the application of
a Boneh-Shaw inner code with length `
2
≥ 2w
2
(w − 1) ln(
2
ε
1
) for some pa-
rameters w,ε
1
with an outer Chor-Fiat-Naor secret fingerprinting code with
length 4w log(
2
ε
) and alphabet 2w. By choosing ε
1
=
ε
8w log(2n/ε)
we can
produce a binary concatenated code that is (ε,w) identifier and has length
` = O(w
4
log(
ε
)(log
ε
+log log n)). This fingerprinting code is binary and may
