The presently claimed invention relates generally to steganography and fingerprinting or hashing. In one embodiment, a method includes: obtaining a first set of plural-bit data, the first set of plural-bit data corresponding to at least a portion of steganographically encoded data in a media signal in the form of a digital watermark; obtaining a second set of plural-bit data, the second set of pural-bit data corresponding to a fingerprint or hash of the media signal. THe fingerprint or hash includes a reduced-bit representation of the media signal, and the first set of plural-bit data is not dependent on information in the second set of plural-bit data. The method further includes carrying out a first action associated with the first set of plural-bit data; and carrying out a second action associated with the second set of plural-bit data. Other embodiments are described and claimed as well.