# A New Reversible Date-Hiding Algorithm for Encrypted Images

Authors: Laicheng Cao; Hao Zhou
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In order to effectively increase embedding capacity and completely extract the watermarking information in information hiding of encrypted images, a new reversible watermarking embedding algorithm based on rhombus prediction model and difference histogram shifting ideas is proposed. Firstly, the images are pretreated according to rhombus prediction model. Then, the watermarking information is embedded in encrypted images by effective combination of homomorphism encryption scheme and reversible watermarking techniques. Finally, the watermarking information is completely extracted and the images are recovered based on computed difference histogram from left to right and from top to bottom. So, the efficiency and reversibility are ensured when watermarking information is embedded in encrypted image. Experiment results show that the proposed algorithm is simple and easy to realize, the embedding capacity is effectively increased, watermarking information is completely reversible, and the image can be recovered with no distortion.


---

## Body

## 1. Introduction

With the advent of the digital age, media content gradually changes from analog to digital. Digital technology makes the multimedia data (image, video, and text) storage, replication, and communication become very convenient. Therefore, how to implement effective copyright protection and information security measures in the network environment has become an urgent realistic problem.At present, there are three types of reversible watermarking methods: (1) compression based reversible watermarking [1–3]; (2) expansion based reversible watermarking [4–6]; (3) histogram modification based reversible watermarking [7–9].Encryption technology [10] and digital watermarking [11] are all with different maintenance information security function. So, they are often used together. In traditional way, the watermarking information is embedded in the multimedia works, and then the multimedia works that contain the watermarking information are encrypted. However, in some occasions, we must first encrypt the image and then embed watermarking. So there is the digital watermarking in encryption images. Reference [12] has proposed the corresponding algorithm, but the algorithm is all irreversible. However, in the military, medicine, and so on, the fidelity of the occasion possesses high demand, and any distortion of the multimedia data is not allowed. So, the encryption technique of reversible watermarking is developed. Zhang et al. [13] have truly realized the combination of encryption and watermarking. They embed watermarking by flipping the cipher image pixels’ three least significant bits (LSBs), and then the same operation is performed in the decrypted image. Using the correlation between the nature image spaces, it can extract watermarking information. But the amount of data and image watermarking extraction rate is not optimistic, especially when the block is smaller and the error rate is higher. Hong et al. [14] have proposed an algorithm of reversible data hiding in encrypted images by fully considering the images edge pixel and using edge match technology, so that the extraction accuracy is increased some. However, errors still exist in the restored image, and algorithm is not reversible. Zhang et al. have put forward a new idea [15, 16] that uses the method of matrix calculation compressing the encrypted images LSB (least significant bit) to make the room for hiding information. In the receiver, the data extraction and image restoration can be separated. However, watermarking extraction still uses the characteristics of the relationship of the nature image pixel and so does not guarantee the ability to completely extract the watermarking information. Reference [17] has proposed reserving room before encryption. However, this method is not handled in the encrypted domain, because it is the original place to fill the data. Zheng et al. [18] have proposed using wonton scrambling to image encryption, in the cipher image; based on histogram shift algorithm, watermarking information is embedded in the cipher image. Reference [19] has proposed hiding algorithm based on cipher image lossless compression, but the watermarking extraction is still using the relationship of the nature image pixels characteristics, so it dose not guarantee the ability to completely extract the watermarking information. Others like [20–25] are also about data hiding in encrypted images.According to the problem above, we propose a new reversible watermarking embedding algorithm in encrypted image. Figure1 gives a sketch of reversible data hiding in encrypted image. The image is first pretreated and encryption key is embedded before the image is encrypted, then the sender encrypts image by this encryption key, the administrator embeds addition bits through this embedded encryption key, and finally the receiver can get the encrypted image with embedded bits. In the same ways, when the watermarking is extracted and the image is recovered, the encrypted image is first preoperated with embedded bits, and then embedded encryption key is gotten, and finally the receiver decrypts image through decryption key and gets the decrypted image with embedded bits; accordingly legitimate watermarking information application can extract encryption key and addition bits, and it can also recover image.Figure 1
Sketch of reversible data hiding in encrypted image.Our reversible watermarking embedding algorithm is based on rhombus prediction model and difference histogram shifting ideas; it can effectively increase embedding capacity and completely extract the watermarking information in information hiding of encrypted images while the efficiency and reversibility can be ensured. In order to achieve this innovation, we first pretreat the images according to rhombus prediction model, and then we embed the watermarking information in encrypted images by effective combination of homomorphism encryption scheme and reversible watermarking techniques; the watermarking information can be completely extracted and the images are recovered based on computed difference histogram from left to right and from top to bottom.The remainder of this paper is organized as follows. In Section2, the theory of homomorphic encryption and the information entropy of the encrypted image are analyzed. The proposed algorithm is presented in Section 3. Section 4 shows our experimental results and analysis. Finally, in Section 5, we summarize our results and present the conclusion.


## 2. Theory Analysis

### 2.1. Homomorphic Encryption

The characteristics of homomorphic encryption are for some operations in plaintext and then encryption effect is equivalent to some operation directly in the ciphertext [26–30]. The general definition of homomorphic encryption is(1)Em1⊗Mm2⟵Em1⊕CEm2,∀m1,m2∈M,where ⊗M represents the operation in the plaintext M, ⊕C represents the operation in the ciphertext C, and “←” represents “homomorphic encryption can be directly obtained by calculating from the ciphertext”; namely, it does not exist in the middle of the decryption process.But the encryption methods and the corresponding homomorphism (addition, subtraction, multiplication, and division) must satisfy the image encryption. In order to make the image encryption have a low complexity, we choose the RC4 encryption [30]; thus the corresponding homomorphism satisfies the additive homomorphic, and the encryption mechanism is specified as follows.RecordM is a gray image pixel in plaintext, a key seed S is selected to generate RC4 random key stream K that encrypts per pixel in M, and then the encrypted image C is gotten. In the following formula, E represents encryption operation and D represents decryption operation.The encryption method is shown as follows:(2)C=EM,K=M+Kmod⁡256=mi+kimod⁡256=ci,∀i=1,2,…,L,where L is the number of pixels in the image and mi,ki,ci, respectively, show the ith plaintext pixel, the key stream of random number, and the ciphertext pixel.The decryption method is shown as follows:(3)DC,K=ci-kimod⁡256=mimod⁡256,∀i=1,2,…,L.Suppose that m1,m2 are, respectively, for two different pixels in gray image and k1,k2 are the random numbers from the key stream used to encrypt m1,m2. According to definition (1), if ⊗M is the arithmetic plus, ⊕C is the modular addition; then (4)Em1⊗Mm2,k1+k2=Em1+m2,k1+k2=m1+m2+k1+k2mod⁡256=m1+k1mod⁡256+m2+k2mod⁡256mod⁡256=Em1,k1+Em2,k2mod⁡256=Em1,k1⊕Cm2,k2.So, this encryption method satisfies the additive homomorphism. Correspondingly, usek1+k2 to description Em1,k1⊕CEm2+k2, which is (5)DEm1,k1⊕CEm2,k2,k1+k2=DEm1⊗Mm2,k1+k2,k1+k2=m1⊗Mm2mod⁡256=m1+m2mod⁡256.The security of this encryption mechanism depends on the use of the stream cipher, and RC4 is a mature encryption mechanism [30].


### 2.2. Analysis Information Entropy of the Encrypted Image

The information entropy is used to measure the amount of information lost in the signal transmission process before it is received. After the image is encrypted, if the chaos degree of its pixels reaches maximum, then the image information entropy tends to the maximum value. Reference [31] has proposed a general parser, and the encrypted signal bit stream is divided into a series of nonoverlapping fixed length fields, called the fictional codeword. Supposing that the length of each fictional codeword is L bits and the total length of the encryption signals is N bits, so the total number of fictional codewords CL is calculated, which is (6)CL=NL.The generic parser is a partition function DX,L, and it will divide X into nonoverlapping ordered tuples and each tuple contains L symbols in X, which is(7)DX,L=XL=T1L,T2L,…,TCLL.Below, we give the definition of the information entropy of the XL dependent on L.Suppose thatX=X1,X2,…,XN is a collection of discrete uniform distribution of elements, the probability of each element satisfies PX1=PX2=⋯=PXN=1/N, then a genera parser segmentation X is shown as follows:(8)XL=DX,L,XL+1=DX,L+1.So, for ∀TiL∈XL and ∀TiL+1∈TL+1, the information entropy of tuple TiL and TiL+1 are ITiL and ITiL+1 satisfying the follow formula, which is(9)ITiL>ITiL+1.Equation (9) shows that the sum of self information of L should greater than the length of the self information of L+1.That is to say, the information entropy ofXL is greater than XL+1, which is shown as follows.Suppose that a general parser dividesX into XL and XL+1, such as (8), so, (10)HXL>HXL+1,where X is a discrete uniform distribution of symbol set and HXL and HXL+1 are, respectively, the information entropy for a set of tuples of XL and XL+1, 1≤L≤N.Proof.
According to the definition in [32], the initial HXL is(11)HXL=1L∑i=1CLpTiL×θTiL,where pTiL is the probability of tuple TiL in XL, θTiL is the codeword length that the encoded tuple TiL needs, because X is a discrete uniform distribution, pTiL and θTiL for ∀TiL are constant, which are(12)pTiL=1CL,θTiL=log2⁡CL.
So, (11) can be written as follows:(13)HXL=CL×log2⁡CLL×CL=log2⁡CLL,because(14)log2⁡CL>log2⁡CL+1⟹log2⁡CLL>log2⁡CL+1L⟹log2⁡CL+1L>log2⁡CL+1L+1.
So(15)log2⁡CLL>log2⁡CL+1L+1.
According to (13), (15) can be rewritten as follows:(16)HXL>HXL+1.
BecauseX is fixed, at least it can eliminate redundancy in the parsed signal through the information entropy coding method. Namely, the encrypted image information still exists in redundancy, which means the encrypted image still exists in the information entropy that can be used, and we call it the information entropy difference. In order to make better use of this part of the information entropy difference, we propose a rhombus prediction scheme and use the difference histogram shifting scheme.


## 2.1. Homomorphic Encryption

The characteristics of homomorphic encryption are for some operations in plaintext and then encryption effect is equivalent to some operation directly in the ciphertext [26–30]. The general definition of homomorphic encryption is(1)Em1⊗Mm2⟵Em1⊕CEm2,∀m1,m2∈M,where ⊗M represents the operation in the plaintext M, ⊕C represents the operation in the ciphertext C, and “←” represents “homomorphic encryption can be directly obtained by calculating from the ciphertext”; namely, it does not exist in the middle of the decryption process.But the encryption methods and the corresponding homomorphism (addition, subtraction, multiplication, and division) must satisfy the image encryption. In order to make the image encryption have a low complexity, we choose the RC4 encryption [30]; thus the corresponding homomorphism satisfies the additive homomorphic, and the encryption mechanism is specified as follows.RecordM is a gray image pixel in plaintext, a key seed S is selected to generate RC4 random key stream K that encrypts per pixel in M, and then the encrypted image C is gotten. In the following formula, E represents encryption operation and D represents decryption operation.The encryption method is shown as follows:(2)C=EM,K=M+Kmod⁡256=mi+kimod⁡256=ci,∀i=1,2,…,L,where L is the number of pixels in the image and mi,ki,ci, respectively, show the ith plaintext pixel, the key stream of random number, and the ciphertext pixel.The decryption method is shown as follows:(3)DC,K=ci-kimod⁡256=mimod⁡256,∀i=1,2,…,L.Suppose that m1,m2 are, respectively, for two different pixels in gray image and k1,k2 are the random numbers from the key stream used to encrypt m1,m2. According to definition (1), if ⊗M is the arithmetic plus, ⊕C is the modular addition; then (4)Em1⊗Mm2,k1+k2=Em1+m2,k1+k2=m1+m2+k1+k2mod⁡256=m1+k1mod⁡256+m2+k2mod⁡256mod⁡256=Em1,k1+Em2,k2mod⁡256=Em1,k1⊕Cm2,k2.So, this encryption method satisfies the additive homomorphism. Correspondingly, usek1+k2 to description Em1,k1⊕CEm2+k2, which is (5)DEm1,k1⊕CEm2,k2,k1+k2=DEm1⊗Mm2,k1+k2,k1+k2=m1⊗Mm2mod⁡256=m1+m2mod⁡256.The security of this encryption mechanism depends on the use of the stream cipher, and RC4 is a mature encryption mechanism [30].


## 2.2. Analysis Information Entropy of the Encrypted Image

The information entropy is used to measure the amount of information lost in the signal transmission process before it is received. After the image is encrypted, if the chaos degree of its pixels reaches maximum, then the image information entropy tends to the maximum value. Reference [31] has proposed a general parser, and the encrypted signal bit stream is divided into a series of nonoverlapping fixed length fields, called the fictional codeword. Supposing that the length of each fictional codeword is L bits and the total length of the encryption signals is N bits, so the total number of fictional codewords CL is calculated, which is (6)CL=NL.The generic parser is a partition function DX,L, and it will divide X into nonoverlapping ordered tuples and each tuple contains L symbols in X, which is(7)DX,L=XL=T1L,T2L,…,TCLL.Below, we give the definition of the information entropy of the XL dependent on L.Suppose thatX=X1,X2,…,XN is a collection of discrete uniform distribution of elements, the probability of each element satisfies PX1=PX2=⋯=PXN=1/N, then a genera parser segmentation X is shown as follows:(8)XL=DX,L,XL+1=DX,L+1.So, for ∀TiL∈XL and ∀TiL+1∈TL+1, the information entropy of tuple TiL and TiL+1 are ITiL and ITiL+1 satisfying the follow formula, which is(9)ITiL>ITiL+1.Equation (9) shows that the sum of self information of L should greater than the length of the self information of L+1.That is to say, the information entropy ofXL is greater than XL+1, which is shown as follows.Suppose that a general parser dividesX into XL and XL+1, such as (8), so, (10)HXL>HXL+1,where X is a discrete uniform distribution of symbol set and HXL and HXL+1 are, respectively, the information entropy for a set of tuples of XL and XL+1, 1≤L≤N.Proof.
According to the definition in [32], the initial HXL is(11)HXL=1L∑i=1CLpTiL×θTiL,where pTiL is the probability of tuple TiL in XL, θTiL is the codeword length that the encoded tuple TiL needs, because X is a discrete uniform distribution, pTiL and θTiL for ∀TiL are constant, which are(12)pTiL=1CL,θTiL=log2⁡CL.
So, (11) can be written as follows:(13)HXL=CL×log2⁡CLL×CL=log2⁡CLL,because(14)log2⁡CL>log2⁡CL+1⟹log2⁡CLL>log2⁡CL+1L⟹log2⁡CL+1L>log2⁡CL+1L+1.
So(15)log2⁡CLL>log2⁡CL+1L+1.
According to (13), (15) can be rewritten as follows:(16)HXL>HXL+1.
BecauseX is fixed, at least it can eliminate redundancy in the parsed signal through the information entropy coding method. Namely, the encrypted image information still exists in redundancy, which means the encrypted image still exists in the information entropy that can be used, and we call it the information entropy difference. In order to make better use of this part of the information entropy difference, we propose a rhombus prediction scheme and use the difference histogram shifting scheme.


## 3. The Proposed Algorithm

In the proposed algorithm, the sender will encrypt image and embed data, but the encryption section should be divided into two parts, which are pretreatment phase and encryption phase. When the receiver gets an encrypted image containing embedded data, he can decrypt image, extract the additional data, and recover the original image.


### 3.1. The Sender

This section is divided into three parts: part (1) is image pretreatment; part (2) is image encryption; part (3) is embedding watermarking information.(1) Image Pretreatment. The image is pretreated before it is encrypted; Figure 2 shows the pixel division scheme in the rhombus prediction. Firstly, the pixels of the image are divided into two categories according to Figures 2(a) or 2(b), and white dots and black dots represent the two types of divided pixels. In Figure 2(a), the four black pixels adjacent to the white pixels form a rhombus pattern, the four black pixels are located in the four corners of the rhombus, and the white pixels are located in the center of the rhombus, and the middle white pixel value can be predicted by using the four black pixel values. In Figure 2(b), the four white pixels are located in the four corners of the rhombus, and the black pixels are located in the center of the rhombus; the middle black pixel value can be predicted by using the four white pixel values. In this paper, we use Figure 2(a) to divide the pixels. For the all white pixels Ii,j in the intermediate rhombus, through its four adjacent black points, we can get corresponding prediction value Pi,j, which is(17)Pi,j=Ii-1,j+Ii+1,j+Ii,j-1+Ii,j+14,where Ii-1,j, Ii+1,j, Ii,j-1, and Ii,j+1 are four adjacent pixels (up, down, left, and right) of the Ii,j. watermarking embedding is only to operate on the Ii,j, so the values of Ii-1,j, Ii+1,j, Ii,j-1, and Ii,j+1 are not changed; namely, the value of Pi,j is not changed. Therefore, we can restore image according to the lowest effective bit of Pi,j. Then, we can get the corresponding prediction error, which is(18)ei,j=Pi,j-Ii,j.In (17), we compute all white pixel corresponding prediction error values ei,j that satisfy the condition, generate histogram Hei,j, and find the difference error, which are the top of the difference errors el and erer=el+1.Figure 2
Rhombus prediction scheme.Then, the predicted valueei,j of all pixels Ii,j is divided into two categories according to Figure 3. The error value is in the middle of the diamond and the error value is in the diamond-four angle. Each type of histogram is generated according to the following method. Firstly, the histogram is pretreated, secondly, the watermarking information is embedded in it, and finally, the histogram is encrypted by the RC4 encryption.Figure 3
The dividing scheme of rhombus for difference error value.We compute all white pixel corresponding errorei,j that satisfy the condition and generate two parts of histograms Hei,j of the two categories difference; then, the same operation is performed in each histogram. we find the maximum vertex in the the histogram of the difference between the corresponding er and second values el. In order to facilitate the narrative, remember el<er, and LSBPi,j represents the least significant bit of the Pi,j. We introduce location map Lm1 and location map Lm2; they are a series of binary sequences. Among them, Lm1 is used to mark the location information which can be embedded (0 represents no embedded location and 1 represents embedded location), and Lm2 is used to record the embedding watermarking information (binary 0 and 1). For the white point of satisfying the rhombus conditions, they are adjusted from left to right and from top to bottom, and the operation is shown as follows.Case 1.
Ifei,j<el-1 then Ii,j=Ii,j+1 (ei,j=ei,j-1), Lm1 = 0, Lm2 not marked.Case 2.
Ifel-1<ei,j≤el and LSBPi,j=0 then Lm1 = 1, Lm2 = 0.Case 3.
Ifel-1<ei,j≤el and LSBPi,j=1 then Ii,j=Ii,j+1 (ei,j=ei,j-1), Lm1 = 0, Lm2 not marked.Case 4.
Ifel<ei,j≤er and LSBPi,j=1 then Lm1 = 1, Lm2 = 1.Case 5.
Ifel<ei,j≤er and LSBPi,j=0 then Ii,j=Ii,j-1 (ei,j=ei,j+1), Lm1 = 0, Lm2 not marked.Case 6.
Ifei,j>er then Ii,j=Ii,j-1 (ei,j=ei,j+1), Lm1 = 0, Lm2 not marked.In this way, we can get the two parts of the different histogram corresponding to the two location maps. The temporary maps Lm1 and Lm2 are encrypted and compressed; then they are transferred to the user of legitimate embedding watermarking. Once finishing the embedding watermarking at the sender, two temporary maps are immediately destroyed.(2) Image Encryption. We encrypt each pixel in M by the RC4’s random key stream K and get encrypted image C (the specific method is in accordance with (2)).(3) Embedding Watermarking InformationCase 1.
Legitimate user of the embedding watermarking information gets location maps Lm1 and Lmp2; he can find the embedding watermarking location according to Lm1; then, Lm1 is read by scanning from left to right and from top to bottom of the sequence of operation; if Lm1 = 1, directly operate Case2; otherwise, skip position and go next judgment.Case 2.
Embedding watermarking informationb=0, read Lm2, If corresponding Lm2 = 0, then WCi,j=Ci,j, (where WCi,j represents the encryption image with watermarking and Ci,j represents ciphertext); if corresponding Lm2 = 1, then WCi,j=Ci,j+1mod⁡256; embedding watermarking information b=1, read Lm2; if corresponding Lm2 = 0, then WCi,j=Ci,j-1mod⁡256; if corresponding Lm2 = 1, then WCi,j=Ci,j.Case 3.
Until all the watermarking information is embedded, Lm1 and Lm2 are destructed; end and the encrypted image with watermarking is formed.


### 3.2. The Receiver

This section is divided into two parts: part (1) is image decryption; part (2) is extraction watermarking and restoration image.(1) Image Decryption. The receiver gets the encrypted image with watermarking and the same random seed S and decrypts image by the RC4 decryption after the key sequence Rk is generated (the specific method according to (3)).(2) Extraction Watermarking and Restoration Image(i) Preoperation. Preoperation is done before the extraction watermarking and restoration image. We introduce location map Lm3; it is used to mark the location where watermarking information is embedded or the location where it is not embedded (Lm3 = 1 represents the location where location is embedded and Lm3 = 0 represents the location where it is not embedded). The steps are shown as follows.Step 1.
The sender divides the same pixel as one group and calculates each part of the different error valuecei,j (cei,j represents the pixel of the decrypted image) which is calculated by late the corresponding location pixel wmi,j (wmi,j represents plaintext with watermarking information). Then, a difference histogram is generated after the image is decrypted; we can find the difference error value cel at the top of the difference histogram and the other difference error value cercer=cel+1.Step 2.
To process the plaintext with watermarking, it is shown as follows.Case 1.
Ifcei,j≤cel-2, then wmi,j=wmi,j-1, Lm3 not marked.Case 2.
Ifcel-2<cei,j≤cel-1, then wmi,j=wmi,j-1, Lm3 = 0.Case 3.
Ifcel-1<cei,j≤cer, then Lm3 = 1.Case 4.
Ifcer<cei,j≤cer+1, then wmi,j=wmi,j+1, Lm3 = 0.Case 5.
Ifcei,j>cer+1, then wmi,j=wmi,j+1, Lm3 not marked.So, we can get the decrypted image with watermarking information; therefore, we send Lm3 (Lm3 has been compressed and encrypted) to the legitimate user who can extract the watermarking information.Step 3.
In the algorithm, due to difference histogram change, corresponding pixels will change and cause overflow or underflow phenomenon. This phenomenon is not much; it can be processed according to the following.Case 1.
If175<cei,j≤254, then wmi,j=255.Case 2.
If254<cei,j≤255, then wmi,j=255.Case 3.
If255<cei,j≤256, then wmi,j is unchanged.Case 4.
If-255<cei,j≤-175, then wmi,j=0.Case 5.
If-255<cei,j≤-254, then wmi,j=0.Case 6.
If-156<cei,j≤-255, then wmi,j unchanged.(ii) Image Recovery. Image recovery steps are shown as follows.Step 1.
Applying to Lm3, the legitimate user extracts the watermarking information and divides image again at the same sender’s pixel group.cei,j is calculated by the corresponding white point pixel wmi,j, according to the order from top to bottom and from left to right. Then, a difference histogram is generated, and we can find the difference error value cel at the top of the difference histogram and the other difference error value el and erer=el+1; at this time Pi,j′=wmi-1,j+wmi+1,j+wmi,j-1+wmi,j+1/4, LSBPi,j′ represents the lowest significant bit of Pi,j′, and mi,j represents the restoration pixel.Step 2.
Ifcel-1<cei,j≤cel, read the corresponding Lm3, and when Lm3 = 1, extract watermarking b=1; however, when LSBPi,j′=1, then mi,j=wmi,j; when LSBPi,j′=0, then mi,j=wmi,j+1.Step 3.
Ifcer-1<cei,j≤cer, read the corresponding Lm3, and when Lm3 = 1, extract watermarking b=0; however, when LSBPi,j′=0, then mi,j=wmi,j; when LSBPi,j′=1, then mi,j=wmi,j-1.Step 4.
In other cases, we directly judge the next embedding watermarking information and go to Step1.Step 5.
When all the watermarking information is extracted, the two-part watermark information is extracted according to the first diamond inner, and then the diamond-four angle is connected. We can get all the watermark information, and the image gets recovery; end.(iii) Overflow or Underflow Processing. All the watermarking information extraction is finished and the image is recovered; there will also be a small amount of pixels overflow or underflow, and it is processed as follows.Case 1.
If255<cei,j≤256 then mi,j=255, b=0.Case 2.
If-156<cei,j≤-255 then mi,j=0, b=1.


## 3.1. The Sender

This section is divided into three parts: part (1) is image pretreatment; part (2) is image encryption; part (3) is embedding watermarking information.(1) Image Pretreatment. The image is pretreated before it is encrypted; Figure 2 shows the pixel division scheme in the rhombus prediction. Firstly, the pixels of the image are divided into two categories according to Figures 2(a) or 2(b), and white dots and black dots represent the two types of divided pixels. In Figure 2(a), the four black pixels adjacent to the white pixels form a rhombus pattern, the four black pixels are located in the four corners of the rhombus, and the white pixels are located in the center of the rhombus, and the middle white pixel value can be predicted by using the four black pixel values. In Figure 2(b), the four white pixels are located in the four corners of the rhombus, and the black pixels are located in the center of the rhombus; the middle black pixel value can be predicted by using the four white pixel values. In this paper, we use Figure 2(a) to divide the pixels. For the all white pixels Ii,j in the intermediate rhombus, through its four adjacent black points, we can get corresponding prediction value Pi,j, which is(17)Pi,j=Ii-1,j+Ii+1,j+Ii,j-1+Ii,j+14,where Ii-1,j, Ii+1,j, Ii,j-1, and Ii,j+1 are four adjacent pixels (up, down, left, and right) of the Ii,j. watermarking embedding is only to operate on the Ii,j, so the values of Ii-1,j, Ii+1,j, Ii,j-1, and Ii,j+1 are not changed; namely, the value of Pi,j is not changed. Therefore, we can restore image according to the lowest effective bit of Pi,j. Then, we can get the corresponding prediction error, which is(18)ei,j=Pi,j-Ii,j.In (17), we compute all white pixel corresponding prediction error values ei,j that satisfy the condition, generate histogram Hei,j, and find the difference error, which are the top of the difference errors el and erer=el+1.Figure 2
Rhombus prediction scheme.Then, the predicted valueei,j of all pixels Ii,j is divided into two categories according to Figure 3. The error value is in the middle of the diamond and the error value is in the diamond-four angle. Each type of histogram is generated according to the following method. Firstly, the histogram is pretreated, secondly, the watermarking information is embedded in it, and finally, the histogram is encrypted by the RC4 encryption.Figure 3
The dividing scheme of rhombus for difference error value.We compute all white pixel corresponding errorei,j that satisfy the condition and generate two parts of histograms Hei,j of the two categories difference; then, the same operation is performed in each histogram. we find the maximum vertex in the the histogram of the difference between the corresponding er and second values el. In order to facilitate the narrative, remember el<er, and LSBPi,j represents the least significant bit of the Pi,j. We introduce location map Lm1 and location map Lm2; they are a series of binary sequences. Among them, Lm1 is used to mark the location information which can be embedded (0 represents no embedded location and 1 represents embedded location), and Lm2 is used to record the embedding watermarking information (binary 0 and 1). For the white point of satisfying the rhombus conditions, they are adjusted from left to right and from top to bottom, and the operation is shown as follows.Case 1.
Ifei,j<el-1 then Ii,j=Ii,j+1 (ei,j=ei,j-1), Lm1 = 0, Lm2 not marked.Case 2.
Ifel-1<ei,j≤el and LSBPi,j=0 then Lm1 = 1, Lm2 = 0.Case 3.
Ifel-1<ei,j≤el and LSBPi,j=1 then Ii,j=Ii,j+1 (ei,j=ei,j-1), Lm1 = 0, Lm2 not marked.Case 4.
Ifel<ei,j≤er and LSBPi,j=1 then Lm1 = 1, Lm2 = 1.Case 5.
Ifel<ei,j≤er and LSBPi,j=0 then Ii,j=Ii,j-1 (ei,j=ei,j+1), Lm1 = 0, Lm2 not marked.Case 6.
Ifei,j>er then Ii,j=Ii,j-1 (ei,j=ei,j+1), Lm1 = 0, Lm2 not marked.In this way, we can get the two parts of the different histogram corresponding to the two location maps. The temporary maps Lm1 and Lm2 are encrypted and compressed; then they are transferred to the user of legitimate embedding watermarking. Once finishing the embedding watermarking at the sender, two temporary maps are immediately destroyed.(2) Image Encryption. We encrypt each pixel in M by the RC4’s random key stream K and get encrypted image C (the specific method is in accordance with (2)).(3) Embedding Watermarking InformationCase 1.
Legitimate user of the embedding watermarking information gets location maps Lm1 and Lmp2; he can find the embedding watermarking location according to Lm1; then, Lm1 is read by scanning from left to right and from top to bottom of the sequence of operation; if Lm1 = 1, directly operate Case2; otherwise, skip position and go next judgment.Case 2.
Embedding watermarking informationb=0, read Lm2, If corresponding Lm2 = 0, then WCi,j=Ci,j, (where WCi,j represents the encryption image with watermarking and Ci,j represents ciphertext); if corresponding Lm2 = 1, then WCi,j=Ci,j+1mod⁡256; embedding watermarking information b=1, read Lm2; if corresponding Lm2 = 0, then WCi,j=Ci,j-1mod⁡256; if corresponding Lm2 = 1, then WCi,j=Ci,j.Case 3.
Until all the watermarking information is embedded, Lm1 and Lm2 are destructed; end and the encrypted image with watermarking is formed.


## 3.2. The Receiver

This section is divided into two parts: part (1) is image decryption; part (2) is extraction watermarking and restoration image.(1) Image Decryption. The receiver gets the encrypted image with watermarking and the same random seed S and decrypts image by the RC4 decryption after the key sequence Rk is generated (the specific method according to (3)).(2) Extraction Watermarking and Restoration Image(i) Preoperation. Preoperation is done before the extraction watermarking and restoration image. We introduce location map Lm3; it is used to mark the location where watermarking information is embedded or the location where it is not embedded (Lm3 = 1 represents the location where location is embedded and Lm3 = 0 represents the location where it is not embedded). The steps are shown as follows.Step 1.
The sender divides the same pixel as one group and calculates each part of the different error valuecei,j (cei,j represents the pixel of the decrypted image) which is calculated by late the corresponding location pixel wmi,j (wmi,j represents plaintext with watermarking information). Then, a difference histogram is generated after the image is decrypted; we can find the difference error value cel at the top of the difference histogram and the other difference error value cercer=cel+1.Step 2.
To process the plaintext with watermarking, it is shown as follows.Case 1.
Ifcei,j≤cel-2, then wmi,j=wmi,j-1, Lm3 not marked.Case 2.
Ifcel-2<cei,j≤cel-1, then wmi,j=wmi,j-1, Lm3 = 0.Case 3.
Ifcel-1<cei,j≤cer, then Lm3 = 1.Case 4.
Ifcer<cei,j≤cer+1, then wmi,j=wmi,j+1, Lm3 = 0.Case 5.
Ifcei,j>cer+1, then wmi,j=wmi,j+1, Lm3 not marked.So, we can get the decrypted image with watermarking information; therefore, we send Lm3 (Lm3 has been compressed and encrypted) to the legitimate user who can extract the watermarking information.Step 3.
In the algorithm, due to difference histogram change, corresponding pixels will change and cause overflow or underflow phenomenon. This phenomenon is not much; it can be processed according to the following.Case 1.
If175<cei,j≤254, then wmi,j=255.Case 2.
If254<cei,j≤255, then wmi,j=255.Case 3.
If255<cei,j≤256, then wmi,j is unchanged.Case 4.
If-255<cei,j≤-175, then wmi,j=0.Case 5.
If-255<cei,j≤-254, then wmi,j=0.Case 6.
If-156<cei,j≤-255, then wmi,j unchanged.(ii) Image Recovery. Image recovery steps are shown as follows.Step 1.
Applying to Lm3, the legitimate user extracts the watermarking information and divides image again at the same sender’s pixel group.cei,j is calculated by the corresponding white point pixel wmi,j, according to the order from top to bottom and from left to right. Then, a difference histogram is generated, and we can find the difference error value cel at the top of the difference histogram and the other difference error value el and erer=el+1; at this time Pi,j′=wmi-1,j+wmi+1,j+wmi,j-1+wmi,j+1/4, LSBPi,j′ represents the lowest significant bit of Pi,j′, and mi,j represents the restoration pixel.Step 2.
Ifcel-1<cei,j≤cel, read the corresponding Lm3, and when Lm3 = 1, extract watermarking b=1; however, when LSBPi,j′=1, then mi,j=wmi,j; when LSBPi,j′=0, then mi,j=wmi,j+1.Step 3.
Ifcer-1<cei,j≤cer, read the corresponding Lm3, and when Lm3 = 1, extract watermarking b=0; however, when LSBPi,j′=0, then mi,j=wmi,j; when LSBPi,j′=1, then mi,j=wmi,j-1.Step 4.
In other cases, we directly judge the next embedding watermarking information and go to Step1.Step 5.
When all the watermarking information is extracted, the two-part watermark information is extracted according to the first diamond inner, and then the diamond-four angle is connected. We can get all the watermark information, and the image gets recovery; end.(iii) Overflow or Underflow Processing. All the watermarking information extraction is finished and the image is recovered; there will also be a small amount of pixels overflow or underflow, and it is processed as follows.Case 1.
If255<cei,j≤256 then mi,j=255, b=0.Case 2.
If-156<cei,j≤-255 then mi,j=0, b=1.


## 4. Experimental Results and Analysis

### 4.1. The Data Confidentiality

The RC4 encryption is stream ciphering algorithm with alterable length of key streamK; it accepts a key K from 1 to 256 bytes. As shown in (1) to (5), the RC4 encryption satisfies the confidentiality requirements when the key stream K is long enough and complex enough.Supposing the length of key streamK is 16 bytes (128 bits), the time of performing an encryption is 1 μs, so the number of the keys K is 2128, and the time T of exhausting half key space is (19)T=2128÷2×1μs≈5.4×1024year.It is not feasible on computation for an attacker to analyze the key K by the sender and receiver’s decrypted image. Also, the middle man cannot analyze the key K based on the decrypted image that is transferred over the channel.


### 4.2. Resisting Rotation Attack

We adopt the rotation angle (RA) of-120∘, -90∘, -60∘, -30∘, 30∘, 60∘, 90∘, and 120∘ to test the rotation attack. Table 1 gives the successful extracting times (SET) of the watermarking information in encrypted images against the rotation attack; here the testing times (TT) are 12 times. It shows that this reversible date-hiding algorithm has good resisting rotation attack. The main reason is that the rotation cannot change the relative coordinate value of any pixel of the encrypted images, and there is no essential influence on the embedded watermarking information.Table 1
The test of resisting rotation attack.
Items Datum RA - 12 0 ° - 9 0 ° - 6 0 ° - 3 0 ° 3 0 ° 6 0 ° 9 0 ° 12 0 ° TT 12 12 12 12 12 12 12 12 SET 12 12 12 12 12 12 12 12


### 4.3. The Embedding Capacity and PSNR

In order to verify the effectiveness of our method, simulation experiments are conducted by using MATLAB7.0 platform. We use the peak signal-to-noise (PSNR) and the embedding rate (ER) to evaluate the quality of the encrypted image and embedding capacity. For the512×512 gray image, it is(20)PSNR=10×log10⁡2552MSEdB,MSE=1512×512∑i=0511∑j=0511Hi,j-Hi,j′,where MSE represents mean squared errors.Then, the ER is(21)ER=NWNPbitpixel,bpp,where NW represents the number of binary bits of watermarking information and NP represents the number of pixels of the image.We select a standard test image Lean512×512 to test, as shown in Figure 4(a), and the encrypted image as shown in Figure 4(b); obviously, the image is incomprehensible and completely covers the contents of the original image. In order to further illustrate the problem, we generate the histogram of the image before and after encryption; we can see that the encrypted images histogram is flat from Figure 4(d); it also shows great regularity and uncertainty compared to Figure 4(c); the information entropy tends to maximize.Figure 4
Comparing image Lena encryption before and after: (a) original image; (b) encrypted image; (c) the histogram of the original image; (d) the histogram of the encrypted image.
(a) (b) (c) (d)After 15000 bits watermarking information is embedded in the encrypted image, we can get PSNR = 62.36 (dB) when it is decrypted, as shown in Figure5(a); the effect is very satisfactory looking from the perspective; Figure 5(b) represents the complete recovering image after the watermarking information is extracted; this image and the original image are completely consistent by comparing the data; namely, the proposed algorithm is completely reversible. In order to further experiment, we select four images (512×512) as test images from the image database USC-SIPI: Lena, Plane, Milkdrop, and Woman2, as shown in Figure 6. Table 2 lists the four test images’ PSNR in different ER, and we can see from the table, with the ER increasing, the PSNR of the image decreases gradually. When the ER is 0.06, PSNR can be maintained at more than 62 dB; it not only shows that the images’ PSNR can be maintained at a high level by using this algorithm in different ER to calculate the PSNR but also reflects that the image distortion is still not perceived when PSNR is 62 dB in theory; then it explains the feasibility of this algorithm.Table 2
The ER and PSNR of the four test images.
Images PSNR/dB ER/bpp 0.01 0.02 0.03 0.04 0.05 0.06  Lena 70.36 67.08 65.56 64.26 63.18 62.64 Plane 70.46 67.12 65.61 64.21 63.22 62.68 Milkdrop 70.38 67.10 65.48 64.18 63.12 62.67 Woman2 70.62 67.32 65.52 64.32 63.28 62.72Figure 5
The decrypted image Lena with watermarking and the ultimate recovery image Lena: (a) the decrypted image Lena with watermarking; (b) the ultimate recovery image Lena.
(a) (b)Figure 6
Four test images: (a) Lena; (b) Plane; (c) Milkdrop; (d) Woman2.
(a) (b) (c) (d)


### 4.4. The Experimental Contrast

We use PSNR value to measure direct decrypted image with hidden information. For the images Lena, Plane, Milkdrop, and Woman2, we compare our algorithm with Zhang et al. [13] and Ma’s algorithm [17] from the ER and PSNR, as shown in Figure 7. We assume that Ma and Zhang’s algorithm is perfectly correct in extraction. When the ER is greater than 0.015, we use Zhangs algorithm to make the experiment; the image will appear as serious distortion; that is to say, when the ER is greater than 0.015, the test will lose its meaning, so we only take the ER at 0.005, 0.01, and 0.015. When the ER is between 0 and 0.02 bpp, we use a least significant bit, and when it is more than 0.02 bpp, we use the least two significant bits. We can see that the PSNR gradually decreases with the ER increasing, but our algorithm’s curve is located above Ma and Zhang’s algorithm; namely, our algorithms PSNR is significantly big in the same ER; it further not only shows that this algorithm is more feasible but also illustrates that this algorithm is better than other algorithms.Figure 7
The chart of our algorithm compared with algorithm Zhang’s and Ma’s.
(a)
Test image Lena (b)
Test image Plane (c)
Test image Milkdrop (d)
Test image Woman2


## 4.1. The Data Confidentiality

The RC4 encryption is stream ciphering algorithm with alterable length of key streamK; it accepts a key K from 1 to 256 bytes. As shown in (1) to (5), the RC4 encryption satisfies the confidentiality requirements when the key stream K is long enough and complex enough.Supposing the length of key streamK is 16 bytes (128 bits), the time of performing an encryption is 1 μs, so the number of the keys K is 2128, and the time T of exhausting half key space is (19)T=2128÷2×1μs≈5.4×1024year.It is not feasible on computation for an attacker to analyze the key K by the sender and receiver’s decrypted image. Also, the middle man cannot analyze the key K based on the decrypted image that is transferred over the channel.


## 4.2. Resisting Rotation Attack

We adopt the rotation angle (RA) of-120∘, -90∘, -60∘, -30∘, 30∘, 60∘, 90∘, and 120∘ to test the rotation attack. Table 1 gives the successful extracting times (SET) of the watermarking information in encrypted images against the rotation attack; here the testing times (TT) are 12 times. It shows that this reversible date-hiding algorithm has good resisting rotation attack. The main reason is that the rotation cannot change the relative coordinate value of any pixel of the encrypted images, and there is no essential influence on the embedded watermarking information.Table 1
The test of resisting rotation attack.
Items Datum RA - 12 0 ° - 9 0 ° - 6 0 ° - 3 0 ° 3 0 ° 6 0 ° 9 0 ° 12 0 ° TT 12 12 12 12 12 12 12 12 SET 12 12 12 12 12 12 12 12


## 4.3. The Embedding Capacity and PSNR

In order to verify the effectiveness of our method, simulation experiments are conducted by using MATLAB7.0 platform. We use the peak signal-to-noise (PSNR) and the embedding rate (ER) to evaluate the quality of the encrypted image and embedding capacity. For the512×512 gray image, it is(20)PSNR=10×log10⁡2552MSEdB,MSE=1512×512∑i=0511∑j=0511Hi,j-Hi,j′,where MSE represents mean squared errors.Then, the ER is(21)ER=NWNPbitpixel,bpp,where NW represents the number of binary bits of watermarking information and NP represents the number of pixels of the image.We select a standard test image Lean512×512 to test, as shown in Figure 4(a), and the encrypted image as shown in Figure 4(b); obviously, the image is incomprehensible and completely covers the contents of the original image. In order to further illustrate the problem, we generate the histogram of the image before and after encryption; we can see that the encrypted images histogram is flat from Figure 4(d); it also shows great regularity and uncertainty compared to Figure 4(c); the information entropy tends to maximize.Figure 4
Comparing image Lena encryption before and after: (a) original image; (b) encrypted image; (c) the histogram of the original image; (d) the histogram of the encrypted image.
(a) (b) (c) (d)After 15000 bits watermarking information is embedded in the encrypted image, we can get PSNR = 62.36 (dB) when it is decrypted, as shown in Figure5(a); the effect is very satisfactory looking from the perspective; Figure 5(b) represents the complete recovering image after the watermarking information is extracted; this image and the original image are completely consistent by comparing the data; namely, the proposed algorithm is completely reversible. In order to further experiment, we select four images (512×512) as test images from the image database USC-SIPI: Lena, Plane, Milkdrop, and Woman2, as shown in Figure 6. Table 2 lists the four test images’ PSNR in different ER, and we can see from the table, with the ER increasing, the PSNR of the image decreases gradually. When the ER is 0.06, PSNR can be maintained at more than 62 dB; it not only shows that the images’ PSNR can be maintained at a high level by using this algorithm in different ER to calculate the PSNR but also reflects that the image distortion is still not perceived when PSNR is 62 dB in theory; then it explains the feasibility of this algorithm.Table 2
The ER and PSNR of the four test images.
Images PSNR/dB ER/bpp 0.01 0.02 0.03 0.04 0.05 0.06  Lena 70.36 67.08 65.56 64.26 63.18 62.64 Plane 70.46 67.12 65.61 64.21 63.22 62.68 Milkdrop 70.38 67.10 65.48 64.18 63.12 62.67 Woman2 70.62 67.32 65.52 64.32 63.28 62.72Figure 5
The decrypted image Lena with watermarking and the ultimate recovery image Lena: (a) the decrypted image Lena with watermarking; (b) the ultimate recovery image Lena.
(a) (b)Figure 6
Four test images: (a) Lena; (b) Plane; (c) Milkdrop; (d) Woman2.
(a) (b) (c) (d)


## 4.4. The Experimental Contrast

We use PSNR value to measure direct decrypted image with hidden information. For the images Lena, Plane, Milkdrop, and Woman2, we compare our algorithm with Zhang et al. [13] and Ma’s algorithm [17] from the ER and PSNR, as shown in Figure 7. We assume that Ma and Zhang’s algorithm is perfectly correct in extraction. When the ER is greater than 0.015, we use Zhangs algorithm to make the experiment; the image will appear as serious distortion; that is to say, when the ER is greater than 0.015, the test will lose its meaning, so we only take the ER at 0.005, 0.01, and 0.015. When the ER is between 0 and 0.02 bpp, we use a least significant bit, and when it is more than 0.02 bpp, we use the least two significant bits. We can see that the PSNR gradually decreases with the ER increasing, but our algorithm’s curve is located above Ma and Zhang’s algorithm; namely, our algorithms PSNR is significantly big in the same ER; it further not only shows that this algorithm is more feasible but also illustrates that this algorithm is better than other algorithms.Figure 7
The chart of our algorithm compared with algorithm Zhang’s and Ma’s.
(a)
Test image Lena (b)
Test image Plane (c)
Test image Milkdrop (d)
Test image Woman2


## 5. Conclusion

The cipher image embedding technique is combined with the advantage of encryption technology and information hiding technology. It can be satisfied with the need of important privacy protection and become a new field. This paper presents a novel reversible watermarking embedding algorithm in encrypted image; the algorithm adopts rhombus prediction thought and histogram modification scheme. It truly realizes reversible watermarking extraction and image lossless recovery. Experiments show that the proposed algorithm is better than other algorithms.



---

*Source: 4313580-2016-08-28.xml*