American Institute of Mathematical Sciences

Advanced
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

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]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[2]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[3]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[4]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[5]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[6]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[7]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[8]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[9]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[10]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054
[11]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120
[12]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[13]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[14]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051
[15]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[16]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127
[17]

Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041
[18]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067
[19]

Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123
[20]

Giulia Cavagnari, Antonio Marigonda. Attainability property for a probabilistic target in wasserstein spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 777-812. doi: 10.3934/dcds.2020300

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences