In this article, the authors propose a novel interpolation-based reversible data hiding algorithm for use with images that are encoded in the Joint Photographic Expert Group standard format. This algorithm is able to exactly recover the original coded quality of the image, once the hidden message has been extracted. The proposed algorithm embeds message data into discrete cosine transform blocks by calculating the difference values between the nonzero quantized AC coefficients and their interpolated counterparts and then shifting the histogram of those difference values. Simple linear interpolation is employed to exploit the correlation between the AC coefficients that are colocated across neighboring blocks for the purpose of creating hiding capacity for the insertion of data bits into the AC coefficients. The embedding of data is performed via the shifting of the histogram of interpolation differences. Our experimental results demonstrate that the proposed method not only provides an increased embedding capacity but also maintains a high image quality. Moreover, as an additional processing delay is not introduced and only simple arithmetic computations are involved, the proposed algorithm can operate in real time.