International Association for Cryptologic Research

International Association
for Cryptologic Research


Siaw-Lynn Ng


Traceability Codes
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$.
Prolific Codes with the Identifiable Parent Property
Let C be a code of length n over an alphabet of size q. A word d is a descendant of a pair of codewords x,y if d_i lies in \{x_i ,y_i \} for 1 <= i <= n. A code C is an identifiable parent property (IPP) code if the following property holds. Whenever we are given C and a descendant d of a pair of codewords in C, it is possible to determine at least one of these codewords. The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all q^n words are descendants. It is shown that linear prolific IPP codes fall into three infinite (`trivial') families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds.


Simon R. Blackburn (2)
Tuvi Etzion (2)