### 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 $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$.

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
Short URL
https://ia.cr/2009/046

CC BY

BibTeX

@misc{cryptoeprint:2009/046,
author = {Simon R.  Blackburn and Tuvi Etzion and Siaw-Lynn 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}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.