Techniques for watermarking sequences of digital representations and detecting the watermarks in the digital representations. One of the techniques is used when the message that is contained in a watermark belonging to a digital representation that is derived from an original watermarked digital representation cannot be decoded. The technique obtains information about the watermark by comparing the watermark vector for the watermark that cannot be decoded with a replica of the watermark vector from the original watermarked digital representation. The replica is made using the message. Depending on the degree of similarity, the watermark's presence and some of its characteristics may be determined. Another technique improves the robustness of watermarks that are used for authentication by employing a short (eve single-bit) watermark vector to make the watermark and using the message needed for the authentication to determine where the watermark is located in the digital representation.