A new approach to binary image authentication in multimedia communication with distortion reduction and security enhancement is proposed. Special codes are embedded into the blocks of given images and verified to accomplish the authentication purpose. Enhancement of security in detecting tampered images is achieved by randomly generating the codes and embedding them into randomly selected locations in the image blocks. The reduction of image distortion coming from pixel value replacement in code embedding is carried out by allowing multiple locations for embedding the codes. Security analysis and experimental results are also included to show the effectiveness of the proposed approach.