Simon R. Blackburn (2003) Frameproof Codes. SIAM Journal on Discrete Mathematics, 16 (3). pp. 499-510 . ISSN 0895-4801
Full text access: Open
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).
This is a Published version This version's date is: 01/01/2003 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/fbd01240-eff5-da63-cfb2-eff3854890de/1/
Deposited by () on 24-Jan-2011 in Royal Holloway Research Online.Last modified on 24-Jan-2011
(C) 2003 Society for Industrial and Applied Mathematics whose permission to mount this version for private study and research is acknowledged.