Improved Constructions of Frameproof Codes

Abstract

Frameproof codes are used to preserve the security in the context of coalition when fingerprinting digital data. Let $M_{c,l}(q)$ be the largest cardinality of a $q$-ary $c$-frameproof code of length $l$ and $R_{c,l}={\lim }_{q\to \infty }{M}_{c,l}(q)/q^{\lceil l/c\rceil }$. It has been determined by Blackburn that $R_{c,l}=1$ when $l\equiv 1(\mathrm{mod}c)$, $R_{c,l}=2$ when $c=2$ and $l$ is even, and $R_{3,5}=5/3$. In this paper, we give a recursive construction for $c$-frameproof codes of length $l$ with respect to the alphabet size $q$. As applications of this construction, we establish the existence results for $q$-ary $c$-frameproof codes of length $c+2$ and size $\frac{c+2}{c}(q-1{)}^2+1$ for all odd $q$ when $c=2$ and for all $q\equiv 4(\mathrm{mod}6)$ when $c=3$. Furthermore, we show that $R_{c,c+2}=(c+2)/c$ meeting the upper bound given by Blackburn, for all integers $c$ such that $c+1$ is a prime power.

6 pages, to appear in Information Theory, IEEE Transactions on