Abstract
Whereas the embedding distortion, the payload and the robustness of digital watermarking schemes are well understood, the notion of security is still not completely well defined. The approach proposed in the last five years is too theoretical and solely considers the embedding process, which is half of the watermarking scheme. This paper proposes a new measurement of watermarking security, called the effective key length, which captures the difficulty for the adversary to get access to the watermarking channel. This new methodology is applied to additive spread spectrum schemes where theoretical and practical computations of the effective key length are proposed. It shows that these schemes are not secure as soon as the adversary gets observations in the Known Message Attack context.
Introduction: The Security Gap
In the world of digital watermarking, researchers have long optimized the "magic triangle" of trade-offs: embedding distortion, payload, and robustness. However, the fourth pillar—security—has remained theoretically underdeveloped. Previous attempts to define security relied on Shannon’s information theory, specifically "equivocation" (the entropy of the secret key given some observations).
The authors argue this classical approach is flawed for two primary reasons. First, it focuses exclusively on the embedding process, ignoring how the decoder actually functions. Second, in watermarking (unlike symmetric cryptography), the secret key is rarely unique. An adversary does not necessarily need the exact original key; they only need an "equivalent key" that is close enough to successfully decode or embed messages.
A New Metric: Effective Key Length
To bridge this gap, the paper introduces the concept of Effective Key Length ($\ell$). This metric transposes the cryptographic concept of key length into the watermarking domain by measuring the rarity of keys that grant unauthorized access to the watermarking channel.
As illustrated in Figure 2, the effective key length is defined as $\ell = -\log_2(P)$, where $P$ is the probability that a randomly drawn key falls into the region of equivalent keys $\mathcal{K}_{eq}(\mathbf{k}, \epsilon)$. These are keys that correctly decode a message with a probability higher than a certain threshold ($1-\epsilon$). When an adversary gains observations $O^{N_o}$, the search space for a functional key narrows to $g(O^{N_o})$, which can drastically reduce the effective security level.
The Concept of Equivalent Keys
The shift from "finding the exact key" to "finding an equivalent key" is central to this new methodology. The security of a scheme depends on the size and overlap of decoding regions in the signal space.
Figure 1 demonstrates the relationship between the embedding region $\mathcal{E}_m(\mathbf{k})$ and the decoding regions $\mathcal{D}_m(\mathbf{k})$. By considering the decoding side, the authors show that multiple keys (such as $\mathbf{k}, \mathbf{k}', \mathbf{k}''$) might share overlapping decoding regions. This means an attacker has a much higher probability of stumbling upon a working key than a purely embedding-focused analysis would suggest.
The Robustness-Security Paradox
A striking insight from the paper is the conflict between robustness and security. In Additive Spread Spectrum (SS) schemes, increasing the host signal length ($N_v$) to improve robustness actually decreases "basic" security (security without observations). This paradox highlights that making a watermark harder to erase often makes it easier to detect or crack, as the key's signature becomes more statistically distinct in the signal space.
Results: The Collapse of Spread Spectrum
The methodology was applied to both standard SS and Improved Spread Spectrum (ISS) using synthetic Gaussian models. The results serve as a wake-up call for the industry:
- KMA Vulnerability: Under a Known Message Attack (KMA), where the attacker observes pairs of watermarked content and their corresponding messages, security collapses almost immediately. In a practical setup ($N_v = 300$, DWR = 10 dB), the effective key length drops from approximately 50 bits to nearly 0 bits after only 10 observations.
- ISS vs. SS: Surprisingly, ISS can be less secure than standard SS. Its host-rejection parameter ($\lambda$), designed to improve robustness, can expand the region of equivalent keys, making it easier for an attacker to find a functional key.
Conclusion and Future Work
This work provides a practical framework for quantifying watermarking security beyond theoretical entropy. However, the study is currently limited to spread spectrum techniques and Gaussian signal models. Future research is needed to apply the "effective key length" framework to other popular schemes like Quantization Index Modulation (QIM) and to evaluate performance against Watermarked Only Attacks (WOA) and Oracle Attacks. Furthermore, the impact of non-Gaussian real-world signal statistics remains an open question for the field.
Summary updated