We formalize a new attack model for collusion secure codes, incorporating attacks on the underlying watermarking scheme as well as cut-and-paste attacks traditionally considered for collusion secure codes. We use this model to analyze the collusion resistance of two versions of the Tardos code, both for binary and nonbinary alphabets. The model allows us to consider different signal processing attacks on the content, namely the addition of noise and averaging attacks. The latter may result in content segments that have multiple watermarks embedded. We study two versions of the$q$-ary Tardos code in which the accusation method has been modified so as to allow for the detection of multiple symbols in the same content segment. We show that both variants yield efficient codes in the new model, parametrized for realistic attacker strengths.

Today, mass-scale electronic content distribution systems embed forensic tracking watermarks primarily at the distribution server. For limiting the bandwidth usage and server complexity and enhancing scalability, it is preferable to embed the watermark at the client. Embedding in these untrusted clients requires secure embedding methods that do not leak unmarked content or the watermarking secrets. In this work, we propose a secure watermark embedding scheme based on lookup tables for spread-spectrum watermarks, which are robust to noise and can be detected without comparison to the original content. We also develop fast detection mechanisms that make the watermark detection feasible for tracking systems with a large number of clients. Our fast detection algorithm improves detection speed of existing methods by six orders of magnitude in a typical system with millions of clients.

In a forensic watermarking architecture, a buyer-seller protocol protects the watermark secrets from the buyer and prevents false infringement accusations by the seller. Existing protocols encrypt the watermark and the content with a homomorphic public-key cipher and perform embedding under encryption. When used for multimedia data, these protocols create a large computation and bandwidth overhead. In this correspondence, we show that the same functionality can be achieved efficiently using recently proposed secure watermark embedding algorithms.

Tardos has proposed a randomized fingerprinting code that is provably secure against collusion attacks. We revisit his scheme and show that it has significantly better performance than suggested in the original paper. First, we introduce variables in place of Tardos' hard-coded constants and we allow for an independent choice of the desired false positive (FP) and false negative (FN) error rates. Following through Tardos' proofs with these modifications, we show that the code length can be reduced by more than a factor of two in typical content distribution applications where high FN rates can be tolerated. Second, we study the statistical properties of the code. Under some reasonable assumptions, the accusation sums can be regarded as Gaussian-distributed stochastic variables. In this approximation, the desired error rates are achieved by a code length twice shorter than in the first approach. Overall, typical FP and FN error rates may be achieved with a code length approximately five times shorter than in the original construction.

Human Desoxyribo-Nucleic Acid (DNA) sequences offer a wealth of information that reveal, among others, predisposition to various diseases and paternity relations. The breadth and personalized nature of this information highlights the need for privacy-preserving protocols. In this paper, we present a new error-resilient privacy-preserving string searching protocol that is suitable for running private DNA queries. This protocol checks if a short template (e.g., a string that describes a mutation leading to a disease), known to one party, is present inside a DNA sequence owned by another party, accounting for possible errors and without disclosing to each party the other party's input. Each query is formulated as a regular expression over a finite alphabet and implemented as an automaton. As the main technical contribution, we provide a protocol that allows to execute any finite state machine in an oblivious manner, requiring a communication complexity which is linear both in the number of states and the length of the input string.

In an electronic content distribution system, it is preferable to embed forensic tracking watermarks at the client-side to limit bandwidth usage and server complexity. Embedding in these untrusted clients, however, requires secure embedding methods that do not leak unmarked contents or the watermarking secrets. In this work, we propose a look-up-table (LUT) based cipher, similar to Andersen's Chameleon cipher, for securely embedding spread-spectrum watermarks, which are noise robust and detectable without the original content. We also develop fast detection mechanisms that make the watermark detection feasible for tracking systems with large number of clients. Our fast detection algorithm improves detection speed six orders of magnitude in a typical system.

Unauthorized re-distribution remains a significant threat for emerging electronic movie distribution services. In this paper, we propose a forensic tracking watermark for MPEG-2 bit-streams that can be employed to complement Digital Rights Management and conditional access systems in electronic movie distribution. The watermark is embedded by modulating a subset of quantization matrix entries, which are periodically present in the MPEG-2 headers. When observed over time the watermark can be detected even after cropping, de-interlacing, resizing and DivX compression at 300 kbps or after being captured with a video camera from a flat-screen TV. As the method modifies only a small part of the bit-stream (ap100 bytes per second), it can be readily implemented in resource constrained environments like the current generation set-top boxes, without costly hardware upgrades.

We propose a method for embedding a robust forensic tracking watermark within the AAC decoder during audio playback. For predefined frequency bands, the method intercepts and modifies the scale-factors, which are present in the AAC bit-stream. It thereby modulates the short-time envelope of the band-limited audio and embeds a watermark which is robust to various attacks such as recompression and acoustic transmission. Due to its low complexity - a few additions per AAC frame - the method is suitable for implementation even in resource constrained devices such as portable players. Furthermore, decode-time embedding enables dynamic payload assignments which may be used to signal playback time and location.

In digital rights-management systems, forensic watermarking complements encryption and deters the capture and unauthorized redistribution of the rendered content. In this paper, we propose a novel watermarking method which is integrated into the advanced audio coding (AAC) standard's decoding process. For predefined frequency bands, the method intercepts and modifies the scale factors, which are utilized for dequantization of spectral coefficients. It thereby modulates the short-time envelope of the bandlimited audio and embeds a watermark which is robust to various attacks, such as capture with a microphone and recompression at lower bit rates. Inclusion of watermark embedding in the AAC decoder has practically no effect on the decoding complexity. As a result, the proposed method can be integrated even into resource-constrained devices, such as portable players without any additional hardware.

We introduce a set theoretic framework for watermarking. Multiple requirements, such as watermark embedding strength, imperceptibility, robustness to benign signal processing, and fragility under malicious attacks are described as constraint sets and a watermarked image is determined as a feasible solution satisfying these constraints. We illustrate that several constraints can be formulated as convex sets and develop a watermarking algorithm based on the method of projections onto convex sets. The framework allows flexible incorporation of different constraints, including embedding strength requirements for multiple watermarks that share the same spatial context and different imperceptibility requirements based on frequency-weighted error and local texture perceptual models. We illustrate the effectiveness of the framework by designing a hierarchical semifragile watermark that is tolerant to mild compression, allows tamper localization, and is fragile under aggressive compression. Using a quad-tree representation, a spatial resolution hierarchy is established on the image and a watermark is embedded corresponding to each node of the hierarchy. The spatial hierarchy of watermarks provides a graceful tradeoff between robustness and localization under mild JPEG compression, where watermarks at coarser levels demonstrate progressively higher immunity to JPEG compression. Under aggressive compression, watermarks at all hierarchy levels vanish, indicating a lack of trust in the image data. The constraints implicitly partition watermark power in the resolution hierarchy as well as among image regions based on robustness and invisibility requirements. Experimental results illustrate the flexibility and effectiveness of the method

We present a novel framework for lossless (invertible) authentication watermarking, which enables zero-distortion reconstruction of the un-watermarked images upon verification. As opposed to earlier lossless authentication methods that required reconstruction of the original image prior to validation, the new framework allows validation of the watermarked images before recovery of the original image. This reduces computational requirements in situations when either the verification step fails or the zero-distortion reconstruction is not needed. For verified images, integrity of the reconstructed image is ensured by the uniqueness of the reconstruction procedure. The framework also enables public(-key) authentication without granting access to the perfect original and allows for efficient tamper localization. Effectiveness of the framework is demonstrated by implementing the framework using hierarchical image authentication along with lossless generalized-least significant bit data embedding.

Steganographic methods attempt to insert data in multimedia signals in an undetectable fashion. However, these methods often disrupt the underlying signal characteristics, thereby allowing detection under careful steganalysis. Under repeated embedding, disruption of the signal characteristics is the highest for the first embedding and decreases subsequently. That is, the marginal distortions due to repeated embeddings decrease monotonically. We name this general principle as the principle of diminishing marginal distortions (DMD) and illustrate its validity in the audio domain using a morphological distortion metric. The principle of DMD is used to derive a steganalysis tool that detects the presence of hidden messages in uncompressed audio files. Detailed analysis and experimental results are provided for the detection of spread spectrum watermarking and stochastic modulation steganography.

We propose a speech watermarking algorithm based on the modification of the pitch (fundamental frequency) and duration of the quasi-periodic speech segments. Natural variability of these speech features allows watermarking modifications to be imperceptible to the human observer. On the other hand, the significance of these features makes the system robust to common signal processing operations and low data-rate source excitation based speech coders. This class of coders is particularly obstructive for conventional audio watermarking algorithms when applied to speech signals. A pitch synchronous overlap and add (PSOLA) algorithm is used for pitch and duration modifications in the watermark embedding phase. Experiments with multiple speech codecs show very good robustness with low data-rate (5-8 kbps) speech coders.

We introduce a set theoretic framework for watermarking and illustrate its effectiveness by designing a hierarchical semi-fragile watermark that is tolerant to compression and allows tamper localization. Using a quad-tree representation, a spatial resolution hierarchy is established on the image and a watermark is embedded corresponding to each node of the hierarchy. The watermarked image is determined so as to jointly satisfy the multiple constraints of watermark detectability, imperceptibility, and robustness to compression using the method of projections onto convex sets. The spatial hierarchy of watermarks provides a graceful trade-off between robustness and localization under JPEG compression: mild JPEG compression preserves watermarks at all levels of the hierarchy allowing fine localization of malicious changes while aggressive JPEG compression preserves watermarks at coarser levels of the hierarchy still assuring overall image integrity but giving up the capability for localization. Experimental results are presented to illustrate the effectiveness of the method.

We present a novel lossless (reversible) data-embedding technique, which enables the exact recovery of the original host signal upon extraction of the embedded information. A generalization of the well-known least significant bit (LSB) modification is proposed as the data-embedding method, which introduces additional operating points on the capacity-distortion curve. Lossless recovery of the original is achieved by compressing portions of the signal that are susceptible to embedding distortion and transmitting these compressed descriptions as a part of the embedded payload. A prediction-based conditional entropy coder which utilizes unaltered portions of the host signal as side-information improves the compression efficiency and, thus, the lossless data-embedding capacity.

Fingerprinting of audio-visual content using digital watermarks is an effective means of determining originators of unauthorized/pirated copies. Watermarks embedded in content can trace the traitor responsible for piracy. Multiple users may, however, collude and collectively escape identification by creating an average of their individually watermarked copies that appears unwatermarked. We propose a novel collusion-resilience mechanism, wherein the host signal is warped randomly prior to watermarking. As each copy undergoes a distinctive warp, collusion through averaging either yields low-quality results or requires substantial computational resources to undo random warps. The method is independent of the watermarking scheme used and imposes no restrictions on the watermark signal. We demonstrate the effectiveness of this approach on digital images.

This paper presents a novel watermarking method for low bit-rate video that is compressed according to the Advanced Simple Profile of MPEG-4. A spatial spread spectrum watermark was embedded directly to the MPEG-4 bit-streams by adopting Hartung's approach of watermarking MPEG-2 compressed bitstreams. A synchronization template was employed to combat cropping, scaling, and rotation. A gain control algorithm adjusts the local strength of the watermark depending on local image characteristics, in order to maximize watermark robustness and to minimize the impact on the quality of the video. A drift compensator prevents the accumulation of watermark distortion and reduces inter-frame interference of watermark signals due to motion compensated prediction in inter-coded frames. The developed watermarking algorithm was tested at bit-rates ranging from 128-768 Kbit/s. The watermark's impact on visual quality as well as its robustness after decompression, scaling, rotation, sharpening, and noise reduction was evaluated.

A level-embedded lossless compression method for continuous-tone still images is presented. Level (bit-plane) scalability is achieved by separating the image into two layers before compression and excellent compression performance is obtained by exploiting both spatial and inter-level correlations. A comparison of the proposed scheme with a number of scalable and non-scalable lossless image compression algorithms is performed to benchmark its performance. The results indicate that the level-embedded compression incurs only a small penalty in compression efficiency.

Fingerprinting of audio-visual content using digital watermarks is an effective means of determining the originators of unauthorized copies and fighting piracy in digital distribution networks. In particular, watermarks embedded within the content help trace the traitor responsible for the piracy. A group of users may, however, collude and collectively escape identification by creating an average of their individually watermarked copies that appears unwatermarked. We propose a novel collusion-resilience mechanism, wherein the host signal is warped randomly prior to watermarking. As each copy undergoes a distinctive warp, collusion through averaging either yields low-quality results or requires substantial computational resources to undo random warps. The proposed method is independent of the watermarking scheme used and does not impose any restrictions on the watermark signal that are required by some collusion resistant watermarking schemes. We demonstrate the effectiveness of this approach on digital images.

A novel MPEG-4 compressed domain video watermarking method is proposed and its performance is studied at video bit rates ranging from 128 to 768 kb/s. The spatial spread-spectrum watermark is embedded directly into compressed MPEG-4 bitstreams by modifying DCT coefficients. A synchronization template combats geometric attacks, such as cropping, scaling, and rotation. The method also features a gain control algorithm that adjusts the embedding strength of the watermark depending on local image characteristics, increasing watermark robustness or, equivalently, reducing the watermark's impact on visual quality. A drift compensator prevents the accumulation of watermark distortion and reduces watermark self-interference due to temporal prediction in inter-coded frames and AC/DC prediction in intra-coded frames. A bit-rate controller maintains the bit rate of the watermarked video within an acceptable limit. The watermark was evaluated and found to be robust against a variety of attacks, including transcoding, scaling, rotation, and noise reduction.

We present a novel reversible (lossless) data hiding (embedding) technique, which enables the exact recovery of the original host signal upon extraction of the embedded information. A generalization of the well-known LSB (least significant bit) modification is proposed as the data embedding method, which introduces additional operating points on the capacity-distortion curve. Lossless recovery of the original is achieved by compressing portions of the signal that are susceptible to embedding distortion, and transmitting these compressed descriptions as a part of the embedded payload. A prediction-based conditional entropy coder which utilizes static portions of the host as side-information improves the compression efficiency, and thus the lossless data embedding capacity.

Several fragile watermarking schemes presented in the literature are either vulnerable to vector quantization (VQ) counterfeiting attacks or sacrifice localization accuracy to improve security. Using a hierarchical structure, we propose a method that thwarts the VQ attack while sustaining the superior localization properties of blockwise independent watermarking methods. In particular, we propose dividing the image into blocks in a multilevel hierarchy and calculating block signatures in this hierarchy. While signatures of small blocks on the lowest level of the hierarchy ensure superior accuracy of tamper localization, higher level block signatures provide increasing resistance to VQ attacks. At the top level, a signature calculated using the whole image completely thwarts the counterfeiting attack. Moreover, "sliding window" searches through the hierarchy enable the verification of untampered regions after an image has been cropped. We provide experimental results to demonstrate the effectiveness of our method.

Several fragile watermarking schemes presented in the literature are either vulnerable to vector quantization (VQ) counterfeiting attacks or sacrifice localization accuracy to improve security. Using a hierarchical structure, we propose a method that thwarts the VQ attack while sustaining the superior localization properties of blockwise independent watermarking methods. In particular, we propose dividing the image into blocks in a multi-level hierarchy and calculating block signatures in this hierarchy. While signatures of small blocks on the lowest level of the hierarchy ensure superior accuracy of tamper localization, higher level block signatures provide increasing resistance to VQ attacks. At the top level, a signature calculated using the whole image completely thwarts the counterfeiting attack. Moreover, "sliding window" searches through the hierarchy enable the verification of untampered regions after an image has been cropped.