The ease with which digital data can be duplicated and distributed over the media and the Internethas raised many concerns about copyright infringement.In many situations, multimedia data (e.g., images, music, movies, etc) are illegally circulated, thus violatingintellectual property rights. In an attempt toovercome this problem, watermarking has been suggestedin the literature as the most effective means for copyright protection and authentication. Watermarking is the procedure whereby information (pertaining to owner and/or copyright) is embedded into host data, such that it is:(i) hidden, i.e., not perceptually visible; and(ii) recoverable, even after a (possibly malicious) degradation of the protected work. In this thesis,we prove some theoretical results that establish the fundamental limits of a general class of watermarking schemes.

The main focus of this thesis is the problem ofjoint watermarking and compression of images, whichcan be briefly described as follows: due to bandwidth or storage constraints, a watermarked image is distributed in quantized form, using $R_Q$ bits per image dimension, and is subject to some additional degradation (possibly due to malicious attacks). The hidden message carries $R_W$ bits per image dimension. Our main result is the determination of the region of allowable rates $(R_Q, R_W)$, such that: (i) an average distortion constraint between the original and the watermarked/compressed image is satisfied, and (ii) the hidden message is detected from the degraded image with very high probability. Using notions from information theory, we prove coding theorems that establish the rate regionin the following cases: (a) general i.i.d. image distributions,distortion constraints and memoryless attacks, (b) memoryless attacks combined with collusion (for fingerprinting applications), and (c) general---not necessarily stationary or ergodic---Gaussian image distributions and attacks, and average quadratic distortion constraints. Moreover, we prove a multi-user version of a result by Costa on the capacity of a Gaussian channel with known interference at the encoder.