## IACR paper details

Title | Traceability Codes |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2009 |
---|

URL | http://eprint.iacr.org/2009/046 |
---|

Author | Simon R. Blackburn |
---|

Author | Tuvi Etzion |
---|

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

Search for the paper

@misc{eprint-2009-18221,
title={Traceability Codes},
booktitle={IACR Eprint archive},
keywords={traitor tracing, combinatorial cryptography},
url={http://eprint.iacr.org/2009/046},
note={ s.blackburn@rhul.ac.uk 14271 received 27 Jan 2009},
author={Simon R. Blackburn and Tuvi Etzion and Siaw-Lynn Ng},
year=2009
}

Download a complete BibTeX file.