Yes, but the encryption makes the spatial spread-spectrum analysis look normal, modulo a minuscule increase in overall data "noisiness", undetectable if the size of the watermark info is much smaller than the size of the data
LOL. I could talk about how differential cryptanalysis made the codebreaker's job a little bit easier, or how everyone was just sure that the quadratic sieve was the fastest factorization method until Pollard came up with the number field sieve,
"A little" bit doesn't cut it, and the differences between the two sieve messages are trivial compared with their astronomical slowness on inputs with thousands of digits, and "everyone was just sure that the quadratic sieve was the fastest" is either meaningless, or trivially correct (if what everyone was sure of was that the quadratic sieve was the fastest algorithm discovered up to that time), or trivially wrong (if what everyone was sure of was that the quadratic sieve was the fastest theoretically possible factorization algorithm).
but I'll merely suggest an analogy, so that we can think outside the box for a moment.... The government is easily the biggest, best-funded research organization in the world of cryptography. Easily. And, of course, the most secure, most difficult-to-crack ciphers are put to work by the military, so that they might communicate without anyone eavesdropping. And yet, for all that, from 1967 to 1985, the Soviets were able to read virtually every single secure message that the US Navy sent. And it only cost them a few hundred thousand dollars to do it, whereas it cost the Navy well over a billion dollars to fix the problem once they discovered it.
Those were old-style single-private-key ciphers, not modern public-private-key ciphers
So, how much will the keys to your watermarks be worth? Will it even be as much as a few hundred thousand dollars? If someone can be found who will sell out an entire nation for a few hundred thousand dollars, how much will it take to entice someone to sell out an organization as degenerately awful as a record label?
Each published CD will have its own published public key. If the record label is stupid enough to allow the thousands of corresponding private keys to all be compromised, they'll deserve what they get.
I have my doubts as to the practical invulnerability of any watermarking method - the RIAA can't even keep its own website up, after all - never mind the theoretical invulnerability. In the end, the codebreakers always have an ace up their sleeves. You can hide your data any way you see fit, and encrypt it any way you like, using any method(s) you want, but if it's important enough to me, I'll always be able to get at it, no matter what you do. The stronger the cryptography becomes, the weaker the human links become, relatively speaking...
You haven't grasped one of the major benefits of public-key cryptography, which is that it greatly reduces the potential number of compromisable human links. There will always be some, but that doesn't vitiate my point that digital watermarks can be made so strong that only a risky insider betrayal could crack them, a big improvement over the current protocols.