This disclosure describes methods and systems for encoding a digital watermark into and/or detecting a digital watermark from a host (or media) signal such as audio, video or imagery. One implementation involves a method of detecting a digital watermark. The method includes: receiving a host signal carrying a digital watermark; computing attributes of the host signal; using the attributes of the host signal to compute a key; and using the key to detect the digital watermark in a transform domain dependent on the key. Other methods, systems and apparatus are provided as well.