Luis Pérez-Freire

Member, IEEE Fernando Pérez-González

Teddy Furon
email: teddy.furon@irisa.fr

Pedro Comesaña
email: pcomesan@gts.tsc.uvigo.es

Prof Moulin L Pierre

F Pérez-Freire

P Pérez-González

Comesaña

Security of Lattice-Based Data Hiding Against the Known Message Attack

Keywords: Equivocation, lattice data hiding, mutual information, quantization index modulation, set-membership estimation, watermarking security. I

Security of quantization index modulation (QIM) watermarking methods is usually sought through a pseudorandom dither signal which randomizes the codebook. This dither plays the role of the secret key (i.e., a parameter only shared by the watermarking embedder and decoder), which prevents unauthorized embedding and/or decoding. However, if the same dither signal is reused, the observation of several watermarked signals can provide sufficient information for an attacker to estimate the dither signal. This paper focuses on the cases when the embedded messages are either known or constant. In the first part of this paper, a theoretical security analysis of QIM data hiding measures the information leakage about the secret dither as the mutual information between the dither and the watermarked signals. In the second part, we show how set-membership estimation techniques successfully provide accurate estimates of the dither from observed watermarked signals. The conclusion of this twofold study is that current QIM watermarking schemes have a relative low security level against this scenario because a small number of observed watermarked signals yields a sufficiently accurate estimate of the secret dither. The analysis presented in this paper also serves as the basis for more involved scenarios.

been watermarked with the same secret key, and the attacker has access to these watermarked signals. A first theoretical part measures the amount of information about the secret key which leaks from the watermarked content, using the mutual information and conditional entropy as measures, following the information-theoretic approach for cryptosystems proposed by Shannon in [START_REF] Shannon | Communication theory of secrecy systems[END_REF]-this approach is based on computing the entropy of the key conditioned on the encrypted messages observed by the attacker; when the conditional entropy is null, it means that the attacker has gathered enough observations so as to disclose the secret key. Bear in mind that the original Shannon's work dealt with discrete random variables, whereas our discussion deals with continuous random variables. This is why we need to resort to differential entropies; nevertheless, the main concepts remain the same-whereas discrete entropy is related to the number of possible values of a random variable and their probabilities (and it is always a non-negative quantity), differential entropy accounts for the log-volume of the typical set [6, Sec. 9.2] and as such, still provides a useful measure of uncertainty, regardless of whether it takes negative values; in particular, complete disclosure of the secret key will be possible when its conditional entropy becomes . The information-theoretic analysis allows us to establish lower bounds on the variance of the key estimation error as a function of the number of available observations. The second part of this paper is of practical nature and shows workable algorithms which take as input a collection of watermarked signals and output an estimate of the secret key. This confirms that the attack is manageable within bounded complexity.

This framework (theoretical and practical parts) has already been successfully applied to substitutive [2, Sec. III] and additive spread-spectrum watermarking schemes [2, Sec. IV] [START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF]. Watermarking security under this viewpoint is also briefly addressed in [START_REF] Moulin | Data hiding codes[END_REF]Sec. 10]. Other notable works dealing with the security of spread-spectrum schemes concentrate on the practical part [START_REF] Mihcak | Cryptanalysis of discrete-sequence spread spectrum watermarks[END_REF], [START_REF] Doërr | Security pitfalls of frame-by-frame approaches to video watermarking[END_REF]. As for quantization-based data hiding, preliminary studies of the theoretical part have shown the existence of information leakages [START_REF] Pérez-Freire | Informationtheoretic analysis of security in side-informed data hiding[END_REF], while on the practical part, we are aware of two works: first, the work by Eggers et al. [START_REF] Eggers | Estimation of amplitude modifications before SCS watermark detection[END_REF], although their motivation was not the security analysis but the robustness improvement of the scalar costa scheme (SCS) against scaling and the addition of white Gaussian noise attack (SAWGN), and the work by Bas and Hurri [START_REF] Bas | Security of DM quantization watermarking schemes: A practical study for digital images[END_REF], which is more related to our approach, but focuses on the so-called spread transform methods [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF] without distortion compensation.

The reader must note that the scope of this article is restricted because we mainly focus on the known message attack (KMA) [2, Sec. II-B]-we assume that the attacker is able to gather a collection of signals , watermarked with the same key, while knowing the hidden message for each, denoted by . The pairs will be referred to as observations. This paper is only a first step to a global security analysis of quantization-based watermarking; in fact, as we will discuss in Section VII, both the developed theory and algorithms for the KMA scenario constitute the core of those corresponding to more complex scenarios. In any case, the considered setup is still very important as shown in the following motivations.

1) The copy protection application faces extreme security threats [START_REF] Bloom | Copy protection for DVD video[END_REF]. The secret key is not only unique but the hidden messages are also known by any user. Consider a digital rights management (DRM) system using watermarking.

The secret key is embedded in a chip set included in every compliant device. Content makers also share the secret key to watermark their products. Compliant devices spot these as protected contents whose use is restricted according to the DRM license. Some DRM systems hide the status (i.e., the usage restriction) such as "Copy Never," "Copy Once," and "Copy No More" [START_REF] Bloom | Copy protection for DVD video[END_REF] in the contents. The number of status choices is extremely small compared to the size of the content. This is a typical example of zero-rate watermarking, where the embedding proceeds by blocks (of video or of sound). The Copy Protection Technical Working Group has, for instance, required the embedding of 8 bits within 10 seconds of video [START_REF] Maes | Digital watermarking for DVD video copy protection[END_REF]. Moreover, any user knows the embedded message as the status of a piece of content is public (for instance, the compliant device may warn the user that the copy of a particular content is forbidden due to its restrictive status). Hence, KMA is a main threat in copy protection applications. 2) Video and audio watermarking, in general, might be also put at risk by KMA. The reason is that one usually does not watermark a video, but instead watermarks consecutive blocks of video. This division in blocks maintains a low complexity of the embedding and decoding whereas it eases temporal resynchronization. In the case of zero-rate watermarking (the message space is bounded and small), a common approach is to embed the message repeatedly in consecutive blocks. The division into blocks is usually publicly known (although other strategies are possible), so the attacker is able to gather a number of different blocks hiding the same message. This is not exactly a KMA but a constant message attack (CMA) because the value of the message might not be known. However, we will show that this only brings slight changes in both the theoretical and the practical parts. This matter concerns applications such as copyright enforcement, copy protection, and fingerprinting (traitor tracing). Note that in this last scenario the major source of concern has been collusion attacks (i.e., an arrangement of several traitors), but the CMA could constitute a worse attack for audio or video fingerprinting because there the same message is repeatedly embedded in a block-by-block basis. The success of the CMA depends on the number of blocks in a movie or song. 3) Another motivation is that most QIM schemes are known to be weak against amplitude scaling attacks. Eggers et al.

suggest in [START_REF] Eggers | Estimation of amplitude modifications before SCS watermark detection[END_REF] and [16, Sec. VI] to embed a reference mes-sage (also known as pilot sequence) prior to the message being embedded. Knowing this pilot sequence, the decoder is able to estimate the amplitude scaling and later to retrieve the hidden message. Once again, this implies that all of the watermarked signals contain the same pilot sequence. If the CMA is successful, the attacker may remove the pilot sequence and then apply a slight scaling to the amplitude of the host signal. The decoder will not be able to retrieve the reference message nor the scaling factor. However, bear in mind that in case the attacker does not know the exact location of the pilot signal, the CMA attack can be used only as part of a more global attack. 4) Another important case is the application of QIM schemes for authentication. There exist many different ways of designing a watermarking-based authentication scheme; for instance, Eggers et al. proposed a highly original scheme [START_REF] Eggers | Blind watermarking applied to image authentication[END_REF] taking benefit that a side-informed embedder gives a watermark signal heavily dependent on the host signal. Thus, it is useless to estimate the watermark signal of a signed content, and then copy and paste it into another content in order to forge a signature. This elegantly gets rid of the copy-and-paste attack. In their scheme, Eggers et al. suggest applying SCS to image authentication by watermarking blocks of the image with a reference message.

The verification process considers the image as authentic when the decoded message matches this reference message. Once again, this implies that all of the signed images contain the same reference message and the CMA attack is applicable. We assume the watermark embedder works as follows. A first step extracts some coefficients, for example, discrete cosine transform (DCT), discrete wavelet transform (DWT), fast Fourier transform (FFT) from the original piece of content. These coefficients are ordered in a length-column vector, and the latter is partitioned in blocks of length , denoted by . The embedder hides a message in each , yielding a watermarked vector . Thus, the data hiding rate is bits per coefficient. The specific implementation of QIM considered in this paper is by means of nested lattices [START_REF] Moulin | Data hiding codes[END_REF], which encompasses most of the proposed QIM formulations so far, and it will be referred to as lattice data hiding. According to the discussion above, we assume that both the selection of the extracted coefficients and the partitioning in length-blocks is public; hence, the security of the scheme relies only in the randomization of the lattice via a dithering process, where the dither signal plays the role of secret key. 1Actually, the secret dither signal, which we denote by , may be any deterministic function of a certain cryptographic key (i.e.,

, where is a pseudorandom generator). Although, under the assumptions of Kerckhoffs' principle, such a function should be publicly known, disclosure of the secret dither does not necessarily imply disclosure of the cryptographic key , since should have been properly designed so as to be (ideally) noninvertible. The attacker restricted to a signal processing approach, as the one we are presenting here, can, at most, aspire to disclose the sequence of dither samples provided by the available observations. Inference of the secret key based on the estimate of belongs to the domain of cryptanalysis and, as such, falls out of the scope of the present paper. Nevertheless, the mere disclosure of the plain secret dither in a lattice data hiding scheme allows many harmful attacks, as we shall discuss in Section V-A.

The theoretical security of lattice data hiding schemes is studied in Sections II and III. Sections IV and V present practical estimators and experimental results, respectively, obtained in the lattice data hiding scenario. In Section VI, the theoretical security of quantization-based data hiding methods is linked to the corresponding to Costa's setup [START_REF] Costa | Writing on dirty paper[END_REF], and in Section VII, the extension of the framework proposed in this paper to more general scenarios is discussed. Finally, in Section VIII, the main conclusions are summarized and some remarks are given. Unless otherwise stated, our results will be restricted to a distortion compensation parameter which represents the most important case for lattice data hiding for the following reasons.

• In high watermark-to-noise-ratio (WNR) applications, 2 which is the scenario of main interest for lattice data hiding, the optimal value of is considerably larger than 0.5 (see [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF], for instance). • In low WNR applications, the optimal values of are smaller than 0.5, leading to decoding errors even in the absence of noise. Indeed, it has been shown that for low WNRs, it is better to apply lattice data hiding in conjunction with spread transform [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF], whose main benefit is to increase the effective WNR. This, in turn, leads to an increase of the optimal , in most practical instances to values . A similar conclusion is arrived at when lattice data hiding is combined with channel coding (e.g., repetition coding or Construction A [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF]). The main notational conventions followed throughout the text are the following: random variables and their occurrences are denoted by capital and lowercase letters, respectively; boldface letters denote column vectors, whereas scalar variables are represented in nonboldface characters. Calligraphic letters are reserved for sets. All logarithms are to the base , so all of the mutual informations and differential entropies are expressed in nats.

II. THEORETICAL SECURITY OF LATTICE-BASED DATA HIDING

Before proceeding with the theoretical analysis, we will briefly explain the basics of embedding in lattice data hiding; for more details and other aspects, such as decoding, the interested reader is referred to [START_REF] Moulin | Data hiding codes[END_REF] and the references therein. Consider an -dimensional lattice and the set of possible messages. For each message , let us define the associated coset of as , where is the minimum-norm coset representative corresponding to message . The codebook is defined by the union of all cosets . Given a certain host signal and a to-be-transmitted message , each watermarked signal is generated as [START_REF] Barni | A general framework for robust watermarking security[END_REF] where is the distortion compensation parameter, and is an Euclidean quantizer whose centroids are defined by the coset [START_REF] Cayre | Watermarking security: Theory and practice[END_REF] where denotes the Euclidean norm. This data hiding scheme is commonly known as distortion compensated-dither modulation (DC-DM) [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF]. For adding security to the scheme, several authors [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF], [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF] proposed to introduce an additional term named secret dither vector, which is known only by the embedder and decoder, yielding a randomized embedding function [START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF] where is the th randomized coset, and the second term of (3) is the so-called self-noise term. Notice that the watermark, defined as , is -periodic both in and since it yields the same value for hosts and dither vectors of the form and , respectively. The complete data hiding scheme is summarized in the block diagram of Fig. 1. The aim of the secret dither is just to apply a secret shift to the embedding lattice, and it does not change any of its fundamental properties concerning information transmission. 3 These days, most of the lattice DC-DM schemes base their security on this strategy.

As is usual in the analysis of quantization-based methods for data hiding [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF], [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF], a low embedding distortion regime is assumed, such that the variance of the host is much larger than the volume of the Voronoi region of . The Voronoi region of a lattice is denoted by and is defined as [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF] (4)

In practice, this assumption (which we will refer to in the sequel as the flat-host assumption) implies that the pdf of the host and that of the self-noise are approximately uniform inside each quantization cell and over , respectively.

The flat-host assumption permits us to simplify the theoretical analysis, restricting our attention to the modulo-reduced random variable . 4 Hence, the pdf of conditioned on the embedded message and the secret dither is otherwise [START_REF] Shannon | Communication theory of secrecy systems[END_REF] In our model, as is customary in theoretical analysis of watermarking methods, the host samples are considered independent and identically distributed (iid). Under these premises, a theoretical security analysis will be developed for the two scenarios (KMA and CMA) introduced in Section I. Obviously, the security level of the system depends on the statistical distribution of the secret dither, or better to say, of its modulo-reduced version, . Due to the -periodicity inherent in the watermark generation [see ( 3)], we have that ; hence [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF] where is the pdf of . This means that the pdf of the watermarked signal depends in last instance of the pdf of and, hence, the secrecy of the codebook only depends on the statistics of . 5 Therefore, the support of is bounded by hereinafter. We must note that is usually assumed to be uniformly distributed over in most lattice data hiding schemes [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF], [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF], but this choice was not strictly motivated by security reasons, so it makes sense to wonder about its optimal distribution from this latter point of view.

A. Known Message Attack

When a sequence of watermarked signals and their associated messages are observed, the information leakage about can be calculated by means of the mutual information between the observations and the secret dither [START_REF] Moulin | Data hiding codes[END_REF] where we have made use of the mutual independence between and the embedded messages, also assumed to be mutually independent. Here, is the differential entropy [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF] of the random variable , and the second term of ( 7) is the residual entropy or equivocation of the dither after observations, following Shannon's nomenclature [START_REF] Shannon | Communication theory of secrecy systems[END_REF]. The equivocation measures the remaining ignorance about the secret dither, so the appropriate distribution for should be chosen in order to maximize this value. To this end, let us consider the conditional pdf of the 4 It is worth noting that this modulo operation is virtually information lossless ( [START_REF] Pérez-Freire | Spread-spectrum vs. quantization-based data hiding: Misconceptions and implications[END_REF], Section IV) in low embedding distortion regimes, as is our case. This implies that the analysis is accurate in the sense that I( Ỹ; T) I(Y; T). 5 However, attacks at a cryptographic level would be indeed interested in knowing the exact value of t.

dither. The statistical properties of the watermarked signals give rise to the notion of the feasible region of the dither, formally defined as the support of its conditional pdf after observations. The next property will be widely used throughout the text.

Property 1: Boundedness of the feasible region. The feasible region is bounded by , where

Proof: Application of Bayes' rule yields [START_REF] Doërr | Security pitfalls of frame-by-frame approaches to video watermarking[END_REF] where . Notice that each random variable is a function of the triple , and the host samples in our model are mutually independent. This means that the observations are conditionally independent given the dither; hence, ( 9) can be rewritten as (10) [START_REF] Eggers | Estimation of amplitude modifications before SCS watermark detection[END_REF] where [START_REF] Eggers | Estimation of amplitude modifications before SCS watermark detection[END_REF] follows from the flat-host assumption. By recalling [START_REF] Shannon | Communication theory of secrecy systems[END_REF], it is clear that each term in the numerator of ( 11) is nonzero iff , or equivalently, iff , with given by ( 8). Hence, it is clear that the feasible region of is contained in , independent of the distribution of .

Property 1 allows us to state the following lemma. Lemma 1: Maximization of the residual entropy. The residual entropy is maximized for , yielding a conditional pdf uniformly distributed in , that is otherwise [START_REF] Bas | Security of DM quantization watermarking schemes: A practical study for digital images[END_REF] Proof: By the definition of residual entropy, we have [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF] where the expectation is taken over the joint pdf . Since the feasible region of the dither is bounded by , its entropy will be maximized when the dither is uniformly distributed in , that is [START_REF] Bloom | Copy protection for DVD video[END_REF] Since the denominator of ( 11) does not depend on , then the choice suffices for achieving such distribution and, hence, equality in [START_REF] Bloom | Copy protection for DVD video[END_REF].

The optimal distribution resulting from Lemma 1 also brings additional desirable properties: it provides statistical independence between the self-noise and the host signal [START_REF] Schuchman | Dither signals and their effect on quantization noise[END_REF], and most important, it does not prevent achieving capacity in the Gaussian channel in the asymptotic setup [START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF]. Hence, the choice of is good from the robustness and security points of view, and this will be the chosen distribution in the remainder of this paper unless otherwise stated. Hence, by combining Property 1 and Lemma 1, the residual entropy results in [START_REF] Maes | Digital watermarking for DVD video copy protection[END_REF] where the expectation has taken over the joint pdf of the observations. In case of one observation , we have [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF] and the information leakage is given by [START_REF] Eggers | Blind watermarking applied to image authentication[END_REF] for all , independent of the specific lattice chosen for embedding. This result clearly shows a tradeoff between security and achievable rate: theoretical analyses [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF], [START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF] show that, in AWGN channels, the value of must approach 1 for maximizing the achievable rate in the high-WNR region; however, bear in mind that for , one observation suffices to get an accurate estimate of the centroids in and, consequently, of the secret dither due to the structure imposed on the codebook. This is reflected in the residual entropy of the dither ( 16), for which . For , one must consider two different cases: 1) for , the mutual information is maximum for , as we have just discussed, so more observations will not provide additional information about (i.e., it becomes deterministic for ) and 2) for , the mutual information does not increase linearly due to the dependence between observations. Its general behavior is stated in the following Lemma.

Lemma 2: If , the mutual information about the secret dither is an increasing, concave function of the number of observations . Proof: To see that the mutual information is always increasing, consider the function [START_REF] Costa | Writing on dirty paper[END_REF] which is nothing but the average information about that is gained with the th observation. Such a function is easily seen to be always non-negative [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF] where [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF] follows from the fact that conditioning reduces entropy [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF]. In this case, strict inequality holds in [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF], due to ( 12) and ( 13) (i.e., the mean volume of is always reduced with each new observation, with the obvious exception of deterministic ). Thus, the mutual information is always increasing.

In order to prove the concavity of the mutual information, we make use of the following claim [START_REF] Parnas | On testing convexity and submodularity[END_REF].

Claim: Discrete concavity. A discrete function , with , is (strictly) concave if and only if is (decreasing) nonincreasing, with . Thus, the mutual information will be (strictly) concave iff is (decreasing) nonincreasing. By the definition of mutual information, we have [START_REF] Pérez-Freire | Spread-spectrum vs. quantization-based data hiding: Misconceptions and implications[END_REF] Making use of the chain rule for entropies ([6, Sec. 9.6] in [START_REF] Pérez-Freire | Spread-spectrum vs. quantization-based data hiding: Misconceptions and implications[END_REF], we can write [START_REF] Schuchman | Dither signals and their effect on quantization noise[END_REF] taking into account again that conditioning reduces entropy. This concludes the proof of the lemma.

B. Constant Message Attack

The easiest way of addressing this scenario is to regard it as a collection of several KMA problems. When the message embedded is unknown but unchanged for the whole sequence of observations, the conditional pdf of the dither after observations can be expressed as [START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF] where CM stands for constant message, and denotes the size of the alphabet. This means that the feasible region for the dither in the CMA case is simply the union of the feasible regions of KMA problems. Formally [START_REF] Parnas | On testing convexity and submodularity[END_REF] with defined in Property 1. Using the Borel-Cantelli Lemma, and under the assumptions stated in this paper, it can be shown that converges to zero almost surely when ; thus, the different regions that constitute will be disjointed for sufficiently large ; in such case, the residual entropy is again maximized if is chosen, but it is not necessarily the optimal distribution for all . Due to ( 22), the residual entropy can be upperbounded as [START_REF] Conway | Voronoi regions of lattices, second moments of polytopes, and quantization[END_REF] resulting in a lower bound to the information leakage. The equality in ( 24) is achieved when the regions are disjointed, which means that as increases, the bound will be asymptotically tight. However, if the value of is above a certain threshold (which depends on the lattice partition), such regions are always disjoint, and the bound is reached for all ; this is the case, for instance, when , for self-similar partitions [START_REF] Moulin | Data hiding codes[END_REF], [START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF].

III. LATTICE COMPARISON

This section tries to shed some light on two fundamental questions: 1) given , what is the best lattice (if any) in terms of security; and 2) does an increase of improve the security level. The discussion will be focused on the KMA problem, although it can be extended to the CMA scenario by taking into account the remarks made in Section II-B. Before proceeding with the analysis, we need to introduce the following definition: Definition 1: A set is said to be modulo-convex if there exists such that is convex. The notion of modulo-convexity is key to our analysis, due to the next property.

Property 2: For , the feasible region is always a modulo-convex set.

Proof: Let us define [START_REF] Conway | Fast quantizing and decoding algorithms for lattice quantizers and codes[END_REF] and . By recalling the generation of the watermarked signal (3), it is clear that . If , then . Hence, , and obviously . Since are convex sets, their intersection is also a convex set. Taking into account that , the property follows.

The use of may lead to nonconvex feasible regions, as illustrated in Fig. 2(b), where the feasible region for the dither is composed of three different modulo-sets. However, as can be seen in the Proof of Property 2, under the assumption of , it is possible to find a shifted version of the problem such that the feasible region is always modulo-convex, according to Definition 1. This property permits us to drop out the modulo operation from the expressions of the feasible regions. Bear in mind that the entropy is invariant to translations, so this simplification does not change the results. In order to provide a fair comparison between different lattices, they are scaled so as to present the same embedding distortion, which due to the flat-host assumption is given by [START_REF] Zamir | On lattice quantization noise[END_REF] where is the quantization error, and is the second-order moment per dimension of . For computing the residual entropy, the expectation in (15) must be taken over , but the conditional pdf of , given by [START_REF] Bas | Security of DM quantization watermarking schemes: A practical study for digital images[END_REF], does not depend on the specific sequence of messages embedded, as long as the latter is known; this implies that, for the expectations, the message sequence can be assumed to be deterministic. Since it is not always possible to obtain closed-form expressions for the information leakage (even for low-dimensional lattices), we must resort, in general, to Monte Carlo integration and bounding techniques.

A. Exact Computation for the Cubic Lattice

For the scaled cubic lattice 6it is possible to obtain a closed-form expression for the residual entropy. From [START_REF] Maes | Digital watermarking for DVD video copy protection[END_REF], the residual entropy is given by the expectation of the log-volume of the feasible region for the dither. Since the latter for the cubic lattice is always a hyper-rectangle, using Property 2, we can write [START_REF] Deller | Set membership identification in digital signal processing[END_REF] where is the random variable that measures the length of the feasible interval in the th dimension, and the last equality follows because the quantization step is the same for all dimensions. The random variable is given by [START_REF] Combettes | The foundations of set theoretic estimation[END_REF] with , a random variable uniformly distributed in . Hence, the problem is reduced to a scalar subproblem consisting in computing (i.e., the residual entropy in one dimension). This result is used in Appendix A, under the assumption of , to show that the residual entropy per dimension is given by [START_REF] Gurijala | Speech watermarking with objective fidelity and robustness criteria[END_REF] where is the th harmonic number, is the embedding distortion according to [START_REF] Zamir | On lattice quantization noise[END_REF], and we have taken into account that for the cubic lattice .

B. Monte Carlo Integration

When the analytical evaluation of (15) becomes intractable, we resort to Monte Carlo integration. The fact that the feasible region is reduced with each new observation makes necessary an additional task of computing a tight region of integration so as to preserve the accuracy of the Monte Carlo method (as will be seen in Step 3) of the algorithm outlined below). In order to give a comparison between different standard lattices, we consider the root lattices and their duals (the best known lattice quantizers for ), namely (hexagonal lattice), . For their definition and properties, see [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF] and [START_REF] Conway | Voronoi regions of lattices, second moments of polytopes, and quantization[END_REF]. All of these lattices are scaled so as to present the same embedding distortion per dimension as the cubic lattice with , that is, . The procedure followed for the Monte Carlo simulations is briefly outlined here.

Step 1) We assume without loss of generality that . Hence, a sequence of observed vectors uniformly distributed in , with such that is generated.

Step 2) is outerbounded by a hypercube whose edge length is twice the covering radius [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF] of . This gives an outer bound to [START_REF] Mihcak | Cryptanalysis of discrete-sequence spread spectrum watermarks[END_REF], which is used to compute an outer approximation of the feasible region.

Step 3) The feasible region resulting from the previous step (which is a hyperrectangle) is shrunk along each dimension so as to tightly bound the true feasible region . This is accomplished by means of a bisection algorithm which looks for the tightest limits of the outerbounding hyperrectangle in each dimension. The need for this step is justified by the fact that, for large , the ratio becomes too large, affecting the accuracy of Monte Carlo integration.

Step 4) A large number of points uniformly distributed in the hyperrectangle of the previous step is generated. For each point, it is checked whether it belongs to ; if so, the considered point belongs to . Finally, the log volume of is computed by Monte Carlo integration, and the residual entropy is obtained by averaging the log volume over a large number of realizations. In Steps 3) and 4), fast quantizing algorithms [START_REF] Conway | Fast quantizing and decoding algorithms for lattice quantizers and codes[END_REF] are used. The results of Monte Carlo integration indicate that the lattice that maximizes the residual entropy for each is that with the best mean-squared quantization properties. This can be formally expressed as subject to constant [START_REF] Boyd | Convex Optimization[END_REF] where is the set of root lattices of dimensionality , and is the normalized second-order moment of . Notice that maximizes for given and and, consequently, has the highest a priori entropy in , due to the uniformity of . For illustration purposes, Fig. 3 gives a comparison between the residual entropy per dimension using the cubic lattice and that using some of the root lattices. Fig. 3. Residual entropies per dimension for different lattices. All plots for the root lattices (but for the cubic one, which is theoretical) were obtained through Monte Carlo integration. The asymptotic limit corresponds to [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF]. The embedding distortion in all cases is D = =12, with = 0:5.

Although we do not claim that the above result holds for the whole set of lattices with arbitrary , at least it suggests that the security level of a lattice data hiding scheme be improved by increasing and choosing the lattice with the lowest . This leads us to conjecture that a hypothetical spherically shaped Voronoi region will provide an upper bound to the residual entropy, since the sphere is the region of with the smallest normalized second-order moment. This is indeed so for the set of lattices considered in our experiments: as an example, the result obtained with the 8-D sphere (also obtained through Monte Carlo) is plotted in Fig. 3. Unfortunately, the space cannot be tessellated with spherical regions (except for ), so it is not possible to construct spherical lattice quantizers; nevertheless, as it was shown in [START_REF] Zamir | On lattice quantization noise[END_REF], as increases, there exist lattices whose normalized second-order moment tend to that of a sphere. 7 The security of lattice DC-DM using this type of lattice is studied in the next section.

C. Bounds and Asymptotics on the Equivocation for "Good" Lattices

Throughout this section, we will make use of two assumptions: 1)

; 2) we are using , the optimal (in a meansquared error sense) lattice quantizer in -dimensions. As discussed in the Proof of Property 2, Assumption 1 makes the modulo operation transparent for the computation of the entropy, since this is invariant to translations. Making use of the chain rule for mutual informations [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF], we can write [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF] where is the dither conditioned on the first observation (as it follows from Property 1 and Lemma 1). Thus, each new observation conditioned on and can be written as8 [START_REF] Vandenberghe | Semidefinite programming[END_REF] where is the self-noise term, with the same statistical distribution as and, hence, with the second moment per dimension . From [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF], it can be seen that the following equality holds: for [START_REF] Cheung | An optimal volume ellipsoid algorithm for parameter set estimation[END_REF] so we can use the second term of [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF] for obtaining a lower bound on the equivocation per dimension, as shown in Appendix B [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF] This lower bound is loose for small , but the next result shows that it is asymptotically tight for . Theorem 1: In the limit when , using the optimum lattice quantizer , the equivocation per dimension in lattice DC-DM is given by for [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] where is the embedding distortion per dimension [START_REF] Zamir | On lattice quantization noise[END_REF]. Proof: See Appendix C. Notice that when , (34) coincides with [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF], because . The first term in [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] accounts for the relation between the embedding distortion and the a priori entropy of the secret dither. The second term tells us how the equivocation decreases with , and the third term shows the dependence with the distortion compensation parameter , which basically introduces a constant shift in the equivocation curve (recall that for , the residual entropy is for ). The asymptotic value of the equivocation is plotted in Fig. 3 d = 0 8i = 1; . . . ; N ; without loss of generality for the remainder of this section and in the corresponding appendices. for reference, showing the gap with the root lattices studied before. The above theorem is the formal statement of a more intuitive result: the Voronoi region of tends to a sphere and, in turn, the uniform distribution in tends asymptotically to a Gaussian distribution (in the normalized entropy sense) [START_REF] Zamir | On lattice quantization noise[END_REF]; hence, roughly speaking, each modulo--reduced observation (32) becomes closer to a Gaussian distribution with variance , whose mean is given by the secret dither (also with the same statistical distribution). This interpretation brings more insight in the comparison of the theoretical security between lattice DC-DM and additive spread-spectrum methods. For the latter, the embedding function is given by , where and are the host and the spreading vector, respectively, with the latter playing the role of the secret key. Notice that the resemblance between this embedding function and (32) implies similar security properties for both methods. Considering that and , it was shown in [START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF] that [START_REF] Walter | Exact recursive polyhedral description of the feasible parameter set for bounded-error models[END_REF] where now . It can be readily seen that the decrease in the equivocation for additive spread spectrum is determined by the ratio , which is usually very small due to imperceptibility constraints. Instead, for lattice DC-DM after the modulo-reduction, the power of both the watermark and the host interference are the same (i.e., ); this explains the term in [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] and the rapid decrease of the equivocation, compared to that of [START_REF] Walter | Exact recursive polyhedral description of the feasible parameter set for bounded-error models[END_REF].

Fig. 4 shows a comparison between lattice DC-DM and additive spread spectrum for different values of embedding distortion, parameterized by the document to watermark ratio, defined as .

D. Bounds on the Estimation Error

Let us define the estimation error as , where is the dither estimate. If the covariance matrix of the estimation error is given by , then it is immediate to upperbound its entropy by [START_REF] Pérez-Freire | Secret dither estimation in lattice-quantization data hiding: A set-membership approach[END_REF] Furthermore, note that [START_REF] Lin | Temporal synchronization in video watermarking[END_REF] since is a function of the observations. Thus [START_REF] Moulin | Block QIM watermarking games[END_REF] where the second inequality follows from the fact that ([6] Theorem 16.8.4). Let us define the variance per dimension of the estimation error as . Then, from (39), we have the following lower bound on : [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF] which is nothing but the entropy power of given observations [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF]. It can be observed that, for achieving an error-free estimate, the equivocation must necessarily approach . Substituting [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] into [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF], we arrive at the following bound for and the optimal lattice quantizer:

(41)

The above bound is attained by using the simple averaging estimator, but taking into account that the observations must be properly shifted in order to avoid problems with the moduloreduction; thus, if we define (42) then the optimal dither estimator for , is given by (43)

The achievability of (41) follows from the fact that, for , the self-noise and the secret dither follow asymptotically a Gaussian distribution as . Thus, this result about the estimation error can be compared to the estimation error for the cubic lattice. Since we are interested in obtaining the behavior for large , we make use of the approximation , which is asymptotically tight for large , with the harmonic number and the Euler-Mascheroni constant, defined as . In this case we have, using [START_REF] Gurijala | Speech watermarking with objective fidelity and robustness criteria[END_REF] (44) Thus, the variance per dimension approximately decreases with the inverse of the squared number of observations. This bound can even be compared to the exact error variance of the optimal dither estimator in order to check the tightness of the bound. For the cubic lattice, dither estimation may be carried out independently for each component without loss of optimality. It is a well-known result that the optimal dither estimator in a mean-squared error sense is given by the mean value of the dither conditioned on the observations: in our case, the th component of the dither is uniformly distributed in an interval ; hence, the optimal estimate is , and the variance per dimension of the estimation error is (45) where is the width of the feasible interval, and the expectation is taken over the joint pdf of the observations. Actually, this expectation may be computed by replacing by in (64) of Appendix A, resulting in (46) which for large is dominated by the term , differing from the right-hand side of (44) only in a constant multiplying factor. Note that due to the approximation of used in (44), the latter is a lower bound only for ; nevertheless, making use of the exact expression for , the right-hand side of (44) can be shown to be always lower than (46).

IV. PRACTICAL ALGORITHMS FOR SECRET DITHER ESTIMATION

The theoretical analysis carried out in the previous sections, besides quantifying the information leakage about the secret dither, gives important hints about how to perform dither estimation. Indeed, the information-theoretic formulation given in Section II is closely related to the theory of set-membership estimation (SME) (also known as set-theoretic estimation) [START_REF] Deller | Set membership identification in digital signal processing[END_REF], [START_REF] Combettes | The foundations of set theoretic estimation[END_REF], which is widely known in the field of automatic control and in certain signal processing areas, such as image recovery. 9 In the set-membership formulation of a problem with solution space , the th observation is associated with a subset that contains all estimates which are consistent with that observation; formally, can be expressed as (47) 9 Interestingly, the set-membership framework has been previously applied to watermark embedding in speech signals [START_REF] Gurijala | Speech watermarking with objective fidelity and robustness criteria[END_REF].

where is a certain indicator function that depends on the problem formulation, and is the number of available observations. The subset of estimates which are consistent with all of the available information is the so-called feasible solution set and is given by ; finally, a set-membership estimate consists in choosing any point . In the dither estimation problem, the solution space of interest is . We will deal for now only with the KMA scenario, deferring until Section IV-C the (minor) modifications needed to cope with the CMA case. Thus, the indicator function is given by otherwise (48) so and , where and were defined in Property 1. Moreover, if , which is the worst case for the attacker, the set-membership estimator becomes the maximum likelihood dither estimator. Although intuitively simple, such an estimator may not be practical, since exact computation of the solution sets may be computationally prohibitive, because of the number of vertices in for . Nevertheless, the attacker may not be interested in obtaining the exact , but instead be satisfied with an accurate approximation of the feasible solution set. Algorithms that are suitable for performing such approximation are discussed in this section. Albeit other algorithms with better performance could be devised, our main purpose is to show that the theoretical information leakage may be exploited in practice with manageable complexity.

According to Property 2, the assumption allows us to consider the feasible region as a modulo convex set. Furthermore, if we shift all observations by , then the modulo operation is transparent, so the feasible regions for each observation [START_REF] Mihcak | Cryptanalysis of discrete-sequence spread spectrum watermarks[END_REF] can be now simplified to 10 (49) with defined in (42), rendering the problem convex, since the feasible solution sets (which are, in fact, polytopes) result from the intersection of convex sets. Some guidelines about how to modify the algorithms in order to work with will be given in Section VIII.

The Voronoi region of any lattice can be described in a variety of ways; for our purposes, the most appropriate description is by means of the bounding hyperplanes corresponding to its facets. In the following we assume that, for a Voronoi cell with facets, we know: 1) a vector which is outward-pointing normal to the th facet; 2) a point on the th facet. Taking into account each of the modified observations , we have (50)

A. Inner Polytope Algorithm

The set of modified observations together with (50) define an ensemble of linear inequalities which, in turn, describe 10 Obviously, the offset 0ỹ 0d must be removed from the final estimate. a polytope in -dimensional space. Hence, the feasible solution set can be expressed as (51)

We are interested in computing an approximation of the feasible region. For such an approximation to be valid, it must outerbound (as tightly as possible), since we do not want to discard any point in a priori, and it is also desirable that the approximate region be easy to describe. Then, a reasonable choice is to search for the ellipsoid of minimum volume that contains (formally known as the Löwner-John ellipsoid of [START_REF] Boyd | Convex Optimization[END_REF]). Unfortunately, the problem of finding the ellipsoid of interest is ill-posed (indeed, it has been shown to be an NP-complete problem) [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF], but on the other hand, the problem of finding the maximum volume ellipsoid contained in the polytope defined by a set of linear inequalities is well posed. Moreover, if we scale such an ellipsoid by a factor of around its center ( is the dimensionality of the lattice), then the resulting ellipsoid is guaranteed to bound [START_REF] Boyd | Convex Optimization[END_REF]. An ellipsoid in Euclidean space is defined by its center and a symmetric positive definite matrix such that (52)

The computation of and for the maximum volume ellipsoid contained in can be written as a convex minimization problem with second-order cone constraints [START_REF] Boyd | Convex Optimization[END_REF] (53) This problem can be recast as a semidefinite problem [START_REF] Vandenberghe | Semidefinite programming[END_REF] where a linear function is minimized subject to linear matrix inequality (LMI) constraints; this kind of optimization problems can be efficiently solved by means of interior-point methods [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF]. As will be checked in Section V, this approach yields tight approximations to , but it presents an obvious drawback: the potential complexity of the minimization problem arising from the huge number of constraints imposed by large and . The scheme presented in the next section reduces the complexity by means of an iterative approach. [START_REF] Cheung | An optimal volume ellipsoid algorithm for parameter set estimation[END_REF] This is a classical SME algorithm that was originally devised for estimation in noisy AR models where are the past observations, is the vector of parameters to be estimated, and is the noise term, whose absolute value is assumed to be bounded by . For the th observation, the feasible solution set is given by all points in that are consistent with the observation, that is (54) Equation ( 54) defines a region of delimited by two parallel hyperplanes which encloses the true parameter vector . The series of solution sets is then constructed iteratively as . In order to avoid the costly computation of the exact , the solution sets are approximately described by means of bounding ellipsoids.

B. Optimal Volume Ellipsoid (OVE)

This algorithm can be straightforwardly applied to our problem by slightly modifying the description of the feasible region given in (50): in our case, we need to parameterize as the intersection of a finite number of parallel hyperplanes. Assuming that the Voronoi cell of the considered lattice is composed of pairwise parallel facets [Fig. 5(a)], 11 the feasible solution set for the th observation can be specified by a matrix and a vector such that , where

is the th column of , and is the th element of . Hence, the series of solution sets is given by (56)

The computation of the th solution set amounts to obtaining an ellipsoid . Such an ellipsoid is iteratively computed in the following manner.

Step 1) First, make

Step 2) Compute .

Step 3) Finally, make . This way, in Step 2), we are intersecting iteratively one ellipsoid with one set , as is depicted in Fig. 5(b). Clearly, we are interested in finding the ellipsoid with minimum volume that contains such an intersection, that is subject to (57) which is precisely the minimization problem addressed in the OVE algorithm [START_REF] Cheung | An optimal volume ellipsoid algorithm for parameter set estimation[END_REF], whose analytic solution reads as

where and are variables that depend on the observation , the current ellipsoid and (details about their calculation can be found in [START_REF] Cheung | An optimal volume ellipsoid algorithm for parameter set estimation[END_REF]), and finally is the th column of matrix .

The algorithm just described is obviously optimal in one dimension, since the ellipsoids are simply real intervals. Another interesting feature of this approach, and common to many other iterative SME algorithms is that further refinements on the solution set are possible by recirculating the observed data, that is, by feeding to the system the same set of observations repeatedly (as if they were in a circular buffer, for instance). This is possible because the resulting bounding ellipsoid in the th iteration depends on both the th bounding ellipsoid and the th observation. This important feature provides performance similar to that of the above inner polytope algorithm, as will be checked in Section V.

C. Dither Estimation in the CMA Scenario

The CMA scenario implies minor changes to the estimation algorithms proposed above for the KMA case. Actually, estimation in the CMA case can be performed as follows.

1) Assume that the sequence of observations is watermarked with message . 2) Perform estimation as in the KMA case.

3) Once has been obtained, compute the approximate feasible region as in [START_REF] Parnas | On testing convexity and submodularity[END_REF]. 4) Provided that , two possible cases may arise after performing Step 3: • The resulting feasible regions overlap; then, according to [START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF], the probability of finding the dither in their intersection is higher than in the remaining regions.

• The regions do not overlap; then, the dither is equally likely in any of the feasible regions.

V. EXPERIMENTAL RESULTS

This section provides a comparison of the practical performance for the different estimators proposed in Section IV, considering only the KMA scenario. The optimization problems involving LMIs were solved using the optimization packages YALMIP [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF] and SeDuMi [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] for Matlab, and the set of observations was generated according to the distribution given in [START_REF] Shannon | Communication theory of secrecy systems[END_REF]. As for the theoretical part, we will consider here some of the so-called root lattices and their duals, introduced in Section III. The Voronoi regions of these lattices are described in [START_REF] Conway | Voronoi regions of lattices, second moments of polytopes, and quantization[END_REF], from which we derived all of the parameters needed for implementing our attack. We provide two different measures of performance of the proposed estimators:

1) the first one is based on the volume of the estimated feasible regions. The volume of the th ellipsoid reads as

where stands for the volume of the -dimensional sphere of unit radius. When , all points in the interior of the estimated feasible region have the same probability of being the true dither vector , so it is immediate to compute the residual entropy of the dither as . The average value of this empirical residual entropy is computed over a large number of realizations. The performance of each method is quantified by the gap between this measure and the theoretical result of Section III.

2) The second measure of performance is the squared estimation error per dimension (i.e., ), where has been taken as the center of the resulting ellipsoid. Note that, as long as this center is close to the center of masses of , the resulting estimator will be close to the minimum mean-squared error estimator (i.e., the conditional mean estimator). Again, the plots represent this squared error averaged over a large number of observations.

In the experiments, the embedding distortion was fixed to , with . Fig. 6 shows the performance (in residual entropy terms) of the different estimators when the embedding lattices are the hexagonal and [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF]. Although the inner polytope algorithm provides the best performance, it can be observed that the property of recirculation allows to compensate for the loss of optimality of the OVE algorithm. The performance gain is remarkable for the first recirculations, but marginal above a certain number, as can be seen in Fig. 6(b). Also, notice that the number of recirculations must be increased with in order to match the performance of the inner polytope algorithm. Finally, the plots in Fig. 7 show the empirical mean squared error per dimension obtained with each method. The lower bound given by ( 40) is plotted for comparison, showing the good performance of both methods. Interestingly, the OVE algorithm seems to perform better than the inner polytope in terms of mean squared error. The performance of the averaging estimator is also plotted for reference; such an estimator is optimal for and , as discussed in Section III-D, but for small , it is clearly far from being so.

A. Possible Attacks Based on Dither Estimates

Once the attacker has estimated the dither signal (using the methods proposed here, for instance), he or she can exploit this knowledge in order to devise powerful attacks against the data hiding scheme which would not be possible for a blind attacker. The following are some examples.

1) Complete watermark removal: under the KMA assumptions (i.e., knowledge of the message embedded) the embedding process of lattice DC-DM is fully invertible when the dither is known, as long as the distortion compensation parameter used is smaller than 1 [START_REF] Eggers | Scalar Costa Scheme for information embedding[END_REF]Sec. VII]. This implies that the attacker is able to recover the original host signal, provided that and the watermarked signal does not suffer any noninvertible transformation a posteriori, such as clipping or rounding. In the CMA case, there is not a unique possible original host, but the uncertainty is reduced to a finite set of vectors (as many as

). 2) Unauthorized embedding of messages: in copy protection scenarios, the attacker may remove the watermark inserted in a certain protected content and embed later a different message: for instance, he or she may change the status of a video from "Copy Never" to "Copy Once." 3) Generation of forgeries: in the authentication scenarios proposed by Eggers et al. [START_REF] Eggers | Blind watermarking applied to image authentication[END_REF] that are mainly threatened by the CMA attack, as it was discussed in the introduction, the attacker can watermark contents that will be taken as authentic. Notice that for generating a forgery, there is no need to know the exact correspondence between messages and coset representatives. 4) And, finally, unauthorized decoding of messages embedded in other pieces of content watermarked with the same key. Take into account that reliable decoding is possible only if the dither estimate was obtained in the KMA scenario; in the CMA case, the ambiguity on the embedded message will allow, at most, to check whether different watermarked contents convey the same message or not. Obviously, the goodness of the host reconstruction in the first attack will depend on the accuracy of the dither estimate at hand. For the other attacks, this accuracy will affect their probability of success in the sense that poor estimates may lead to the wrong decoding/detection region.

B. Complexity Issues

One can find in the literature of set-membership estimation approaches that offer better performance than the ellipsoidal approximations by computing the exact solution sets [START_REF] Combettes | The foundations of set theoretic estimation[END_REF], [START_REF] Walter | Exact recursive polyhedral description of the feasible parameter set for bounded-error models[END_REF]. Nevertheless, they may be very computationally demanding in large-scale problems. Instead, the algorithms considered in this paper have proved to be efficient in giving approximate solutions for several hundreds of observations. For the optimization problem in (53), it has been shown that the number of iterations needed to solve the problem (by means of interior-point methods) does not grow faster than a polynomial of the problem size [START_REF] Vandenberghe | Semidefinite programming[END_REF]. 12 Most of the computational cost of each iteration lies in the least-squares problem (of the same size as the original problem) that must be solved, whose number of iterations is again polynomial with the problem size. However, in practice, it is possible to exploit the problem structure (sparsity, for instance) so as to reduce complexity: in our case, for example, there is a potentially large number of redundant constraints that can be removed for alleviating the computational burden. For high-dimensional lattices, it is also possible to simplify the problem description (albeit resulting in looser estimates) by approximating the considered Voronoi region by another simpler polytope that bounds . For the OVE algorithm, the number of arithmetic operations (scalar sums and products) carried out in each iteration is . Also, in the OVE algorithm, we perform exactly iterations, where is the number of observations, is the number of facets of the Voronoi cell (equivalently, the number of linear inequalities specifying the problem), and is the number of recirculations of the data. The term will largely depend on the considered lattice, in general, and will be determined by the required accuracy, giving a degree of freedom to the attacker. Finally, it is interesting to note that OVE-like algorithms automatically get rid of redundant constraints, using only those pairs of hyperplanes that produce an update on the solution set.

VI. COMPARISON: LATTICE DC-DM VERSUS COSTA

For the lattice DC-DM scheme we have analyzed in Section II, the entropy of the codebook is rather limited due to the codeboook structure and the chosen form of randomization, negatively affecting security. Lattice DC-DM schemes are deeply connected with the theoretical construction developed by Costa [START_REF] Costa | Writing on dirty paper[END_REF]. However, the codebook in the latter is totally different since it is random by definition. The main purpose of the brief comparison given in the following is to quantify how much can be gained in terms of security by using a codebook with these characteristics. The theoretical security analysis for Costa's scheme will not be included in this paper due to the lack of space, but it can be found in [START_REF] Pérez-Freire | Informationtheoretic analysis of security in side-informed data hiding[END_REF]. In Costa's scheme, for the KMA case and , it can be shown that (recall that )

where and stand for host and watermark power, respectively, and denotes the differential entropy of the codebook, given by . Equation (60) depends on the ratio which quantifies the embedding distortion, whereas depends both on and , where is the channel noise. Interestingly, if we make (which corresponds to a low embedding distortion regime), the information leakage for Costa tends to , exactly as for DC-DM [START_REF] Eggers | Blind watermarking applied to image authentication[END_REF]. Actually, the information leakage in lattice DC-DM also depends on and, in fact, it is possible to compute this dependency by means of numerical integration. In Fig. 8(a), the information leakage for Costa and scalar DC-DM (i.e., SCS) is shown. The striking similarity in the behavior of both schemes is remarkable. Furthermore, it can be seen that the asymptotic analysis is in good agreement with the numerical results for the range of embedding distortions of practical interest.

Nevertheless, when the comparison between Costa and lattice DC-DM is made in terms of residual entropy, the similarities disappear [Fig. 8(b)] whereas for lattice DC-DM, the entropy of the codebook is bounded by , the residual entropy in Costa's scheme is unbounded when . The last fact is a consequence of the codebook construction in Costa, where all codewords are mutually independent and its number increases with . This constitutes the main advantage, in terms of security, of the random codebook scheme over the lattice scheme that relies solely on dithering. For lattice DC-DM, the number of codewords follows a similar dependence with , but every codeword just depends on , the corresponding coset representative, and the secret dither.

On the other hand, for the CMA case and assuming that the watermarker is transmitting information at the maximum reliable rate allowed by the channel, we have (for )

This result is clearly related to that given in [START_REF] Conway | Voronoi regions of lattices, second moments of polytopes, and quantization[END_REF] for DC-DM.

Here, we can see that the uncertainty about the codebook increases exactly in the same quantity as the reliable transmission rate.

VII. APPLICATION TO OTHER SCENARIOS

In this section, we discuss the application of the proposed approaches to other related but more involved scenarios. This also shows the importance of the KMA scenario and of the estimators developed for such a case. 1) : Our analysis was restricted to the case . In the theoretical part, all of the given information leakages constitute upper bounds for . For this case, the theoretical analysis gets more intricate, since the feasible region may be composed of multiple moduloconvex sets (Fig. 2). Difficulty of the estimation is also greatly increased, since it would be necessary to apply several KMA/CMA estimators in parallel, one for each possible convex set. With large enough, all convex feasible regions are likely to vanish except one (in the KMA case), but the increase in the number of convex sets during the first observations may be fairly large, especially when .

In such a case, other set-membership approaches suited to nonconvex solution sets may perform better [START_REF] Combettes | The foundations of set theoretic estimation[END_REF]. 2) Spread transform dither modulation (STDM) [START_REF] Chen | Quantization Index Modulation: A class of provably good methods for digital watermarking and information embedding[END_REF]:

DC-DM schemes may be applied in conjunction with spread transform in low-rate data-hiding applications.

In that kind of scheme, lattice quantization takes place in a secret projected domain, parameterized by a certain projection matrix, and secret dithering can still be used in the projected domain for improving the security of the scheme. Ignorance of the projection matrix invalidates direct application of the estimation algorithms proposed here; however, recent works [START_REF] Cayre | Watermarking security: Theory and practice[END_REF], [START_REF] Bas | Security of DM quantization watermarking schemes: A practical study for digital images[END_REF] have shown that independent component analysis (ICA) may be used for estimating the projection matrix. Thus, if ICA is successful, dither estimators may be applied in a second step. 3) Total ignorance of the embedded messages: consider a general scenario where the only information at hand for the attacker is the set of watermarked signals; this is the so-called watermark only attack (WOA), following the nomenclature introduced in [START_REF] Cayre | Watermarking security: Theory and practice[END_REF]. A theoretical analysis similar to that of the KMA may be used to show that in this framework, it is possible to achieve (at least theoretically) perfect secrecy in some cases [START_REF] Pérez-Freire | Informationtheoretic analysis of security in side-informed data hiding[END_REF], [START_REF] Pérez-Freire | Secret dither estimation in lattice-quantization data hiding: A set-membership approach[END_REF], for instance, when is used in a binary transmission scheme. In the practical side, it is still possible to carry out dither estimation as long as the perfect secrecy condition is not fulfilled; however, KMA estimators cannot be directly applied: one needs to hypothesize first a message sequence and then apply the KMA estimator. However, the problem can be tackled without the need of a brute-force approach if the posterior probability of the message sequences is considered. The maximum likelihood estimate of the message sequence is (62) and the posterior probability can be factored as (63) where the conditional pdf of the secret dither is given by [START_REF] Eggers | Estimation of amplitude modifications before SCS watermark detection[END_REF]. When the pdf of the secret dither is uniform, computation of each term in (63) is straightforward, since it is proportional to the volume of . Based on this factorization, dither estimation in the WOA scenario may be thought of as a tree search where a KMA estimator is applied to each branch, and each branch corresponds to a hypothesized message sequence whose probability can be computed through (63). During the tree search, those branches with low probability may be discarded for simplifying the estimation. Moreover, if the value of is above a certain threshold (which depends on and the specific lattice partition), the complexity of the tree search can be dramatically reduced because all branches with non-null probability can be written in terms of a unique branch. As an interesting byproduct of this approach, an estimate of the embedded message sequence can be also obtained. Nevertheless, notice that these are only the main guidelines of the procedure that should be applied to the WOA scenario; a more rigorous and complete analysis will be published elsewhere. 4) Permutations: the security of a lattice DC-DM scheme may be improved by applying secret permutations to the host vectors. This introduces an additional degree of uncertainty that invalidates the direct application of the estimators proposed in this paper. However, if the same permutation is used in multiple watermarked blocks, it is still possible to exploit the information leakage, as shown in the next example: assume that the host is partitioned in -length vectors , and these vectors are arranged in a matrix . Given a secret permutation matrix , the columns of the new matrix are watermarked using the standard lattice DC-DM scheme, yielding a watermarked matrix . Later on, the inverse permutation is applied to , obtaining , and its rows are the observations that are made available to the attacker. Depending on the symmetry properties of the embedding lattice, two possible cases arise: 1) The lattice is symmetric to permutations of its components. This happens, for instance, to the cubic and checkerboard (also known as quincunx) lattices in two dimensions [START_REF] Moulin | Data hiding codes[END_REF], [START_REF] Conway | Sphere Packings, Lattices and Groups, ser[END_REF]. If this is the case, then the attacker can run the dither estimation algorithm disregarding the actual permutation, obtaining an estimate of the permuted dither. It is easy to see that this permuted estimate allows the same attacks as those discussed in Section V-A, as long as the permutation and the secret dither are the same in the attacked contents.

2) The lattice is not symmetric to permutations. The main consequence is that the feasible regions for the dither are different under each permutation, and this can be exploited to detect inconsistent arrangements in the components of the observations (i.e., those arrangements that produce an empty feasible region cannot be correct). Some experiments performed with the OVE algorithm and the hexagonal lattice have shown that, using ten recirculations, an average of 32 observations is needed to successfully detect inconsistent arrangements of the components. Using the inner polytope algorithm, it is also possible to check inconsistencies: one just needs to run the feasibility test to check whether all constraints in the optimization problem can be simultaneously satisfied or not. If not, the considered arrangement is inconsistent.

VIII. CONCLUSION

The main conclusion of this work is that lattice DC-DM schemes for data hiding relying only on secret dithering are vulnerable to security attacks both in the KMA and CMA scenarios, of practical interest as discussed in the Introduction.

For the scenarios considered in this paper, it was shown in Section III that the security level (in terms of residual entropy)

Fig. 1 .

 1 Fig. 1. Block diagram of lattice-based DC-DM with pseudorandom dithering. Parameter 2 is the secret key.

2

 2 WNR log (D = ), where D and are the embedding distortion and noise power per dimension, respectively. Throughout this paper, the terms high and low WNR are loosely applied to WNR > 0 dB and WNR 0 dB, respectively.

Fig. 2 .

 2 Fig. 2. Illustration of a nonconnected feasible region for two observations using small . In (a), the solid lines are the Voronoi regions of 3, and the feasible regions for the centroids defined by each observation are the shaded ones and (b) depicts the modulo-3 reduction of the intersection between the shaded regions in (a), showing three resulting modulo-3 convex regions (illustrated with different shadings).

Fig. 4 .

 4 Fig. 4. Comparison, in terms of equivocation per dimension, between lattice DC-DM and additive spread spectrum. = 0:7 for DC-DM.

Fig. 5 .

 5 Fig. 5. (a) Voronoi region of the hexagonal lattice delimited by three pairs of parallel hyperplanes. (b) Intersection between an ellipsoid and a pair of hyperplanes.

Fig. 6 .

 6 Fig. 6. Performance comparison (in terms of residual entropy) for the hexagonal lattice (a) and Gosset lattice E (b), for KMA and = 0:5.

Fig. 7 .

 7 Fig. 7. Mean squared error per dimension of the dither estimate, for the hexagonal lattice (a) and Gosset lattice E (b), for KMA and = 0:5.

Fig. 8 .

 8 Fig. 8. Comparison of the security provided by Costa's scheme and lattice DC-DM, in terms of mutual information (a), and residual entropy (b) per dimension. DWR 10 log (), and WNR log ().

The extension to more general scenarios using secret coefficient permutations, for instance, will be addressed in Section VII.

Strictly speaking, this is true only if the flat-host assumption (to be defined later) holds, as noted in[START_REF] Pérez-Freire | Spread-spectrum vs. quantization-based data hiding: Misconceptions and implications[END_REF].

We consider the same quantization step in each dimension, although the results can be straightforwardly extended to a general case.

Moreover, this is a necessary condition for the lattices to achieve the channel capacity in the lattice DC-DM scheme[START_REF] Erez | Achieving 1=2 log(1 + SNR) over the additive white gaussian noise channel with lattice encoding and decoding[END_REF].

As discussed before, the residual entropy in the KMA scenario does not depend on the specific message sequence as long as this is known, so we consider

Should this not be true, the problem can still be recast in a similar manner by adding some additional hyperplanes.

The size of an optimization problem is commonly understood as the dimensionality of a vector whose components are the coefficients of the analytical expressions for the constraints and the objective variables.

ACKNOWLEDGMENT

The authors would like to thank Prof. P. Moulin for his useful comments that helped to improve the final version of this paper, and to T. Liu for helpful discussions about the Proof of Theorem 1.

This work was supported in part by Xunta de Galicia under Projects PGIDT04 TIC322013PR and PGIDT04 PXIC32202PM; in part by MEC Project DIPSTICK, Reference TEC2004-02551/TCM; in part by FIS Project IM3, Reference G03/185, European Commission through the IST Program under Contract IST-2002-507932

ECRYPT, and in part by the Fundación Caixa Galicia Grant for postgraduate studies. The information in this paper is provided as is, and no guarantee or warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.

can be enlarged by increasing the dimensionality and choosing the appropriate lattice quantizer, although the gain for small is rather limited; also, asymptotic values are given for the equivocation and the variance of the estimation error, explaining the fundamental gap between the security of DC-DM schemes and spread-spectrum methods. Section V shows the strong link between the information-theoretic and set-membership estimation frameworks, applying the latter for the first time to attacks in the data hiding scenario. Additionally, the results in that section confirm that (suboptimal) attacks to security can be made with manageable complexity, yielding accurate dither estimates. This highlights the need for key management solutions, such as those proposed in [START_REF] Lin | Temporal synchronization in video watermarking[END_REF] through temporal redundancy control, in order to reduce the number of observations conveying information about the same dither sample.

The comparison given in Section VI shows that the security weaknesses of lattice DC-DM are not inherent to quantizationbased schemes, but they are due to the fact that the randomness of the codeboook relies only on secret dithering. A possible improvement using permutations was briefly considered in Section VII, but dither estimation attacks still seem to be possible, at least with low-dimensional lattices. A new strategy, recently proposed in [START_REF] Moulin | Block QIM watermarking games[END_REF], is the application of secret rotations to the embedding lattice. This approach, in conjunction with permutations, still keeps the structure of the codebook (which is desirable from an implementation point of view) while increasing its a priori entropy. Obviously, the counterpart is the increase needed in the length of the key, but it still constitutes a promising strategy that deserves rigorous analysis in the future.

APPENDIX A RESIDUAL ENTROPIES IN ONE DIMENSION

Here, we compute the mean value of [START_REF] Combettes | The foundations of set theoretic estimation[END_REF]. It can be seen that . Hence, , where is the random variable defined as where , so the pdf of is . This allows us to rewrite the problem as (64) First, let us see how the pdf of can be computed. For having , it should be and ; this is so when , and , for , but taking into account that there are infinite values of that yield . Hence, the pdf of reads as (65) where the factor comes from the number of different orderings of the minimum and the maximum in vector ; since all observations are iid, we can simply multiply the integral by this factor. When , the computation of (65) in this case is straightforward and yields (66) for

. By inserting (66) into (64) and applying integration by parts recursively, the residual entropy results finally in (67) where is the th harmonic number.

APPENDIX B LOWER BOUND ON THE EQUIVOCATION

By the definition of mutual information, we have (

The first term of (68) can be bounded from the above as [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF] (69) where is the th component of , and denotes the th component of . Since the host signals and the secret dither are mutually independent, it follows that and are independent. Hence, we can write (70) where , and . Furthermore, it follows from Assumption 2 that the self-noise is white [START_REF] Zamir | On lattice quantization noise[END_REF] Taking into account that , and rearranging terms, we finally arrive at the following lower bound to the equivocation per dimension:

(75) and after substituting , we obtain [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF].

APPENDIX C PROOF OF THEOREM 1

In order to arrive at [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF], we start from the expression (76) which can be straightforwardly obtained by following the reasoning in Appendix II. First, we note that for the sequence of optimum lattice quantizers , we have [START_REF] Zamir | On lattice quantization noise[END_REF] (77)

On the other hand, we want to prove that the following relation holds:

(78) with independent and uniformly distributed in , being the Voronoi cell of with second moment per dimension

. Notice that we have rearranged the observation indices from to , for the sake of clarity. We will prove this result by making use of two lemmas.

Lemma 3: Let be two independent random variables uniformly distributed in . We have that (79)

Proof: The entropy power inequality [START_REF] Cover | Elements of Information Theory, ser. Wiley series in Telecommunications[END_REF] states that (80) Furthermore, we know that [START_REF] Zamir | On lattice quantization noise[END_REF] (81) so we can write (82) with . Thus, from (80), we have that (83) and we know from (72) that (84) for all . Hence, by combining (83) and (84), the lemma follows.

Lemma 4: For uniformly distributed in , the following result holds:

(85) Proof: We will prove the result by induction. Since it was proven for in Lemma 3, we will show now that it is true for , assuming that it holds for . Making use of the entropy power inequality and the convexity of in [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF], we can write (86) By using the chain rule for entropies, it can be shown that the following equivocation can be written as:

(87) and making use of the inductive hypothesis we have that (88) Thus, if we take limits in (86), we arrive at the following bound:

(89) Note that from the bounding given in (72) and the inductive hypothesis, it follows that:

(90) Hence, by combining ( 89) and ( 90), the lemma follows. Now, using the chain rule for differential entropies, we can write (91) and taking the limit when , by virtue of Lemma 4, we arrive at the result given in (78). Finally, by combining (76)-(78), we can conclude that which is the desired result. If we identify now , then Theorem 1 follows. Fernando Pérez-Gonz ´alez (M'90) received the telecommunications engineer degree from the University of Santiago, Santiago, Spain, in 1990 and the Ph.D. degree in telecommunications engineering from the University of Vigo, Vigo, Spain, in 1993.

He joined the faculty of the School of Telecommunications Engineering, University of Vigo, as an Assistant Professor in 1990 and is currently Professor in the same institution. He has visited the University of New Mexico, Albuquerque, for different periods spanning ten months. His research interests are digital communications, adaptive algorithms, robust control, and digital watermarking. He has been the manager of a number of projects concerned with digital television and radio, both for satellite and terrestrial broadcasting. He is co-editor of the book Intelligent Methods in Signal Processing and Communications (Birkhauser, 1997), has been Guest Editor of three special sections of the EURASIP Journal Signal Processing devoted to signal processing for communications and digital watermarking, as well as Guest Editor of a Feature Topic of the IEEE Communications Magazine on digital watermarking. He has also coauthored more than 30 papers in leading international journals and over 80 papers published in various conference proceedings.

Dr