The Gaussian watermarking game

Watermarking models a copyright protection mechanism where an original source sequence or "covertext" is modifled before distribution to the public in order to embed some extra information. The embedding should be transparent (i.e., the modified data sequence or "stegotext" should be similar to the covertext) and robust (i.e., the extra information should be recoverable even if the stegotext is modified further, possibly by a malicious "attacker"). We compute the coding capacity of the watermarking game for a Gaussian covertext and squared-error distortions. Both the public version of the game (covertext known to neither attacker nor decoder) and the private version of the game (covertext unknown to attacker but known to decoder) are treated. While the capacity of the former cannot, of course, exceed the capacity of the latter, we show that the two are, in fact, identical. These capacities depend critically on whether the distortion constraints are required to be met in expectation or with probability one. In the former case, the coding capacity is zero, whereas in the latter it coincides with the value of related zero-sum dynamic mutual informations games of complete and perfect information. We also compute the capacity when the attacker is restricted to additive attacks. This capacity turns out to be strictly larger than the watermarking capacity, thus demonstrating that additive attacks are suboptimal. In fact, under the additive attack restriction, capacity turns out to coincide with the capacity of Costa's model for "writing on dirty paper," thus demonstrating that in Costa's model, the independent and identically distributed (i.i.d.) Gaussian "noise" is the most malevolent power-limited "noise." Additionally, Costa's observation that in the presence of i.i.d. Gaussian "noise," an i.i.d. Gaussian "dirt" process that is noncausally known to the transmitter (but not receiver) does not reduce capacity, is extended here to general ergodic "dirt" and to stationary (but not necessarily white) Gaussian "noise." Contrary to the average power limited jamming game, where the analysis of a modified (saddle-point achieving) white Gaussian jammer suffices to prove the converse, the watermarking game does not have a memoryless saddle-point, and our proof of the converse requires the analysis of an attacker that depends on the entire stegotext sequence (but not otherwise on the encoder). This dependence must be carefully controlled to guarantee that the choice of the attacking strategy will asymptotically not reveal any information about the embedded message. The proof of the converse exploits only the ergodicity and the second-order properties of the covertext, thus allowing for the characterization of the memoryless Gaussian covertext as the covertext that has the highest watermarking capacity among all finite fourth-moment ergodic covertexts of a given second moment.