Welcome to the resource topic for
**2009/046**

**Title:**

Traceability Codes

**Authors:**
Simon R. Blackburn, Tuvi Etzion, Siaw-Lynn Ng

**Abstract:**

Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used in traitor tracing schemes to protect digital content. A k-traceability code is used in a scheme to trace the origin of digital content under the assumption that no more than k users collude. It is well known that an error correcting code of high minimum distance is a traceability code. When does this `error correcting constructionâ€™ produce good traceability codes? The paper explores this question. The paper shows (using probabilistic techniques) that whenever k and q are fixed integers such that k\geq 2 and q\geq k^2-\lceil k/2\rceil+1, or such that k=2 and q=3, there exist infinite families of q-ary k-traceability codes of constant rate. These parameters are of interest since the error correcting construction cannot be used to construct k-traceability codes of constant rate for these parameters: suitable error correcting codes do not exist because of the Plotkin bound. This answers a question of Barg and Kabatiansky from 2004. Let \ell be a fixed positive integer. The paper shows that there exists a constant c, depending only on \ell, such that a q-ary 2-traceability code of length \ell contains at most cq^{\lceil \ell/4\rceil} codewords. When q is a sufficiently large prime power, a suitable Reedâ€“Solomon code may be used to construct a 2-traceability code containing q^{\lceil \ell/4\rceil} codewords. So this result may be interpreted as implying that the error correcting construction produces good q-ary 2-traceability codes of length \ell when q is large when compared with \ell.

**ePrint:**
https://eprint.iacr.org/2009/046

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .