The invention provides methods for embedding digital watermarks for authentication of printed objects, and corresponding methods for authenticating these objects. One aspect of the invention is a method of embedding a digital watermark in a digital image to be printed on an object. The method embeds an auxiliary signal in the digital image so that the auxiliary signal is substantially imperceptible, yet machine readable. It converts the image to a halftone image using an inherently unstable halftone screen structure that is likely to cause ink flow errors when reproduced. The errors introduced by reproducing the unstable halftone screen structure incorrectly are automatically detectable by reading the auxiliary signal.