Identification in the presence of side information with application to watermarking

Watermarking codes are analyzed from an information-theoretic viewpoint as identification codes with side information that is available at the transmi tter only or at both ends. While the information hider embeds a secret mess age (watermark) in a covertext message (typically, text, image, sound, or v ideo stream) within a certain distortion level, the attacker, modeled here as a memoryless channel, processes the resulting watermarked message (withi n limited additional distortion) in attempt to invalidate the watermark. In most applications of watermarking codes, the decoder need not carry out fu ll decoding, as in ordinary coded communication systems, but only to test w hether a watermark at all exists and if so, whether it matches a particular hypothesized pattern. This fact motivates us to view the watermarking prob lem as an identification problem, where the original covertext source serve s as side information. In most applications, this side information is avail able to the encoder only, but sometimes it can be available to the decoder as well. For the case where the side information is available at both encod er and decoder, we derive a formula for the identification capacity and als o provide a characterization of achievable error exponents. For the case wh ere side information is available at the encoder only, we derive upper and lower bounds on the identification capacity. All characterizations are obta ined as single-letter expressions.