## CryptoDB

### Tuvi Etzion

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

2009

EPRINT

Key Predistribution Techniques for Grid-Based Wireless Sensor Networks
Abstract

We consider symmetric key predistribution in grid-based wireless sensor networks. Networks consisting of wireless sensor nodes arranged in a grid pattern have many useful applications, including environmental monitoring and agribusiness. The structured physical distribution of nodes in such networks facilitates efficient distribution of keys to the nodes prior to deployment. It has been shown that combinatorial objects known as distinct-difference configurations (DDCs) can be used to construct effective key predistribution schemes (KPSs) for grid-based networks. In this paper we observe that the regular topology of a grid-based network enables an efficient trade-off between the connectivity, resilience and storage requirements of a KPS, and we discuss the balancing of these properties to suit application requirements. We then show how recent results on the construction of DDCs can be used to produce KPSs that achieve the desired balance, and we provide explicit algorithms for the instantiation of these schemes.

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.

2007

EPRINT

A Bound on the Size of Separating Hash Families
Abstract

The paper provides an upper bound on the size of a (generalised)
separating hash family, a notion introduced by Stinson, Wei and
Chen. The upper bound generalises and unifies several previously known
bounds which apply in special cases, namely bounds on perfect hash
families, frameproof codes, secure frameproof codes and separating
hash families of small type.

#### Coauthors

- Simon R. Blackburn (4)
- Keith M. Martin (1)
- Siaw-Lynn Ng (2)
- Maura B. Paterson (1)
- Douglas R. Stinson (1)
- Gregory M. Zaverucha (1)