Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate

Multimedia fingerprinting codes are used to protect digital content from illegal copying and redistribution. The key idea of this technique is to embed a unique signal, called watermark, into every copy, so that it can be tracked to its buyer [2, 3]. Watermarks should be able to protect the dealer from collusion attack, when a coalition of dishonest users (pirates) construct a new file, for example, by averaging their copies of the same content. By gathering a big enough coalition it is possible to sufficiently decrease the impact of each individual fingerprint, which makes it hard for the dealer to identify the pirates. In papers [4, 5] the authors propose to use separable (or signature) codes to track all members of the coalition.

A model of multimedia fingerprinting with an adversarial noise was proposed in [6], i.e. the coalition of dishonest users can add some noise to the content in order to hide their fingerprints. In [7] it was shown that there are no multimedia codes resistant to a general linear attack and an adversarial noise. However, in [1] the authors proved that for the most common case of averaging attack one can construct multimedia codes with a non-vanishing rate. We continue their research and prove a new lower bound on the rate, which has the same order as an upper bound. A detailed survey of state-of-the-art results can be found in [8].

The rest of the paper is structured as follows. In Section 2 we introduce the required notation and definitions and formally describe the problem. Our main result is proved in Section 3. Section 4 concludes the paper and discusses some open problems.

Vectors are denoted by bold letters, such as $\bm{x}$, and the $i$th entry is referred to as $x_{i}$. The set of integers $\{1,\,2,\,\ldots,\,M\}$ is abbreviated by $[M]$. The sign $\lVert\cdot\rVert$ stands for the Euclidean norm. A support $supp(\bm{x})$ of a vector $\bm{x}$ is a set of such coordinates $i$ that $x_{i}\neq 0$. Scalar (dot) product of vectors $\bm{x}$ and $\bm{y}$ is denoted as $\langle\bm{x},\,\bm{y}\rangle$, greatest common divisor of integers $a$ and $b$ is referred to as $(a,b)$. For a given binary $n\times M$ matrix $H$ with columns $\bm{h}_{1},\,\ldots,\,\bm{h}_{M}$ and set $I\subset[M]$ introduce notation for a result of averaging attack

A binary entropy function $h(x)$ is defined as follows

Suppose that multimedia content is represented by a vector $\bm{x}\in\mathbb{R}^{N}$, which is being sold to $M$ users. Vector $\bm{x}$ is often called a host signal. To protect the content from unauthorized copying the dealer constructs a set of watermarks $\bm{w}_{1},\,\ldots,\,\bm{w}_{M}$, which are also called fingerprints. The dealer fixes $n$ orthonormal vectors $\bm{f}_{1},\,\ldots,\,\bm{f}_{n}$ of length $N,\,\bm{f}_{i}\in\mathbb{R}^{N}$ and forms watermarks $\bm{w}_{i}$ as linear combinations of $\bm{f}_{j}$ with binary coefficients $h_{ij}\in\{0,\,1\}$

Then watermarks are added to the host signal to obtain a final copy $\bm{y}_{i}$ for the $i$-th user

We assume that $\lVert\bm{w}_{i}\rVert\ll\lVert\bm{x}\rVert$, so the added watermark doesn’t change the content much.

A coalition of dishonest users $I\subset[M]$ may come together to forge a new copy and redistribute it among other users. They can apply a linear attack, i.e., create a new copy $\bm{y}$ as a linear combination of their copies. In addition, they may add a noise vector $\bm{\varepsilon}$, $\lVert\bm{\varepsilon}\rVert\ll\lVert\bm{x}\rVert$, to make it harder for the dealer to identify them.

where $\lambda_{i}>0$ for each dishonest user in $I$ exactly participates in the attack, $\lambda_{i}\in\mathbb{R}$ and $\sum_{i\in I}\lambda_{i}=1$ to ensure the multimedia content $\bm{x}$ not be changed. Especially in averaging attack, the last condition is $\lambda_{i}=1/\lvert I\rvert$ for every $i\in I$ and it implies that

Note that

therefore, $\bm{y}$ is close enough to the original signal $\bm{x}$.

In order to find the coalition of dishonest users based on the forged copy $\bm{y}$, the dealer evaluates

where $e_{k}=\langle\bm{\varepsilon},\bm{f}_{k}\rangle$, and forms a syndrome vector $\bm{S}=(s_{1},\,\ldots,\,s_{n})$. The syndrome vector $\bm{S}$ can be equivalently defined through the matrix equation

where $\Lambda=(\lambda_{1},\,\ldots,\,\lambda_{M})$, $\lambda_{i}=0$ for $i\notin I$, and $\bm{e}=(e_{1},\,\ldots,\,e_{n})$, $\lVert\bm{e}\rVert\leq\lVert\bm{\varepsilon}\rVert$.

The dealer wants to design a matrix $H$ in such a way, that by observing $\bm{S}$ he always can find the support $supp(\bm{\Lambda})$ if the size of the coalition $I$ is at most $t$. The following definition for a noiseless scenario was introduced in [6].

Denote the maximal cardinality and the maximal rate of $t$-MDF code of length $n$ as $M(n,t)$ and $R(n,t)=n^{-1}\log_{2}M(n,t)$. Denote by $R^{*}(t)$ and $R_{*}(t)$ an upper and a lower limits of $R(n,t)$ as $n\to\infty$. It is known that

The upper bound of (2) can be derived from an upper bound for a binary adder channel from [9]. The lower bound is based on the following observation from [6]. If any $2t$ columns of a binary matrix $H$ are independent over the field of real numbers $\mathbb{R}$, then $H$ is a $t$-MDF code. Since parity check matrices of binary codes with a distance $d>2t$ poses this property, application of Goppa or BCH codes gives an explicit construction with a rate $R_{*}(t)\geq 1/t$[6]. An improved lower bound $\Omega\left(\frac{\log_{2}t}{t}\right)$ can be derived from the results of the paper [10], where the authors proved the existence of binary $n\times M$ matrices, $n^{-1}\log_{2}M=\Omega(\log_{2}t/t)$, such that any $2t$ columns are independent over the field $\mathds{Z}_{p}$, $p>2t$. We note that the latter result was proved with a probabilistic method, i.e. it’s not explicit.

Now we discuss a noisy scenario. In [7] the authors defined $(t,\delta)$-light complete traceability multimedia digital fingerprinting codes and proved that they don’t exist. Informally, if some coefficient $\lambda_{i}$ is sufficiently small, then it is possible to compensate the signal of $i$th user by the noise so that it would be impossible to identify this user. However, for the case of averaging attacks, when all non-zero coefficients $\lambda_{i}$ are equal, the situation is different. Let us give the corresponding definition from [1].

In other words, Euclidean distance between vectors $\sigma(H\mid I_{1})$ and $\sigma(H\mid I_{2})$, generated by different coalitions $I_{1}$ and $I_{2}$, $\lvert I_{1}\rvert,\lvert I_{2}\rvert\leq t$, should be big, i.e.

Define codes for the case of noise vectors with a bounded cardinality of their support.

Equivalently, the number of different coordinates of vectors $\sigma(H\mid I_{1})$ and $\sigma(H\mid I_{2})$, generated by distinct coalitions $I_{1}$ and $I_{2}$, $\lvert I_{1}\rvert,\lvert I_{2}\rvert\leq t$, should be big, i.e.

Denote the maximal cardinality of Euclidean and Hamming light complete traceability codes of length $n$ by $M_{E}(n,t,\delta)$ and $M_{H}(n,t,T)$ respectively. Define the rates of these codes as follows

In the following proposition we show an obvious connection between these two families of codes.

In [1] it was proved that $\liminf_{n\to\infty}R_{E}(n,t,\delta)\geq\Omega(1/t)$ for constant $\delta$. An upper bound is the same as in the noiseless case, $\limsup_{n\to\infty}R_{E}(n,t,\delta)\leq\frac{\log_{2}t}{2t}(1+o(1))$, since the proof works for an averaging attack. Therefore, there is a $\Theta(\log_{2}t)$ gap between the lower and upper bound. We eliminate this gap in the next section.

In this section we prove

Combining Theorem 1 and Proposition 1 we obtain the following

For the case of small noise $\delta=o(\sqrt{n})$ and $n\to\infty$ a new lower bound has the following form

It improves the previous lower bound $\Omega(1/t)$ and has the same order $\Theta(\log_{2}t/t)$ as the upper bound. However, the new bound is not explicit, i.e. there is no effective encoding or decoding algorithm for a new code.

In this paper we proved a new lower bound on the rate of Euclidean $(t,\delta)$-light complete traceability codes, which shows that the optimal rate has order $\Theta(\log_{2}t/t)$. However, the proof uses probabilistic arguments and does not provide an explicit construction with efficient encoding and decoding algorithms. A natural open problem is to design a code with an optimal rate and efficient decoding algorithm.

Coefficient $\lambda_{i}$ shows what proportion of the original content was contributed by user $i$ into an illegal copy. It is natural that if the contribution of user $i$ was very small then it will be hard for a dealer to identify such user. So, another open task is to design a code capable of finding all members of a coalition for an adversarial noise and linear attack, whose coefficients $\lambda_{i}$ are lower bounded by some constant, i.e. all users, whose contribution was big enough.

The reported study was supported by RFBR and National Science Foundation of Bulgaria (NSFB), project number 20-51-18002, and by RFBR, grant no. 20-01-00559.