A passport or other document is steganographically encoded with two steganographic digital watermarks. Data conveyed by these watermarks can be cross-checked for expected correspondence to help authenticate the document. The document may also include other machine-readable features, such as a bar code, a magnetic stripe, or OCR-B text. These other machine-readable features can likewise convey data that can be cross-checked for expected correspondence with watermark-conveyed data. In one arrangement, four machine-readable features are provided (two watermarks and two others), three of which convey data relating to a passport identifier, and a different three of which convey data relating to a document batch number. Such logical linking between several machine-readable features allows tampering with any feature to be readily detected. A variety of related methods and apparatuses, some involving a third watermark and biometric data, are also detailed.