International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tuvi Etzion

Publications

Year
Venue
Title
2009
EPRINT
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$.
2009
EPRINT
Key Predistribution Techniques for Grid-Based Wireless Sensor Networks
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
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
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.