Paper 2009/046
Traceability Codes
Simon R. Blackburn, Tuvi Etzion, and SiawLynn 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 ReedSolomon 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$.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 traitor tracingcombinatorial cryptography
 Contact author(s)
 s blackburn @ rhul ac uk
 History
 20090129: received
 Short URL
 https://ia.cr/2009/046
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/046, author = {Simon R. Blackburn and Tuvi Etzion and SiawLynn Ng}, title = {Traceability Codes}, howpublished = {Cryptology ePrint Archive, Paper 2009/046}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/046}}, url = {https://eprint.iacr.org/2009/046} }