Watermarking digital content is a very common approach leveraged by creators of copyrighted digital data to embed fingerprints into their data. The rationale of such operation is to mark each copy of the data in order to uniquely identify it. These watermarks are embedded in a suitable way to prevent their stripping or modification by users for illegal distribution of the copy. If a copy is illegally distributed by a pirate user (or a set of users referred as coalition) it can be identified by the distributor that can analyze the fingerprint and accuse as traitor the person in charge of that copy. Actions can then be taken against this user, to prevent further illegal distribution. Many approaches have been defined to obtain optimal fingerprinting code based on the well-known Tardos encoding. However, such approaches suffer a great limitation, i.e., when the fingerprinting code embedded in a document is too short, it is not useful for accusing a traitor in a trial, as the probability that s/he might be innocent is too high, nevertheless, the fingerprint code can be used to drive further investigation. To overcome this limitation, in this work we provide a simple yet powerful accusation scheme that can be applied for a widely used approach such phrase substitution[4] that prove itself to be effective in many real world applications when the length of the fingerprinting codes is too short to be used for accusing a traitor in a trial with the classical approaches.
Protection of copyrighted contents is a crucial activity for digital content producers in order to avoid unauthorized use of the artifacts or worse in order to prevent sensible information to be stealth (e.g. private documents of an administrative board). A common solution is the unique identification of each copy by embedding some distinguishing features. This activity is usually known as fingerprinting (a.k.a. watermarking) and the embedded content is referred as code.
In order to make this process robust against possible malicious users attacks, it is mandatory to hide the positions where the code is embedded. Indeed, attacks can be performed by group of malicious users (referred in what follows as pirates), who compare their copies and identify the positions where they differ as a position of the embedded code. The latter is referred as coalition attack. If the coalition succeeds in this identification process, pirates can then arbitrarily change the code in these positions. For the purpose of designing proper protection strategies, we can assume however that they do not know the positions of the hidden code where the bits of their codes agreed and therefore they cannot alter these positions. This assumption is referred as the marking condition.
A (collusion resistant) fingerprinting code can be built by a randomized procedure to choose codewords (the code generation) and a tracing algorithm tailored for tracing one of the pirates based on all these codewords and the forged codeword read from the unauthorized copy made by the pirates.
Obviously, we should avoid two type of errors: 1) accusing an innocent user and 2) not accusing a pirate. In this respect, the tracing algorithm fails if it falsely accuses an innocent user or outputs no accused user at all. The above mentioned errors should occur with small probability.
This problem have been largely investigated in the literature and all the approaches proposed so far shares a common terminology that we introduce here in order to ease the reading of next sections.
More in detail, we briefly recall the following key terms: – Alphabet size. The codewords are sequences over a fixed alphabet . Usually, fingerprinting codes are built by leveraging the binary alphabet = f0; 1g, however larger alphabets can be used thus the size of the alphabet is an important parameter; – Codelength. This parameter refers to the length of the codewords, usually denoted by n; – Number of users. Usually denoted by N, it coincides with the number of codewords. – Pirate Coalition Size. This parameter takes into account the actual size of the coalition that could be lower than the expected one (say it c), in such a case, the accusation algorithm should achieve a small error probability; – Error probability. A code is -secure against a coalition of c pirates if the probability of the error of the accusation algorithm is at most for any set of at most c pirates performing an arbitrary pirate strategy to produce the forged codeword under the marking assumption; – Code rate. The rate R of a fingerprinting code is computed as R = log(N) , where n the logarithm is binary.
The goal of fingerprinting schemes is to find efficient and secure fingerprinting codes
while taking into account the high cost of embedding every single digit of the code. This
implies that fingerprinting codes should be short. However, in literature many proposal
have been defined based on the seminal work of Tardos[
In order to overcome the above mentioned limitations, new approaches have been
proposed and one of the most interesting is joint-decoding. Joint-decoders compute
the guilty probability for a set of users instead of a single one. A first proposal has
been made in [
To ameliorate this problem, joint-decoding has been investigated from the theoretical
viewpoint in order to define efficient approaches that work properly for real life
situations. In this respect, a Markov Chain Monte Carlo (MCMC) based approach has been
proposed in [
The main limitation of the above mentioned Tardos based approaches is that they
perform satisfactorily when dealing with image or video fingerprinting[
In order to overcome such limitations, we propose a simpler but still effective accusation model based on Metropolis-Hastings (MH) sampling. Next sections are devoted to our proposal description. 1.1
In this paper we address the fingerprinting code design by leveraging joint decoding strategies based on Metropolis-Hastings scheme. More in detail: – we implemented an accusation scheme based on MH Joint-decoding, which is remarkably accurate even in condition where the code rate R is very low; – we performed a deep experimental assessment of our approach that resulted quite effective w.r.t. the actual baseline for this kind of approaches. 2 2.1
In this section, we briefly describe the fingerprinting scheme proposed in [
The following definition introduce some key notions about fingerprinting codes. Definition 2 (Fingerprinting Code). A fingerprint code of length m for n users over the alphabet is a distribution over the pairs (X, ), where X is fingerprint set of length m for n users and is an algorithm that takes a string y 2 m (the pirated copy) as input, and produces a subset (y) [n] = f1; 2; : : : ; ng (the set of accused users). For ; 6= C [n], a C-strategy is an algorithm that takes the submatrix of X formed by the rows with indexes in C as input, and produces a string y = (X) 2 m as output. If for each X y = (X) satisfy the marking condition w.r.t. C and X we say that satisfies the marking condition. We say that a fingerprint code is -secure against coalitions of size c, if for any coalition C of size jCj c and for any C-strategy , the error probability
P [ ( (X)) = ; _ ( (X))
C] is at most . 2.2
Let n and c be positive integers, 0 < < 1 and let k = dlog(1= )e. We define the binary fingerprint code Fnc of length m = 100c2k for n users to be the following distribution over the pairs (X; ).
(X; ) is constructed in two phases. First, let pi be independent, identically distributed random variables from [t; 1 t] for all 1 i m obtained as follows. Let t = 3010c , t0 = arcsin(pt) and ri be selected by picking uniformly at random a value in [t0; =2 t0]. pi is choosen equal to sin2 ri.
In the second phase, we select the code matrix X, by selecting each entry Xji independently from the binary alphabet f0; 1g with P [Xji = 1] = pi. Notice that independence of the entries Xji holds only in the second phase. That is, two random variables Xji and Xj0i are positively correlated as both of them tend to be 1 if pi is large.
When constructing the code log always denotes the natural logarithm. 2.3
The accusation algorithm is built by leveraging the values pi and the matrix X, as follows. We define the n by m matrix U with entries
Let accuse user j on the pirated copy y 2 f0; 1gm as input if
Uji = 8 q 1 pi if Xji = 1; < pi : q 1 pipi if Xji = 0 m P yiUji > Z i=1 where Z = 20ck is a threshold parameter. In other words, (y) consists of the indices j for which the jth entry of U yT exceeds Z. 2.4
The following two theorems bound the error probabilities of the codes Fnc . Theorem 1 bounds the “soundness error” of accusing an innocent user, while Theorem 2 bounds the “completeness error” of not accusing any guilty one. For both theorems n c 1 and 0 < < 1 are arbitrary.
Theorem 1 (Soundeness). Let (X; ) be distributed according to Fnc . Let j 2 [n] be an arbitrary user, let C [n] be a coalition of arbitrary size not containing j, and let be any C-strategy. We have
P [j 2
( (X)] < : Theorem 2 (Completeness). Let (X; ) be distributed according to Fnc . Let C 2 [n] be a coalition of size jCj c, and let be any C-strategy satisfying the marking condition. We have
P [C \ ( (X)) = ;] < "c=4:
Based on the two theorems above the following corollary holds.
Corollary 1. The fingerprint code Fnc n is -secure against coalitions of size c if c The length of this code is O(c2log(n= )). 4. 3
In this section, we describe our encoding scheme, based on Metropolis-Hastings algorithm. 3.1
Metropolis-Hastings (MH) algorithm aims at approximating a probability density function F (x1; : : : ; xn), named target distribution, whose exact formulation is unknown, exploiting the knowledge of a computable function P (x1; : : : ; xn), named proposal distribution, that is proportional to F (x1; : : : ; xn). The result of an executions of a MH sampler is a sequence of samples. This sequence of samples, which is typically represented as an histogram, yields an approximation of F (x1; : : : ; xn) as it is generated with the guarantee that the occurrences of each sample s 2 S are proportional to P (x1; : : : ; xn) (thus to F (x1; : : : ; xn)). In a sense, S has a similar shape to F . A possible implementation of M H algorithm is reported below. 7: 8: 9: 10: 11: return S Algorithm 1 The MH sampler Input: N output samples; B: number of samples for burn-in; Output: a sequence of k accused users P = [p1; : : : ; pk] 1: S = ; 2: generate an initial sample s 3: for i = 0 to B + N do 4: s0 s 5: perturb s0 6: jitter = random() if jitter min(1; PP((ss0)) ) then
s = s if k B then
Add s to S
The algorithm works as follows. We first generate an initial sample s by random picking up from the n-dimensional domain of P . At each step i a new candidate sample s0 is generated by random perturbation of s. The perturbation is performed by modifying each component of s in order to obtain a new point in the sampling space. In order to make the perturbation strategy effective, we need to have specific implementation for the context at hand, i.e., we need to take into account the semantic of each dimension for the sample being considered.
Once s0 is computed, we compute the ratio r = PP((ss0)) . The latter operation measures the variation of the target function F as it is proportional to P . Tus, r is leveraged for deciding if s0 can be accepted as a new sample for F . If s0 can be used it is queued to S. More in detail, this action is performed according to a probabilistic evaluation: we generate a random number jitter 2 [0; 1] and we decide to accept s0 if and only if jitter min(1; PP((ss0)) ). The latter implies that s0 will be accepted if F (s0) value is greater than F (s) otherwise we conditionally accept s0 with a probability score whose value is as lower as P (s0) is lower than P (s). If s0 is not acceptable, we add s to S’s queue. Intuitively enough, it means that the adopted sampling generates samples with higher P values (thus higher F values) while samples with low P values have few occurrences in S or are excluded at all.
It is worth noticing that M H algorithm generates B + N samples where B and N are input parameters, namely the number of samples you may want to burn before collecting the actual samples is S and the expexted cardinality of S. We need to perform an initial burn-in for the first samples generated by M H as the initial samples tend to be highly correlated with the initial samples thus they could be generated according to a different distribution w.r.t. the target one. For practical use, the burn-in is effective when at least 1000 iterations have been performed. 3.2
Algorithm 2 describes our accusation strategy based on MH sampling.
Herein: cCoal is the current coalition, cP coal is the probability of the current coalition, tCoal is the generated coalition and tP Coal is the probability of the generated coalition. Finally, ST is the set of generated coalition (that could contain duplicated elements).
The algorithm works in two phases. The first phase initializes the coalition set by generating burnIt coalitions that will be discarded as explained in previous section. The second phase generates it coalition that are added to ST . Each new coalition is generated by applying the following operation to the current coalition: 1. a random user not yet included in the coalition is added to it if the length of the coalition in not maximum; 2. a random user is removed from the coalition (if at least one user is in the coalition); 3. a random user of the coalition is replaced with a random user not included in the coalition.
More in detail, function genericUpdate updates the coalition by applying one of the above mentioned operations. Function addUser implements the third operation while remUser implements the second modification strategy.
Function computeProb(tCoal,y) computes the probability that a pirated copy y has been generated by coalition tCoal whose users hold the codes included in matrix XtCoal as follows: m computeP rob(tCoal; y) = pCoaljtCoalj 1 Y p(XtCoal [i] ; y [i]) i=1 (1) where p (XtCoal [i] ; y [i]) is defined as follows. p (XtCoal [i] ; y [i]) = 31 ; if 9h; k s.t. XtCoal[i][h] 6= XtCoal[i][k] and if no such h; k exists, and otherwise p (XtCoal [i] ; y [i]) = 8 pu; > >>>< (1 pu)p[i];
pup[i]; >> pu(1 p [i]); > >: (1 pu)(1 p [i]); if y [i] = 1 (a) if y [i] = 1 e XtCoal [i] = 1 (b) if y [i] = 1 e XtCoal [i] = 0 (c) if y [i] = 0 e XtCoal [i] = 1 (d) if y [i] = 0 e XtCoal [i] = 0 (e) (2)
Specifically, the definition computeP rob(tCoal; y) assumes that the probability that tCoal generates y is the combination of two different independent contributions: – the fact that jtCoalj users formed a coalition, and – the probability that the user in tCoal generated y The first contribution is represented by the factor pCoaljtCoalj 1 in Equation (1), where pCoal is the probability that two randomly picked users cooperate. The second contribution is represented by the product, for each bit i of the pirated copy y, of the probability that the users in tCoal generated the i-th bit of y. The latter probability is assumed to be pu if the i-th bit of y is unreadable (case (a) of Equation (2)), where pu is a constant representing the probability that a bit of the code is accidentally discovered by the pirates which made it unreadable or swithced its value even in the case that they all share the same value for that bit. In cases (b); (e) of Equation (2), the probability that the users in tCoal generated the i-th bit of y is assumed proportional to the probability the the bit is not accidentally discovered and the probability that that value of the bit was generated by the Tardos code generator. Finally, in cases (c); (d) of Equation (2) the probability that the users in tCoal generated the i-th bit of y is assumed proportional to the probability the the bit is accidentally discovered and the probability that that value of the bit was generated by the Tardos code generator. Summarizing, given a generic bit of the pirated copy, the probability that a coalition generated that bit is equal to =1 3 if the corresponding bits of the coalition are different from one another, otherwise it is assigned the value pu or 1 pu multiplied by the probability p(i) (or (1 p(i)) that it has been generated by the Tardos fingerprint generator. 4
In this section, we will describe the extensive experimental evaluation that we performed in order to assess the validity of our joint-decoding technique. More in detail, we will first describe the dataset generation then we will describe the standard approach we compare to and finally, we will describe the performance metrics that we computed by our experiments. 4.1
Testing the accuracy of fingerprinting codes requires a deep experimental evaluation, thus, we generated a dataset composed of 1.296.000 test cases that have been obtained as described in the following.
The dataset generator takes as input the following parameters: – N : is the number of users that are going to receive the target document; – L: is the length of the code generated for each user; – A: is the attack type (in our study we consider Random, Majority and Minority attacks that will be explained below); – C: is the pirate coalition size; – P change: is the probability that coalition users will change a bit. Each bit can be changed independently by other bits.
For each bit of the code, every attack perform a code hiding by setting it to 1 with P change probability. After this step, if all the pirates have the same bit they emit this common bit. If a given bit is not the same for all the pirates the different attack types work as follows: 1. Random: the bit is set to 1 or 0 with the same probability 21 ; 2. Majority: the bit is set to the value that occur in more than 50% of users. If the bit value occurrences are tied we apply Random strategy; 3. Minority: the bit is set to the value that occur in less than 50% of users. If the bit value occurrences are tied we apply Random strategy;
Once defined the possible attack types we can generate a test case instance by performing the steps below: 1. We generate the Tardos codes of length L for N users; 2. We generate a pirate coalition of size C; 3. We generate an attack of type A performed by the pirates in the coalition that produce a pirated copy y.
As mentioned above, we generated a huge amount of instances. More in detail: – We used the code length in the set f100; 150; 200; 250; 300; 350g; – Number of users in the set f50; 100; 150; 200; 250; 300g; – P change values f0:01; 0:03; 0:05; 0:07; 0:09g; – Coalition size ranging from 1 to 8; – Random, Majority and Minority attacks.
For each combination of the above values we generate 300 test cases, thus the total number of cases is 300 3 6 6 5 8 = 1:296:000. 4.2
In order to compare our results with a reliable baseline, in this section we compare the performance of WFinger with the Tardos accusation algorithm. However, since we consider very short codes the choice of an adeguate probability threshold for the Tardos algorithm is very hard. Indeed, for a code of 200 bits, assuming that the maximum coalition size is 3 and requiring a probability of accusing an innocent lower than 20% no user will be accused. Hence, we had to consider a slightly modified version of the Tardos m accusation algorithm, which accuses the user having the gretest value of P yiUji (see i=1 Section 2.3).
Finally, in order to perform a fair comparison with this modified version of the Tardos accusation algorithm, we considered as accuracy measure for both WFinger and Tardos the accuracy at one (named Acc in the figures), that is the fraction of the experiments where the accused user (which is the first one returned by WFinger and Tardos, respectively) is a guilty user. 4.3
In Fig. 1 we first report the accuracy values obtained by our algorithm (denoted in the following as WFinger) and the modified Tardos algorithm (denoted in the following as Tardos) by averaging the results on the three types of attack. Fig. 1(a),(b),(c) and (d) report, respectively, the accuracy w.r.t. the coalition size (a), the length of the code (b), the number of users (c) and the probability of changing a bit of the code (d). As a remarkable result, we observe that, on average, the accuracy of WFinger that is greater than Tardos by a 20%.
As regards the accuracy w.r.t. the coalition size (Fig. 1(a)), it is worth noticing that the accuracy of both algorithms decreases as the coalition dimension increases as expected. However, for WFinger it is over 80% until the coalition size is 6, while for Tardos this result is obtained only for coalition size lower than 3. The better accuracy of our approach is compelling also when the coalition size further increase to 7 or 8 pirates.
As regards the accuracy w.r.t. the length of the code (Fig. 1(b)), it is easy to see that, for code length greater than 100 bits the accuracy of WFinger is greater than 80% and
Fig. 1: Average Accuracy Results for code length greater than 200 bits it is greater than 90%, while Tardos never reach an 80% accuracy.
As regards the accuracy w.r.t. the number of users (Fig. 1(c)), we can note that even for a huge number of users (greater than 250) the accuracy of WFinger is greater than 80% while Tardos never reach an 80% accuracy.
As regards the accuracy w.r.t. the probability of changing a bit of the code (Fig. 1(d)), we point out tha this analysis give an hint about the robusteness of our approach. More in detail, we introduce in our evaluation a parameter that states the possibility that a random bit of the code is accidentally changed. The probability of this event is very low, so we assign this parameter values lower than 10%. Also in this case WFinger (accuracy greater than 90%) performs better than Tardos (accuracy lower than 70%) for all probability values.
In order to provide a more detailed view of the obtained results, we report in Fig. 2, 3 and 4 the results obtained considering a single type of attack. It is easy to see that, also when considering a single type of attack, the accuracy of WFinger always overcome
WFinger Tardos Tar1d00os for every expe1r0i0mental setting. 100 100 .)(ccA%864000 .)(ccA%864000 .)(ccA%864000 .)(ccA%864000 20 1 3 5 7 820100 150 200 250 300 23050 100 150 200 250 230010 3 5 7 9 Coalition size Code Length Num. of Users Prob. of Changing a bit (%) (a) (b) (c) (d) 3 5 Coalition size (a) 1 3 5 Coalition size (a) In this paper we investigated the design of a fingerprinting code based on MetropolisHastings scheme. We implemented an encoding scheme that is quite accurate even if the code length is very short (300 bits). The deep experimental evaluation we performed, confirmed the validity of our approach in several stressing test bench.