1. A method of converting a gray-scale image into a halftone image having embedded binary data, the gray-scale image comprising a plurality of pixels having one of at least three tone values, the method comprising: designating a plurality of pixels of the gray-scale image for embedding binary data by employing a random number generator; toggling a tone value of the designated pixels of the gray-scale image in accordance with associated binary data; determining error values for a plurality of the toggled pixels of the gray-scale image based, at least in part, on a comparison between a tone value of a toggled pixel of the gray-scale image and a tone value of an associated pixel of the gray-scale image prior to toggling; and performing error diffusion on the gray-scale image based, at least in part, on the determined error values to convert a plurality of the gray-scale image pixels having one of at least three tone values to halftone image pixels having one of two tone values.