Bounds and Algorithms for Frameproof Codes and Related Combinatorial Structures

In this paper, we study upper bounds on the minimum length of frameproof codes introduced by Boneh and Shaw [3] to protect copyrighted materials. A q-ary (k,n)-frameproof code of length t is a t×n matrix having entries in {0,1,…,q−1} and with the property that for any column 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 c. In this paper, we show the existence of q-ary (k,n)-frameproof codes of length $t = O\left( {\frac{{{k^2}}}{q}\log n} \right)$ for q ≤ k, using the Lovász Local Lemma, and of length $t = O\left( {\frac{{{k^2}}}{{\log \left( {q/k} \right)}}\log \left( {n/k} \right)} \right)$ for q > k using the expurgation method. Remarkably, for the practical case of q ≤ k our findings give codes whose length almost matches the lower bound $\Omega \left( {\frac{{{k^2}}}{{q\log k\log n}}} \right)$ on the length of any q-ary (k,n)-frameproof code and, more importantly, allow us to derive an algorithm of complexity O(tn
²
) for the construction of such codes.