The present invention relates to steganographically hiding messages in media signals such as video and audio signals. In one implementation, a method of decoding an encoded media signal to extract a plural-bit auxiliary signal therefrom is provided. The media signal includes a plurality of intervals, with the plural-bit auxiliary signal being steganographically encoded in at least some of the intervals. Once encoded in the media signal the plural-bit auxiliary signal is generally imperceptible to a human observer of the encoded media signal. The encoding includes subtle changes to at least some portions of the media signal to thereby represent the plural-bit auxiliary signal. The method includes receiving the encoded media signal; and decoding the received encoded media signal to extract the plural-bit auxiliary signal therefrom. The decoding analyzes a plurality of intervals of the media signal with greater or lesser confidence in the extracted multi-bit auxiliary data signal being obtained by processing more or less intervals of the encoded media signal, respectively.