Frameproof Codes
Author:
- Simon R. BlackburnSBSimon R. Blackburn
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 16 (3) , 499-510
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).
Keywords
This publication has 11 references indexed in Scilit:
- Combinatorial properties of frameproof and traceability codesIEEE Transactions on Information Theory, 2001
- Efficient constructions of frameproof codesElectronics Letters, 2000
- Dynamic Traitor Tracing1999
- Combinatorial Properties and Constructions of Traceability Schemes and Frameproof CodesSIAM Journal on Discrete Mathematics, 1998
- Shadow bounds for self-dual codesIEEE Transactions on Information Theory, 1998
- Tracing Traitors1994
- Erdös–Ko–Rado Theorem—22 Years LaterSIAM Journal on Algebraic Discrete Methods, 1983
- SETS OF INDEPENDENT EDGES OF A HYPERGRAPHThe Quarterly Journal of Mathematics, 1976
- A simple proof of the Erdös-Chao Ko-Rado theoremJournal of Combinatorial Theory, Series B, 1972
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETSThe Quarterly Journal of Mathematics, 1961