Reversible data hiding is an area explored widely in recent days due to its scope of applications in secure message transmission by embedding it in images. The existing RDH schemes in the encrypted image are lagging in terms of embedding rate. In this paper, we propose a new RDH scheme in encrypted images that will ensure the embedding rate without compromising the bit error rate or image recovery. In the proposed scheme, the encrypted image pixels will be classified into black-and-white pixels based on a checkerboard pattern. During the data hiding phase, the sender will select 8 unique random integer sequences S, that form the data keys and whose values are within the range 0 to 255. Data hiding is performed by performing bit-XOR with the white pixels in an image block (size B × B pixels) using one integer sequence from the 8 keys. Each key is correlated to a 3-bit sequence from the secret message. The receiver must have the data keys and the decryption key to extract the hidden message and recover the original image. A smoothness measure between adjacent pixels is defined and used for data extraction and image recovery. The experimental results show that the proposed scheme performs well on the standard image data set (USC-SIPI).