This paper presents a blind watermarking method for embedding large data into halftone images. Watermarking in ready-to-print halftones is desirable in printer applications such as authentication and document/image security. It is challenging to embed large information into halftones, while maintaining high image quality. In this paper, we first review a series of halftone watermarking methods that embed data by using Embedding Toggle (ET) in the selected positions. We find that such ET-based methods have two shortcomings: 1) the image quality is limited because of the unknown input data and randomly selected embedding positions, and 2) the selected embedding positions must be recorded to retrieve the hidden data. To tackle the above disadvantages, this study makes two improvements. First, we propose a random toggle approach, in which the embedding positions are movable. Therefore, after the data are embedded, each dot can still be shifted to the most appropriate position to improve the image quality. Second, a self-decodable even/odd parity checking scheme is proposed to embed one bit information in each image block. We also propose a new search strategy, called Swap-Only Block-Based (SOBB) search. By integrating SOBB search with the direct binary search method, the image quality can be greatly improved without damaging the hidden data. From experimental results, the proposed method demonstrated sufficient robustness and excellent image quality.