## CryptoDB

### Siaw-Lynn Ng

#### Publications

**Year**

**Venue**

**Title**

2009

EPRINT

Traceability Codes
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$.

2007

EPRINT

Prolific Codes with the Identifiable Parent Property
Abstract

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.

#### Coauthors

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