Skip to main content
Erschienen in: Designs, Codes and Cryptography 1/2015

01.01.2015

False Negative probabilities in Tardos codes

verfasst von: Antonino Simone, Boris Škorić

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Forensic watermarking is the application of digital watermarks for the purpose of tracing unauthorized redistribution of content. One of the most powerful types 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^2\). 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 a bound on the False Negative accusation probabilities.
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The proportionality \(m\propto c_0^2\) was already noted in the context of spread-spectrum watermarking by Kilian et al. [14]. They showed that, if the watermarks have a component-wise normal distribution, \(\varOmega (\sqrt{m/ln\;n})\) differently marked copies are required to erase any mark with non-negligible probability.
 
Literatur
1.
Zurück zum Zitat Amiri E., Tardos G.: High rate fingerprinting codes and the fingerprinting capacity. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 336–345 (2009). Amiri E., Tardos G.: High rate fingerprinting codes and the fingerprinting capacity. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 336–345 (2009).
2.
Zurück zum Zitat Blayer O., Tassa T.: Improved versions of Tardos’ fingerprinting scheme. Des. Codes Cryptogr. 48(1), 79–103 (2008). Blayer O., Tassa T.: Improved versions of Tardos’ fingerprinting scheme. Des. Codes Cryptogr. 48(1), 79–103 (2008).
3.
Zurück zum Zitat Boesten D., Škorić B.: Asymptotic fingerprinting capacity for non-binary alphabets. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 1–13. Springer, Heidelberg (2011). Boesten D., Škorić B.: Asymptotic fingerprinting capacity for non-binary alphabets. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 1–13. Springer, Heidelberg (2011).
4.
Zurück zum Zitat Boneh D., Shaw J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44(5), 1897–1905 (1998). Boneh D., Shaw J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44(5), 1897–1905 (1998).
5.
Zurück zum Zitat Charpentier A., Xie F., Fontaine C., Furon T.: Expectation maximization decoding of Tardos probabilistic fingerprinting code. In: SPIE Proceedings of Media Forensics and Security, vol. 7254, p. 72540 (2009). Charpentier A., Xie F., Fontaine C., Furon T.: Expectation maximization decoding of Tardos probabilistic fingerprinting code. In: SPIE Proceedings of Media Forensics and Security, vol. 7254, p. 72540 (2009).
7.
Zurück zum Zitat Furon T., Pérez-Freire L., Guyader A., Cérou F.: Estimating the minimal length of Tardos code. In: Information Hiding. Lecture Notes in Computer Science, vol. 5806, pp. 176–190. Springer, Berlin (2009). Furon T., Pérez-Freire L., Guyader A., Cérou F.: Estimating the minimal length of Tardos code. In: Information Hiding. Lecture Notes in Computer Science, vol. 5806, pp. 176–190. Springer, Berlin (2009).
8.
Zurück zum Zitat Furon T., Guyader A., Cérou F.: On the design and optimization of Tardos probabilistic fingerprinting codes. In: Information Hiding. Lecture Notes in Computer Science, vol. 5284, pp. 341–356. Springer, Berlin (2008). Furon T., Guyader A., Cérou F.: On the design and optimization of Tardos probabilistic fingerprinting codes. In: Information Hiding. Lecture Notes in Computer Science, vol. 5284, pp. 341–356. Springer, Berlin (2008).
9.
Zurück zum Zitat Gradshteyn I.S., Ryzhik I.M.: Table of Integrals, Series, and Products, 5th edn. Academic Press, New York (1994). Gradshteyn I.S., Ryzhik I.M.: Table of Integrals, Series, and Products, 5th edn. Academic Press, New York (1994).
10.
Zurück zum Zitat He S., Wu M.: Joint coding and embedding techniques for multimedia fingerprinting. IEEE Trans. Inf. Forensics Secur. 1, 231–248 (2006). He S., Wu M.: Joint coding and embedding techniques for multimedia fingerprinting. IEEE Trans. Inf. Forensics Secur. 1, 231–248 (2006).
11.
Zurück zum Zitat Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M.: On codes with the identifiable parent property. J. Comb. Theory 82, 472–479 (1998). Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M.: On codes with the identifiable parent property. J. Comb. Theory 82, 472–479 (1998).
12.
Zurück zum Zitat Huang Y.W., Moulin P.: On fingerprinting capacity games for arbitrary alphabets and their asymptotics. In: IEEE International Symposium on Information Theory (ISIT), pp. 2571–2575 (2012). Huang Y.W., Moulin P.: On fingerprinting capacity games for arbitrary alphabets and their asymptotics. In: IEEE International Symposium on Information Theory (ISIT), pp. 2571–2575 (2012).
13.
Zurück zum Zitat Huang Y.W., Moulin P.: Saddle-point solution of the fingerprinting capacity game under the marking assumption. In: IEEE International Symposium on Information Theory (ISIT), pp. 2256–2260 (2009). Huang Y.W., Moulin P.: Saddle-point solution of the fingerprinting capacity game under the marking assumption. In: IEEE International Symposium on Information Theory (ISIT), pp. 2256–2260 (2009).
14.
Zurück zum Zitat Kilian J., Leighton F.T., Matheson L.R., Shamoon T.G., Tarjan R.E., Zane F.: Resistance of digital watermarks to collusive attacks. In: IEEE International Symposium on Information Theory (ISIT), p. 271 (1998). Kilian J., Leighton F.T., Matheson L.R., Shamoon T.G., Tarjan R.E., Zane F.: Resistance of digital watermarks to collusive attacks. In: IEEE International Symposium on Information Theory (ISIT), p. 271 (1998).
15.
Zurück zum Zitat Kuribayashi M., Akashi N., Morii M.: On the systematic generation of Tardos’s fingerprinting codes. In: IEEE International Workshop on Multimedia Signal Processing (MMSP), pp. 748–753 (2008). Kuribayashi M., Akashi N., Morii M.: On the systematic generation of Tardos’s fingerprinting codes. In: IEEE International Workshop on Multimedia Signal Processing (MMSP), pp. 748–753 (2008).
17.
Zurück zum Zitat Laarhoven T., Doumen J., Roelse P., Škorić B., de Weger B.M.M.: Dynamic Tardos traitor tracing schemes. IEEE Trans. Inf. Theory 59, 1–13 (2013). Laarhoven T., Doumen J., Roelse P., Škorić B., de Weger B.M.M.: Dynamic Tardos traitor tracing schemes. IEEE Trans. Inf. Theory 59, 1–13 (2013).
18.
Zurück zum Zitat Meerwald P., Furon T.: Towards joint Tardos decoding: the ‘Don Quixote’ algorithm. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 28–42. Springer, Prague (2011). Meerwald P., Furon T.: Towards joint Tardos decoding: the ‘Don Quixote’ algorithm. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 28–42. Springer, Prague (2011).
20.
Zurück zum Zitat Nuida K.: Short collusion-secure fingerprint codes against three pirates. In: Information Hiding. Lecture Notes in Computer Science, vol. 6387, pp. 86–102. Springer, Calgary (2010). Nuida K.: Short collusion-secure fingerprint codes against three pirates. In: Information Hiding. Lecture Notes in Computer Science, vol. 6387, pp. 86–102. Springer, Calgary (2010).
21.
Zurück zum Zitat Nuida K., Hagiwara M., Watanabe H., Imai H.: Optimal probabilistic fingerprinting codes using optimal finite random variables related to numerical quadrature. CoRR, abs/cs/0610036 (2006). Nuida K., Hagiwara M., Watanabe H., Imai H.: Optimal probabilistic fingerprinting codes using optimal finite random variables related to numerical quadrature. CoRR, abs/cs/0610036 (2006).
22.
Zurück zum Zitat Prudnikov A.P., Brychkov Y.A., Marichev O.I.: Integrals and Series, vol. 1. CRC Press, Boca Raton (1994). Prudnikov A.P., Brychkov Y.A., Marichev O.I.: Integrals and Series, vol. 1. CRC Press, Boca Raton (1994).
23.
Zurück zum Zitat Schaathun H.G.: On error-correcting fingerprinting codes for use with watermarking. Multimedia Syst. 13(5–6), 331–344 (2008). Schaathun H.G.: On error-correcting fingerprinting codes for use with watermarking. Multimedia Syst. 13(5–6), 331–344 (2008).
24.
Zurück zum Zitat Simone A., Škorić B.: Asymptotically false-positive-maximizing attack on non-binary Tardos codes. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 14–27. Springer, Berlin (2011). Simone A., Škorić B.: Asymptotically false-positive-maximizing attack on non-binary Tardos codes. In: Information Hiding. Lecture Notes in Computer Science, vol. 6958, pp. 14–27. Springer, Berlin (2011).
25.
Zurück zum Zitat Simone A., Škorić B.: Accusation probabilities in Tardos codes: beyond the Gaussian approximation. Des. Codes Cryptogr. 63(3), 379–412 (2012). Simone A., Škorić B.: Accusation probabilities in Tardos codes: beyond the Gaussian approximation. Des. Codes Cryptogr. 63(3), 379–412 (2012).
27.
Zurück zum Zitat Somekh-Baruch A., Merhav N.: On the capacity game of private fingerprinting systems under collusion attacks. IEEE Trans. Inf. Theory 51, 884–899 (2005). Somekh-Baruch A., Merhav N.: On the capacity game of private fingerprinting systems under collusion attacks. IEEE Trans. Inf. Theory 51, 884–899 (2005).
28.
Zurück zum Zitat Tardos G.: Optimal probabilistic fingerprint codes. In: ACM Symposium on Theory of Computing (STOC), pp. 116–125 (2003). Tardos G.: Optimal probabilistic fingerprint codes. In: ACM Symposium on Theory of Computing (STOC), pp. 116–125 (2003).
29.
Zurück zum Zitat Škorić B., Katzenbeisser S., Celik M.U.: Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes. Des. Codes Cryptogr. 46(2), 137–166 (2008). Škorić B., Katzenbeisser S., Celik M.U.: Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes. Des. Codes Cryptogr. 46(2), 137–166 (2008).
30.
Zurück zum Zitat Škorić B., Katzenbeisser S., Schaathun H.G., Celik M.U.: Tardos fingerprinting codes in the combined digit model. In: IEEE Workshop on Information Forensics and Security (WIFS), pp. 41–45 (2009) Škorić B., Katzenbeisser S., Schaathun H.G., Celik M.U.: Tardos fingerprinting codes in the combined digit model. In: IEEE Workshop on Information Forensics and Security (WIFS), pp. 41–45 (2009)
31.
Zurück zum Zitat Škorić B., Vladimirova T.U., Celik M.U., Talstra J.C.: Tardos fingerprinting is better than we thought. IEEE Trans. Inf. Theory 54(8), 3663–3676 (2008). Škorić B., Vladimirova T.U., Celik M.U., Talstra J.C.: Tardos fingerprinting is better than we thought. IEEE Trans. Inf. Theory 54(8), 3663–3676 (2008).
32.
Zurück zum Zitat Xie F., Furon T., Fontaine C.: On-off keying modulation and Tardos fingerprinting. In: ACM Workshop on Multimedia and Security (MM &Sec), pp. 101–106 (2008). Xie F., Furon T., Fontaine C.: On-off keying modulation and Tardos fingerprinting. In: ACM Workshop on Multimedia and Security (MM &Sec), pp. 101–106 (2008).
Metadaten
Titel
False Negative probabilities in Tardos codes
verfasst von
Antonino Simone
Boris Škorić
Publikationsdatum
01.01.2015
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-013-9856-x

Weitere Artikel der Ausgabe 1/2015

Designs, Codes and Cryptography 1/2015 Zur Ausgabe