Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 94B60; Secondary: 94B65.


    \begin{equation} \\ \end{equation}
  • [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-865.doi: 10.1109/TIT.2003.809570.


    D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data, in "Advances in Cryptology--CRYPTO'95 (Santa Barbara, CA),'' Springer, (1995), 452-465.doi: 10.1007/3-540-44750-4_36.


    D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data, IEEE Trans. Inform. Theory, 44 (1998), 1897-1905.doi: 10.1109/18.705568.


    B. Chor, A. Fiat and M. Naor, Tracing traitors, in "Advances in Cryptology--CRYPTO'94 (Santa Barbara, CA),'' Springer, (1994), 480-491.


    B. Chor, A. Fiat, M. Naor and B. Pinkas, Tracing traitors, IEEE Trans. Inform. Theory, 46 (2000), 893-910.doi: 10.1109/18.841169.


    G. D. Cohen and H. G. Schaathun, Asymptotic overview on separating codes, Tech. Report 248, Dep. Informatics, Univ. Bergen, Norway, 2003.


    G. D. Cohen and H. G. Schaathun, Upper bounds on separating codes, IEEE Trans. Inform. Theory, 50 (2004), 1291-1294.doi: 10.1109/TIT.2004.828140.


    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-635.doi: 10.1016/j.cose.2009.12.012.


    A. D. Friedman, R. L. Graham and J. D. Ullman, Universal single transition time asynchronous state assignments, IEEE Trans. Comput., C-18 (1969), 541-547.doi: 10.1109/T-C.1969.222707.


    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-133.doi: 10.1006/jcta.1997.2851.


    H. Jin and M. Blaum, Combinatorial properties for traceability codes using error correcting codes, IEEE Trans. Inform. Theory, 53 (2007), 804-808.doi: 10.1109/TIT.2006.889730.


    J. Körner and G. Simonyi, Separating partition systems and locally different sequences, SIAM J. Discr. Math., 1 (1988), 355-359.doi: 10.1137/0401035.


    R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition, Cambridge University Press, UK, 1994.doi: 10.1017/CBO9781139172769.


    M. S. Pinsker and Y. L. Sagalovich, Lower bound on the cardinality of code of automata's states, Probl. Inform. Transm., 8 (1972), 59-66.


    I. S. Reed and G. Solomon, Polynomial codes over certain finite fields, SIAM J. Appl. Math., 8 (1960), 300-304.doi: 10.1137/0108018.


    Y. L. Sagalovich, Completely separating systems, Probl. Inform. Transm., 18 (1982), 140-146.


    Y. L. Sagalovich, Separating systems, Probl. Inform. Transm., 30 (1994), 105-123.


    A. Silverberg, J. Staddon and J. L. Walker, Efficient traitor tracing algorithms using list decoding, in "Advances in Cryptology--ASIACRYPT 2001 (Gold Coast, Australia),'' Springer, (2001), 175-192.doi: 10.1007/3-540-45682-1_11.


    A. Silverberg, J. Staddon and J. L. Walker, Applications of list decoding to tracing traitors, IEEE Trans. Inform. Theory, 49 (2003), 1312-1318.doi: 10.1109/TIT.2003.810630.


    J. N. Staddon, D. R. Stinson and R. Wei, Combinatorial properties of frameproof and traceability codes, IEEE Trans. Inform. Theory, 47 (2001), 1042-1049.doi: 10.1109/18.915661.


    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-617.doi: 10.1016/S0378-3758(99)00131-7.

  • 加载中

Article Metrics

HTML views() PDF downloads(89) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint