Block_QIM_Watermarking_Games.pdf
(
869 KB
)
Pobierz
591030981 UNPDF
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
293
Block QIM Watermarking Games
Pierre Moulin
, Fellow, IEEE
, and Anil Kumar Goteti
Abstract—
While binning is a fundamental approach to blind
data embedding and watermarking, an attacker may devise
various strategies to reduce the effectiveness of practical bin-
ning schemes. The problem analyzed in this paper is design
of worst-case noise distributions against -dimensional lattice
quantization index modulation (QIM) watermarking codes.
The cost functions considered are 1) probability of error of the
maximum-likelihood decoder, and 2) the more tractable Bhat-
tacharyya upper bound on error probability, which is tight at
low embedding rates. Both problems are addressed under the
following constraints on the attacker’s strategy: the noise is inde-
pendent of the marked signal, blockwise memoryless with block
length , and may not exceed a specied quadratic-distortion
level. The embedder’s quadratic distortion is limited as well.
Three strategies are considered for the embedder: optimization of
the lattice ination parameter (also known as Costa parameter),
dithering, and randomized lattice rotation. Critical in this analysis
are the symmetry properties of QIM nested lattices and convexity
properties of probability of error and related functionals of the
noise distribution. We derive the minmax optimal embedding and
attack strategies and obtain explicit solutions as well as numerical
solutions for the worst-case noise. The role of the attacker’s
memory is investigated; in particular, we demonstrate the remark-
able effectiveness of impulsive-noise attacks as increases. The
formulation proposed in this paper is also used to evaluate the
capacity of lattice QIM under worst-noise conditions.
noise (AWGN) channel, the family of all additive-noise chan-
nels subject to a squared-error distortion constraint, and the
family of all channels subject to a squared-error distortion con-
straint. Most models assume the use of memoryless channels; in
other models, this restriction is relaxed. For the watermarking
games of [9] and [10], in which the host signal is Gaussian
and the squared-error distortion constraints are imposed on the
embedder and the attacker, the capacity-achieving distributions
turn out to be Gaussian.
When no structure is imposed on the quantizers, random
coding methods have been used to prove the achievability
of capacity and error exponents [6]–[10]. Such methods are
unpractical, but methods based on lattice vector quantization
(henceforth referred to as lattice QIM) are more manageable.
For AWGN channels, Erez and Zamir [6] have proven that
such structural constraints on the quantizers do not cause a
loss of capacity: capacity is achievable asymptotically as the
lattice dimension tends to innity. Surprisingly, a similar result
applies to error exponents at high rates [8]. However, there is
always a performance loss when low-dimensional lattices are
used. For scalar QIM [2], [5], the lattice dimension is equal
to one, and the watermark-to-noise ratio (WNR) penalty for
achieving a target rate is typically between 1.5 and 3 dB.
This paper is about achievable error probabilities for nite-di-
mensional lattice QIM methods at low embedding rates. Our
study includes the popular scalar and hexagonal QIM methods
as special cases. We consider the class of additive-noise chan-
nels subject to a squared-error distortion constraint, and var-
ious memory constraints. Detection-theoretic functionals of the
noise probability density function (pdf) are formulated and used
as cost functions in a game between the watermark embedder
and the attacker. The strategies to be optimized by the embedder
include the selection of the QIM lattice ination parameter (also
known as the Costa parameter) as well as randomization strate-
gies. Fundamental to our study are the convexity properties of
the cost functions used. Our methods are applied to error-proba-
bility, Bhattacharyya, and mutual-information functionals of the
noise pdf.
Part of this study was reported in the second author’s Master’s
thesis [11]. Related work, conducted independently of ours, in-
cludes Pérez–González [12] and Vila–Forcén
et al.
[13], where
the worst-noise pdf against scalar QIM was sought using a non-
linear optimization algorithm; and Tzschoppe
et al.
[14], where
the worst-noise pdf is sought within a nonparametric family, and
obtained using an elegant application of the Blahut–Arimoto al-
gorithm. In both [12] and [14], the cost functional was mutual
information. In [13], the cost functional was the probability of
error based on a single received sample, and a minimum-dis-
tance decoder.
The general problem of design and analysis of worst-case ad-
ditive-noise distributions appears frequently in the communica-
tions literature (e.g. see the analysis of [15] for worst-noise in
Index Terms—
Capacity, convex optimization, data hiding, detec-
tion theory, error exponents, game theory, quantization index mod-
ulation, random codes, watermarking.
I. I
NTRODUCTION
has been developed over the last ten years. Much atten-
tion has been focused on quantization index modulation (QIM)
methods, which are information-theoretic binning schemes and
are relatively easy to implement [1]–[10]. The most important
property of binning schemes is their ability to approach fun-
damental communication limits, such as the maximum rate of
reliable transmission (data-hiding capacity) for a given family
of attack channels and the error exponents (the rate of decay of
error probability) at rates below capacity.
Different families of attack channels have been studied in
[1]–[10], corresponding to various degrees of generality in the
channel model. This includes a single additive white Gaussian
Manuscript received September 2, 2005; revised May 3, 2006. This work was
supported by the National Science Foundation under Grants CCR 02-08809 and
CCR 03-25924, presented in part at ICIP, Singapore (Oct. 2004) and at ICIP,
Genoa, Italy (Sep. 2005). The associate editor coordinating the review of this
manuscript and approving it for publication was Dr. Ton Kalker.
P. Moulin is with the University of Illinois at Urbana–Champaign, Urbana,
IL 61801 USA (e-mail: moulin@ifp.uiuc.edu).
A. K. Goteti is with Qualcomm, Inc., Campbell, CA 95008 USA (e-mail:
agoteti@qualcomm.com).
Digital Object Identier 10.1109/TIFS.2006.879299
1556-6013/$20.00 © 2006 IEEE
A
VARIETY of blind watermarking and data hiding schemes
294
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
Fig. 1. Communication model for watermarking. The encoder is a two-stage encoder.
binary-input channels). The mathematical structure of our opti-
mization problems is, however, quite different from those in [15]
because of the fundamentally different nature of the channel in
the QIM problem: the channel introduces modulo-lattice addi-
tive noise (MLAN). As we shall see, the resulting worst-case
distributions differ signicantly from those in [15].
This paper is organized as follows. Section II states our block
coding model, and Section III specializes it to the case of lattice
QIM. Section IV denes the lattice maximum-likelihood (ML)
decoder and sets up the game between the watermark embedder
and the attacker. Section V solves the game for a simple but in-
sightful special case: scalar QIM with binary alphabets, subject
to memoryless attacks. Analytical solutions are derived, and the
asymptotic optimality of impulsive-noise attacks at high water-
mark-to-noise ratios is established. Section VI treats the more
general case of a -dimensional lattice subject to blockwise-
memoryless noise, and designs optimal attacks against the QIM
code. To counter such attacks, a randomized rotation strategy is
proposed for the watermark embedder in Section VII; the worst-
case noise distribution is now isotropic. Section VIII extends
these results to spread transform dither modulation (STDM)
block codes, using a similar randomized rotation strategy: the
host signal is projected onto a secret lower-dimensional sub-
space prior to embedding. The STDM case is more amenable to
analytical exploration, and we present closed-form expressions
for decoding performance under isotropic impulsive-noise at-
tacks. In Section IX, we study the capacity limits of lattice QIM
subject to the worst blockwise memoryless noise. Finally, con-
clusions are presented in Section X.
signal sequence, using a two-stage code. The host sequence is
subdivided into
blocks of length
each. We
denote by
the th host signal
block .
In the rst stage, is mapped to a -ary sequence
(codeword) using an error-correction
code (ECC) with rate . The ECC will be referred to as
the outer code. In the second stage, an embedding function
is applied to each block. The
th marked block is given by , where
is a secret key (with alphabet ) shared with the decoder.
The per-sample, mean-squared distortion of the host signal due
to embedding is given by
.
The rate of the two-stage code is given by
bit/sample
(2.1)
The case corresponds to an uncoded scheme (high
payload) in which no ECC is used in the rst stage. The other
extreme case
, corresponds to a low-payload scheme in
which
and the ECC could be, for instance, a simple
repetition code.
The choice of the attack models and performance metrics
used in this paper is based on the assumption that the code rate
is low and that the ECC is suitably randomized. Such would be
the case, for instance, of random expurgated codes [16], [17]
and random constant-composition codes [18].
The attacker chooses a noise pdf
that satises the ex-
pected-distortion constraint
II. M
ATHEMATICAL
M
ODEL
Notation:
We denote random variables with uppercase letters
and individual realizations with lowercase letters. Boldface let-
ters are used to represent sequences and vectors. The Euclidean
norm of a vector
(2.2)
is denoted by
. The pdf of a random
and uses this pdf to generate independent and identically
distributed (i.i.d.)
-dimensional random vectors
,
variable
is denoted by
. The volume of a set
is
to the marked blocks. Each
is independent
denoted by
, the indicator function of a set
by
of
. The quantity WNR
is referred to as the
, the Dirac impulse by
, and the mathematical expec-
watermark-to-noise ratio (WNR).
The decoder observes the resulting degraded blocks
and outputs a decision
, where denotes the decoding function.
Note that our attack model allows for dependencies between
the components of , but not across blocks. If the ECC was
not randomized, the attacker’s performance could be improved
tation operator by
. Finally, given two functions
and
, we write
(resp.
)as
if
the ratio tends to 1 (resp. 0) as .
Let and be integers. (We use and as ex-
amples throughout this paper.) Referring to Fig. 1, we wish to
embed a message
in a length- host
MOULIN AND GOTETI: BLOCK QIM WATERMARKING GAMES
295
by exploiting the structure of the ECC. Due to our assumption
that the ECC is randomized, this strategy is not considered in
this paper.
III. L
ATTICE
QIM
Each symbol may be embedded into the host signal block
, , using various methods [7]. Of interest in
this paper are Chen and Wornell’s QIM method; their STDM
method [1], [2]; and, more generally, nested lattice codes [3],
[4], [6], [7]. We briey review nested lattice codes and introduce
the notation.
A lattice in -dimensional Euclidean space is dened as a
set of points in such that and implies
and , which equips with the structure of an additive
subgroup of [20].
A nested lattice code consists of a coarse lattice
Fig. 2. Nested two-dimensional lattices. The coarse lattice
is the set of heavy
dots and its cosets are represented by squares and circles. The lightly shaded
region is
V
, the Voronoi cell of
. (a) Quincunx lattice
q=2
and (b) hexagonal
lattice
q=3
.
and a ne
Example 2:
Ta k e and let be the hexagonal lattice
to be scaled by , and be the union of rotated by and
scaled by and itself [Fig. 2(c)]. Then, is the cyclic
group of order three and .
Since is uniformly distributed over , the quantization
noise is also uniformly distributed over
and is independent of , for any random vector
lattice
. The coarse lattice
is a sublattice of
. The ne
lattice
may be decomposed as the union of cosets of
[21]. The
where . The choice of is nonunique, but it is con-
venient to choose a minimum-norm vector, in which case
mean-squared distortion due to embedding is
is
(3.3)
called the coset leader of
. The set
(3.1)
Neither distortion nor decoding performance is affected
if the code representers in (3.2) are shifted
by an arbitrary amount (i.e., if we allow ). For
instance, in Example 1 above, one may prefer to use
.
As described in Section II, the attacker is subjected to a power
constraint (2.2). For a given lattice , the embedder selects to
optimize the performance of the system against the attacks. The
attacker knows the watermarking code and optimizes the noise
pdf . We call this noise pdf the worst attack.
Modulo Operations:
The operation on any
is dened as . The shorthand
denotes integration over a set , folded into
by using the operation. Given a function ,
we dene its -periodic extension as for
all . The Dirac impulse on the torus is dened by the
shifting property , for any
and continuous -periodic function . The following properties
of the operation will be used.
• Distributivity:
carries a group structure and is called the quotient group of
by . may be efciently represented by the coset leaders
and
. Next, we dene
quantization function mapping each point
to
the nearest lattice point in ;
Voronoi cell of .
Finally, a lattice ination parameter (“Costa parameter”)
is introduced to control the amount of distortion compensation
introduced in the embedding. The host vector
is marked
using the dithered-QIM formula
(3.2)
where is an external dither sequence, randomized over , and
known to the embedder and the decoder but not to the attacker.
The (second stage) watermarking code is the triple .
The motivation for using the randomized dither vector in the
QIM embedding formula (3.2) is twofold: i) improve security
against surgical attacks, and ii) obtain a tractable model for the
self-noise. The following examples of QIM watermarking codes
will be used throughout this paper.
1
Example 1 (Chen–Wornell Scheme):
Let
be the scaled
,
for all
.
• Uniform noise: if
is random and uniformly distributed
over , then so is
for any random
vector
.
-dimensional cubic lattice and
be
times the so-called
IV. QIM W
ATERMARK
D
ECODING
G
AMES
checkerboard, or
, lattice [20]. Here,
,
,
is isomorphic to the
A. Lattice Decoder
The QIM lattice decoder reduces the data
group with two elements, and
. The lattice
is
to a length-
also known as the quincunx lattice [Fig. 2(a)].
sequence of -valued statistics
1
STDM involves a projection of the host signal onto a lower-dimensional
subspace and will be considered in Section VIII.
(4.1)
296
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
After this reduction step, the dither values are no longer
used. Note that further reduction of the data, in the form of a
quantization of each to the ne lattice , would be tan-
tamount to block-level minimum-distance decoding and would
generally cause a loss of information about . Even in the ab-
sence of ECC, when blocks are independent and symbols em-
bedded in different blocks may be decoded independently, min-
imum-distance decoding need not be equivalent to the optimal
ML decoding rule.
2
An improved idea would be quantizing each
to the cosets of the coarse lattice . While
this operation is information-lossless in the absence of ECC, it
is still information lossy when an ECC is used.
Denote by the pdf of random vector given that
was embedded in the block. Under the
hypothesis, that message
Fig. 3. Modulo lattice additive noise channel.
Due to (4.3), (4.4), (4.5), and the independence of
and
,
the pdf of
is of the form
was transmitted (and, thus,
was embedded in block for
), the random
variables
are conditionally independent, with respective
pdfs
. To obtain good decoding performance, we need the
pdfs
to be “well separated,” in a sense made
precise below.
(4.6)
B. Equivalent Channel Model
From (4.2), we view as the output of an MLAN channel
with input (Fig. 3). The transition probabilities of the
channel are given by
Here, we derive a model for
analogous to the MLAN model
of Erez and Zamir [6], in which
was white Gaussian noise.
(4.7)
The outer ECC maps message
into codeword . In block ,
is the sum
of the coset vector
and a random
vector
(4.2)
C. Lattice ML Decoding Rule
The random vectors
are i.i.d. and independent of . Each
We assume that all messages are equally likely.
Due to the i.i.d. noise model, the decoder is assumed to be
able to learn the noise pdf when the number of blocks
is large enough. Therefore, we shall assume that the de-
coder knows and implements the lattice ML detection
rule, which minimizes the probability of error given
vector
is the sum
of two components
(4.3)
and
where is the self-noise due to quantization, which is uniform
over the scaled Voronoi cell
[22]
(4.4)
(4.8)
and
is the scaled attacker’s noise, folded into
. Its pdf is
We refer to (4.8) as the lattice ML decoder. Its probability of
error is given by
(4.5)
The parameter trades off the amount of self-noise against
the attacker’s noise at the receiver. When
(4.9)
is small, the self-
where we have used the shorthand
.
noise
dominates the attacker’s noise. When
, there is
no self-noise, and
.
D. Probability-of-Error Game
2
The minimum-distance decoding rule coincides with the lattice ML rule in
some cases, but not always. As an example, where these rules differ, consider
scalar QIM with
q=2
,
=1
, and noise pdf
p(w)=(1=2)[(wa)+
(w+a)]
, where
=4<a<=2
. The lattice ML decoder is error-free
because the rival pdf’s
p(~y)
and
p(~y)
have disjoint supports. But clearly the
minimum-distance decoder is always in error.
Given the watermarking code, the embedder wants to choose
that minimizes . Similarly, given the code and the optimal
, the attacker wants to choose
that maximizes
. Equiva-
lently, we may adopt
as the gure of merit of the
MOULIN AND GOTETI: BLOCK QIM WATERMARKING GAMES
297
system. This becomes a maxmin game between the embedder
and the attacker
Therefore, the Bhattacharyya bound is frequently used to predict
how large should be to achieve a desired probability of error.
3
The upper bound in (4.13) is much easier to evaluate than
(4.9), because the evaluation of requires only a -di-
mensional integration over , no matter how large
is. Note that in practice, should be a relatively small number
(say 1, 2, or 3); otherwise, the evaluation of itself be-
comes hard. Since is a function of and , we de-
note this function as . Instead of (4.10), we solve the
simpler (and asymptotically equivalent) problem
(4.10)
where the minimization is subject to the distortion constraint
(2.2). Moreover, we shall see in Section IV-I that this minimiza-
tion can be restricted without loss of optimality to a compact
set of pdfs. The existence of a maximum and a minimum is
then guaranteed because the cost functional is continuous and
bounded, and the maximization and minimization are over com-
pact sets.
For
(4.15)
, the union bound may be used to relate
to
the probabilities of error
for all
where the minimization is subject to (2.2). The optimal value of
is the maxmin error exponent for the
binary tests between messages
game, and we
The union bound is achieved when .
The special case corresponds to hard
symbol decoding and generally a high probability of error—un-
less WNR is large. When
refer to (4.15) as the Bhattacharyya game.
Case :
The Bhattacharyya bound can be extended
to the case of multiple messages. Different bounds can be
considered (e.g., random coding bound and expurgated bound
[16]–[19]). To simplify the presentation, we x one that is fairly
tractable and provides a useful characterization of decoding
performance at very low rates. Our performance metric is the
Bhattacharyya parameter for the MLAN channel, which we
dene as
, the cost function in
(4.10) becomes
(4.11)
(4.16)
(i.e., the uniform average of the pairwise Bhattacharyya
distances).
Equidistant Channels:
If , the summand of (4.16)
is the same for all , the channel is said to be equidis-
tant [19]. All channels with binary inputs are equidistant. The
MLAN channel with the hexagonal lattice of Fig. 2(b) has three
inputs and is also equidistant, as can be veried using a simple
change of variables in the Bhattacharyya integrals. This holds
for any choice of .
The Bhattacharyya metric (4.16) is used in conjunction with
the normalized minimum distance of the ECC, which is dened
as follows. Denote by
E. Bhattacharyya Game
Even in the simple case , evaluation of the exact
probability of error (4.9) requires the evaluation of an -dimen-
sional integral, which unfortunately is infeasible unless is very
small or is relatively large. For large , a more convenient
approach is to use the Bhattacharyya upper bound on [7],
[17], [22]. Appendix A presents a succinct derivation of the error
bounds stated in this section.
Case :
For simplicity, we begin with the case
of two messages , , and a repetition outer
code. The per-sample Bhattacharyya distance between
, the Hamming distance between
two codewords
and
(the number of
and
positions where and
differ), and
is given by [23]
(4.17)
(4.12)
the normalized minimum-distance of the code. Applying
Plotkin’s bound, we ha
v
e
which is zero if
, and positive otherwise. The Bhat-
for any -ary code [17, p. 549]. For many low-rate codes, the
Plotkin bound is tig
h
t. When for instance, any reason-
able code satises (i.e., achieves the Plotkin bound
with equality). If tends to innity as a subexponential func-
tion of , expurgat
ed
random codes [16], [17] approach the
Plotkin bound (i.e.,
tacharyya bound
(4.13)
is tight in the exponent when and satisfy a certain sym-
metry property (as will be the case throughout this paper)
).
(4.14)
3
A classical example is the binary symmetric chan
nel with
crossover proba-
bility
. In this case, we have
B(p;p)=ln2(1)
and
P =
(4(1))
.
Plik z chomika:
Kuya
Inne pliki z tego folderu:
Behavior_Forensics_for_Scalable_Multiuser_Collusion_Fairness_Versus_Effectivenes.pdf
(964 KB)
Block_QIM_Watermarking_Games.pdf
(869 KB)
Correspondence.pdf
(176 KB)
Dual_Protection_of_JPEG_Images_Based_on_Informed_Embedding_and_Two-Stage_Waterma.pdf
(1549 KB)
Estimation_of_Message_Source_and_Destination_From_Network_Intercepts.pdf
(613 KB)
Inne foldery tego chomika:
2006-1
2006-2
2006-4
2007-1
2007-2
Zgłoś jeśli
naruszono regulamin