Frameproof Codes

Abstract

Frameproof codes were first introduced by Boneh and Shaw in the context of digital fingerprinting. Variants of these codes have been studied by several authors, and several similar definitions of frameproof codes exist in the literature. The paper considers frameproof codes from a combinatorial point of view, where we define frameproof codes as follows. Let F be a (finite) set, and let $P\subseteq F^\ell$ be a set of words of length $\ell$ over the alphabet F. The set of descendants of P, desc$(P)$, is the set of all words $x\in F^\ell$ such that for all $i\in\{1,2,\ldots ,\ell\}$, the ith component of x agrees with the ith component of some member of P. Let c be an integer such that $c\geq 2$. A c-frameproof code is a subset $C\subseteq F^\ell$ such that for all $P\subseteq C$ with $|P|\leq c$, we have that desc$(P)\cap C= P$. The paper considers the following question: What is the largest cardinality n of a c-frameproof code of length $\ell$, over an alphabet of size q? The paper concentrates on the case when q is large. The paper shows that $n=\ell(q-1)$ in the case when $2\leq \ell\leq c$ and shows that if c=2, then n is approximately $t q^{\lceil \ell/2\rceil}$, where t=1 when $\ell$ is odd and t=2 if $\ell$ is even. The paper establishes improved upper bounds on n by applying techniques from extremal set theory (namely, a generalization of the Erdos--Ko--Rado theorem).