This report analyzes watermark embedding in Error Diffusion halftone images. A distortion measure for halftone modifications is introduced, and an embedding scheme is selected so as to minimize the proposed distortion. Next a statistical model is suggested for "natural-images", leading to a lower bound on the halftone distortion as a function of watermark rate. Bound realization is argued to be equivalent to solving a prediction problem. Accurate prediction is not possible, however a good estimator is suggested for watermark embedding. The proposed embedding procedure is compared to alternative procedures, and shown to have better distortion versus rate performance. The visual impact in real images is also demonstrated. 19 Pages