so, it looks like watermarking is a thing that is coming back to its (controversial) life. the idea of watermarking is to enable content producers to mark their own contents so as to track where those contents are being consumed without introducing too much of disruption. one of the simplest watermarking techniques i run into quite often is on a plan with their entertainment system; when you watch a movie on an airplane, you often notice the airline code (e.g. “DL” in the case of Delta) embroiled on the screen once a while. i presume the heightened interest in watermarking is because we want to ensure we can detect whether a piece of content we see on the internet was generated by a particular machine learning model or by a particular artist. why this is necessary and important is a topic for a whole new blog post in the future (not today).
in this blog post, i will write out what kind of conditions i believe any watermarking technique should satisfy, in order for watermarking to be useful and effective.
let $x \in \mathcal{X}$ be the observation we want to watermark with a marker $m \in \mathcal{M}$. we will use $F: \mathcal{X} \times \mathcal{M} \to \mathcal{X}$ as a watermarking function. the first condition $F$, called perceptual Indistinguishability, needs to satisfy is
$$d_{\mathrm{perceptual}}(x, F(x, m)) \leq \delta,$$
which states that the percetual difference between $x$ and its watermarked version $F(x, m)$ must be very small (smaller than $\delta$). that is, we shouldn’t be able to distinguish between the original and watermarked observations.
the second condition is marker verifiability. there must be a tractable way (i will get to why it needs to be tractable shortly when discussing the third condition) to tell whether a certain marker was applied. given a verification function $G: \mathcal{X} \times \mathcal{M} \to \left\{0, 1\right\}$, this can be written down as
$$\frac{\mathrm{Pr}(G(F(x,m), m)=1)}{\mathrm{Pr}(G(F(x,m), m)=0)} > 1$$
and
$$\frac{\mathrm{Pr}(G(F(x,m), m)=1)}{\mathrm{Pr}(G(F(x,m), m’)=1)} > 1~\forall m \neq m’.$$
that is, $G$ must be able to tell whether the watermark was applied and which watermark was applied as well.
the third condition, to which i will refer as marker irreversibility, implies that a watermarked version cannot easily be reverted to the original version. this is as important as the first two conditions, but is often overlooked, which makes many watermarking techniques pretty much obsolete. for instance, you have probably noticed that pirated TV shows often have top-5% of each frame cut off; this is done in order to remove the TV station mark, which is sometimes used as a watermark to track whether a TV show from that particular TV station was pirated.
we can write this condition in the context of computational complexity. for instance, we want to ensure that the inverse watermarking function $F^{-1}: \mathcal{X} \times \mathcal{M} \to \mathcal{X}$ takes exponential time w.r.t. the sizes of the watermarked object $F(x, m) \in \mathcal{X}$ and the marker $m \in \mathcal{M}$, i.e., $O(e^{\max\{|F(x,m)|, |m|\}})$.
then, we must think a bit about what this complexity should be; is exponential complexity enough? an interesting observation here is that what is enough is relative to the second condition on the marker verifiability above. if the computational complexities of verification $G$ and removal $F^{-1}$ were of the same order, e.g. both take linear time $O(\max\{|F(x,m)|, |m|\})$, watermarking is a bit of a moot point, since anyone who wants to break tracking by watermarking would simply remove the marker from the content before watching and forwarding it to others, while spending the same amount of computation as any verify would.
in other words, this condition of marker irreversibility is defined w.r.t. the condition of marker verifiability. that is, the marker removal and verification must reside in different levels in the polynomial hierarchy, with the verification on a lower level.
in summary, there are three conditions that must be met by any reasonable watermarking technique:
- perceptual indistinguishability: a watermarked object must be (almost) perceptually indistinguishable from the original object.
- marker verifiability: we must be able to tractably verify a given object was watermarked with a particular marker and not with another.
- marker irreversibility: it must be tractable for anyone to remove the marker from a watermarked object to obtain the original object.
up until this point, i have assumed the marker $m$ is openly available, as in the airline marker on movies on airplanes. this is the reason why we wanted to ensure that marker reversal was significantly more complex than marker verification. if we however can (it’s a big CAN) keep the marker $m$ secret, it becomes trivial to separate marker verification and reversibility in terms of computational complexity, as the marker space can be made arbitrarily large. this is however a bit unrealistic, and it may be that the marker will leak via multiple watermarked objects eventually.
based on these conditions, let’s examine the airline’s watermarking strategy:
- perceptual indistinguishability: largely satisfied ✓. those airline markers only show up quite rarely throuhgout the whole show that it doesn’t really bother me or many viewers.
- marker verifiability: largely satisfied ✓. not sure how to implement it effectively off the top of my head, but it feels pretty straightforward to do so with rudimentary image processing tools.
- marker irreversibility: not satisfied ×. it’s quite trivial to remove such a marker especially with the recent advances in machine learning for image processing and generation, which can be done in almost linear time w.r.t. the length of the show.
so, it’s not really a great watermarking technology from the technical perspective, although simplicity of such an approach is quite attractive from both business and maintenance perspectives. if i were a hollywood studio executive, i would ask for a stronger watermarking strategy, as any leak affects my studio much more so than the airline via which the show was leaked.
that said, how does your novel watermarking algorithm fare?