Traitor Tracing - Encryption for Digital Content - page 133

Let p i the probability of success of an experiment of type i and ρ i the
number of successes of the i-th experiment. The tracer will perform K ex-
periments of each type for a parameter K to be determined. After perform-
ing all experiments the tracer will output the smallest s ∈ [n] that satisfies
|ρ s−1 −ρ s |≥ 5 ·K σ−1/|M|

n or it fails if such value s does not exist.
We will now prove by setting K ≥ 75n 2 ·ln(8/ε)

(σ−1/|M|) 2 , that the tracer T S satisfies
the following: For all resettable adversaries A that make the hA,T S i pair
σ-admissible, assuming σ > 10nε p + 1

|M| , it holds that for any C ⊆ [n],

Prob[∅6= hA,T S i(tk,ek,sk 1 ,...,sk n ,C) ⊆ C] ≥ 1−ε

In other words we will show that the tracer will output an index from the
set [n] that corresponds to a traitor with probability 1−.
We observe that due to the allowed resettability the experiments performed
by the tracer are independent. By applying lemma 3.18 we deduce that the
tracer will output an index s with probability 1−ε that satisfies

|p s −p s−1 |≥ 1

5 · σ−1/|M|

> 2ε p

n

where the final inequality follows from the bound on σ required in the
theorem's statement. By Lemma 3.17 this means that s ∈ C which completes
the argument that the tracer succeeds. The bound on the number of rounds
comes directly from the lower bound on K and the fact that n+1 experiments
need to be performed.

It should be noted that the above argumentation is oblivious to the num-
ber of corrupted users thus it is possible to trace any number of traitors by
employing ME L . Unfortunately, this incurs a high transmission overhead. It
should also be observed that the the tracing overhead is quite high. There are
various strategies to reduce such costs. For example, one can employ multiuser
encryption schemes based on fingerprinting codes to trace against a bounded
size traitor-coalition. We will discuss this further in the following section.

3.5.2 Traceability of Schemes Based on Fingerprinting Codes

Let us first revisit the key distribution algorithm that is common for each of
the schemes based on fingerprinting codes.

KeyDist F : The key distribution algorithm employs a q-ary fingerprinting
code F = (CodeGen ` ,Identify). Given 1 n , the algorithm first produces
a (`,n,q)-code W = {w 1 ,...,w n } where (W,ik) ← Codegen ` (1 n ) over
an alphabet Q.
It, then, produces a collection of keys {k i,j } (i,j)∈[q]×[`] ⊆ K which is also set
to be the transmission key ek for encryption. The user key sk u , for u ∈ [n],
is set to hk w 1 ,1 ,k w 2 ,2 ,...,k w ` ,` i where w u = hw 1 ,w 2 ,...,w ` i ∈ W. The
pair (W,ik) is set to be the tracing key tk.