The presently claimed invention relates generally to encoding and decoding video with auxiliary information. One claim recites a method of encoding video, the video has a plurality of samples. The method includes: obtaining an N-bit auxiliary data string to be encoded into the video, where N is at least two, the string including bits having a value of “1” or “0”; and utilizing a configured multi-purpose electronic processor to perform encoding as follows, for a first bit in the N-bit auxiliary data string: if the bit comprises a “1” value, making a corresponding change to the video to represent the “1” value in the video, the change being essentially unnoticeable to a human viewer of the video, but if the first bit comprises a “0” value, making no corresponding change to the video; performing the aforesaid act for the second through Nth bits of the N-bit auxiliary data string. Of course, other claims and combinations are provided as well.