On random coding error exponents of watermarking systems

Watermarking codes are analyzed from an information-theoretic viewpoint as a game between an information hider and an active attacker. While the information hider embeds a secret message (watermark) in a covertext message (typically: text, image, sound, or video stream) within a certain distortion level, the attacker processes the resulting watermarked message, within limited additional distortion, in attempt to invalidate the watermark. For the case where the covertext source is memoryless (or, more generally where there exists some transformation that makes it memoryless), we provide a single-letter characterization of the maximin game of the random coding error exponent associated with the average probability of erroneously decoding the watermark. This single-letter characterization is in effect because if the information hider utilizes a memoryless channel to generate random codewords for every covertext message, the (causal) attacker will maximize the damage by implementing a memoryless channel as well. Partial results for the dual minimax game and the conditions for the existence of a saddle point are also presented