Universal Decoding of Watermarks Under Geometric Attacks

Pierre Moulin
University of Illinois
Beckman Inst., Coord. Sci. Lab and ECE Dept.
405 N. Mathews Ave., Urbana, IL 61801
Email: moulin@ifp.uiuc.edu


Designing watermarking codes that can withstand geometric and other
desynchronization attacks is a notoriously difficult problem. 
One may ask whether these difficulties are due to limitations of current 
codes, or rather to fundamental limitations on achievable performance.
This problem was addressed in our recent ISIT paper in the case of
host signals defined over finite alphabets, and is extended to
the Gaussian case here. The attack channel is modeled as the cascade
of an AWGN channel and a smooth, invertible mapping 
$T_{\theta}, \theta \in \Theta_n$, representing the geometric attack. 

The decoder does not know the value of $\theta$. We adopt a random-coding 
strategy based on the Erez-Zamir lattice coding scheme and quantify 
the performance loss (in terms of probability of error exponents)
due to lack of knowledge of $\theta$ by the receiver. 

Our first result is that provided the parameter set $\Theta_n$ is not 
too complex (e.g., $\Theta_n$ is a finite set whose cardinality
grows subexponentially in $n$, or the family of mappings satisfies 
a certain smoothness condition), geometric attacks cause 
no performance loss under the specified model. In other words, 
the random codes used are universal against geometric attacks.
The next question is what is the structure of the universal decoders.

We show that generalized maximum likelihood decoders are generally
suboptimal, unlike the generalized normalized correlation decoder
which is universal. Finally, the theory is extended to the case 
where the noise distribution itself is unknown to the decoder.