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̅-separable codes lie somewhere between t-frameproof and (t - 1)-frameproof codes: all t-frameproof codes are t̅-separable, and all t̅-separable codes are (t - 1)-frameproof. Results for frameproof codes show that (when q is large) there are q-ary t̅-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-l)] codewords. This paper provides improved probabilistic existence results for t-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̅-separable code of length n with at least κ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̅-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̅-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 κ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/2 q^[n/3] (q^[n/3] -1).