Abstract
We review known results about codes that are able to protect multimedia content from illegal redistribution by coalitions of malicious users.
Similar content being viewed by others
References
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
Liu, K.J.R., Trappe, W., Wang, Z.J., Wu, M., and Zhao, H., Multimedia Fingerprinting Forensics for Traitor Tracing, Cairo, Egypt: Hindawi, 2005.
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
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
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
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
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
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
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
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
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
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
Tardos, G., Optimal Probabilistic Fingerprint Codes, J. ACM, 2008, vol. 55, no. 2, Art. 10 (24 pp.). https://doi.org/10.1145/1346330.1346335
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
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
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
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
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.
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
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
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
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
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
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
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
Rényi, A., On a Problem in Information Theory, Magyar Tud. Akad. Mat. Kutató Int. Közl., 1961, vol. 6, pp. 505–516.
Ulam, S.M., Adventures of a Mathematician, New York: Scribner, 1976.
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
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
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
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.
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
Shamir, A., How to Share a Secret, Comm. ACM, 1979, vol. 22, no. 11, pp. 612–613. https://doi.org/10.1145/359168.359176
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
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
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
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.
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.
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
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
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
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
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.
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
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
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
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
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
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
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
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
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.
Forney, G.D., Jr., Concatenated Codes, Cambridge: MIT Press, 1966. Translated under the title Kaskadnye kody, Moscow: Mir, 1970.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Additional information
Translated from Problemy Peredachi Informatsii, 2021, Vol. 57, No. 2, pp. 90–111 https://doi.org/10.31857/S0555292321020066.
Rights and permissions
About this article
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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S003294602102006X