This paper proposes a novel reversible data hiding algorithm for images, which the original host image can be exactly recovered from the marked image after the hidden data has been extracted. The proposed algorithm considers shifting the histogram of the difference values between the subsampled target pixel intensities and their interpolated counterparts to hide secret data. The shifting of the histogram of difference values is carried out by modifying the target pixel values. As compared to other schemes, the proposed method can make more utilization of the correlation between nearby pixels in an image via simple interpolation techniques to increase embedding capacity without sacrificing much distortion for data hiding. The reason of the feasibility is that the difference histogram derived in the paper renders so highly centralized distribution around zero that much more embedding capacity than before can be thus obtained. The experimental results demonstrate that the proposed method not only provides larger embedding capacity than other histogram shifting methods but also maintains a high visual quality. Moreover the computational complexity of the proposed method is low since only simple arithmetic computations are needed.