Fingerprinting Codes - Encryption for Digital Content - page 15

Definition 1.5 ) . The second variant is secret code and hence the adversary is
not privy to the code; it achieves better e ciency parameters.
Code Generation. Given the number of users n, the CodeGen ` CFN algo-
rithm is parameterized by the length ` which is a function of n and q; we
write (C,tk = C) ← CodeGen ` CFN (1 n ). The (`,n,q)-code C is constructed
by sampling n codewords uniformly and randomly from the codeword space
Q ` .

Analysis. An easy observation is that if the resulting code turns out to be a w-
TA code then we can employ the identifying algorithm Identify TA for which
the resulting fingerprinting code is w-identifier as it is shown in theorem 1.11 .
Theorem 1.13 presents a su cient but a stronger condition on a code to
satisfy the requirements of a traceability code. More specifically, an approach
might be checking if the the output of the CodeGen ` CFN is an [`,n,d] q error-
correcting code such that d > `(1 − w 2 ). This is quite easy but takes time
quadratic in the size of code to verify if the generated code is an [`,n,d] q error-
correcting code, by examining all the pairs of codewords (x,y) and checking
if I(x,y) ≤ w 2 . A question in this context becomes what would be a suit-
able length so that the event that this happens is relatively high. This would
be required to calculate the number of samplings from the CodeGen ` CFN
algorithm that are needed to get such an [`,n,d] q error-correcting code.
Relaxing the above strong condition we recall the necessary condition on
the output of CodeGen ` CFN to be a w-TA code: for the descendant set of
any coalition of w traitor codewords, any codeword from the descendant set
shall not share more than w positions with any other codeword in the code
generated by CodeGen ` CFN . This, indeed, would be satisfactory as it happens
that there exists a traitor for any descendant codeword that shares at least
`/w positions.
In the open code scenario, we assume that the adversary has access to the
code C generated by CodeGen ` CFN . Hence, the adversary is allowed to choose
a descendant codeword that shares the most with any of the other codewords
if they wish. Towards calculating the probability of having a w-TA code we
first present a general lemma over a number of strings sampled independently
and randomly from each other.

Lemma 1.15. Supppose w+1 strings of length ` over an alphabet Q are sam-
pled uniformly and independently. Denote the strings by f 0 , f 1 ,..., f w . Pro-
vided that |Q| = q = 2w 2 and ` ≥ 4w log(1/ε) it holds that

{i |∃j ∈ [w] s.t. f i = f i }

≥ `
w

Prob ≤ ε

where the probability is taken over all the choices of the vectors.

Proof of Lemma 1.15 : Let X i , for i = 1,...,`, be the random variable such
that X i = 1 if the i-th symbol in f 0 matches with one of the i-th symbols