Fingerprinting Codes - Encryption for Digital Content - page 14

Limitations on Combinatorial Constructions

Although, w-IPP (especially e cient w-TA) codes are good for identifica-
tion purposes, the alphabet size bounds the coalition size as illustrated in
Theorem 1.9 . This in turn imposes a limitation on designing w-identifier fin-
gerprinting codes:.

Theorem 1.14. Provided that w ≥ q, there is no q-ary fingerprinting code
(CodeGen,Identify) that is w-identifier.

Proof of Theorem 1.14 : We will prove the statement by contradiction. Pro-
vided that w ≥ q we assume the existence of a q-ary fingerprinting code
(CodeGen,Identify) that is w-identifier. The algorithm CodeGen samples
an (`,n,q) code C = {c 1 ,...,c n } and an identifying key tk. Recall the defi-
nition for w-identifier: For any Forging algorithm that satisfies the marking
assumption, it holds that

∀T ⊆ [n] s.t |T|≤ w Prob[∅ * Identify(tk,p) ⊆ T] = 1

where p ∈ Q ` is the output of the Forging algorithm on input C T = {c j | j ∈
T}.

First, observe that, the code C is not w-IPP. Indeed, otherwise Theo-
rem 1.9 , i.e. w < q, would be effective which contradicts with the fact that
w ≥ q. Given that C is not w-IPP, then there exists a codeword x ∈ desc w (C)
for which we have

\

C T = ∅ (1.11)

{T:x∈desc(C T )∧|T|≤w}

The Identify algorithm, on input x, will return an index j ∈ [n]. The
equation 1.11 implies that there exists a set T 0 with size less than w such
that j ∈ T 0 . Hence, consider the case where the Forging algorithm of an
adversary has corrupted T 0 and produces the pirate codeword x. In such case,
the Identify algorithm fails to identify the traitor correctly, hence there is a
possibility of error that contradicts with the statement that the q-ary finger-
printing code (CodeGen,Identify) is w-identifier.
As we will see later, we can overcome the limitation of the above theo-
rem by allowing some failure probability in the identification process (see the
constructions of Sections 1.4.3 and 1.4.4 ) .

1.4.2 The Chor-Fiat-Naor Fingerprinting Codes

In this section we will consider two basic variants of this class of codes. The
first variant is an open code, i.e., the adversary is allowed to have access to
the code. Moreover, given that the tracing key is the code itself this amounts
to a public fingerprinting code (cf. see the discussion on these notion after