Fingerprinting Codes - Encryption for Digital Content - page 11

The identifiable parent property implies that the intersection of all these

sets is not empty, while on the other hand, it is obvious that T j=0 T j = ∅.
This contradiction concludes the proof of the statement of the theorem.

Combinatorial Fingerprinting Codes

Among the properties of codes listed above, the w-IPP property is necessary
and su cient to produce a perfect identification of a traitor, and hence, as
we see here, we can obtain a fingerprinting code based on an IPP code. It
should be noted though that the corresponding Identify algorithm may take
exponential amount of time (but is guaranteed to succeed always).
IPP Identifying Algorithm. We will now describe the straightforward iden-
tifying algorithm Identify IPP that is associated with an IPP code. The algo-
rithm is given a pirate codeword p ∈ Q ` , with |Q| = q, and the (`,n,q) code
C, it outputs an index t ∈ [n]. It first computes the user coalitions S ⊆ [n] for
which p ∈ desc(C S ) and |S| ≤ w, i.e. the set S is a possible traitor coalition
that is responsible for producing the pirate codeword p. The time-complexity

of this algorithm is proportional to w

`.
Listing the collection of all such traitor coalitions by

T p = {S ⊆ [n] | p ∈ desc(C S ),|S|≤ w}
The algorithm returns T S∈T p S if such set is non-empty or it exists or fails.
Theorem 1.10. Provided that CodeGen(1 n ) generates a w-IPP code for all
n ∈ N, the q-ary fingerprinting code hCodeGen,Identify IPP i is w-identifier.
Proof. Based on the condition of the theorem, when (C,tk) ← CodeGen(1 n ),
we assume without loss of generality that the identifying key tk = is empty
and C = {c 1 ,...,c n } is a w-IPP q-ary code.
For any x ∈ desc w (C) we define T x by {S ⊆ [n] | x ∈ desc(C S ),|S|≤ w}; the
identifiable parent property implies that

\

∀x ∈ desc w (C) S 6= ∅ (1.7)

S∈T x

Consider now a Forging adversary that is subject to the marking assump-
tion that is given in Definition 1.4 . Consider 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 outputs a pirate codeword p ∈ desc(C T ).
Due to the fact that the code is w-IPP, the pirate codeword p satisfies the
equation in 1.7 ; hence, the identifying algorithm Identify IPP (C,p) returns

an user-index that belongs to the intersection T S∈T p S 6= ∅.
This concludes the fact that no matter the strategy of the forging algo-
rithm, on input traitor set T ⊆ [n] with |T|≤ w, outputs a pirate codeword p
it holds that Prob[∅6=⊆ Identify IPP (C,p) ⊆ T] = 1, i.e. the fingerprinting
code hCodeGen,Identify IPP i is w-identifier provided that CodeGen(1 n )
generates a w-IPP code.