Article Preview
TopIntroduction
Reversible data hiding (RDH) is an effective tool by which the original image can be perfectly restored and the embedded message completely extracted. Since RDH can losslessly recover the original image after data extraction, it becomes a hot topic and is extensively used in many areas, such as medical imagery, military imagery and law forensics. And RDH is a relatively mature technology, which can generally be divided into three kinds: the general RDH framework by lossless compression in (Fridrich, Goljan & Du, 2002), difference expansion (DE) (Kundur & Karthik, 2004; Celik, Sharma, Tekal & Saber, 2005) and histogram shifting (HS) (Ni, Shi, Ansari & Su, 2006; Tian, 2003). Other RDH methods can be found in (Thodi & Rodríguez, 2007; Tai, Yeh, & Chang, 2009; Luo, Chen, Chen, Zeng, & Xiong, 2010; Li, Yang, & Zeng, 2011).
With the increasing demands for privacy protection, data encryption is vital in cloud computing (Hwang & Li, 2010; Wang, Wang, Ren & Lou, 2010; Takabi, Joshi & Ahn, 2010), especially in some scenarios that the owner of the image is unwilling to publish the image content for the sake of privacy. For example, the image owner wants to upload an image to the server. However, he does not want to expose the image content. On the other side, the server hopes to embed some information of the encrypted data, like the owner’s information and the uploading time, for labelling the image. To this end, some works have been done to hide messages into encrypted images using RDH. Zhang (2011) divides the encrypted image into several non-overlapping blocks sized s×s. In order to embed data, pixels in each block should be randomly partitioned to two pixel sets 
and 
with the data hiding key. Each block is embedded with one bit by flipping 3 LSBs (Least Significant Bits) of 
(or 
). Hong, Chen & Wu (2012) improve the accuracy of image recovery in method (Zhang, 2011) by utilizing the spatial correlation and side match technique.
Zhang (2012) first pseudo-randomly permutes the encrypted image into several groups. And all the bits in each group are compressed by multiplying a low density parity check matrix, while the vacated room can be used to embed data. Zhang, Qian, Feng & Ren (2014) losslessly compress partition of the encrypted image using Low Density Parity Check Code (LDPC) and obtain the extra room for embedding the data; on the receiver side, with the help of compressed data and the uncompressed data, the image content can be perfectly recovered. Qian, Han & Zhang (2013) utilize the property of the random histogram in encrypted image, and modulate the histogram for embedding room. All these methods in (Zhang, 2011; Hong et al, 2012; Zhang, 2012) vacate room before encryption and recover the image through the correlation of pixels. Another concept of state-of-art work is to reserve room before encryption. Ma, Zhang, Zhao, Yu & Li (2013) first empty out space by reversibly embedding LSBs of some pixels into other pixels employing traditional RDH algorithms, thus, the emptied positions of these LSBs can be used to embed data. To reserve room before encryption, Zhang, Ma, & Yu (2014) propose a method based on estimation technique. A few parts of pixels are estimated by the rest pixels before encryption. The estimated errors are trimmed and modified to vacate room for embedding data.