A watermark embedding method for embedding a secret message sequence in a document. The techniques include obtaining layout information of the document, extracting a digest of the document by using a Hash function, calculating embedded positions where the secret message sequence is embedded in the document, and dispersedly hiding the secret message sequence in each of the calculated embedded positions by altering the layout of the document. Also provided is a watermark embedding apparatus, a corresponding watermark detecting method and apparatus, and a method and system for detecting document integrity. The integrity of documents in various forms can be detected, and secret information to be hidden can be embedded therein and extracted therefrom. The techniques described are not limited to the document either in soft copy or in hard copy and have good robustness.