Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Separable Collusion-Secure Multimedia Codes

  • INFORMATION PROTECTION
  • Published:
Problems of Information Transmission Aims and scope Submit manuscript

Abstract

We review known results about codes that are able to protect multimedia content from illegal redistribution by coalitions of malicious users.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Trappe, W., Wu, M., Wang, Z.J., and Liu, K.J.R., Anti-Collusion Fingerprinting for Multimedia, IEEE Trans. Signal Process., 2003, vol. 51, no. 4, pp. 1069–1087. https://doi.org/10.1109/TSP.2003.809378

    Article  MathSciNet  Google Scholar 

  2. Liu, K.J.R., Trappe, W., Wang, Z.J., Wu, M., and Zhao, H., Multimedia Fingerprinting Forensics for Traitor Tracing, Cairo, Egypt: Hindawi, 2005.

    Book  Google Scholar 

  3. Cheng, M. and Miao, Y., On Anti-Collusion Codes and Detection Algorithms for Multimedia Fingerprinting, IEEE Trans. Inform. Theory, 2011, vol. 57, no. 7, pp. 4843–4851. https://doi.org/10.1109/TIT.2011.2146130

    Article  MathSciNet  Google Scholar 

  4. Cheng, M., Ji, L., and Miao, Y., Separable Codes, IEEE Trans. Inform. Theory, 2012, vol. 58, no. 3, pp. 1791–1803. https://doi.org/10.1109/TIT.2011.2174614

    Article  MathSciNet  Google Scholar 

  5. Wagner, N.R., Fingerprinting, in Proc. 1983 IEEE Symp. on Security and Privacy, Oakland, CA, USA, Apr. 25–27, 1983, pp. 18–22. https://doi.org/10.1109/SP.1983.10018

    Book  Google Scholar 

  6. Blakley, G.R., Meadows, C., and Purdy, G.B., Fingerprinting Long Forgiving Messages, Advances in Cryptology—CRYPTO’85 (Proc. Conf. on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, USA, Aug. 18–22, 1985), Williams, H.C., Ed., Lect. Notes Comp. Sci., vol. 218, Berlin: Springer, 1986, pp. 180 –189. https://doi.org/10.1007/3-540-39799-X_15

  7. Chor, B., Fiat, A., and Naor, M., Tracing Traitors, Advances in Cryptology—CRYPTO’94 (Proc. 14th Annu. Int. Cryptology Conf., Santa Barbara, CA, USA, Aug. 21–25, 1994), Desmedt, Y.G., Ed., Lect. Notes Comp. Sci., vol. 839, Berlin: Springer, 1994, pp. 257–270. https://doi.org/10.1007/3-540-48658-5_25

  8. Chor, B., Fiat, A., Naor, M., and Pinkas, B., Tracing Traitors, IEEE Trans. Inform. Theory, 2000, vol. 46, no. 3, pp. 893–910. https://doi.org/10.1109/18.841169

    Article  Google Scholar 

  9. Hollmann, H.D.L., van Lint, J.H., Linnartz, J.-P., and Tolhuizen, L.M.G.M., On Codes with the Identifiable Parent Property, J. Combin. Theory Ser. A, 1998, vol. 82, no. 2, pp. 121–133. https://doi.org/10.1006/jcta.1997.2851

    Article  MathSciNet  Google Scholar 

  10. Barg, A., Cohen, G., Encheva, S., Kabatiansky, G., and Zémor, G., A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents, SIAM J. Discrete Math., 2001, vol. 14, no. 3, pp. 423–431. https://doi.org/10.1137/S0895480100376848

    Article  MathSciNet  Google Scholar 

  11. Boneh, D. and Shaw, J., Collusion-Secure Fingerprinting for Digital Data, IEEE Trans. Inform. Theory, 1998, vol. 44, no. 5, pp. 1897–1905. https://doi.org/10.1109/18.705568

    Article  MathSciNet  Google Scholar 

  12. Barg, A., Blakley, G.R., and Kabatiansky, G.A., Digital Fingerprinting Codes: Problem Statements, Constructions, Identification of Traitors, IEEE Trans. Inform. Theory, 2003, vol. 49, no. 4, pp. 852–865. https://doi.org/10.1109/TIT.2003.809570

    Article  MathSciNet  Google Scholar 

  13. Tardos, G., Optimal Probabilistic Fingerprint Codes, J. ACM, 2008, vol. 55, no. 2, Art. 10 (24 pp.). https://doi.org/10.1145/1346330.1346335

  14. Kabatiansky, G.A., Traceability Codes and Their Generalizations, Probl. Peredachi Inf., 2019, vol. 55, no. 3, pp. 93–105 [Probl. Inf. Transm. (Engl. Transl.), 2019, vol. 55, no. 3, pp. 283–294]. https://doi.org/10.1134/S0032946019030074

  15. Egorova, E., Fernandez, M., Kabatiansky, G., and Lee, M.H., Signature Codes for the A-Channel and Collusion-Secure Multimedia Fingerprinting Codes, in Proc. 2016 IEEE Int. Symp. on Information Theory (ISIT’2016), Barcelona, Spain, July 10–15, 2016, pp. 3043–3047. https://doi.org/10.1109/ISIT.2016.7541858

  16. Chang, S.C. and Wolf, J.K., On the T-User M-Frequency Noiseless Multiple-Access Channel with and without Intensity Information, IEEE Trans. Inform. Theory, 1981, vol. 27, no. 1, pp. 41–48. https://doi.org/10.1109/TIT.1981.1056304

    Article  MathSciNet  Google Scholar 

  17. Egorova, E., Fernandez, M., Kabatiansky, G., and Lee, M.H., Signature Codes for Weighted Noisy Adder Channel, Multimedia Fingerprinting and Compressed Sensing, Des. Codes Cryptogr., 2019, vol. 87, no. 2– 3, pp. 455–462. https://doi.org/10.1007/s10623-018-0551-9

  18. Györfi, L., Győri, S., Laczay, B., and Ruszinkó, M., Lectures on Multiple Access Channels, Book draft, 2005. Available at http://www.szit.bme.hu/~gyori/AFOSR_05/book.pdf.

  19. Mathys, P., A Class of Codes for T Active Users out of N Multiple-Access Communication System, IEEE Trans. Inform. Theory, 1990, vol. 36, no. 6, pp. 1206–1219. https://doi.org/10.1109/18.59923

    Article  MathSciNet  Google Scholar 

  20. Donoho, D.L., Compressed Sensing, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 4, pp. 1289–1306. https://doi.org/10.1109/TIT.2006.871582

    Article  MathSciNet  Google Scholar 

  21. Candes, E.J. and Tao, T., Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 12, pp. 5406–5425. https://doi.org/10.1109/TIT.2006.885507

    Article  MathSciNet  Google Scholar 

  22. Kashin, B.S. and Temlyakov, V.N., A Remark on Compressed Sensing, Mat. Zametki, 2007, vol. 82, no. 6, pp. 829–837 [Math. Notes (Engl. Transl.), 20070, vol. 82, no. 5–6, pp. 748–755]. https://doi.org/10.1134/S0001434607110193

    Article  MathSciNet  Google Scholar 

  23. Kabatiansky, G., Fernandez, M., and Egorova, E., Multimedia Fingerprinting Codes Resistant against Colluders and Noise, in Proc. 8th IEEE Int. Workshop on Information Forensics and Security (WIFS’2016), Abu Dhabi, UAE, Dec. 4–7, 2016, pp. 1–5. https://doi.org/10.1109/WIFS.2016.7823904

  24. Egorova, E.E., Fernandez, M., Kabatiansky, G.A., and Miao, Y., Existence and Construction of Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise, Probl. Peredachi Inf., 2020, vol. 56, no. 4, pp. 97–108 [Probl. Inf. Transm. (Engl. Transl.), 2000, vol. 56, no. 4, pp. 388–398]. https://doi.org/10.1134/S0032946020040080

    MATH  Google Scholar 

  25. Wolf, J.K., Born Again Group Testing: Multiaccess Communications, IEEE Trans. Inform. Theory, 1985, vol. 31, no. 2, pp. 185–191. https://doi.org/10.1109/TIT.1985.1057026

    Article  MathSciNet  Google Scholar 

  26. Rényi, A., On a Problem in Information Theory, Magyar Tud. Akad. Mat. Kutató Int. Közl., 1961, vol. 6, pp. 505–516.

    MathSciNet  MATH  Google Scholar 

  27. Ulam, S.M., Adventures of a Mathematician, New York: Scribner, 1976.

  28. Pelc, A., Solution of Ulam’s Problem on Searching with a Lie, J. Combin. Theory Ser. A, 1987, vol. 44, no. 1, pp. 129–140. https://doi.org/10.1016/0097-3165(87)90065-3

  29. Kabatiansky, G.A. and Egorova, E.E., Adversarial Multiple Access Channels and a New Model of Multimedia Fingerprinting Coding, in Proc. 2020 IEEE Conf. on Communications and Network Security (CNS’2020), Avignon, France, June 29 – July 1, 2020, pp. 1–5. https://doi.org/10.1109/CNS48642.2020.9162248

  30. Sagalovich, Yu.L., Separating Systems, Probl. Peredachi Inf., 1994, vol. 30, no. 2, pp. 14–35 [Probl. Inf. Transm. (Engl. Transl.), 1994, vol. 30, no. 2, pp. 105–123]. http://mi.mathnet.ru/eng/ppi228

  31. Cohen, G.D. and Schaathun, H.G., Asymptotic Overview on Separating Codes, Tech. Rep. of Dept. of Informatics, Univ. of Bergen, Bergen, Norway, 2003, no. 248. Available at http://www.ii.uib.no/~georg/sci/inf/coding/hyperpdf/cs03rep.pdf.

  32. Blakley, G.R., Safeguarding Cryptographic Keys, Proc. 1979 National Computer Conf.: Int. Workshop on Managing Requirements Knowledge (MARK), New York, June 4–7, 1979, Merwin, R.E., Zanca, J.T., and Smith, M., Eds., AFIPS Conf. Proceedings, vol. 48, Montvale, NJ: AFIPS Press, 1979, pp. 313–317. https://doi.org/10.1109/MARK.1979.8817296

  33. Shamir, A., How to Share a Secret, Comm. ACM, 1979, vol. 22, no. 11, pp. 612–613. https://doi.org/10.1145/359168.359176

    Article  MathSciNet  Google Scholar 

  34. Egorova, E.E., Generalization of IPP Codes and IPP Set Systems, Probl. Peredachi Inf., 2019, vol. 55, no. 3, pp. 46–59 [Probl. Inf. Transm. (Engl. Transl.), 2019, vol. 55, no. 3, pp. 241–253]. https://doi.org/10.1134/S0032946019030049

  35. Zhao, H.V., Wu, M., Wang, Z.J., and Liu, K.J.R., Forensic Analysis of Nonlinear Collusion Attacks for Multimedia Fingerprinting, IEEE Trans. Image Process., 2005, vol. 14, no. 5, pp. 646–661. https://doi.org/10.1109/TIP.2005.846035

    Article  Google Scholar 

  36. Fan, J., Gu, Y., Hachimori, M., and Miao, Y., Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting, IEEE Trans. Inform. Theory, 2021, vol. 67, no. 1, pp. 200–216. https://doi.org/10.1109/TIT.2020.3033445

    Article  MathSciNet  Google Scholar 

  37. Djackov, A.G., On a Search Model of False Coins, Topics in Information Theory (Proc. 2nd Colloq. on Information Theory, Keszthely, Hungary, Aug. 25–30, 1975), Csiszár, I. and Elias, P., Eds., Colloq. Math. Soc. János Bolyai, vol. 16, Amsterdam: Horth Holland, 1977, pp. 163–170.

  38. MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.

  39. Bshouty, N.H. and Mazzawi, H., On Parity Check \((0,1)\)-Matrix over \({{\mathbb Z}_p}\), in Proc. 22nd Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA’11), San Francisco, CA, Jan. 23–25, 2011, pp. 1383–1394. https://dl.acm.org/doi/10.5555/2133036.2133142

  40. Kautz, W. and Singleton, R., Nonrandom Binary Superimposed Codes, IEEE Trans. Inform. Theory, 1964, vol. 10, no. 4, pp. 363–377. https://doi.org/10.1109/TIT.1964.1053689

    Article  Google Scholar 

  41. Friedman, A.D., Graham, R.L., and Ullman, J.D., Universal Single Transition Time Asynchronous State Assignments, IEEE Trans. Comput., 1969, vol. 18, no. 6, pp. 541–547. https://doi.org/10.1109/T-C.1969.222707

    Article  Google Scholar 

  42. Blackburn, S.R., Probabilistic Existence Results for Separable Codes, IEEE Trans. Inform. Theory, 2015, vol. 61, no. 11, pp. 5822–5827. https://doi.org/10.1109/TIT.2015.2473848

    Article  MathSciNet  Google Scholar 

  43. Manin, Yu.I., What Is the Maximum Number of Points on a Curve over \({{\rm{F}}_{\rm{2}}}\)?, J. Fac. Sci. Univ. Tokyo Sect. IA Math., 1981, vol. 28, no. 3, pp. 715–720.

    MathSciNet  MATH  Google Scholar 

  44. Randriambololona, H., \((2,1)\)-Separating Systems beyond the Probabilistic Bound, Israel J. Math., 2013, vol. 195, no. 1, pp. 171–186. https://doi.org/10.1007/s11856-012-0126-9

    Article  MathSciNet  Google Scholar 

  45. Cohen, G., Litsyn, S., and Zémor, G., Binary \({B_2}\)-Sequences: A New Upper Bound, J. Combin. Theory Ser. A, 2001, vol. 94, no. 1, pp. 152–155. https://doi.org/10.1006/jcta.2000.3127

    Article  MathSciNet  Google Scholar 

  46. Erdős, P., Frankl, P., and Füredi, Z., Families of Finite Sets in Which No Set Is Covered by the Union of Two Others, J. Combin. Theory Ser. A, 1982, vol. 33, no. 2, pp. 158–166. https://doi.org/10.1016/0097-3165(82)90004-8

    Article  MathSciNet  Google Scholar 

  47. Erdős, P., Frankl, P., and Füredi, Z., Families of Finite Sets in Which No Set Is Covered by the Union of \(r\) Others, Israel J. Math., 1985, vol. 51, no. 1–2, pp. 79–89. https://doi.org/10.1007/BF02772959

    Article  MathSciNet  Google Scholar 

  48. Vorob’ev, I.V., Bounds on the Rate of Separating Codes, Probl. Peredachi Inf., 2017, vol. 53, no. 1, pp. 34–46 [Probl. Inf. Transm. (Engl. Transl.), 2017, vol. 53, no. 1, pp. 30–41]. https://doi.org/10.1134/S0032946017010021

  49. Bassalygo, L.A., Gelfand, S.I., and Pinsker, M.S., Simple Methods for Deriving Lower Bounds in Coding Theory, Probl. Peredachi Inf., 1991, vol. 27, no. 4, pp. 3–8 [Probl. Inf. Transm. (Engl. Transl.), 1991, vol. 27, no. 4, pp. 277–281]. http://mi.mathnet.ru/eng/ppi576

  50. D’yachkov, A.G. and Rykov, V.V., Bounds on the Length of Disjunctive Codes, Probl. Peredachi Inf., 1982, vol. 18, no. 3, pp. 7–13 [Probl. Inf. Transm. (Engl. Transl.), 1982, vol. 18, no. 3, pp. 166–171]. http://mi.mathnet.ru/eng/ppi1232

  51. Guruswami, V. and Sudan, M., Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes, IEEE Trans. Inform. Theory, 1999, vol. 45, no. 6, pp. 1757–1767. https://doi.org/10.1109/18.782097

    Article  MathSciNet  Google Scholar 

  52. Guruswami, V., List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doct. Diss. Competition), Lect. Notes Comp. Sci., vol. 3282, Berlin: Springer, 2005.

    Google Scholar 

  53. Forney, G.D., Jr., Concatenated Codes, Cambridge: MIT Press, 1966. Translated under the title Kaskadnye kody, Moscow: Mir, 1970.

  54. Alon, N., Explicit Construction of Exponential Sized Families of k-Independent Sets, Discrete Math., 1986, vol. 58, no. 2, pp. 191–193. https://doi.org/10.1016/0012-365X(86)90161-5

    Article  MathSciNet  Google Scholar 

  55. Indyk, P., Ngo, H.Q., and Rudra, A., Efficiently Decodable Non-adaptive Group Testing, in Proc. 21st Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA’10), Austin, TX, Jan. 17–19, 2010, pp. 1126– 1142. https://dl.acm.org/doi/10.5555/1873601.1873692

  56. Sagalovich, Yu.L., Upper Bound for the Power of an Automaton State Code, Probl. Peredachi Inf., 1973, vol. 9, no. 1, pp. 73–83 [Probl. Inf. Transm. (Engl. Transl.), 1973, vol. 9, no. 1, pp. 55–63]. http://mi.mathnet.ru/eng/ppi884

  57. Sagalovich, Yu.L., New Upper Bounds on Cardinality of Separating Systems, Probl. Peredachi Inf., 1993, vol. 29, no. 2, pp. 109–111 [Probl. Inf. Transm. (Engl. Transl.), 1993, vol. 29, no. 2, pp. 199–202]. http://mi.mathnet.ru/eng/ppi182

  58. Körner, J. and Simonyi, G., Separating Partition Systems and Locally Different Sequences, SIAM J. Discrete Math., 1988, vol. 1, no. 3, pp. 355–359. https://doi.org/10.1137/0401035

    Article  MathSciNet  Google Scholar 

  59. Kabatiansky, G., Vlăduţ, S., and Tavernier, C., On the Doubly Sparse Compressed Sensing Problem, Cryptography and Coding (Proc. 15th IMA Int. Conf. IMACC’2015, Oxford, UK, Dec. 15–17, 2015), Groth, J., Ed., Lect. Notes Comp. Sci., vol. 9496, Berlin: Springer, 2015, pp. 184–189. https://doi.org/10.1007/978-3-319-27239-9_11

  60. Gritsenko, V., Kabatiansky, G., Lebedev, V., and Maevskiy, A., Signature Codes for Noisy Multiple Access Adder Channel, Des. Codes Cryptogr., 2017, vol. 82, no. 1–2, pp. 293–299. https://doi.org/10.1007/s10623-016-0228-1

    Article  MathSciNet  Google Scholar 

  61. Ericson, T. and Györfi, L., Superimposed Codes in \({{\mathbb R}^n}\), IEEE Trans. Inform. Theory, 1988, vol. 34, no. 4, pp. 877–880. https://doi.org/10.1109/18.9789

    Article  MathSciNet  Google Scholar 

  62. Füredi, Z. and Ruszinkó, M., An Improved Upper Bound of the Rate of Euclidean Superimposed Codes, IEEE Trans. Inform. Theory, 1999, vol. 45, no. 2, pp. 799–802. https://doi.org/10.1109/18.749032

    Article  MathSciNet  Google Scholar 

  63. Ericson, T. and Levenshtein, V.I., Superimposed Codes in the Hamming Space, IEEE Trans. Inform. Theory, 1994, vol. 40, no. 6, pp. 1882–1893. https://doi.org/10.1109/18.340463

    Article  Google Scholar 

  64. Vlǎduţ, S.G., Kabatiansky, G.A., and Lomakov, V.V., On Error Correction with Errors in Both the Channel and Syndrome, Probl. Peredachi Inf., 2015, vol. 51, no. 2, pp. 50–56 [Probl. Inf. Transm. (Engl. Transl.), 2015, vol. 51, no. 2, pp. 132–138]. https://doi.org/10.1134/S0032946015020040

  65. Komlós, J. and Greenberg, A.G., An Asymptotically Fast Nonadaptive Algorithm for Conflict Resolution in Multiple-Access Channels, IEEE Trans. Inform. Theory, 1985, vol. 31, no. 2, pp. 302–306. https://doi.org/10.1109/TIT.1985.1057020

    Article  MathSciNet  Google Scholar 

  66. Clementi, A.E.F., Monti, A., and Silvestri, R., Selective Families, Superimposed Codes, and Broadcasting on Unknown Radio Networks, in Proc. 12th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA’01), Washington, DC, USA, Jan. 7–9, 2001, pp. 709–718. https://dl.acm.org/doi/10.5555/365411.365756

  67. Chlebus, B.S. and Kowalski, D.R., Almost Optimal Explicit Selectors, Fundamentals of Computation Theory (Proc. 15th Int. Symp. FCT’2005, Lübeck, Germany, Aug. 17–20, 2005), Liśkiewicz, M. and Reischuk, R., Eds., Lect. Notes Comp. Sci., vol. 3623, Berlin: Springer, 2005, pp. 270–280. https://doi.org/10.1007/11537311_24

  68. Cicalese, F. and Vaccaro, U., Superselectors: Efficient Constructions and Applications, Algorithms (Proc. 18th Annu. European Symp. ESA’2010, Liverpool, UK, Sept. 6–8, 2010. Part I), de Berg, M. and Meyer, U., Eds., Lect. Notes Comp. Sci., vol. 6346, Berlin: Springer, 2010, pp. 207–218. https://doi.org/10.1007/978-3-642-15775-2_18

  69. Alon, N., Fachini, E., and Körner, J., Locally Thin Set Families, Combin. Probab. Comput., 2000, vol. 9, no. 6, pp. 481–488. https://doi.org/10.1017/S0963548300004521

    Article  MathSciNet  Google Scholar 

  70. D’yachkov, A.G., Vorob’ev, I.V., Polyansky, N.A., and Shchukin, V.Yu., Bounds on the Rate of Disjunctive Codes, Probl. Peredachi Inf., 2014, vol. 50, no. 1, pp. 31–63 [Probl. Inf. Transm. (Engl. Transl.), 2014, vol. 50, no. 1, pp. 27–56]. https://doi.org/10.1134/S0032946014010037

  71. D’yachkov, A.G., Vorob’ev, I.V., Polyansky, N.A., and Shchukin, V.Yu., Erratum to: “Bounds on the Rate of Disjunctive Codes,” Probl. Peredachi Inf., 2016, vol. 52, no. 2, p. 111 [Probl. Inf. Transm. (Engl. Transl.), 2016, vol. 52, no. 2, p. 200]. https://doi.org/10.1134/S0032946016020083

Download references

Acknowledgment

The authors consider it their pleasant duty to express their gratitude to I.V. Vorob'ev for useful discussions and comments.

Funding

The research was supported in part by the Russian Foundation for Basic Research, project nos. 20-17-50013 and 20-51-50007.

Author information

Authors and Affiliations

Authors

Additional information

Translated from Problemy Peredachi Informatsii, 2021, Vol. 57, No. 2, pp. 90–111 https://doi.org/10.31857/S0555292321020066.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Egorova, E., Kabatiansky, G. Separable Collusion-Secure Multimedia Codes. Probl Inf Transm 57, 178–198 (2021). https://doi.org/10.1134/S003294602102006X

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S003294602102006X

Key words

Navigation