Probabilistic Existence Results for Separable Codes

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, (t) over bar -separable codes lie somewhere between t -frameproof and (t - 1)-frameproof codes: all t -frameproof codes are t-separable, and all (t) over bar -separable codes are (t -1)-frameproof. Results for frameproof codes show that (when q is large) there are q-ary (t) over bar -separable codes of length n with approximately q([n/t]) codewords, and that no q-ary t-separable codes of length n can have more than approximately q([n/(t-1)]) codewords. This paper provides improved probabilistic existence results for (t) over bar -separable codes when t >= 3. More precisely, for all t >= 3 and all n >= 3, there exists a constant. (depending only on t and n), such that there exists a q-ary (t) over bar -separable code of length n with at least kappa q(n/(t-1)) codewords for all sufficiently large integers q. This shows, in particular, that the upper bound [derived from the bound on (t -1)-frameproof codes] on the number of codewords in a (t) over bar -separable code is realistic. The results above are more surprising after examining the situation when t = 2. Results due to Gao and Ge show that a q-ary (2) over bar -separable code of length n can contain at most 3/2q(2[n/3]) - 1/2q([n/3]) codewords, and that codes with at least kappa q(2n/3) codewords exist. Thus, optimal 2-separable codes behave neither like two-frameproof nor one-frameproof codes. This paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a q-ary 2-separable code of length n is at most q([2n/3]) + 1/2q([n/3])(q([n/3]) - 1).