nach oben

Designs, Codes and Cryptography

Erschienen in:

01.06.2015

False positive probabilities in q-ary Tardos codes: comparison of attacks

verfasst von: Antonino Simone, Boris Škorić

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

Einloggen, um Zugang zu erhalten

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

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Difference matrices related to Sophie Germain primes using functions on the fields

Nächster Artikel Fourier-reflexive partitions and MacWilliams identities for additive codes

Nur mit Berechtigung zugänglich

The proportionality \(m\propto c_0^2\) was already known in the context of spread-spectrum watermarking. Kilian et al. [13] showed that, if the watermarks have a component-wise normal distribution, then \(\Omega (\sqrt{m/ln\;n})\) differently marked copies are required to successfully erase any mark with non-negligible probability.

Not to be confused with the total false positive probability (which we denote as \(\eta \)). The relation is \(\eta =1-(1-\varepsilon _1)^{n-c_0}\approx n\varepsilon _1\).

At the time of writing this was still work in progress.

This is also known as a Dirichlet integral. The ordinary Beta function (\(n=2\)) is \(B(x,y)=\Gamma (x)\Gamma (y)/\Gamma (x+y)\).

The coefficients \(\nu _t\) appear as powers of \(k/\sqrt{m}\) in the series expansion of \(\tilde{\varphi }^m\).

An implementation in Wolfram Mathematica is available at http://www.win.tue.nl/CREST/

By ‘convergence’ we mean convergence of the series to the correct value \(R_m(\tilde{Z})\), not to be confused with the CLT effect that the pdf tends to the Gaussian form.

This is work in progress.

This also makes it impossible to do the strategy comparison in the other order, “comparing FN at fixed FP”.

In fact, this is the first numerical corroboration of the statement made in [19] that the \(\tilde{\mu }\)-min attack is optimal in the Gaussian regime.

Amiri E., Tardos G.: High rate fingerprinting codes and the fingerprinting capacity. In: SODA 2009, pp. 336–345 (2009).

Beaulieu N.C.: An infinite series for the computation of the complementary probability distribution function of a sum of independent random variables and its application to the sum of Rayleigh random variables. IEEE Trans. Commun. 38(9), 1463–1474 (1990).

Blayer O., Tassa T.: Improved versions of Tardos’ fingerprinting scheme. Des. Codes Cryptogr. 48(1), 79–103 (2008).

Boesten D., Škorić B.: Asymptotic fingerprinting capacity for non-binary alphabets. In: Information Hiding 2011. Lecture Notes in Computer Science, vol. 6958, pp. 1–13. Springer, Berlin (2011).

Boneh D., Shaw J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44(5), 1897–1905 (1998).

Cérou F., Del Moral P., Furon T., Guyader A.: Sequential Monte Carlo for rare event estimation. Stat. Comput. 22(3), 795–808 (2012).

Charpentier A., Xie F., Fontaine C., Furon T.: Expectation maximization decoding of Tardos probabilistic fingerprinting code. In: SPIE Media Forensics and Security 2009, p. 72540 (2009).

Furon T., Guyader A., Cérou F.: On the design and optimization of Tardos probabilistic fingerprinting codes. In: Information Hiding. LNCS, vol. 5284, pp. 341–356. Springer, Berlin (2008).

Furon T., Pérez-Freire L., Guyader A., Cérou F.: Estimating the minimal length of Tardos code. In: Information Hiding. LNCS, vol. 5806, pp. 176–190. Springer, Berlin (2009).

10.

He S., Wu M.: Joint coding and embedding techniques for multimedia fingerprinting. TIFS 1, 231–248 (2006).

11.

Huang Y.W., Moulin P.: Saddle-point solution of the fingerprinting capacity game under the marking assumption. In: ISIT 2009 (2009).

12.

Huang Y.W., Moulin P.: On fingerprinting capacity games for arbitrary alphabets and their asymptotics. In: IEEE International Symposium on Information Theory (ISIT 2012). Cambridge, MA(2012).

13.

Kilian J. Leighton F.T., Matheson L.R., Shamoon T.G., Tarjan R.E., Zane F.: Resistance of digital watermarks to collusive attacks. In: ISIT 1998, p. 271 (1998).

14.

Kolassa J.E.: Series Approximation Methods in Statistics. Springer, New York (2006).

15.

Meerwald P., Furon T.: Toward practical joint decoding of binary tardos fingerprinting codes. IEEE Trans. Inf. Forensics Security 7(4), 1168–1180 (2012).

16.

Moulin P.: Universal fingerprinting: capacity and random-coding exponents. Preprint, arXiv:0801.3837v2 (2008).

17.

Nuida K., Hagiwara M., Watanabe H., Imai H.: Optimal probabilistic fingerprinting codes using optimal finite random variables related to numerical quadrature. In: CoRR, abs/cs/0610036 (2006).

18.

Schaathun H.G.: On error-correcting fingerprinting codes for use with watermarking. Multimed. Syst. 13(5–6), 331–344 (2008).

19.

Simone A., Škorić B.: Asymptotically false-positive-maximizing attack on non-binary Tardos codes. In: Information Hiding, pp. 14–27 (2011).

20.

Simone A., Škorić B.: Accusation probabilities in Tardos codes: beyond the Gaussian approximation. Des. Codes Cryptogr. 63(3), 379–412 (2012).

21.

Somekh-Baruch A., Merhav N.: On the capacity game of private fingerprinting systems under collusion attacks. IEEE Trans. Inf. Theory 51, 884–899 (2005).

22.

Tardos G.: Optimal probabilistic fingerprint codes. In: STOC 2003, pp. 116–125 (2003).

23.

Škorić B., Katzenbeisser S., Celik M.U.: Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes. Des. Codes Cryptogr. 46(2), 137–166 (2008).

24.

Škorić B., Oosterwijk J.: Binary and q-ary Tardos codes, revisited. http://arxiv.org/abs/cs/0610036v1. Accessed 14 Feb 2014.

25.

Š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).

Titel: False positive probabilities in q-ary Tardos codes: comparison of attacks
verfasst von: Antonino Simone
Boris Škorić
Publikationsdatum: 01.06.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-014-9937-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2015

Self-embeddings of Hamming Steiner triple systems of small order and APN permutations

The largest Erdős–Ko–Rado sets in designs

Triple arrays and Youden squares

On small line sets with few odd-points

Construction of minimal non-abelian left group codes

Hanani triple packings and optimal -ary codes of constant weight three