6.1.1. The contribution of the cryptography community

Cryptologists were the first to study this problem. They came up with a model that explains what content and collusion attack are. Content is a series of discrete symbols (e.g. bits), some of which can be modified without damaging the use of the content. Only the defender (the official source of the document) knows the location of these modifiable symbols, which they can use to insert a user’s codeword into the content. On receiving the document, the traitors can reveal certain so-called detectable positions by comparing their versions. This model, known by the name Marking Assumption, was invented by Boneh and Shaw (1998).

The model restricts what traitors can do to detectable positions. The group of c traitors is denoted by = {j₁,. . . , j_c} ⊂ . The narrow-sense version (or restricted digit model) requires traitors to assemble the pirated copy of the document symbol by symbol. If they have the same symbol in a certain location, the position is not detectable and this symbol is found in the pirated copy. Otherwise, at a detectable position, they choose one of their symbols at this location, according to a certain collusion strategy. This model is summarized by:

[6.1]

where y is the hidden sequence in pirated content, y_i is its symbol at the ith position and x_j,i is the hidden symbol in the copy of the jth user at position i.

Note that there are as many codewords as there are users, and their length is m.

There are other less restrictive models for collusion: the wide-sense version or arbitrary digit model (Boneh and Shaw 1998), the unreadable digit model (Boneh and Shaw 1998), the general digit model or the weak marking assumption (Safavi-Naini and Wang 2001; Fodor et al. 2018).

The second contribution of cryptologists was the definition of desirable properties of a code (group of identifiers) (Stinson and Wei 1998) and the proposal of solutions that were mainly based on error correction codes. These will not be covered since we now know that Tardos codes are better.

6.1.2. Multimedia content

In multimedia applications, content is modeled as a series of blocks (a few seconds of audio, a scene from a movie, a block of pixels from an image). A watermarking technique (see Chapter 3) hides a symbol of an identifier in each block. The idea of detectable position is useless here: everyone knows that each block hides a symbol. However, watermarking is a secret codeword primitive. Without this codeword, we assume that we cannot read or modify the hidden symbols. Therefore, an attack involves constructing the pirated copy by copying and pasting blocks from the personalized versions. Thus, the Marking Assumption model described in equation [6.1] becomes valid.

Figure 6.1 shows a standard solution in the film industry (called “DNA watermarking”). The watermarking of the video blocks is done in advance. For a binary code, there are two versions of each block: watermarked with a “1” or a “0”. The personalization during the distribution is fast because it is enough to sequentially take the blocks that hide the codeword of the user (Shahid et al. 2013). When the traitors have a certain block in only one version (watermarked with “1” for example), this symbol ends up in the pirated copy.

6.1.3. Error probabilities

The most important criterion in the specifications is to avoid accusing an innocent user. The probability of accusing at least one innocent user is noted by . This probability must be low and we must make sure that it is smaller than a level η_R stated. This is what we call proof of robustness.

The second criterion is the identification of traitors. We must set a goal:

• – “catch one”: the aim is to identify at least one traitor;
• – “catch all”: the aim is to identify all of the traitors. You must assume that all traitors participate in the collusion fairly. It is impossible to identify a traitor if they have little involvement in the counterfeiting of the pirated copy;
• – “catch a colluder”: the aim is to identify one traitor in particular.

The completeness of a scheme comes down to proving that the probability of not achieving the set goal is smaller than a certain stated level η_C. The first two aims require investigating the events of accusation of the c traitors. This is difficult because these events are not independent. The last aim is simpler because it only considers one traitor.

In practice, η_C should be low enough so that traitor tracing is deterrent enough. is sometimes used as a metric to compare accusation schemes that meet all of the first criterion on η_R. Other comparisons are based on the number of identified traitors (“catch many”) still under the constraint ≤ η_R.

6.1.4. Collusion strategy

The collusion strategy, or attack, describes the process that traitors use to create pirated content, and more precisely its impact on the series of symbols that will be extracted by decoding the watermark of the pirated content. This series of symbols is called the pirated series and is denoted by y.

The descent set is the set of all pirated series that a collusion can construct from the codewords of the traitors. According to the Marking Assumption [6.1], the descent set can contain 2^m_d series for a binary code, where m_d < m is the number of detectable positions. A working hypothesis is that traitors share the risk evenly (unless there are traitors among traitors; seec Zhao and Liu (2006)), which reduces the descent set. How the accusation behaves for each pirated series of this set should then be judged, and this should be done for any possible collusion of a certain size. This is impossible. It results in more assumptions about the collusion strategy.

Four hypotheses are commonly used (Furon et al. 2008):

• – memoryless (Moulin 2008, definition 2.4): as we will see later, in Tardos codes, the symbols of the identifiers are statistically independent. We make the same assumption about the symbols of the pirated series. So the value of y_i depends on the traitors’ symbols at this position only {x_j1,i, · · · , x_jc,i};
• – permutation invariant (Moulin 2008, definition 2.5): there is no concept of order among traitors. So the way of deciding the value of y_i is invariant to any permutation of {x_j1,i, · · · , x_jc,i}. This means that this strategy only considers the empirical distribution (the histogram) of these symbols. In the binary case, this distribution is completely defined by the number σ_i of symbols “1” to position i: (so the number “0” is c − σ_i);
• – stationary: we assume that collusion has a unique strategy that it employs across all positions. So we can leave out the index i ∈ [m] later;
• – random: this strategy is not necessarily deterministic.

The following model of a collusion attack of size c comes from these four hypotheses:

[6.2]

The attack is then described by the probability that the traitors choose a symbol “1” in the pirated series, when they have σ “1” of c symbols in their codeword to a certain position. In other words, traitors have c + 1 biased coins. At a certain position i, they have σ_i symbols “1”, they then flip the coin σ_i to choose the value of the symbol y_i. The Marking Assumption (see equation [6.1]) requires that θ_c,0 = 0 and θ_c,c = 1. Amiri and Tardos (2009) mention an eligible channel. This model defines the set Θ_c of size c collusion strategies of size:

[6.3]

Here is a list of classic strategies at each position i ∈ [m]:

• – interleaving attack (or uniform attack): traitors randomly pick which of them will place their content block into pirated content. If σ of them have block “1”, then the probability of this block ending up in the pirated copy is:
  [6.4]
• – majority vote: traitors choose the majority symbol:
  [6.5]
• – minority vote: traitors choose the minority symbol when possible:
  [6.6]
• – coin flip: the traitors toss an unbiased coin to choose when given a choice:
  [6.7]
• – all 1 attack: the traitors always choose the symbol “1” when they can, that is, if σ > 0:
  [6.8]
• – all 0 attack: the traitors always choose the symbol “0” when they can, that is, if σ < c:
  [6.9]

These are only a few examples; the set of available strategies Θ_c is actually infinite.

6.2.1. Constructing the code

The construction is done in three stages:

• – a r.v. (random variable) P ∈ (0, 1) is defined. This can be a discrete r.v. with a set of possible values and associated probabilities {f_i := Pr(P = or an absolutely continuous r.v. with a probability density f : (0, 1) → ⁺;
• – the encoder takes m realizations of this r.v. independently according to its law. These realizations are stored in the vector p := (p₁, . . . , p_m), called secret series;
• – the encoder generates the codewords of the users by independently drawing n × m Bernoulli r.v. such that X_j,i ~ (p_i). The code X is a binary matrix of size n × m, and the codeword of the user j is x_j = (x_j,1, . . . , x_j,m). This means that, for all users, Pr(X_j,i = 1) = p_i depends on the position in the series.

The law of the r.v. P is public while the vector p is a secret shared with the accusation algorithm. The code is made up of n private codewords, in that a user only knows, at most, their own identifier, unless they are a traitor. By forming a collusion, traitors can share their knowledge of their c codewords.

6.2.2. The collusion strategy and its impact on the pirated series

The hypotheses on the collusion strategy in section 6.1.4 are very useful in deriving a statistical model of r.v. decoded symbols of the pirated series. We define Π(p_i) := Pr(Y_i = 1|p_i) (the dependency in θ_c is omitted, unless there is ambiguity). At the index i, the symbols of the codewords of the traitors are distributed as Bernoulli r.v. (p_i), given the construction of the code. So Σ_i, the number of “1” for c traitors in position i, following a binomial distribution (c, p_i):

[6.10]

For a given position i, Y_i is a Bernoulli r.v.: Y_i ~ (Π(p_i)) of parameter:

[6.11]

[6.12]

We see that Y_i follows a different law from X_ji and that this law depends on the collusion strategy. Note the following properties of this function illustrated in Figure 6.2:

• 1) Π(p) is a polynomial of degree at most c, where Π(0) = θ_c,0 = 0 and Π(1) = θ_c,c = 1;
• 2) two collusion strategies of the same size c produce two different distributions:
  [6.13]
• 3) a collusion strategy produces an attack “between ‘All-0’ and ‘All-1”’, in that:
  [6.14]
• 4) the so-called interleaving attack has the remarkable property that Π(p) is independent from c: ∀p ∈ [0, 1], Π(p) = p.

The second property proves the identifiability of the model when the size of the collusion is known. This means that we can learn the θ_c strategy if we see a large number of (Y_i, P_i) occurrences. However, the fourth property shows that the identifiability of the model no longer remains when we do not know the size of the collusion: it is sometimes impossible to distinguish attacks of different sizes (since they generate the same distribution of symbols Y_i).

In the same way, we can also calculate the distribution of Y_i, knowing that one of the traitors has a “1” symbol in the i position (say x_j1i = 1). Together, the collusion has σ > 0 symbols “1”, if the remaining traitors (c − 1) have σ − 1 “1”:

If x_j1i = 0, the collusion has σ < c symbols “1”, if the remaining traitors (c − 1) have σ “1”:

Generally, we note Π_x(p_i) := (Y_i = 1|p_i, x_j1i = x) for x ∈ {0, 1}:

[6.15]

The following properties are given:

• 1) Π(p) is the barycenter of Π₁(p) and Π₀(p) with the weights p and 1 − p:
  [6.16]
• 2) at the extreme values of p, we have:
  
• 3) by a simple calculation: ∀p ∈ (0, 1):
  [6.17]
  [6.18]

where Π′(·) is the derivative of Π(·) (see equation [6.11]), with relation to p. This last equation does not have a simple interpretation, but it is essential for proving the completeness of the Tardos code (see section 6.2.3.2).

6.2.3. Accusation with a simple decoder

Once a pirated copy is found, decoding the watermark of content block by block results in the pirated series y, which is no longer random. To decide if user j is a traitor, a simple decoder calculates a score s_j from the codeword x_j, the pirated series y and the secret p:

[6.19]

where U (·): {0, 1} × {0, 1} × (0, 1) → is called the score function.

The user is accused if s_j > τ, where τ is a threshold. In other words, the accusation tests two hypotheses for each user: ₀, the user j is innocent versus ₁, the user j is guilty. Let _fp and _fn be false positive (wrongly accusing someone of being innocent) and false negative probabilities (exonerating someone that is guilty) of this test for each user. The r.v. modeling the score of an innocent user (a traitor) is denoted S_inn (respectively S_tra). So _fp = (S_inn > τ) and _fn = (S_tra < τ).

6.2.3.1. Robustness

The robustness requires the probability of accusing one innocent user in n tests to be smaller than η_R. As the codewords of the innocent users are independent (knowing p and y), the scores are also independent:

[6.20]

[6.21]

where n − c is the number of innocent users.

It is easy to see that if _fp < ηR/n, the constraint of equation [6.21] is respected. Robustness is not so easy since we are faced with a rare event: a classic requirement is η_R ≈ 10⁻³ and n ≈ 10⁶, so much so that ηR/n is of the order 10^–9.

6.2.4. Study of the Tardos code-Škorić original

This section explains the choices made in Tardos (2003, 2008) and the improvements offered in Škorić et al. (2008a). The proofs of robustness and completeness are simplified. We assume that η_C = ½ for a “catch one” or “catch a colluder” objective. Therefore, it is enough to show that _fn < ½.

The main idea is to choose a score function, such that the statistics of S_inn do not depend on the collusion strategy. So the scores of the users are compared to a universal threshold τ. Here, universal means that the threshold is set, regardless of the collusion strategy and (y, p). The constraint _fp = P(S_inn > τ) must be guaranteed, whatever the size and collusion strategy. In statistical terms, the size c and the collusion strategy are nuisance parameters since they are unknown to the accusation algorithm. Ideally, the score of someone innocent must be a pivotal quantity, that is, whose distribution does not depend on nuisance parameters. In practice, only moments of orders 1 and 2 will be invariant.

For an innocent user, insisting that ∀p ∈ (0, 1), ∀y ∈ {0, 1}, (U (X_inn, y, p)) = 0 and (U (X_inn, y, p)) = 1 is equivalent to choosing the following score function (Furon et al. 2008) called Tardos-Škorić:

[6.24]

We see that the score function takes positive values when the user has the same symbol as the one found in the pirated series. This quantity is especially large as this symbol is rare at this position in the code. This gives us a clue that this user is potentially a traitor. In the same way, the score function takes negative values if the symbols are different. This gives us a clue that the user is potentially innocent. Their final score reflects this evidence by adding up these quantities over all of the positions of the code. Let us define the random variables:

[6.25]

[6.26]

We see that this score function has good sense, making (S_inn) = 0 and (S_inn)= m, whatever the secret series, p, and the decoded pirated series y may be.

Bernstein’s inequality gives an upper bound to the probability _fp, which decreases exponentially with τ (Furon and Desoubeaux 2014). Other inequalities are possible (e.g. Hoeffding, Kearns and Saul). This makes it possible to find the necessary code length given in Tardos (2003, 2008). The r.v. U (X_inn,i, y_i, p_i) are independent (according to the construction of the code and the collusion strategy model) of zero-expectation and unit variance. Furthermore, ∀i ∈ [m], |U (X_{inn, i}, y_i, p_i)| < M, where . So, ∀τ > 0:

[6.27]

This Bernstein bound is true for a given secret series since M depends on p. It is very useful in practice to find the value of the threshold τ, but this bound is not universal. One solution is to introduce a limit parameter 0 < t < ½, which is used to bound the score function¹. The score function becomes:

[6.28]

One consequence is that we can now set M to . Equation [6.27] is now valid, whatever the couple (p, y).

As for the score of a traitor, using the properties of section 6.2.2, we can show that:

[6.29]

where Π′(·) is derivative of Π(·) (see equation [6.11]) in relation to p.

The choice made in the original article (Tardos 2003) by an absolutely continuous r.v. P of density:

[6.30]

gives:

[6.31]

[6.32]

For any strategy following the model explained in section 6.1.4, (S_tra) → 2m/πc when t → 0 (in fact, we can show that 2(1 − t)^c − 1 ≤ Π(1 − t) − Π(t) ≤ 1). The more traitors there are, the lower (S_tra) is, and, at the first order, the distribution of S_tra converges with that of S_inn. To combat this effect, we need to increase the length of the m code.

The score S_tra is a sum of m finite variance independent r.v. The law of S_tra tends toward a Gaussian distribution when m → ∞, according to the central limit theorem (assuming Lindeberg’s condition to be true). So, mean and median converge asymptotically: (S_tra < (S_tra)) ≈ ½ (a more precise proof of completeness uses a probability bound that S_tra deviates from its expectation, like a Chebychev bound, for example). This makes _fn smaller than ½ if τ is smaller than (S_tra).

All of these elements placed end-to-end give a constraint on the length of the code m. With a probability greater than ½ (assuming this is sufficiently deterrent), a particular traitor will be identified (whatever the collusion strategy) if 2m/πc(2(1 − t)^c − 1) = τ. At the same time, the probability of accusing at least one innocent user will be smaller than η_R, if by equation [6.27]. These two parts limit the length of the code:

[6.33]

where:

[6.34]

By making t dependent on c, we can limit G(t, c). For example, let t_c := 1 − ((h+1)/2)^1/c (s.t. 2(1 − t_c)^c − 1 = h where 0 < h < 1) to get G(t_c, c) ≤ 2 for h = 0, 9. In the end, robustness and completeness are proved if (n, c, η_R, 1/2) where:

[6.35]

This is an asymptotic result (using the central limit theorem for completeness). In other words, m = Ω(c² log n/η_R).

6.2.5. Advantages

This demonstration has the following advantages.

6.2.5.1. Pedagogy

Equation [6.29] is very important for understanding the construction of the code. Suppose the set secret code, that is, f(p) = δ(p − p₀). In other words, P is no longer a r.v. but a constant p₀ ∈ (t, 1 − t). In this case, (S_tra) = m( (X_tra, Y, p₀)). The code will be even shorter, as the expectation (S_tra) will be larger than (S_inn) = 0.

Figure 6.3 plots the function ( (X_tra, Y, p)) according to p for classical attacks. We can see that p₀ = 1/2 is a great choice to fight against the collusion strategy “interleaving”, since function y is maximal. On the other hand, this choice is catastrophic for the collusion strategy “minority vote”, since the function takes a zero value in 1/2 for c = 3. It then becomes impossible to distinguish the score of someone that is innocent from the score of a traitor since they have the same expectation. For c > 3, the minority strategy even gives negative expectations. To fight against the “minority vote”, it is better to choose a value of p₀ close to 0 or 1, but this is a very bad choice against interleaving, for example. Figure 6.3 shows that it is impossible to choose a satisfactory value of p₀ for all of the strategies.

Since the value of p₀ must be decided at the code creation before the traitors choose their attack, the game is unfair for the defender. Introducing a random variable P reverses the situation: not only can traitors no longer adapt their strategy to the p_i values (since p is a secret sequence), but they must also choose a unique strategy to “fight” against all cases, i.e. all of the values stored in p. Not knowing this strategy in advance, the defender is advised to choose values across the (0, 1) support, so that on average it gives (S_tra). This is shown in equation [6.31].

6.2.6. The problems

This demonstration has three problems.

6.2.6.1. Too restrictive

This educational study is simple, but only works for η_C = ½ and asymptotically for n → ∞. A more useful proof uses an upper bound of _fn, which generally depends on (S_tra). This variance is bounded by m since ( (X_tra, Y, p)²) = 1, ∀p ∈ [t, 1 − t]. A very loose bound, such as the Chebyshev inequality, gives a good result. Suppose that _fn must be less than ϵ, then for all values of n:

[6.36]

In fact, the most critical part is the proof of the robustness, where the finest possible bound is required, while the proof of completeness is less challenging.

6.3.1. Length of the code

The most known improvement on code length was provided by Škorić et al. (2008a), which mirrored the initial score function by dividing the length by two. This score function (see equation [6.24]) is now the norm.

The following works have kept the same definition of P and U (·), as in Blayer and Tassa (2008), Škorić et al. (2008a), and Laarhoven and de Weger (2014), but have developed a finer analysis to reveal smaller constants. The latest developments on the constant κ := m/(c² log n/ηR) are as follows:

• – asymptotically when c → ∞, κ → π²/2 ≈ 4, 93 (Škorić et al. 2008a);
• – for a large collusion, κ = π²/2 + O(c^−1/3) (Laarhoven and de Weger 2014);
• – for all c > 2, κ = 10.89.

6.3.2. Other criteria

6.3.2.2. Signal-to-noise ratio

Replacing the threshold τ by (S_tra), we note the following condition: (S_inn > (S_tra)) = η_R/n, which means that someone innocent should not have a score as high as the typical score of a traitor. A rough approximation is to say that S_inn follows a Gaussian law, since it is the sum of a large number of independent r.v. (but not of the same law, hence Lindeberg’s condition). So m ≈ ρ⁻¹ (Φ⁻¹(1 − ηR/n))², where ρ is similar to a signal-to-noise ratio for a symbol coming out of the score function:

[6.37]

This criterion is used in the articles (Furon et al. 2008; Škorić et al. 2008a, 2008b). Special attention is given to the attack that minimizes ρ to define the code length needed to fight against a worst-case collusion. Note that the central limit theorem explains that ρ is a citerion (the larger it is, the better), but this theorem cannot be used for the proof of robustness.

6.3.2.3. Theoretical rates

A third criterion is the attainable rate of a simple decoder R^(S)(P; θ_c), which is defined as mutual information I(Y; X_tra|P, θ_c) between the symbols of the pirated series and symbols of the traitor’s codeword. Section 6.4.2 provides more detail on this quantity from information theory, and defined by the equation [6.41]. As the decoder performs a hypothesis test for each user (is the user j innocent or guilty?), this quantity is the maximum among all of the simple decoders of the error exponent E_fp of the probability of wrongly accusing an innocent person (for a given false negative probability η_C):

[6.38]

If it is not zero, _fp can converge to 0, as m approaches infinity as fast as e^−mR(S) (P;θ_c). In fact, a Chernoff type upper bound decreases toward 0 for the best simple decoder. Therefore, we guarantee _fp ≤ ηR/n if:

[6.39]

This makes the quantity R^(S)(P; θ_c) a criteria (the larger it is, the better it is). Note that this is a theoretical result: the best score function achieving this error exponent is given by the Neyman–Pearson lemma (see section 6.4.1). However, this score function is the log-likelihood (see equation [6.40]), which requires the expression of (Y = y, X_tra = x|p, θ_c) and (Y = y|p, θ_c). This is a problem since these probabilities depend on the collusion strategy θ_c, which is unknown by the decoder initially. On the other hand, any simple decoder has a lower error exponent than R^(S)(P; θ_c). Therefore, the collusion strategy minimizing this quantity will be a powerful attack for any simple decoder.

This criterion has been generalized to joint decoders. These decoders calculate a score per user group of size ℓ. These decoders are theoretically more powerful, but their complexity proportional to the number of groups of size ℓ among n is much bigger. In fact, for ℓ = c, this leads to the concept of capacity (Moulin 2008; Huang and Moulin 2012, 2014).

6.3.3. Extensions

Literature on Tardos codes proposes three families of the following extensions.

6.4.1. The optimal score function

The simple decoder corresponds to a series of n hypotheses tests to decide if the user j ∈ [n] is innocent or a traitor. Decision theory gives us the optimal test, that is to say the one that minimizes _fn for a set _fp. This is the Neyman–Pearson test. For this, we need to have a statistical model of the hypotheses to be tested.

• – If the user is innocent, then the symbols of their codeword are independent of the decoded symbols in the pirated content: Pr(Y = y, X = x|p, θ_c) = Pr(Y = y|p, θ_c)p^x(1 − p)^(1−x).
• – If the user is a traitor, then the symbols correlate with those of the pirated copy: Pr(Y = y, X = x|p, θ_c) = Pr(Y = y|x, p, θ_c)p^x(1 − p)^(1−x).

The optimal score function is simply the log-likelihood of the ratio of these two probabilities (we also call this accusation a maximum likelihood decoder):

[6.40]

The expressions of Π(·) and Π_x(·) are given by equations [6.11] and [6.15]. Here, we have added the notation θ_c to make it clear that these functions are calculated for a given collusion strategy. In fact, this score function is only optimal if the collusion strategy is definitely θ_c. However, when accusing, this is never known. So this optimal score function is elusive in practice. Its interest is theoretical to measure the difference between a heuristic score function and optimality if we know the collusion strategy. Applying this test blindly proves to be dangerous: it will be optimal if the traitors really have used this strategy, it will possibly be disastrous for another strategy.

6.4.2. The theory of the compound communication channel

Let us pick out one specific traitor. Collusion can be seen as the transmission of its codeword through a binary communication channel. This channel is characterized by the transition probabilities Π_x(p; θ_c) that depend on a state of the channel θ_c.

This is exactly the scenario of the compound communication channel, where a codeword is transmitted through a channel which is not totally unknown. The decoder knows that this channel belongs to a certain family, but it does not know which member of this family transmitted the codeword. Under certain conditions, it has recently been shown that a good strategy is to expect the worst (Abbe and Zheng 2010). Some channels produce more transmission errors than others. We can measure their quality by mutual information I(Y; X). The worst channel of the family is the one with the lowest measurement. If this is strictly positive, then a Neyman–Pearson decoder designed for this channel is theoretically justified. If the channel that was used is actually the worst, then the decoder is optimal. If the channel that was used is not the worst, then the decoder will at least be as powerful as the worst case.

In Tardos codes, the conditions of this compound communication channel theorem are met (Meerwald and Furon 2012). To apply this result, we need to find the worst collusion strategy, that is, the one that minimizes mutual information, as mentioned in section 6.3.2, R^(S)(P; θ_c) = I(Y; X_tra|P, θ_c).

Knowing that the more traitors there are, potentially the more powerful they are (also many of us are often stupid), the decoder will assume that c ≤ c_max. Prosaically, the formula for the length of the necessary code (see equation [6.36]) says that it is pointless to want to accuse if there are more traitors. So the worst collusion strategy is one that minimizes R^(S)(P; θ_c) for c = c_max. We will find this collusion strategy numerically, then we will put it into equation [6.40] to get a score function. We must therefore minimize the function:

[6.41]

with:

Minimizing this function is not so easy when c is large. A useful simplification observes that the “interleaving” strategy quickly becomes (as c increases) one of the worst strategies in the Θ_c set. So the idea is to inject this model into equation [6.40] to get a new function score. This is what Laarhoven suggests (2014, equation (2)). The optimal score function for the strategy θ_cmax = (0, 1/c_max, . . . , (c_max–1)/c_max, 1) simplifies to:

[6.42]

Oosterwijk et al.’s score function (Oosterwijk et al. 2013, equation (43)) is in fact a first-order approximation when c_max is large:

[6.43]

Just like for the Tardos–kori decoder, the parameter t > 0 is needed to limit its amplitude. This score function is optimal, in that it produces a saddle point equilibrium for the signal-to-noise ratio criterion (see equation [6.37]) (Oosterwijk et al. 2013, th. 2).

6.4.3. Adaptive score functions

Adaptive score functions proceed in two steps. They analyze the pirated series y, knowing the secret p, to deduce an inference as to the collusion strategy. Then, they calculate a score using a score function adapted to what it has learned. This approach is sometimes called “learn and match”.

6.4.3.1. Estimation of the collusion strategy knowing c

If the decoder knows the size c but not the strategy, it can estimate θ_c from the observations (y, p). This is possible, according to property 2 of the function Π(·) (see equation [6.13]). The maximum likelihood estimator is given by the following formulation, which is solved numerically:

[6.44]

Another possibility is the expectation–maximization algorithm, since the distribution of Y_i knowing p_i is a mix of Bernoulli distributions. Let Σ_i = ∑_j∈C X_j,i, that is, the number of “1” symbols that the traitors have at the index i. This variable will be a latent variable. The expectation–maximization algorithm starts by choosing a random collusion strategy, , and then iterates through the following steps.

6.4.3.1.1. Step E

At the iteration t, this step evaluates the distribution of Σ_i ∈ {0, . . . , c} for an estimated strategy , because of the Bayes’ rule:

[6.45]

where Pr(Σ_i = σ|p_i) is given by equation [6.10].

6.4.3.1.2. Step M

At the t iteration, this step gives a new estimate of the collusion strategy knowing the probabilities of the latent variables. This is done by maximizing the expectation of the log-likelihood: = arg max Q(θ_c) with:

[6.46]

The (c − 1) parameters are estimated by maximizing this quantity, while , according to the Marking Assumption (see equation [6.3]). With the second derivative always being negative, maximizing means canceling the gradient given by:

[6.47]

So:

[6.48]

The algorithm iterates these two steps until the maximum of the function Q(·) no longer increases. This expectation–maximization algorithm can be generalized to take deletions or double detections into account (see section 6.3.3.1; (Furon et al. 2012, section V)).

6.4.4. Comparison

We have seen several alternative score functions to the Tardos-Škorić one (see equation [6.24]). Some are fixed, and others adapt to the pirated series received. Here is an experimental protocol to compare them in the spirit of the proof in section 6.2.4, where _fn = 1/2. We choose a certain size and a certain collusion strategy. We generate a secret sequence, p, and many codewords knowing p, we choose c of them, form a pirated series, and calculate the traitors’ and innocent people’s scores. We choose a threshold τ as the median of the traitors’ scores to have _fn ≈ 1/2 (half of the traitors are accused). Finally, we estimate _fp = (S_inn > τ).

Figure 6.4 gives a comparison of these score functions for the classical collusion strategies from section 6.1.4. Here, the quantity indicated is , the bigger it is, the more the scores of the innocent and traitors are statistically separated, and the better the score function. The Tardos-Škorić function has almost the same performance from one strategy to another. This is the sense of his invention: the distributions of the scores S_inn and S_tra are independent of θ_c. Its worst attack is minority voting (see section 6.2.4). The performances of the “Optimal” score function reveal the difficulty of the attack. So, “interleaving” and “coin flip” are the most dangerous collusion strategies for c = 5 (among those tested). The “Compound” and “Laarhoven” score functions are equal, with the major weakness of the majority vote for the Compound, and the minority vote for the Laarhoven score function. Finally, the adaptive score function has the performance closest to the optimal. However, it is more complex due to the estimation of .