Fingerprinting Codes - Encryption for Digital Content - page 19

M 1 ... d d + 1 ... 2d ... (n−2)d + 1 ... (n−1)d
1 1 ... 1 1 ... 1 ... 1 ... 1

2 0 ... 0 1 ... 1 ... 1 ... 1

2 0 ... 0 0 ... 0 ... 1 ... 1

. . . . . . . . . . .

n 0 ... 0 0 ... 0 ... 0 ... 0

Fig. 1.1. The master matrix of the Boneh-Shaw codes.

x ∈ {0,1} d(n−1) satisfies x i = p π(i) . The Identify ` BS algorithm will then
partition x into n− 1 blocks of length d. Let's denote B i as the i-th block.
The identifying procedure calculates the weight k i which is the Hamming
weight of x projected onto the to the block B i . The algorithm finally outputs
an integer from [n] as follows:

1. if k 1 > 0 then return 1.
2. if k n−1 < d then return n.
3. if k s−1 < k s−1 +k s
2

q (k s−1 +k s )(λ+ln 2n)
2

− then return s for s = 2,...,n−1.

4. Otherwise fail.

Analysis. As we will see the Boneh-Shaw fingerprinting code is fully-collusion
resistant, i.e., it works for any coalition size, and the length of the code affects
the failure probability of underlying identification algorithm. We, first, would
like to find a su cient condition that makes the Identify ` BS algorithm to
output an index from the set [n].

Lemma 1.19. If d ≥ 2n 2 (λ + ln 2n), then Identify ` BS always outputs an
index from the set [n].

Proof of Lemma 1.19 : Towards proving the lemma we first claim the fol-
lowing: If the algorithm fails, i.e. no user-index is returned, then it holds that

k s ≤ 2s 2 (λ + ln 2n) for s ∈{1,...,n−1}

We will prove the above claim by induction.

Base Case: As the algorithm fails, it does not return 1. This is possible only
when we have k 1 = 0, hence the base case satisfies the claim.
Induction Assumption: For some 2 ≤ s ≤ n−1, suppose that k i ≤ 2·i 2 ·
(λ + ln 2n) for all i = 1,...,s−1.
Induction Step: We will now show that k s ≤ 2s 2 (λ + ln 2n):
(1) From the induction assumption we have k s−1 ≤ 2(s−1) 2 (λ + ln 2n).
(2) Given the fact that the output of the algorithm is not s, we also know
that