Digital watermarks are embedded and decoded from host media signals like images and audio using encryption keys. The encryption keys are used to encrypt different components of the digital watermark message. The encryption keys can be used to scramble the digital watermark and components of it in alternative ways, including scrambling the mapping of the message to the host signal and scrambling carrier signals used to encode the message. Spread spectrum, feature based, and quantization based embedding and decoding schemes may be used in various combinations in the watermark encoder and decoder. Portions of the digital watermark may be encrypted to provide private watermark data, while other portions may be un-encrypted to provide public watermark data.