Optimal Suspicion Functions for Tardos Traitor Tracing Schemes
Jan-Jaap Oosterwijk, Boris Škorić & Jeroen DoumenWe investigate alternative suspicion functions for Tardos traitor tracing schemes. In the simple decoder approach (computation of a score for every user independently) we derive suspicion functions that optimize a performance indicator related to the sufficient code length l in the limit of large coalition size c. Our results hold for the Restricted-Digit Model as well as the Combined-Digit Model. The scores depend on information that is usually not available to the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such results can be used in realistic contexts.
We study several combinations of coalition attack strategy versus suspicion function optimized against some attack (another attack or the same). In many of these combinations the usual scaling l ∝ c² is replaced by a lower power of c, e.g. c3/2. We find that the interleaving strategy is an especially powerful attack, and the suspicion function tailored against interleaving is effective against all considered attacks.
Downloads:
- presentation by Jan-Jaap Oosterwijk at IH&MMSec, Montpellier, France, 2013-06-17, 15:10-15:30
- paper at the 1st ACM Workshop on Information Hiding and Multimedia Security (IH&MMSec'13), June 17-19, 2013, Montpellier, France
- updated preprint in Cryptology ePrint Archive, Report 2013/154, 2013-05-06, 15 pp.
- preprint in Cryptology ePrint Archive, Report 2013/154, 2013-03-14, 15 pp.
False Negative probabilities in Tardos codes
Antonino Simone & Boris ŠkorićForensic watermarking is the application of digital watermarks for the purpose of tracing unauthorized redistribution of content. The most powerful type of attack on watermarks is the collusion attack, in which multiple users compare their differently watermarked versions of the same content. Collusion-resistant codes have been developed against these attacks. One of the most famous such codes is the Tardos code. It has the asymptotically optimal property that it can resist c attackers with a code of length proportional to c².
Determining error rates for the Tardos code and its various extensions and generalizations turns out to be a nontrivial problem. In recent work we developed an approach called the Convolution and Series Expansion (CSE) method to accurately compute false positive accusation probabilities. In this paper we extend the CSE method in order to make it possible to compute false negative accusation probabilities as well.
Downloads:
- notebook for Wolfram Mathematica
- presentation (Statistical properties of Tardos codes) by Boris Škorić at the Eindhoven Stochastics Seminar, Eindhoven, the Netherlands, 2012-11-28, 13:30-14:30
- preprint in Cryptology ePrint Archive, Report 2012/667, 2012-11-26, 18 pp.
Faster Batch Forgery Identification
Daniel J. Bernstein, Jeroen Doumen, Tanja Lange & Jan-Jaap OosterwijkBatch signature verification detects whether a batch of signatures contains any forgeries. Batch forgery identification pinpoints the location of each forgery. Existing forgery-identification schemes vary in their strategies for selecting subbatches to verify (individual checks, binary search, combinatorial designs, etc.) and in their strategies for verifying subbatches. This paper exploits synergies between these two levels of strategies, reducing the cost of batch forgery identification for elliptic-curve signatures.
Downloads:
- presentation by Jan-Jaap Oosterwijk at IndoCrypt in Kolkata, India, 2012-12-12
- presentation by Jeroen Doumen at Cryptography Working Group in Utrecht, the Netherlands, 2012-12-07
- presentation by Jan-Jaap Oosterwijk at Irdeto Research in Eindhoven, the Netherlands, 2012-11-26
- paper in Progress in Cryptology - INDOCRYPT 2012 (Proceedings of the 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012), Lecture Notes in Computer Science, Volume 7668, 2012, pp. 454-473
- software
- preprint in Cryptology ePrint Archive, Report 2012/549, 2012-09-19, 20pp
False Positive probabilities in q-ary Tardos codes: comparison of attacks
Antonino Simone & Boris ŠkorićWe investigate False Positive (FP) accusation probabilities for q-ary Tardos codes in the Restricted Digit Model. We employ a computation method recently introduced by us, to which we refer as Convolution and Series Expansion (CSE). We present a comparison of several collusion attacks on q-ary codes: majority voting, minority voting, Interleaving, $\tilde\mu$-minimizing and Random Symbol (the q-ary equivalent of the Coin Flip strategy). The comparison is made by looking at the FP rate at approximately fixed False Negative rate. In nearly all cases we find that the strongest attack is either minority voting or $\tilde\mu$-minimizing, depending on the exact setting of parameters such as alphabet size, code length, and coalition size.
Furthermore, we present results on the convergence speed of the CSE method, and we show how FP rate computations for the Random Symbol strategy can be sped up by a pre-computation step.
Downloads:
- notebook for Wolfram Mathematica
- preprint in Cryptology ePrint Archive, Report 2012/522, 2012-09-05, 20 pp.
Dynamic Traitor Tracing for Arbitrary Alphabets: Divide and Conquer
Thijs Laarhoven, Jan-Jaap Oosterwijk & Jeroen DoumenWe give a generic divide-and-conquer approach for constructing collusion-resistant probabilistic dynamic traitor tracing schemes with larger alphabets from schemes with smaller alphabets. This construction offers a linear tradeoff between the alphabet size and the codelength. In particular, we show that applying our results to the binary dynamic Tardos scheme of Laarhoven et al. leads to schemes that are shorter by a factor equal to half the alphabet size. Asymptotically, these codelengths correspond, up to a constant factor, to the fingerprinting capacity for static probabilistic schemes. This gives a hierarchy of probabilistic dynamic traitor tracing schemes, and bridges the gap between the low bandwidth, high codelength scheme of Laarhoven et al. and the high bandwidth, low codelength scheme of Fiat and Tassa.
Awarded for Best Paper at WIFS 2012!
Downloads:
- poster at WIFS in Costa Adeje, Tenerife, Spain, 2012-12-05
- flash presentation by Jan-Jaap Oosterwijk at WIFS in Costa Adeje, Tenerife, Spain, 2012-12-05
- paper at 2012 IEEE International Workshop on Information Forensics and Security (WIFS) in Costa Adeje, Tenerife, Spain, December 2-5, 2012, pp. 240-245
- presentation by Jan-Jaap Oosterwijk at EIPSI seminar in Eindhoven, the Netherlands, 2012-11-14
- presentation by Jan-Jaap Oosterwijk at ICT.OPEN 2012 in Rotterdam, the Netherlands, 2012-10-22
- poster at ICT.OPEN 2012 in Rotterdam, the Netherlands, 2012-10-22
- updated preprint on arXiv.org [cs.CR] No. 1206.6720, 2012-09-26
- presentation by Jan-Jaap Oosterwijk at Cryptography Working Group in Utrecht, the Netherlands, 2012-09-21
- presentation by Jan-Jaap Oosterwijk at Irdeto in Eindhoven, the Netherlands,
- preprint on arXiv.org [cs.CR] No. 1206.6720, 2012-06-28
Binary and q-ary Tardos codes, revisited
Boris Škorić & Jan-Jaap OosterwijkThe Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal length m ∝ c0², where c0 is the number of colluders.
In this paper we simplify the security proofs for this code, making use of the Bernstein inequality and Bennett inequality instead of the typically used Markov inequality. This simplified proof technique also slightly improves the tightness of the bound on the false negative error probability. We present new results on code length optimization, for both small and asymptotically large coalition sizes.
Downloads:
- revised preprint in Cryptology ePrint Archive, Report 2012/249, 2012-10-20, 30 pp.
- preprint in Cryptology ePrint Archive, Report 2012/249, 2012-05-03, 32 pp.
Asymptotic fingerprinting capacity in the Combined Digit Model
Dion Boesten & Boris ŠkorićWe study the channel capacity of q-ary fingerprinting in the limit of large attacker coalitions. We extend known results by considering the Combined Digit Model, an attacker model that captures signal processing attacks such as averaging and noise addition. For q = 2 we give results for various attack parameter settings. For q ≥ 3 we present the relevant equations without providing a solution. We show how the channel capacity in the Restricted Digit Model is obtained as a limiting case of the Combined Digit Model.
Downloads:
- presentation by Boris Škorić at the 2nd Joint WIC/IEEE Symposium on Information Theory and Signal Processing in the Benelux, 2012-05-25, 14:00-14:15
- presentation by Jan-Jaap Oosterwijk at IH, Berkeley CA, USA, 2012-05-18
- paper in Information Hiding (14th International Conference, IH 2012, Berkeley CA, USA, May 15-18, 2012. Revised Selected Papers), Lecture Notes in Computer Science, Volume 7692, 2013, pp. 255-268
- presentation by Boris Škorić at EIPSI seminar in Eindhoven, the Netherlands, 2012-05-09
- paper in preproceedings of IH 2012
- updated preprint in Cryptology ePrint Archive, Report 2012/184, 2012-04-16, 12 pp.
- preprint in Cryptology ePrint Archive, Report 2012/184, 2012-04-05, 11 pp.
Asymptotic fingerprinting capacity for non-binary alphabets
Dion Boesten & Boris ŠkorićWe compute the channel capacity of non-binary fingerprinting under the Marking Assumption, in the limit of large coalition size c. The solution for the binary case was found by Huang and Moulin. They showed that asymptotically, the capacity is 1/(c² 2 ln 2), the interleaving attack is optimal and the arcsine distribution is the optimal bias distribution. In this paper we prove that the asymptotic capacity for general alphabet size q is (q - 1)/(c² 2 ln q). Our proof technique does not reveal the optimal attack or bias distribution. The fact that the capacity is an increasing function of q shows that there is a real gain in going to non-binary alphabets.
Downloads:
- presentation by Dion Boesten at the Cryptography Working Group, Utrecht, the Netherlands, 2011-12-02
- presentation by Dion Boesten at ICT.OPEN, Veldhoven, the Netherlands, 2011-11-14
- poster (Asymptotic channel capacity of collusion resistant watermarking for non-binary alphabets) by Dion Boesten at ICT.OPEN, Veldhoven, the Netherlands, 2011-11-14
- presentation by Dion Boesten at IH, Prague, Czech Republic, 2011-05-18, 9:30-10:00
- paper in Information Hiding (13th International Conference, IH 2011, Prague, Czech Republic, May 18-20, 2011. Revised Selected Papers), Lecture Notes in Computer Science, Volume 6958, pp. 1-13
- poster (Asymptotic channel capacity of collusion resistant watermarking for non-binary alphabets) by Dion Boesten at the WIC/IEEE SP Symposium on Information Theory and Signal Processing in the Benelux, Brussels, Belgium, 2011-05-10
- presentation (On Tardos Fingerprinting and Channel capacities) by Dion Boesten at the EIPSI Seminar, Eindhoven, the Netherlands, 2011-03-09
- preprint on arXiv.org [cs.CR] No. 1102.0445, 2011-02-02, 11 pp.
Asymptotically false-positive-maximizing attack on non-binary Tardos codes
Antonino Simone & Boris ŠkorićWe use a method recently introduced by us to study accusation probabilities for non-binary Tardos fingerprinting codes. We generalize the pre-computation steps in this approach to include a broad class of collusion attack strategies. We analytically derive properties of a special attack that asymptotically maximizes false accusation probabilities. We present numerical results on sufficient code lengths for this attack, and explain the abrupt transitions that occur in these results.
Downloads:
- notebook for Wolfram Mathematica
- presentation by Antonino Simone at ICT.OPEN, Veldhoven, the Netherlands, 2011-11-14
- poster (Attacks on non-binary Tardos codes) by Antonino Simone at ICT.OPEN, Veldhoven, the Netherlands, 2011-11-14
- presentation by Antonino Simone at IH, Prague, Czech Republic, 2011-05-18, 10:00-10:30
- paper in Information Hiding (13th International Conference, IH 2011, Prague, Czech Republic, May 18-20, 2011. Revised Selected Papers), Lecture Notes in Computer Science, Volume 6958, pp. 14-27
- preprint on arXiv.org [cs.CR] No. 1102.0451, 2011-02-02, 14 pp.
Awarded a student travel grant at IH 2011
Accusation probabilities in Tardos codes : beyond the Gaussian approximation
Antonino Simone & Boris ŠkorićWe study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a method, based on power series expansions, to systematically compute the probability of accusing innocent users. The `small parameter' in the power series is 1/m, where m is the code length. We use our method to semi-analytically study the performance of the Tardos code against majority voting and interleaving attacks. The bias function `shape' parameter κ strongly influences the distance between the actual probabilities and the asymptotic Gaussian curve. The impact on the collusion-resilience of the code is shown. For some realistic parameter values, the false accusation probability is even lower than the Gaussian approximation predicts.
Downloads:
- notebook for Wolfram Mathematica
- paper in Designs, Codes and Cryptography, June 2012, Volume 63, Issue 3, pp 379-412.
- presentation by Antonino Simone at the Cryptography Working Group, Utrecht, the Netherlands, 2010-12-03
- presentation by Antonino Simone at the 5th Benelux Workshop on Information and System Security (WISSec), Nijmegen, the Netherlands, 2010-11-30
- presentation by Boris Škorić at the Center for Advanced Security Research Darmstadt (CASED), Darmstadt, Germany, 2010-09-14
- preprint (the Gaussian approximation is better than we thought) in Cryptology ePrint Archive, Report 2010/472, 2010-09-06, 31 pp.
