In this paper, a new digital watermarking method based on vector quantization (VQ) is proposed. In contrast with conventional VQ‐based watermarking schemes, the mean of sub‐blocks is used to train the VQ codebook. In addition, the Anti‐Gray Coding (AGC) technique is employed to enhance the robustness of the proposed watermarking scheme. In this scheme, the secret keys are used to hide the associated information between the original image and the watermark. Then the set of secret keys will be registered to a trusted third party for future verification. Thus, the original image remains unchanged after the watermark is melted into the set of secret keys. Experimental results show that the watermark can survive various possible attacks. Besides that, the size of the secret keys can be reduced.