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

07.04.2016

Codes with the identifiable parent property for multimedia fingerprinting

verfasst von: Minquan Cheng, Hung-Lin Fu, Jing Jiang, Yuan-Hsun Lo, Ying Miao

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

Einloggen, um Zugang zu erhalten

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

search-config
loading …

Abstract

Let \({\mathcal {C}}\) be a q-ary code of length n and size M, and \({\mathcal {C}}(i) = \{\mathbf{c}(i) \ | \ \mathbf{c}=(\mathbf{c}(1), \mathbf{c}(2), \ldots , \mathbf{c}(n))^{T} \in {\mathcal {C}}\}\) be the set of ith coordinates of \({\mathcal {C}}\). The descendant code of a sub-code \({\mathcal {C}}^{'} \subseteq {\mathcal {C}}\) is defined to be \({\mathcal {C}}^{'}(1) \times {\mathcal {C}}^{'}(2) \times \cdots \times {\mathcal {C}}^{'}(n)\). In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or t-MIPPC(nMq), so that given the descendant code of any sub-code \({\mathcal {C}}^{'}\) of a multimedia t-IPP code \({\mathcal {C}}\), one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in \({\mathcal {C}}^{'}\). We first derive a general upper bound on the size M of a multimedia t-IPP code, and then investigate multimedia 3-IPP codes in more detail. We characterize a multimedia 3-IPP code of length 2 in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia 3-IPP code of length 2, and construct several infinite families of (asymptotically) optimal multimedia 3-IPP codes of length 2.
Literatur
1.
Zurück zum Zitat Barg A., Blakley G.R., Kabatiansky G.: Digital fingerprinting codes: problem statements, constructions, identification of traitors. IEEE Trans. Inf. Theory 49, 852–865 (2003). Barg A., Blakley G.R., Kabatiansky G.: Digital fingerprinting codes: problem statements, constructions, identification of traitors. IEEE Trans. Inf. Theory 49, 852–865 (2003).
2.
Zurück zum Zitat Barg A., Cohen G., Encheva S., Kabatiansky G., Zémor G.: A hypergraph approach to the identifying parent property: the case of multiple parents. SIAM J. Discret. Math. 14, 423–431 (2001). Barg A., Cohen G., Encheva S., Kabatiansky G., Zémor G.: A hypergraph approach to the identifying parent property: the case of multiple parents. SIAM J. Discret. Math. 14, 423–431 (2001).
3.
Zurück zum Zitat Barg A., Kabatiansky G.: A class of I.P.P. codes with efficient identification. J. Complex. 20, 137–147 (2004). Barg A., Kabatiansky G.: A class of I.P.P. codes with efficient identification. J. Complex. 20, 137–147 (2004).
4.
Zurück zum Zitat Blackburn S.R.: An upper bound on the size of a code with the \(k\)-identifiable property. J. Comb. Theory Ser. A 102, 179–185 (2003). Blackburn S.R.: An upper bound on the size of a code with the \(k\)-identifiable property. J. Comb. Theory Ser. A 102, 179–185 (2003).
5.
Zurück zum Zitat Blackburn S.R.: Combinatorial schemes for protecting digital content. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 307, pp. 43–73. Cambridge University Press, Cambridge (2003). Blackburn S.R.: Combinatorial schemes for protecting digital content. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 307, pp. 43–73. Cambridge University Press, Cambridge (2003).
6.
Zurück zum Zitat Cheng M., Fu H.-L., Jiang J., Lo Y.-H., Miao Y.: Codes with the identifiable parent property for multimedia fingerprinting. arXiv:1411.6784 Cheng M., Fu H.-L., Jiang J., Lo Y.-H., Miao Y.: Codes with the identifiable parent property for multimedia fingerprinting. arXiv:​1411.​6784
7.
Zurück zum Zitat Cheng M., Ji L., Miao Y.: Separable codes. IEEE Trans. Inf. Theory 58, 1791–1803 (2012). Cheng M., Ji L., Miao Y.: Separable codes. IEEE Trans. Inf. Theory 58, 1791–1803 (2012).
8.
Zurück zum Zitat Cheng M., Miao Y.: On anti-collusion codes and detection algorithms for multimedia fingerprinting. IEEE Trans. Inf. Theory 57, 4843–4851 (2011). Cheng M., Miao Y.: On anti-collusion codes and detection algorithms for multimedia fingerprinting. IEEE Trans. Inf. Theory 57, 4843–4851 (2011).
9.
Zurück zum Zitat Chor B., Fiat A., Naor M.: Tracing traitors. In: Advances in Cryptology-CRYPTO’94. Lecture Notes in Computer Science, vol. 839, pp. 257–270. Springer, Berlin (1994). Chor B., Fiat A., Naor M.: Tracing traitors. In: Advances in Cryptology-CRYPTO’94. Lecture Notes in Computer Science, vol. 839, pp. 257–270. Springer, Berlin (1994).
10.
Zurück zum Zitat Etzion T., Trachtenberg A., Vardy A.: Which codes have cycle-free Tanner graphs. IEEE Trans. Inf. Theory 45, 2173–2181 (1999). Etzion T., Trachtenberg A., Vardy A.: Which codes have cycle-free Tanner graphs. IEEE Trans. Inf. Theory 45, 2173–2181 (1999).
11.
Zurück zum Zitat Forney G.D.: Concatenated Codes. MIT Press, Cambridge, MA (1966). Forney G.D.: Concatenated Codes. MIT Press, Cambridge, MA (1966).
12.
Zurück zum Zitat Gao F., Ge G.: New bounds on separable codes. IEEE Trans. Inf. Theory 60, 5257–5262 (2014). Gao F., Ge G.: New bounds on separable codes. IEEE Trans. Inf. Theory 60, 5257–5262 (2014).
13.
Zurück zum Zitat García-Vázquez P., Balbuena C., Marcote X., Valenzuela J.C.: On extremal bipartite graphs with high girth. In: Electronic Notes Discrete Mathematics, vol. 26, pp. 67–73 (2006). García-Vázquez P., Balbuena C., Marcote X., Valenzuela J.C.: On extremal bipartite graphs with high girth. In: Electronic Notes Discrete Mathematics, vol. 26, pp. 67–73 (2006).
14.
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 Ser. A 82, 121–133 (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 Ser. A 82, 121–133 (1998).
15.
Zurück zum Zitat Kautz W.H., Singleton R.R.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory 10, 363–377 (1964). Kautz W.H., Singleton R.R.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory 10, 363–377 (1964).
16.
Zurück zum Zitat Lam T.: Graphs without cycles of even length. Bull. Aust. Math. Soc. 63, 435–440 (2001). Lam T.: Graphs without cycles of even length. Bull. Aust. Math. Soc. 63, 435–440 (2001).
17.
Zurück zum Zitat Lam T.: A result on \(2k\)-cycle-free bipartite graphs. Australas. J. Comb. 32, 163–170 (2005). Lam T.: A result on \(2k\)-cycle-free bipartite graphs. Australas. J. Comb. 32, 163–170 (2005).
18.
Zurück zum Zitat Liu K.J.R., Trappe W., Wang Z.J., Wu M., Zhao H.: Multimedia Fingerprinting Forensics for Traitor Tracing. Hindawi, New York (2005). Liu K.J.R., Trappe W., Wang Z.J., Wu M., Zhao H.: Multimedia Fingerprinting Forensics for Traitor Tracing. Hindawi, New York (2005).
20.
Zurück zum Zitat Payne S.E.: Generalized quadrangles. In: Handbook of Combinatorial Designs, 2nd edn, pp. 472–477. Chapman & Hall/CRC, Boca Raton (2007). Payne S.E.: Generalized quadrangles. In: Handbook of Combinatorial Designs, 2nd edn, pp. 472–477. Chapman & Hall/CRC, Boca Raton (2007).
21.
Zurück zum Zitat Staddon J.N., Stinson D.R., Wei R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042–1049 (2001). Staddon J.N., Stinson D.R., Wei R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042–1049 (2001).
22.
Zurück zum Zitat Tanner M.: A recursive approach to low complexity codes. IEEE Trans. Inf. Theory 27, 533–547 (1981). Tanner M.: A recursive approach to low complexity codes. IEEE Trans. Inf. Theory 27, 533–547 (1981).
23.
Zurück zum Zitat Trappe W., Wu M., Wang Z.J., Liu K.J.R.: Anti-collusion fingerprinting for multimedia. IEEE Trans. Signal Process 51, 1069–1087 (2003). Trappe W., Wu M., Wang Z.J., Liu K.J.R.: Anti-collusion fingerprinting for multimedia. IEEE Trans. Signal Process 51, 1069–1087 (2003).
24.
Zurück zum Zitat van Trung T., Martirosyan S.: New constructions for IPP codes. Des. Codes Cryptogr. 35, 227–239 (2005). van Trung T., Martirosyan S.: New constructions for IPP codes. Des. Codes Cryptogr. 35, 227–239 (2005).
25.
Zurück zum Zitat Wu M., Trappe W., Wang Z.J., Liu K.J.R.: Collusion-resistant fingerprinting for multimedia. IEEE Signal Process. Mag. 21, 15–27 (2004). Wu M., Trappe W., Wang Z.J., Liu K.J.R.: Collusion-resistant fingerprinting for multimedia. IEEE Signal Process. Mag. 21, 15–27 (2004).
Metadaten
Titel
Codes with the identifiable parent property for multimedia fingerprinting
verfasst von
Minquan Cheng
Hung-Lin Fu
Jing Jiang
Yuan-Hsun Lo
Ying Miao
Publikationsdatum
07.04.2016
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0203-x

Weitere Artikel der Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017 Zur Ausgabe