A VQ-based, reversible information hiding method embeds secret data into a VQ-encoded image to achieve data protection. It produces either a VQ-encoded image or a compressed codestream as the output. The embedded secret data and the original VQ-encoded image can be extracted from the encoded output when needed. This paper proposes a novel information hiding method for VQ-encoded images. The proposed method allows the users to decide the embedding capacity of secret data in an image. The proposed method utilizes the fact that two neighboring blocks in a VQ-encoded image are usually similar. First, it re-orders the codebook according to the similarity to the codeword of the first block in an image. Second, it sequentially picks up two consequent blocks, calculates the difference of their new indices that are mapped from the re-ordered codebook, and encodes the secret bits along with the difference value as the compressed output for each block. We conducted several experiments, and used the results to compare the performance of the proposed method with the performance of a recent similar method. The experimental results showed that the proposed method is very efficient in terms of bit rate, in particular when an image has many similar neighboring blocks in it.