On random coding error exponents of watermarking systems

Watermarking codes are analyzed from an information-theoretic viewpoint as a game between an information hider and an active attacker. While the information hider embeds a secret message (watermark) in a covertext message (typically: text, image, sound, or video stream) within a certain distortion level, the attacker processes the resulting watermarked message, within limited additional distortion, in attempt to invalidate the watermark. For the case where the covertext source is memoryless (or, more generally where there exists some transformation that makes it memoryless), we provide a single-letter characterization of the maximin game of the random coding error exponent associated with the average probability of erroneously decoding the watermark. This single-letter characterization is in effect because if the information hider utilizes a memoryless channel to generate random codewords for every covertext message, the (causal) attacker will maximize the damage by implementing a memoryless channel as well. Partial results for the dual minimax game and the conditions for the existence of a saddle point are also presented     

Low-complexity sequential lossless coding for piecewise-stationarymemoryless sources

Three strongly sequential, lossless compression schemes, one with linearly growing per-letter computational complexity, and two with fixed per-letter complexity, are presented and analyzed for memoryless sources with abruptly changing statistics. The first method, which improves on Willems' (1994) weighting approach, asymptotically achieves a lower bound on the redundancy, and hence is optimal. The second scheme achieves redundancy of O(log N/N) when the transitions in the statistics are large, and O (log log N/log N) otherwise. The third approach always achieves redundancy of O (√log N/N). Obviously, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the analytical bounds derived for all the coding schemes     

Lower bounds on the error probability of block codes based on improvements on de Caen's inequality

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.     

Achievable Error Exponents for the Private Fingerprinting Game

Fingerprinting systems in the presence of collusive attacks are analyzed as a game between a fingerprinter and a decoder on the one hand, and a coalition of two or more attackers on the other hand. The fingerprinter distributes, to different users, different fingerprinted copies of a host data (covertext), drawn from a memoryless stationary source, embedded with different fingerprints. The coalition members create a forgery of the data while aiming at erasing the fingerprints in order not to be detected. Their action is modeled by a multiple-access channel (MAC). We analyze the performance of two classes of decoders, associated with different kinds of error events. The decoder of the first class aims at detecting the entire coalition, whereas the second is satisfied with the detection of at least one member of the coalition. Both decoders have access to the original covertext data and observe the forgery in order to identify member(s) of the coalition. Motivated by a worst case approach, we assume that the coalition of attackers is informed of the hiding strategy taken by the fingerprinter and the decoder, while they are uninformed of the attacking scheme. Achievable single-letter expressions for the two kinds of error exponents are obtained. Single-letter lower bounds are also derived for the subclass of constant composition codes. These lower and the upper bounds coincide for the error exponent of the first class. Further, for the error of the first kind, a decoder that is optimal is introduced, and the worst case attack channel is characterized     

Min-norm interpretations and consistency of MUSIC, MODE and ML

The multiple signal characterization (MUSIC) approach, its generalization to correlated signals known as the method of direction estimation (MODE), and the deterministic maximum likelihood (ML) approach for bearing estimation in array processing are shown to be signal subspace fitting approaches in a minimum norm sense. MODE, for example, is shown to be an approach in which the array manifold is linearly estimated from principal empirical eigenvectors in a minimum weighted Frobenius norm sense. Using the min-norm interpretations, a unified proof for strong consistency of the three approaches is provided for stationary and ergodic signals     

On causal and semicausal codes for joint information embedding and source coding

A source of random message bits is to be embedded into a covertext modeled as a discrete memoryless source (DMS), resulting in a stegotext from which the embedded bits should be recoverable. A causal code for such a scenario consists of an encoder that generates the stegotext as a causal function of the message bits and the covertext, and a decoder that reproduces the message bits as a causal function of the stegotext. A semicausal code, on the other hand, has an encoder that is causal only with respect to the covertext, and not necessarily with respect to the message, and has a possibly noncausal decoder. We analyze the possible tradeoffs among: a) the distortion between the stegotext and the covertext, b) the compressibility of the stegotext, and c) the rate at which random bits are embedded, that are achievable with causal and semicausal codes, with and without attacks on the stegotext. We also study causal and semicausal codes for the private version of the above scenario in which the decoder has access to the covertext. Connections are made with the causal rate-distortion function of Neuhoff and Gilbert, as well as the problem of channel coding with causal side information at the transmitter analyzed by Shannon.     

A competitive minimax approach to robust estimation of random parameters

We consider the problem of estimating, in the presence of model uncertainties, a random vector x that is observed through a linear transformation H and corrupted by additive noise. We first assume that both the covariance matrix of x and the transformation H are not completely specified and develop the linear estimator that minimizes the worst-case mean-squared error (MSE) across all possible covariance matrices and transformations H in the region of uncertainty. Although the minimax approach has enjoyed widespread use in the design of robust methods, we show that its performance is often unsatisfactory. To improve the performance over the minimax MSE estimator, we develop a competitive minimax approach for the case where H is known but the covariance of x is subject to uncertainties and seek the linear estimator that minimizes the worst-case regret, namely, the worst-case difference between the MSE attainable using a linear estimator, ignorant of the signal covariance, and the optimal MSE attained using a linear estimator that knows the signal covariance. The linear minimax regret estimator is shown to be equal to a minimum MSE (MMSE) estimator corresponding to a certain choice of signal covariance that depends explicitly on the uncertainty region. We demonstrate, through examples, that the minimax regret approach can improve the performance over both the minimax MSE approach and a "plug in" approach, in which the estimator is chosen to be equal to the MMSE estimator with an estimated covariance matrix replacing the true unknown covariance. We then show that although the optimal minimax regret estimator in the case in which the signal and noise are jointly Gaussian is nonlinear, we often do not lose much by restricting attention to linear estimators.     

On the error exponent of trellis source coding

In this paper, we develop a single-letter lower bound on the error exponent for the problem of trellis source coding. We demonstrate that for the case of a binary source with the Hamming distortion measure, and for rates close to the rate-distortion curve, this bound is superior to Marton's block-coding exponent, for the same computational complexity.     

Lower and upper bounds on the minimum mean-square error incomposite source signal estimation

The performance of a minimum mean-square error (MMSE) estimator for the output signal from a composite source model (CSM), which has been degraded by statistically independent additive noise, is analyzed for a wide class of discrete-time and continuous-time models. In both cases, the MMSE is decomposed into the MMSE of the estimator, which is informed of the exact states of the signal and noise, and an additional error term. This term is tightly upper and lower bounded. The bounds for the discrete-time signals are developed using distribution tilting and Shannon's lower bound on the probability of a random variable exceeding a given threshold. The analysis for the continuous-time signal is performed using Duncan's theorem. The bounds in this case are developed by applying the data processing theorem to sampled versions of the state process and its estimate, and by using Fano's inequality. The bounds in both cases are explicitly calculated for CSMs with Gaussian subsources. For causal estimation, these bounds approach zero harmonically as the duration of the observed signals approaches infinity     

The Shannon cipher system with a guessing wiretapper

The Shannon theory of cipher systems is combined with recent work on guessing values of random variables. The security of encryption systems is measured in terms of moments of the number of guesses needed for the wiretapper to uncover the plaintext given the cryptogram. While the encrypter aims at maximizing the guessing effort, the wiretapper strives to minimize it, e.g., by ordering guesses according to descending order of posterior probabilities of plaintexts given the cryptogram. For a memoryless plaintext source and a given key rate, a single-letter characterization is given for the highest achievable guessing exponent function, that is, the exponential rate of the pth moment of the number of guesses as a function of the plaintext message length. Moreover, we demonstrate asymptotically optimal strategies for both encryption and guessing, which are universal in the sense of being independent of the statistics of the source. The guessing exponent is then investigated as a function of the key rate and related to the large-deviations guessing performance