Probabilistic existence results for separable codes

Abstract

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, $\overline{t}$-separable codes lie somewhere between $t$-frameproof and $(t-1)$-frameproof codes: all $t$-frameproof codes are $\overline{t}$-separable, and all $\overline{t}$-separable codes are $(t-1)$-frameproof. Results for frameproof codes show that (when $q$ is large) there are $q$-ary $\overline{t}$-separable codes of length $n$ with approximately $q^{\lceil n/t\rceil }$ codewords, and that no $q$-ary $\overline{t}$-separable codes of length $n$ can have more than approximately $q^{\lceil n/(t-1)\rceil }$ codewords. The paper provides improved probabilistic existence results for $\overline{t}$-separable codes when $t\ge 3$. More precisely, for all $t\ge 3$ and all $n\ge 3$, there exists a constant $\kappa$ (depending only on $t$ and $n$) such that there exists a $q$-ary $\overline{t}$-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 $\overline{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 $\overline{2}$-separable code of length $n$ can contain at most $\frac{3}{2}{q}^{2\lceil n/3\rceil }-\frac{1}{2}{q}^{\lceil n/3\rceil }$ codewords, and that codes with at least $\kappa q^{2n/3}$ codewords exist. So optimal $\overline{2}$-separable codes behave neither like $2$-frameproof nor $1$-frameproof codes. Also, the Gao--Ge bound is strengthened to show that a $q$-ary $\overline{2}$-separable code of length $n$ can have at most \[ q^{\lceil 2n/3\rceil}+\tfrac{1}{2}q^{\lfloor n/3\rfloor}(q^{\lfloor n/3\rfloor}-1) \] codewords.

16 pages. Typos corrected and minor changes since last version. Accepted by IEEE Transactions on Information Theory

References in corpus (1)

• Multimedia IPP Codes with Efficient Tracing

Cited by in corpus (6)

• Signature codes for weighted binary adder channel and multimedia fingerprinting
• On capacities of the two-user union channel with complete feedback
• Bounds and Constructions for $\overline{3}$-Strongly Separable Codes with Length $3$
• Probabilistic Existence Results for Parent-Identifying Schemes
• Improved Lower Bounds for Secure Codes and Related Structures
• A note on $\overline{2}$-separable codes and $B_2$ codes