Title:Bounds and Algorithms for Frameproof Codes and Related Combinatorial Structures

Abstract:In this paper, we study upper bounds on the minimum length of frameproof codes introduced by Boneh and Shaw to protect copyrighted materials. A $q$-ary $(k,n)$-frameproof code of length $t$ is a $t \times n$ matrix having entries in $\{0,1,\ldots, q-1\}$ and with the property that for any column $\mathbf{c}$ and any other $k$ columns, there exists a row where the symbols of the $k$ columns are all different from the corresponding symbol (in the same row) of the column $\mathbf{c}$. In this paper, we show the existence of $q$-ary $(k,n)$-frameproof codes of length $t = O(\frac{k^2}{q} \log n)$ for $q \leq k$, using the Lovász Local Lemma, and of length $t = O(\frac{k}{\log(q/k)}\log(n/k))$ for $q > k$ using the expurgation method. Remarkably, for the practical case of $q \leq k$ our findings give codes whose length almost matches the lower bound $\Omega(\frac{k^2}{q\log k} \log n)$ on the length of any $q$-ary $(k,n)$-frameproof code and, more importantly, allow us to derive an algorithm of complexity $O(t n^2)$ for the construction of such codes.