We propose a scheme of reversible watermarking with high security, low distortion and large capacity. After setting the reference sets, we use a keyinformationbased adaptive interpolation algorithm to estimate a complementary image. Because the predicted images are close to the desired ones, the difference image has a high peak in the histogram. Histogram shifting is performed to achieve a large payload while keeping low embedding distortion. As the operation is controlled by a key, the method conforms to the Kerckhoffs’ criterion and is therefore secure.