Steganographic methods for encoding auxiliary data into a host signal are used to authenticate physical and electronic objects. One claim recites an object comprising: a first graphic provided on an object surface, and a storage device carried by the object. The storage device includes a second graphic stored therein. The first and second graphics are related graphics, and the second graphic includes first steganographic encoding including a plural-bit payload. Of course, other combinations are provided as well.