The paper proposes a new approach for evaluating the security levels of digital watermarking schemes, which is more in line with the formulation proposed in cryptography. We first exhibit the class of equivalent decoding keys. These are the keys allowing a reliable decoding of contents watermarked with the secret key. Then, we evaluate the probability that the adversary picks an equivalent key. The smaller this probability, the higher the key length. This concept is illustrated on two main families of watermarking schemes: DC-QIM (Distortion Compensation Quantization Index Modulation) and SS (Spread Spectrum). The trade-off robustness-security is again verified and gives some counter-intuitive results: For instance, the security of SS is a decreasing function of the length of the secret vector at a fixed Document to Watermark power ratio. Additionally, under the Known Message Attack, the practical key length of the watermarking scheme rapidly decreases to 0 bits per symbol.