Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Abstract

Let $\mathcal{C}$ be a $q$-ary code of length $n$ and size $M$, and $\mathcal{C}(i)=\{\mathbf{c}(i)|\mathbf{c}=(\mathbf{c}(1),\mathbf{c}(2),\dots ,\mathbf{c}(n){)}^T\in \mathcal{C}\}$ be the set of $i$th coordinates of $\mathcal{C}$. The descendant code of a sub-code ${\mathcal{C}}^{{}^{\prime }}\subseteq \mathcal{C}$ is defined to be ${\mathcal{C}}^{{}^{\prime }}(1)\times {\mathcal{C}}^{{}^{\prime }}(2)\times \cdots \times {\mathcal{C}}^{{}^{\prime }}(n)$. In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or $t$-MIPPC$(n,M,q)$, so that given the descendant code of any sub-code ${\mathcal{C}}^{{}^{\prime }}$ of a multimedia $t$-IPP code $\mathcal{C}$, one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in ${\mathcal{C}}^{{}^{\prime }}$. We first derive a general upper bound on the size $M$ of a multimedia $t$-IPP code, and then investigate multimedia $3$-IPP codes in more detail. We characterize a multimedia $3$-IPP code of length $2$ in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia $3$-IPP code of length $2$, and construct several infinite families of (asymptotically) optimal multimedia $3$-IPP codes of length $2$.

7 pages, submitted to IEEE transction on information theory