Methods and systems for utilizing conjugate cluster halftone screens to embed patterns or images as invisible watermarks into both digital halftone image files and corresponding printed documents are disclosed. In general, two or more two-conjugate halftone screens can be configured to provide a basic information carrier for embedding a digital watermark into a document. Thereafter, one or more clusters can be created from the two-conjugate halftone screens, wherein such clusters include the same centroid position relative to a grid defined by fundamental halftone frequencies. Two halftone patterns can then be blended from the two-conjugate halftone screens in a cluster-to-cluster basis so that virtually no loss of image quality occurs in comparison with an output of either the two-conjugate halftone screens, thereby permitting the digital watermark to be embedded into the document utilizing the two-conjugate halftone screens.