On the relationship between the traceability properties of Reed-Solomon codes

Previous Article
An algebraic approach for decoding spread codes
AMC Home
This Issue
Next Article
Extended combinatorial constructions for peer-to-peer user-private information retrieval

November 2012, 6(4): 467-478. doi: 10.3934/amc.2012.6.467

On the relationship between the traceability properties of Reed-Solomon codes

José Moreira ^1, , Marcel Fernández ^1, and Miguel Soriano ^2,

1.	Department of Telematics Engineering, Universitat Politècnica de Catalunya, C. Jordi Girona 1-3, 08034 Barcelona, Spain, Spain
2.	Department of Telematics Engineering, Universitat Politècnica de Catalunya, C. Jordi Girona 1-3, 08034 Barcelona, Spain, and Centre Tecnològic de Telecomunicacions de Catalunya (CTTC), Av. Carl Friedrich Gauss 7, 08860 Castelldefels (Barcelona), Spain

Received October 2011 Revised June 2012 Published November 2012

Abstract
Related Papers

Fingerprinting codes are used to prevent dishonest users (traitors) from redistributing digital contents. In this context, codes with the traceability (TA) property and codes with the identifiable parent property (IPP) allow the unambiguous identification of traitors. The existence conditions for IPP codes are less strict than those for TA codes. In contrast, IPP codes do not have an efficient decoding algorithm in the general case. Other codes that have been widely studied but possess weaker identification capabilities are separating codes. It is a well-known result that a TA code is an IPP code, and an IPP code is a separating code. The converse is in general false. However, it has been conjectured that for Reed-Solomon codes all three properties are equivalent. In this paper we investigate this equivalence, providing a positive answer when the number of traitors divides the size of the ground field.

Keywords: separating codes, Reed-Solomon codes., identifiable parent property, Fingerprinting and traitor tracing, MDS codes.

Mathematics Subject Classification: Primary: 94B60; Secondary: 94B6.

Citation: José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467

References:

[1]	A. Barg, G. R. Blakley and G. A. Kabatiansky, Digital fingerprinting codes: problem statements, constructions, identification of traitors,, IEEE Trans. Inform. Theory, 49 (2003), 852. doi: 10.1109/TIT.2003.809570. Google Scholar
[2]	D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data,, in, (1995), 452. doi: 10.1007/3-540-44750-4_36. Google Scholar
[3]	D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data,, IEEE Trans. Inform. Theory, 44 (1998), 1897. doi: 10.1109/18.705568. Google Scholar
[4]	B. Chor, A. Fiat and M. Naor, Tracing traitors,, in, (1994), 480. Google Scholar
[5]	B. Chor, A. Fiat, M. Naor and B. Pinkas, Tracing traitors,, IEEE Trans. Inform. Theory, 46 (2000), 893. doi: 10.1109/18.841169. Google Scholar
[6]	G. D. Cohen and H. G. Schaathun, Asymptotic overview on separating codes,, Tech. Report 248, (2003). Google Scholar
[7]	G. D. Cohen and H. G. Schaathun, Upper bounds on separating codes,, IEEE Trans. Inform. Theory, 50 (2004), 1291. doi: 10.1109/TIT.2004.828140. Google Scholar
[8]	M. Fernandez, J. Cotrina, M. Soriano and N. Domingo, A note about the identifier parent property in Reed-Solomon codes,, Comput. Security, 29 (2010), 628. doi: 10.1016/j.cose.2009.12.012. Google Scholar
[9]	A. D. Friedman, R. L. Graham and J. D. Ullman, Universal single transition time asynchronous state assignments,, IEEE Trans. Comput., C-18 (1969), 541. doi: 10.1109/T-C.1969.222707. Google Scholar
[10]	H. D. L. Hollmann, J. H. van Lint, J.-P. Linnartz and L. M. G. M. Tolhuizen, On codes with the identifiable parent property,, J. Combin. Theory Ser. A, 82 (1998), 121. doi: 10.1006/jcta.1997.2851. Google Scholar
[11]	H. Jin and M. Blaum, Combinatorial properties for traceability codes using error correcting codes,, IEEE Trans. Inform. Theory, 53 (2007), 804. doi: 10.1109/TIT.2006.889730. Google Scholar
[12]	J. Körner and G. Simonyi, Separating partition systems and locally different sequences,, SIAM J. Discr. Math., 1 (1988), 355. doi: 10.1137/0401035. Google Scholar
[13]	R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition,, Cambridge University Press, (1994). doi: 10.1017/CBO9781139172769. Google Scholar
[14]	M. S. Pinsker and Y. L. Sagalovich, Lower bound on the cardinality of code of automata's states,, Probl. Inform. Transm., 8 (1972), 59. Google Scholar
[15]	I. S. Reed and G. Solomon, Polynomial codes over certain finite fields,, SIAM J. Appl. Math., 8 (1960), 300. doi: 10.1137/0108018. Google Scholar
[16]	Y. L. Sagalovich, Completely separating systems,, Probl. Inform. Transm., 18 (1982), 140. Google Scholar
[17]	Y. L. Sagalovich, Separating systems,, Probl. Inform. Transm., 30 (1994), 105. Google Scholar
[18]	A. Silverberg, J. Staddon and J. L. Walker, Efficient traitor tracing algorithms using list decoding,, in, (2001), 175. doi: 10.1007/3-540-45682-1_11. Google Scholar
[19]	A. Silverberg, J. Staddon and J. L. Walker, Applications of list decoding to tracing traitors,, IEEE Trans. Inform. Theory, 49 (2003), 1312. doi: 10.1109/TIT.2003.810630. Google Scholar
[20]	J. N. Staddon, D. R. Stinson and R. Wei, Combinatorial properties of frameproof and traceability codes,, IEEE Trans. Inform. Theory, 47 (2001), 1042. doi: 10.1109/18.915661. Google Scholar
[21]	D. R. Stinson, T. van Trung and R. Wei, Secure frameproof codes, key distribution patterns, group testing algorithms and related structures,, J. Stat. Plan. Infer., 86 (2000), 595. doi: 10.1016/S0378-3758(99)00131-7. Google Scholar

show all references

References:

[1]	A. Barg, G. R. Blakley and G. A. Kabatiansky, Digital fingerprinting codes: problem statements, constructions, identification of traitors,, IEEE Trans. Inform. Theory, 49 (2003), 852. doi: 10.1109/TIT.2003.809570. Google Scholar
[2]	D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data,, in, (1995), 452. doi: 10.1007/3-540-44750-4_36. Google Scholar
[3]	D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data,, IEEE Trans. Inform. Theory, 44 (1998), 1897. doi: 10.1109/18.705568. Google Scholar
[4]	B. Chor, A. Fiat and M. Naor, Tracing traitors,, in, (1994), 480. Google Scholar
[5]	B. Chor, A. Fiat, M. Naor and B. Pinkas, Tracing traitors,, IEEE Trans. Inform. Theory, 46 (2000), 893. doi: 10.1109/18.841169. Google Scholar
[6]	G. D. Cohen and H. G. Schaathun, Asymptotic overview on separating codes,, Tech. Report 248, (2003). Google Scholar
[7]	G. D. Cohen and H. G. Schaathun, Upper bounds on separating codes,, IEEE Trans. Inform. Theory, 50 (2004), 1291. doi: 10.1109/TIT.2004.828140. Google Scholar
[8]	M. Fernandez, J. Cotrina, M. Soriano and N. Domingo, A note about the identifier parent property in Reed-Solomon codes,, Comput. Security, 29 (2010), 628. doi: 10.1016/j.cose.2009.12.012. Google Scholar
[9]	A. D. Friedman, R. L. Graham and J. D. Ullman, Universal single transition time asynchronous state assignments,, IEEE Trans. Comput., C-18 (1969), 541. doi: 10.1109/T-C.1969.222707. Google Scholar
[10]	H. D. L. Hollmann, J. H. van Lint, J.-P. Linnartz and L. M. G. M. Tolhuizen, On codes with the identifiable parent property,, J. Combin. Theory Ser. A, 82 (1998), 121. doi: 10.1006/jcta.1997.2851. Google Scholar
[11]	H. Jin and M. Blaum, Combinatorial properties for traceability codes using error correcting codes,, IEEE Trans. Inform. Theory, 53 (2007), 804. doi: 10.1109/TIT.2006.889730. Google Scholar
[12]	J. Körner and G. Simonyi, Separating partition systems and locally different sequences,, SIAM J. Discr. Math., 1 (1988), 355. doi: 10.1137/0401035. Google Scholar
[13]	R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition,, Cambridge University Press, (1994). doi: 10.1017/CBO9781139172769. Google Scholar
[14]	M. S. Pinsker and Y. L. Sagalovich, Lower bound on the cardinality of code of automata's states,, Probl. Inform. Transm., 8 (1972), 59. Google Scholar
[15]	I. S. Reed and G. Solomon, Polynomial codes over certain finite fields,, SIAM J. Appl. Math., 8 (1960), 300. doi: 10.1137/0108018. Google Scholar
[16]	Y. L. Sagalovich, Completely separating systems,, Probl. Inform. Transm., 18 (1982), 140. Google Scholar
[17]	Y. L. Sagalovich, Separating systems,, Probl. Inform. Transm., 30 (1994), 105. Google Scholar
[18]	A. Silverberg, J. Staddon and J. L. Walker, Efficient traitor tracing algorithms using list decoding,, in, (2001), 175. doi: 10.1007/3-540-45682-1_11. Google Scholar
[19]	A. Silverberg, J. Staddon and J. L. Walker, Applications of list decoding to tracing traitors,, IEEE Trans. Inform. Theory, 49 (2003), 1312. doi: 10.1109/TIT.2003.810630. Google Scholar
[20]	J. N. Staddon, D. R. Stinson and R. Wei, Combinatorial properties of frameproof and traceability codes,, IEEE Trans. Inform. Theory, 47 (2001), 1042. doi: 10.1109/18.915661. Google Scholar
[21]	D. R. Stinson, T. van Trung and R. Wei, Secure frameproof codes, key distribution patterns, group testing algorithms and related structures,, J. Stat. Plan. Infer., 86 (2000), 595. doi: 10.1016/S0378-3758(99)00131-7. Google Scholar

[1]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[2]	Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[3]	Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[4]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[5]	Janne I. Kokkala, Patric R. J. Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020
[6]	Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543
[7]	Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005
[8]	Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349
[9]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[10]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[11]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[12]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[13]	Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
[14]	Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[15]	Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039
[16]	Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[17]	Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[18]	M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13
[19]	Noam Presman, Simon Litsyn. Recursive descriptions of polar codes. Advances in Mathematics of Communications, 2017, 11 (1) : 1-65. doi: 10.3934/amc.2017001
[20]	Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences