Paper 2009/046

Traceability Codes

Simon R. Blackburn, Tuvi Etzion, and 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 $$ and $$ are fixed integers such that $$ and $$, or such that $$ and $$, there exist infinite families of $$-ary $$-traceability codes of constant rate. These parameters are of interest since the error correcting construction cannot be used to construct $$-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 $$ be a fixed positive integer. The paper shows that there exists a constant $$, depending only on $$, such that a $$-ary $$-traceability code of length $$ contains at most $$ codewords. When $$ is a sufficiently large prime power, a suitable Reed--Solomon code may be used to construct a $$-traceability code containing $$ codewords. So this result may be interpreted as implying that the error correcting construction produces good $$-ary $$-traceability codes of length $$ when $$ is large when compared with $$.