# Reversible Data Hiding with Pixel Prediction and Additive Homomorphism for Encrypted Image

Authors: Chunqiang Yu; Xianquan Zhang; Zhenjun Tang; Yan Chen; Jingyu Huang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Data hiding in encrypted image is a recent popular topic of data security. In this paper, we propose a reversible data hiding algorithm with pixel prediction and additive homomorphism for encrypted image. Specifically, the proposed algorithm applies pixel prediction to the input image for generating a cover image for data embedding, referred to as the preprocessed image. The preprocessed image is then encrypted by additive homomorphism. Secret data is finally embedded into the encrypted image via modular 256 addition. During secret data extraction and image recovery, addition homomorphism and pixel prediction are jointly used. Experimental results demonstrate that the proposed algorithm can accurately recover original image and reach high embedding capacity and good visual quality. Comparisons show that the proposed algorithm outperforms some recent algorithms in embedding capacity and visual quality.


---

## Body

## 1. Introduction

Data hiding is an important technology for embedding secret data into a meaningful cover medium (such as an image or a video) to generate a stego-medium with a small distortion [1, 2]. Reversible data hiding (RDH) is a branch of data hiding, which can restore the original image from the stego-image after extraction of the embedded data. This restoration property of RDH plays an important role in those data-sensitive applications, such as medical imagery, military imagery, and law forensics, in which the cover image must be accurately restored.In the past years, various RDH algorithms have been proposed. Generally, these RDH algorithms can be classified into three categories: lossless compression based algorithms, difference expansion (DE) based algorithms, and histogram shifting (HS) based algorithms. Lossless compression based algorithms vacate space for embedding secret message by losslessly compressing the least significant bit (LSB) planes or quantization residuals [3, 4]. They can be applied to image authentication and watermarking, but their embedding capacities are limited. DE based algorithms usually shift the difference of neighboring pixels for creating a vacant least significant bit (LSB) and append one secret bit to the vacated LSB [5, 6]. The HS based algorithms firstly shift the bins of histogram of gray values [7] or the predicted errors [8–12] for generating vacated space and then embed secret data into the vacated space. This kind of algorithms can provide a good trade-off between embedding capacity and visual quality.Image encryption is a useful technique for protecting image content [13, 14]. It can convert an original image, known as plaintext image, into a meaningless image called the encrypted image. Since it cannot observe any useful information from the encrypted image, image content security is achieved. In some application scenarios, such as cloud storage, there are many encrypted images and people would like to embed secret message into encrypted images for privacy protection. These applications require efficient RDH algorithms for encrypted images.Recently, many researchers have developed various RDH algorithms in encrypted images since the encrypted images are widely generated and stored in cyberspace. For example, Zhang [15] proposed a famous RDH algorithm in encrypted image. This RDH algorithm divides the encrypted image into several blocks and embeds a secret bit into a block by flipping 3 LSBs of a half of pixels in the block. This algorithm extracts secret data by exploiting a fluctuation function in terms of spatial correlation in natural images. Zhang’ algorithm is the preliminary research of RDH algorithms in encrypted images, but this algorithm will cause bit errors in the recovered image and the extracted data for some cases. Hong et al. [16] exploited the spatial correlation using a different estimation equation and side match technique to achieve a low error rate. To reduce error rate, Liao and Shu [17] designed a useful metric for measuring block complexity by considering neighbor pixels in terms of the locations. In another work, Qin and Zhang [18] presented an RDH scheme with capability of image content protection. This scheme only alters three LSBs of selected pixels of encrypted image for secret bit embedding. The above-mentioned algorithms rely on spatial correlation of original image when extracting data, and their procedures of image recovery and data extraction are similar. For the encrypted JPEG images, Qian et al. [19] exploited the coding/decoding principle of the JPEG image to design a reversible data hiding scheme.To separate data extraction from image decryption, Zhang [20] proposed to compress the encrypted images to vacate room for data hiding. In [21], Qian and Zhang exploited distributed source coding to improve the embedding capacity of the RDH algorithm [20]. However, their encryption disorganizes spatial correlation of pixels and thus it is difficult to vacate space for data hiding. In another study, Yi et al. [22] exploited block permutation conduct image encryption for preserving spatial redundancy and used adaptive block-level based prediction-error expansion to conceal secret bits in the encrypted image blocks. Tang et al. [23] proposed a reversible data hiding algorithm in encrypted domain by exploiting alpha channel of portable network graphics (PNG) image. In this RDH algorithm, secret data is divided into some segments. For each segment, one bit is embedded into the LSB of encrypted pixel and other bits are hidden in the corresponding element of the alpha channel. A common feature of the above RDH algorithms is that they all embed secret data after image encryption.Some researchers [24–27] have proposed the idea of preprocessing image before encryption for data embedding. For example, Ma et al. [24] provided an RDH algorithm in encrypted images by reserving room before encryption. This algorithm first empties out room by embedding LSBs of some pixels into other pixels with a traditional RDH method, then encrypts the image, and finally uses the positions of these LSBs in the encrypted image to conceal secret data. Xu et al. [25] designed a specific encryption mode to encrypt interpolation-error of nonsample pixels and embedded secret data into interpolation-error using a modified version of histogram shifting and difference expansion technique. In another work, Nguyen et al. [26] used half of the pixels to classify the rest of the pixels into smooth and complex regions to provide room for embedding additional data. Agrawal and Kumar [27] divided original image into several consecutive sets, calculated mean of each set, stored it at the first element of its set before encryption, and finally embedded a secret bit into the encrypted pixels of one set except for the pixel holding the mean value in the set.Recently, homomorphic encryption is introduced to RDH algorithms in encrypted images [28–32]. In [28], the exclusive-or values of two neighboring pixels are reserved after image encryption so as to carry the additional data to be embedded. This is done by using the same pseudorandom bits to encrypt two neighboring pixels. Actually, the homomorphic property is equipped in the scheme [28]. Chen et al. [29] used Paillier encryption [33] to encrypt each pixel and embedded a secret bit into a pair of adjacent encrypted pixels. Shiu et al. [30] proceed a pair of adjacent original pixels using difference expansion to obtain a pair of odd or even pixels and then used Paillier encryption to encrypt the proceeded pixels. Similar to [29], this algorithm also embeds a secret bit into a pair of adjacent encrypted pixels. A common weakness of the use of Paillier encryption in [29, 30] is data expansion. In another study, Li et al. [31] divided image into several crosses, adopted the same key to encrypt pixels in each cross, and accommodated for data hiding by using the difference histogram of the encrypted image. Xiao et al. [32] divided image into several blocks and conducted data hiding in each block via additive homomorphism and pixel value ordering strategy. Zhang et al. [34] proposed a lossless and reversible data hiding algorithm for ciphertext images encrypted by public key cryptography with probabilistic and homomorphic properties. This algorithm shows better performances than some previous algorithms [15, 16, 20] in terms of PSNR in directly decrypted image.Although some useful homomorphism encryption-based RDH algorithms [29–31] for encrypted image have been reported. Their embedding capacity and visual quality are not desirable yet. For example, Chen’s method [29] and Shiu’s method [30] can only reach 0.5 bpp, and Li’ scheme [31] cannot reach 0.8 bpp for most test images. Aiming at these problems, we propose an error-free RDH algorithm in encrypted domain. Our algorithm not only perfectly recovers original images but also reaches high embedding capacity and good visual quality. Many experiments are conducted to validate our efficiency and the results demonstrate that our algorithm outperforms some recent algorithms. The remainder of this paper is organized as follows. Section 2 explains our algorithm and Section 3 discusses experimental results. Conclusions are finally drawn in Section 4.


## 2. Proposed Reversible Data Hiding

Our proposed algorithm consists of four components: image encryption with homomorphism, data embedding with additive homomorphism, data extraction, and image recovery. Details of these components will be explained in the following sections.


### 2.1. Image Encryption with Homomorphism

This component can be divided into two parts: the preprocessed image generation with prediction and homomorphism encryption. In our RDH algorithm, secret data will be embedded into the encrypted image by using additive homomorphism.


#### 2.1.1. Preprocessed Image Generation with Prediction

Predictors [35–38] are widely used in RDH algorithms for plaintext image. In this paper, we select an accurate gradient selective prediction (AGSP) predictor [38] to determine the original pixel predictions, which are used to construct preprocessed pixels. The reason of our selection of AGSP predictor is that it can reach a good balance between predictor performance and computational cost. The AGSP predictor operates on the nine neighboring pixels (i.e., x1,x2,x3,x4,x5,x6,x7,x8, andx9) of the current pixelx, as shown in Figure 1. The estimated gradients of four directions (i.e., horizontal, vertical, 45 degrees, and -45 degrees) are denoted byD1,D2,D3, andD4. The corresponding pixels of these gradientsD1,D2,D3, andD4 arex6,x9,x7, andx5, respectively. Suppose that Dmin1 and Dmin2 are two smallest gradients amongD1,D2,D3, andD4 and their corresponding pixels are Cmin1 and Cmin2. The prediction ofx can be calculated as follows:(1)x′=Dmin1×Cmin2+Dmin2×Cmin1Dmin1+Dmin2Figure 1
The currentx and its neighboring pixels.LetI be an 8-bit grayscale uncompressed original image withH×W size andI(i,j) be the pixel value in thei-th row andj-th column ofI, where 1 ≤i ≤H, 1 ≤j ≤W. As shown in Figure 2, the original imageI is divided into four regions denoted as Ω1, Ω2, Ω3, and Ω4, where Ω1 consists of all pixels used for embedding auxiliary information, Ω2 consists of unused pixels, Ω3 consists of pixels used for prediction, and Ω4 consists of pixels used for embedding secret data. The sizes of Ω1, Ω2, Ω3, and Ω4 will be described in Section 2.2. Those pixels of Ω1, Ω2, and Ω3 are kept unchanged in this stage. The pixels of Ω4 are scanned from left to right and top to down, as shown in Figure 2. For the pixelI(i,j) of Ω4, if it is located in a texture region, it may have a poor prediction. Here the local smoothness estimator is defined as the invariance denoted byCp(i,j), which is used to determine whetherI(i,j) is located in a smooth region or not. Consequently,Cp(i,j) can be determined as follows.(2)Cpi,j=Vmax-Vminwhere Vmax and Vmin are the maximum value and minimum value of the nine neighboring pixels ofI(i,j), respectively. IfCp(i,j) is not bigger than a predefined threshold T∈[0,255],I(i,j) and its neighboring pixels are highly correlative and it is considered as the pixel in smooth region. Otherwise,I(i,j) is viewed as the pixel in textural region. Note thatT should be determined in terms of image content. In general, a smallT value is good for smooth image and a bigT value is suitable for textural image.Figure 2
Different regions in the image.IfI(i,j) is located in a textural region,I(i,j) is kept unchanged. IfI(i,j) is located in a smooth region, we calculate the prediction ofI(i,j) using AGSP predictor and denote it asI(i,j)′. Therefore, the prediction-error can be calculated asD(i,j)=I(i,j) −I(i,j)′. SinceI(i,j) is close to its predictive valueI(i,j)′,D(i,j) is small with a high probability. Consequently, the preprocessed pixelIp(i,j) can be calculated as follows:(3)Ipi,j=Ii,j+2r-1×Di,jwherer (r≥1) implies how many bits can be embedded in the pixel andr will be introduced in Section 2.2. Further, (3) can be rewritten as (4)Ipi,j=2r×Ii,j-2r-1×Ii,j′.Note thatIp(i,j) may cause underflow or overflow. To avoid this, a location mapL1 withH×W size is exploited to record the underflow or overflow pixels. Specifically, ifIp(i,j) >255 orIp(i,j)<0,L1(i,j)=1 andI(i,j) is kept unchanged. Otherwise,L1(i,j)=0 and we use (3) to calculateIp(i,j). LetF be the preprocessed image andF(i,j) (1 ≤i ≤H, 1 ≤j ≤W) be the pixel value in thei-th row andj-th column ofF. Thus,F(i,j) can be obtained as follows.(5)Fi,j=Ii,jCp>TorL1i,j=1ori,j∉Ω42r×Ii,j-2r-1×Ii,j′OtherwiseAfter the above calculation, the preprocessed imageF is generated.


#### 2.1.2. Homomorphism Encryption

Homomorphic encryption is an efficient encryption technology with the useful property that computation on ciphertext is equivalent to the computation on its plaintext. Here, a homomorphic encryption method [39] by addition modulo 256 is used. Suppose thatm andc represent the plaintext and ciphertext. Thus, the homomorphic encryption and homomorphic decryption are described in (6) and (7), respectively,(6)c=Em,k=m+kmod256(7)m=Dc,k=c-kmod256wherek denotes encryption key andE(·,·) andD(·,·) are the encryption and decryption operations, respectively. An important property of the above encryption is the addition homomorphism in the plaintext domain. Letm1 andm2 be two different plain values whose corresponding random encryption keys arek1 andk2. Thus, we have the following equations:(8)Em1,k1⊕Em2,k2=Em1+m2,k1+k2mod256(9)DEm1,k1⊕Em2,k2,k1+k2=m1+m2mod256where ⊕ is modular 256 addition. Especially, ifk2 is equal to zero,m2 is considered as a given signal. Therefore, (8) and (9) can be rewritten as(10)Em1,k1⊕m2=Em1+m2,k1mod256(11)DEm1,k1⊕m2,k1=m1+m2mod256From (10) and (11), it can be found that addition operation can be done directly on the encrypted data without decryption.In this work, we exploit the RC4 [40] controlled by an encryption keyseed to generate a key matrixk(i,j) (1≤i≤H, 1≤j≤W), encryptF(i,j) with the corresponding keyk(i,j) by (6), and obtain the encrypted pixelC(i,j). After all pixels are processed, the encrypted imageC is then available.


### 2.2. Data Embedding with Additive Homomorphism

Since the encrypted imageC is generated using homomorphic encryption, we can embed secret data according to the property of additive homomorphism. Firstly, we convert a binary secret message into a sequence of secret digits in 2r-ary notational system. Then, secret digits can be embedded into those pixels of the encrypted imageC in Ω4 except the marked pixels byL1. Let a secret digit bes (0 ≤s ≤2r−1). For a pixelC(i,j), ifCp(i,j)>T,C(i,j) is kept unchanged; i.e.,C(i,j)′=C(i,j). Otherwise, we use the key whose value is 0 to encrypts and embeds intoC(i,j) as follows.(12)Ci,j′=Ci,j⊕s=EFi,j+s,ki,jmod256Note that if (F(i,j) +s) ≥ 256, the decrypted result of (10) should be (F(i,j)+s) mod 256. To accurately recover the original image and extract secret data, those pixels satisfying (F(i,j) +s) ≥ 256 must be recorded. To do so, another location mapL2 is used here. Since 0 ≤s ≤ 2r−1, the location mapL2 records the pixels whose values are larger than or equal to 256 −s =256 − (2r−1). Therefore, ifF(i,j) ≥ 256−(2r−1),L2(i,j)=1 andC(i,j)′=C(i,j). Otherwise,L2(i,j)=0 ands is embedded according to (12). Moreover, secret bits are not embedded into those pixels marked byL1 andL2. Note that the location mapL1 is generated in the process of image encryption, while the location mapL2 is generated during data hiding. Both location maps should be embedded into the cover image. To reduce the size of data embedded, lossless compression with arithmetic coding is exploited to compress the location maps.To exactly extract the secret data and recover the original image, some auxiliary information must be embedded into the encrypted image, including the size of secret digits, capacity parameterr, the thresholdT, the sizes of two compressed location maps, and the two compressed location maps. As the size of secret digits is less than or equal to the number of pixels in the original image, log2HW bits are enough to record it, whereH andW are the height and width of the original image, respectively. Similarly, 2log2HW bits are enough to save the sizes of two compressed location maps. Although a largerr will bring higher embedding capacity, it will also degrade image quality according to (3). To balance the embedding capacity and image quality, ther value should be less than or equal to 7. Therefore, 3 bits can represent ther value. As the range ofT is [0,255], 8 bits can represent theT value. Let the size of compressed version ofL1 bel1 and the size of compressed version ofL2 bel2. Thus, the size of auxiliary information can be determined as follows.(13)tau=l1+l2+11+3log2⁡HWTable 1 presents the auxiliary information and their data sizes.Table 1
Auxiliary information and its sizes.
Auxiliary information Size (Bit) Size of secret digits log2HW Capacity parameterr 3 ThresholdT 8 Size of compressed version ofL1 log2HW Size of compressed version ofL2 log2HW Compressed version ofL1 l 1 Compressed version ofL2 l 2Here the auxiliary information is embedded into the 3 LSBs of the encrypted pixels inΩ1 by using LSB replacement technique. Note that secret data and the 3 LSBs of the encrypted pixels in Ω1 are firstly concatenated to construct the data for embedding into Ω4 in our algorithm. As the 3 LSBs of the used encrypted pixels in Ω1 are preserved in advance, they can be accurately recovered during image recovery.Clearly, the number of pixels inΩ1 is t1=tau/3, where · is the rounding function. The number of pixels in Ω2 is(14)t2=0tau3modW=0W-tau3modWOtherwise.The number of pixels in Ω3 ist3=2×W+3×(H − tau/3/W − 2). Let the total number of the pixels marked byL1 andL2 in Ω4 bet4. Thus, the maximum pure embedding capacity (EC) of our RDH algorithm can be calculated as follows.(15)EC=r×H×W-t1-t2-t3-t4-tauNote that the data hiding keys of our algorithm are ther value and theT value. In addition, the encrypted image containing secret data is called the marked encrypted image in the following sections.


### 2.3. Data Extraction and Image Recovery

When the receiver obtains a marked encrypted image, he/she can conduct different operations according to the knowledge of keys. If only the encryption key is available, he/she can decrypt the marked encrypted image to directly retrieve the decrypted image, which is approximate to the original image. If both the encryption key and data hiding key are known, he/she can extract secret data exactly and recover the original image without errors. In this case, auxiliary information is firstly extracted from the 3 LSBs of pixels inΩ1. Then, the two compressed location maps are decompressed to retrieve the location mapsL1 andL2. Next, we extract secret digits and recover the original pixels as follows.IfCi,j′∈Ω2 or Ci,j′∈Ω3 or Ci,j′∈Ω4 andL1(i,j)=1, we directly decrypt Ci,j′ withk(i,j) to recover the original pixelI(i,j) according to (7).IfCi,j′∈Ω4 andL1(i,j)=0, we can obtain a decrypted pixel Fi,j′ byk(i,j). Since the original pixels which belong to Ω2 or Ω3 have been recovered,Cp(i,j) can be calculated by AGSP predictor. IfCp(i,j) >T,I(i,j)=F(i,j)′. Otherwise,Cp(i,j) ≤T and secret digits are embedded by additive homomorphism. Clearly, ifL2(i,j)=0,F(i,j)′=F(i,j)+s. OtherwiseF(i,j)′=F(i,j). Clearly,I(i,j)=(F(i,j)+(2r−1)×I(i,j)′)/2r by (5), whereI(i,j)′ is the prediction which can be calculated by AGSP predictor. ForL2(i,j)=1, its original pixel can be determined byI(i,j) =(F(i,j)+(2r−1)×I(i,j)′)/2r =Fi,j′+2r-1×Ii,j′/2r, where · is the floor rounding operation. ForL2(i,j)=0, sinceF(i,j)′=F(i,j)+s, its original pixelI(i,j)=(F(i,j)′−s+(2r−1)×I(i,j)′)/2r=Fi,j′+2r-1×Ii,j′/2r-s/2r. As 0 ≤s ≤ 2r−1, s/2r is 0. Therefore,I(i,j)=Fi,j′+2r-1×Ii,j′/2r. Consequently, the original pixel can be uniformly rewritten as(16)Ii,j=Fi,j′+2r-1×Ii,j′2rMeanwhile, ifL2(i,j)=0,F(i,j)′=F(i,j)+s=2r×I(i,j) − (2r−1)×I(i,j)′+s. It is clear thatF(i,j)′-I(i,j)′=2r×(I(i,j)-I(i,j)′)+s. Then the secret digits can be extracted as follows.(17)s=Fi,j′-Ii,j′mod2rThe recovered pixelI(i,j) is used to recover the next pixel and extract the next secret digit. Consequently, the entire original pixels in Ω4 are recovered and all secret digits are extracted according to the above scheme. Then, the secret digits are converted into a sequence of binary data. Note that the binary data is constructed by secret bits and the 3 LSBs of the used pixels in Ω1. Consequently, the binary data is divided into two parts and the preserved 3 LSBs of the used pixels are used to replace the 3 LSBs of the corresponding pixels in Ω1. After that, the encrypted pixels in Ω1 are recovered and then they are decrypted to restore the original pixels. Finally, the original image is restored by the recovered pixels of the four regions.


## 2.1. Image Encryption with Homomorphism

This component can be divided into two parts: the preprocessed image generation with prediction and homomorphism encryption. In our RDH algorithm, secret data will be embedded into the encrypted image by using additive homomorphism.


### 2.1.1. Preprocessed Image Generation with Prediction

Predictors [35–38] are widely used in RDH algorithms for plaintext image. In this paper, we select an accurate gradient selective prediction (AGSP) predictor [38] to determine the original pixel predictions, which are used to construct preprocessed pixels. The reason of our selection of AGSP predictor is that it can reach a good balance between predictor performance and computational cost. The AGSP predictor operates on the nine neighboring pixels (i.e., x1,x2,x3,x4,x5,x6,x7,x8, andx9) of the current pixelx, as shown in Figure 1. The estimated gradients of four directions (i.e., horizontal, vertical, 45 degrees, and -45 degrees) are denoted byD1,D2,D3, andD4. The corresponding pixels of these gradientsD1,D2,D3, andD4 arex6,x9,x7, andx5, respectively. Suppose that Dmin1 and Dmin2 are two smallest gradients amongD1,D2,D3, andD4 and their corresponding pixels are Cmin1 and Cmin2. The prediction ofx can be calculated as follows:(1)x′=Dmin1×Cmin2+Dmin2×Cmin1Dmin1+Dmin2Figure 1
The currentx and its neighboring pixels.LetI be an 8-bit grayscale uncompressed original image withH×W size andI(i,j) be the pixel value in thei-th row andj-th column ofI, where 1 ≤i ≤H, 1 ≤j ≤W. As shown in Figure 2, the original imageI is divided into four regions denoted as Ω1, Ω2, Ω3, and Ω4, where Ω1 consists of all pixels used for embedding auxiliary information, Ω2 consists of unused pixels, Ω3 consists of pixels used for prediction, and Ω4 consists of pixels used for embedding secret data. The sizes of Ω1, Ω2, Ω3, and Ω4 will be described in Section 2.2. Those pixels of Ω1, Ω2, and Ω3 are kept unchanged in this stage. The pixels of Ω4 are scanned from left to right and top to down, as shown in Figure 2. For the pixelI(i,j) of Ω4, if it is located in a texture region, it may have a poor prediction. Here the local smoothness estimator is defined as the invariance denoted byCp(i,j), which is used to determine whetherI(i,j) is located in a smooth region or not. Consequently,Cp(i,j) can be determined as follows.(2)Cpi,j=Vmax-Vminwhere Vmax and Vmin are the maximum value and minimum value of the nine neighboring pixels ofI(i,j), respectively. IfCp(i,j) is not bigger than a predefined threshold T∈[0,255],I(i,j) and its neighboring pixels are highly correlative and it is considered as the pixel in smooth region. Otherwise,I(i,j) is viewed as the pixel in textural region. Note thatT should be determined in terms of image content. In general, a smallT value is good for smooth image and a bigT value is suitable for textural image.Figure 2
Different regions in the image.IfI(i,j) is located in a textural region,I(i,j) is kept unchanged. IfI(i,j) is located in a smooth region, we calculate the prediction ofI(i,j) using AGSP predictor and denote it asI(i,j)′. Therefore, the prediction-error can be calculated asD(i,j)=I(i,j) −I(i,j)′. SinceI(i,j) is close to its predictive valueI(i,j)′,D(i,j) is small with a high probability. Consequently, the preprocessed pixelIp(i,j) can be calculated as follows:(3)Ipi,j=Ii,j+2r-1×Di,jwherer (r≥1) implies how many bits can be embedded in the pixel andr will be introduced in Section 2.2. Further, (3) can be rewritten as (4)Ipi,j=2r×Ii,j-2r-1×Ii,j′.Note thatIp(i,j) may cause underflow or overflow. To avoid this, a location mapL1 withH×W size is exploited to record the underflow or overflow pixels. Specifically, ifIp(i,j) >255 orIp(i,j)<0,L1(i,j)=1 andI(i,j) is kept unchanged. Otherwise,L1(i,j)=0 and we use (3) to calculateIp(i,j). LetF be the preprocessed image andF(i,j) (1 ≤i ≤H, 1 ≤j ≤W) be the pixel value in thei-th row andj-th column ofF. Thus,F(i,j) can be obtained as follows.(5)Fi,j=Ii,jCp>TorL1i,j=1ori,j∉Ω42r×Ii,j-2r-1×Ii,j′OtherwiseAfter the above calculation, the preprocessed imageF is generated.


### 2.1.2. Homomorphism Encryption

Homomorphic encryption is an efficient encryption technology with the useful property that computation on ciphertext is equivalent to the computation on its plaintext. Here, a homomorphic encryption method [39] by addition modulo 256 is used. Suppose thatm andc represent the plaintext and ciphertext. Thus, the homomorphic encryption and homomorphic decryption are described in (6) and (7), respectively,(6)c=Em,k=m+kmod256(7)m=Dc,k=c-kmod256wherek denotes encryption key andE(·,·) andD(·,·) are the encryption and decryption operations, respectively. An important property of the above encryption is the addition homomorphism in the plaintext domain. Letm1 andm2 be two different plain values whose corresponding random encryption keys arek1 andk2. Thus, we have the following equations:(8)Em1,k1⊕Em2,k2=Em1+m2,k1+k2mod256(9)DEm1,k1⊕Em2,k2,k1+k2=m1+m2mod256where ⊕ is modular 256 addition. Especially, ifk2 is equal to zero,m2 is considered as a given signal. Therefore, (8) and (9) can be rewritten as(10)Em1,k1⊕m2=Em1+m2,k1mod256(11)DEm1,k1⊕m2,k1=m1+m2mod256From (10) and (11), it can be found that addition operation can be done directly on the encrypted data without decryption.In this work, we exploit the RC4 [40] controlled by an encryption keyseed to generate a key matrixk(i,j) (1≤i≤H, 1≤j≤W), encryptF(i,j) with the corresponding keyk(i,j) by (6), and obtain the encrypted pixelC(i,j). After all pixels are processed, the encrypted imageC is then available.


## 2.1.1. Preprocessed Image Generation with Prediction

Predictors [35–38] are widely used in RDH algorithms for plaintext image. In this paper, we select an accurate gradient selective prediction (AGSP) predictor [38] to determine the original pixel predictions, which are used to construct preprocessed pixels. The reason of our selection of AGSP predictor is that it can reach a good balance between predictor performance and computational cost. The AGSP predictor operates on the nine neighboring pixels (i.e., x1,x2,x3,x4,x5,x6,x7,x8, andx9) of the current pixelx, as shown in Figure 1. The estimated gradients of four directions (i.e., horizontal, vertical, 45 degrees, and -45 degrees) are denoted byD1,D2,D3, andD4. The corresponding pixels of these gradientsD1,D2,D3, andD4 arex6,x9,x7, andx5, respectively. Suppose that Dmin1 and Dmin2 are two smallest gradients amongD1,D2,D3, andD4 and their corresponding pixels are Cmin1 and Cmin2. The prediction ofx can be calculated as follows:(1)x′=Dmin1×Cmin2+Dmin2×Cmin1Dmin1+Dmin2Figure 1
The currentx and its neighboring pixels.LetI be an 8-bit grayscale uncompressed original image withH×W size andI(i,j) be the pixel value in thei-th row andj-th column ofI, where 1 ≤i ≤H, 1 ≤j ≤W. As shown in Figure 2, the original imageI is divided into four regions denoted as Ω1, Ω2, Ω3, and Ω4, where Ω1 consists of all pixels used for embedding auxiliary information, Ω2 consists of unused pixels, Ω3 consists of pixels used for prediction, and Ω4 consists of pixels used for embedding secret data. The sizes of Ω1, Ω2, Ω3, and Ω4 will be described in Section 2.2. Those pixels of Ω1, Ω2, and Ω3 are kept unchanged in this stage. The pixels of Ω4 are scanned from left to right and top to down, as shown in Figure 2. For the pixelI(i,j) of Ω4, if it is located in a texture region, it may have a poor prediction. Here the local smoothness estimator is defined as the invariance denoted byCp(i,j), which is used to determine whetherI(i,j) is located in a smooth region or not. Consequently,Cp(i,j) can be determined as follows.(2)Cpi,j=Vmax-Vminwhere Vmax and Vmin are the maximum value and minimum value of the nine neighboring pixels ofI(i,j), respectively. IfCp(i,j) is not bigger than a predefined threshold T∈[0,255],I(i,j) and its neighboring pixels are highly correlative and it is considered as the pixel in smooth region. Otherwise,I(i,j) is viewed as the pixel in textural region. Note thatT should be determined in terms of image content. In general, a smallT value is good for smooth image and a bigT value is suitable for textural image.Figure 2
Different regions in the image.IfI(i,j) is located in a textural region,I(i,j) is kept unchanged. IfI(i,j) is located in a smooth region, we calculate the prediction ofI(i,j) using AGSP predictor and denote it asI(i,j)′. Therefore, the prediction-error can be calculated asD(i,j)=I(i,j) −I(i,j)′. SinceI(i,j) is close to its predictive valueI(i,j)′,D(i,j) is small with a high probability. Consequently, the preprocessed pixelIp(i,j) can be calculated as follows:(3)Ipi,j=Ii,j+2r-1×Di,jwherer (r≥1) implies how many bits can be embedded in the pixel andr will be introduced in Section 2.2. Further, (3) can be rewritten as (4)Ipi,j=2r×Ii,j-2r-1×Ii,j′.Note thatIp(i,j) may cause underflow or overflow. To avoid this, a location mapL1 withH×W size is exploited to record the underflow or overflow pixels. Specifically, ifIp(i,j) >255 orIp(i,j)<0,L1(i,j)=1 andI(i,j) is kept unchanged. Otherwise,L1(i,j)=0 and we use (3) to calculateIp(i,j). LetF be the preprocessed image andF(i,j) (1 ≤i ≤H, 1 ≤j ≤W) be the pixel value in thei-th row andj-th column ofF. Thus,F(i,j) can be obtained as follows.(5)Fi,j=Ii,jCp>TorL1i,j=1ori,j∉Ω42r×Ii,j-2r-1×Ii,j′OtherwiseAfter the above calculation, the preprocessed imageF is generated.


## 2.1.2. Homomorphism Encryption

Homomorphic encryption is an efficient encryption technology with the useful property that computation on ciphertext is equivalent to the computation on its plaintext. Here, a homomorphic encryption method [39] by addition modulo 256 is used. Suppose thatm andc represent the plaintext and ciphertext. Thus, the homomorphic encryption and homomorphic decryption are described in (6) and (7), respectively,(6)c=Em,k=m+kmod256(7)m=Dc,k=c-kmod256wherek denotes encryption key andE(·,·) andD(·,·) are the encryption and decryption operations, respectively. An important property of the above encryption is the addition homomorphism in the plaintext domain. Letm1 andm2 be two different plain values whose corresponding random encryption keys arek1 andk2. Thus, we have the following equations:(8)Em1,k1⊕Em2,k2=Em1+m2,k1+k2mod256(9)DEm1,k1⊕Em2,k2,k1+k2=m1+m2mod256where ⊕ is modular 256 addition. Especially, ifk2 is equal to zero,m2 is considered as a given signal. Therefore, (8) and (9) can be rewritten as(10)Em1,k1⊕m2=Em1+m2,k1mod256(11)DEm1,k1⊕m2,k1=m1+m2mod256From (10) and (11), it can be found that addition operation can be done directly on the encrypted data without decryption.In this work, we exploit the RC4 [40] controlled by an encryption keyseed to generate a key matrixk(i,j) (1≤i≤H, 1≤j≤W), encryptF(i,j) with the corresponding keyk(i,j) by (6), and obtain the encrypted pixelC(i,j). After all pixels are processed, the encrypted imageC is then available.


## 2.2. Data Embedding with Additive Homomorphism

Since the encrypted imageC is generated using homomorphic encryption, we can embed secret data according to the property of additive homomorphism. Firstly, we convert a binary secret message into a sequence of secret digits in 2r-ary notational system. Then, secret digits can be embedded into those pixels of the encrypted imageC in Ω4 except the marked pixels byL1. Let a secret digit bes (0 ≤s ≤2r−1). For a pixelC(i,j), ifCp(i,j)>T,C(i,j) is kept unchanged; i.e.,C(i,j)′=C(i,j). Otherwise, we use the key whose value is 0 to encrypts and embeds intoC(i,j) as follows.(12)Ci,j′=Ci,j⊕s=EFi,j+s,ki,jmod256Note that if (F(i,j) +s) ≥ 256, the decrypted result of (10) should be (F(i,j)+s) mod 256. To accurately recover the original image and extract secret data, those pixels satisfying (F(i,j) +s) ≥ 256 must be recorded. To do so, another location mapL2 is used here. Since 0 ≤s ≤ 2r−1, the location mapL2 records the pixels whose values are larger than or equal to 256 −s =256 − (2r−1). Therefore, ifF(i,j) ≥ 256−(2r−1),L2(i,j)=1 andC(i,j)′=C(i,j). Otherwise,L2(i,j)=0 ands is embedded according to (12). Moreover, secret bits are not embedded into those pixels marked byL1 andL2. Note that the location mapL1 is generated in the process of image encryption, while the location mapL2 is generated during data hiding. Both location maps should be embedded into the cover image. To reduce the size of data embedded, lossless compression with arithmetic coding is exploited to compress the location maps.To exactly extract the secret data and recover the original image, some auxiliary information must be embedded into the encrypted image, including the size of secret digits, capacity parameterr, the thresholdT, the sizes of two compressed location maps, and the two compressed location maps. As the size of secret digits is less than or equal to the number of pixels in the original image, log2HW bits are enough to record it, whereH andW are the height and width of the original image, respectively. Similarly, 2log2HW bits are enough to save the sizes of two compressed location maps. Although a largerr will bring higher embedding capacity, it will also degrade image quality according to (3). To balance the embedding capacity and image quality, ther value should be less than or equal to 7. Therefore, 3 bits can represent ther value. As the range ofT is [0,255], 8 bits can represent theT value. Let the size of compressed version ofL1 bel1 and the size of compressed version ofL2 bel2. Thus, the size of auxiliary information can be determined as follows.(13)tau=l1+l2+11+3log2⁡HWTable 1 presents the auxiliary information and their data sizes.Table 1
Auxiliary information and its sizes.
Auxiliary information Size (Bit) Size of secret digits log2HW Capacity parameterr 3 ThresholdT 8 Size of compressed version ofL1 log2HW Size of compressed version ofL2 log2HW Compressed version ofL1 l 1 Compressed version ofL2 l 2Here the auxiliary information is embedded into the 3 LSBs of the encrypted pixels inΩ1 by using LSB replacement technique. Note that secret data and the 3 LSBs of the encrypted pixels in Ω1 are firstly concatenated to construct the data for embedding into Ω4 in our algorithm. As the 3 LSBs of the used encrypted pixels in Ω1 are preserved in advance, they can be accurately recovered during image recovery.Clearly, the number of pixels inΩ1 is t1=tau/3, where · is the rounding function. The number of pixels in Ω2 is(14)t2=0tau3modW=0W-tau3modWOtherwise.The number of pixels in Ω3 ist3=2×W+3×(H − tau/3/W − 2). Let the total number of the pixels marked byL1 andL2 in Ω4 bet4. Thus, the maximum pure embedding capacity (EC) of our RDH algorithm can be calculated as follows.(15)EC=r×H×W-t1-t2-t3-t4-tauNote that the data hiding keys of our algorithm are ther value and theT value. In addition, the encrypted image containing secret data is called the marked encrypted image in the following sections.


## 2.3. Data Extraction and Image Recovery

When the receiver obtains a marked encrypted image, he/she can conduct different operations according to the knowledge of keys. If only the encryption key is available, he/she can decrypt the marked encrypted image to directly retrieve the decrypted image, which is approximate to the original image. If both the encryption key and data hiding key are known, he/she can extract secret data exactly and recover the original image without errors. In this case, auxiliary information is firstly extracted from the 3 LSBs of pixels inΩ1. Then, the two compressed location maps are decompressed to retrieve the location mapsL1 andL2. Next, we extract secret digits and recover the original pixels as follows.IfCi,j′∈Ω2 or Ci,j′∈Ω3 or Ci,j′∈Ω4 andL1(i,j)=1, we directly decrypt Ci,j′ withk(i,j) to recover the original pixelI(i,j) according to (7).IfCi,j′∈Ω4 andL1(i,j)=0, we can obtain a decrypted pixel Fi,j′ byk(i,j). Since the original pixels which belong to Ω2 or Ω3 have been recovered,Cp(i,j) can be calculated by AGSP predictor. IfCp(i,j) >T,I(i,j)=F(i,j)′. Otherwise,Cp(i,j) ≤T and secret digits are embedded by additive homomorphism. Clearly, ifL2(i,j)=0,F(i,j)′=F(i,j)+s. OtherwiseF(i,j)′=F(i,j). Clearly,I(i,j)=(F(i,j)+(2r−1)×I(i,j)′)/2r by (5), whereI(i,j)′ is the prediction which can be calculated by AGSP predictor. ForL2(i,j)=1, its original pixel can be determined byI(i,j) =(F(i,j)+(2r−1)×I(i,j)′)/2r =Fi,j′+2r-1×Ii,j′/2r, where · is the floor rounding operation. ForL2(i,j)=0, sinceF(i,j)′=F(i,j)+s, its original pixelI(i,j)=(F(i,j)′−s+(2r−1)×I(i,j)′)/2r=Fi,j′+2r-1×Ii,j′/2r-s/2r. As 0 ≤s ≤ 2r−1, s/2r is 0. Therefore,I(i,j)=Fi,j′+2r-1×Ii,j′/2r. Consequently, the original pixel can be uniformly rewritten as(16)Ii,j=Fi,j′+2r-1×Ii,j′2rMeanwhile, ifL2(i,j)=0,F(i,j)′=F(i,j)+s=2r×I(i,j) − (2r−1)×I(i,j)′+s. It is clear thatF(i,j)′-I(i,j)′=2r×(I(i,j)-I(i,j)′)+s. Then the secret digits can be extracted as follows.(17)s=Fi,j′-Ii,j′mod2rThe recovered pixelI(i,j) is used to recover the next pixel and extract the next secret digit. Consequently, the entire original pixels in Ω4 are recovered and all secret digits are extracted according to the above scheme. Then, the secret digits are converted into a sequence of binary data. Note that the binary data is constructed by secret bits and the 3 LSBs of the used pixels in Ω1. Consequently, the binary data is divided into two parts and the preserved 3 LSBs of the used pixels are used to replace the 3 LSBs of the corresponding pixels in Ω1. After that, the encrypted pixels in Ω1 are recovered and then they are decrypted to restore the original pixels. Finally, the original image is restored by the recovered pixels of the four regions.


## 3. Experimental Results

Many experiments are carried out to validate our performances. In the experiments, for a given embedding capacity, the thresholdT is varied from 0 to 255 until the embedding capacity is satisfied. Section 3.1 presents the performance of encryption, Section 3.2 discusses our embedding capacity and visual quality, and Section 3.3 analyzes comparisons with other RDH algorithms.


### 3.1. Encryption Performance

Eight images sized 512×512 as shown in Figure3 are used to test the perceptual security and the statistical security of the proposed encryption scheme. For space limitation, we encrypt eight images withr=1 to obtain the encrypted versions, as shown in Figure 4. Clearly, the encrypted images are meaningless images, and we cannot observe any useful details of the original images from Figure 5. This verifies that the proposed encryption scheme is effective.Figure 3
Eight test images.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyFigure 4
The encrypted images withr=1.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyFigure 5
The directly decrypted images withr=1.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyTo quantitatively measure the performance of the proposed encryption scheme, the objective metrics including entropy and correlation coefficient are used. The information entropy is an important measure of randomness, which is defined as follows.(18)HE=-∑i=0L-1Peilog2Pe2whereE={e0,e1, …, eL-1} andP(ei) is the possibility of occurrence ofei. In general, the bigger the entropy, the more secure the algorithm. For grayscale images,L=256 and the theoretical maximum value of entropy is 8. Table 2 presents the entropies of the encrypted images. It is found that all values are close to 8. This means that our encryption scheme is secure.Table 2
Results of entropy and correlation coefficient.
Image Entropy Correlation coefficient Lena 7.9992 −0.0003 Airplane 7.9993 0.0022 Barbara 7.9994 0.0005 Baboon 7.9993 −0.0026 Peppers 7.9993 0.0007 Boats 7.9994 −0.0002 Man 7.9993 0.0002 Tiffany 7.9993 0.0009Here, the well-known correlation coefficient is exploited to measure correlation among an image pair. It is defined as(19)ρXY=CovX,YDXDYwhereX andY denote the matrices of the original image and the encrypted image, respectively, Cov means the covariance, andD means the variance. Table 2 illustrates the correlation coefficients between the original images and the encrypted images. It can be seen that the correlation coefficients are all almost 0. This means that there is almost no correlation between the encrypted image and the original image, indicating security of our encryption scheme.


### 3.2. Embedding Capacity and Visual Quality

WhenT=255, all pixels except those marked pixels byL1 andL2 in Ω4 of the encrypted image can be used for data hiding. Obviously, the maximum pure embedding capacity of each image is determined by the parameterr, as shown in (12). Tables 3–6 list the pure embedding rate and PSNR of the directly decrypted images with differentr values. For space limitation, the directly decrypted images withr=1 are shown in Figures 5(a)–5(h). It is found that their visual qualities are satisfactory and their PSNR values are 30.6759, 32.3934, 28.458, 23.2063, 32.1131, 32.3676, 30.2753, and 30.7629. It can be also seen that there exists a maximum embedding rate for each image. In Tables 3–6, the texts in bold are the maximum embedding rates of the test images. For Lena, Airplane, Barbara, Baboon, Peppers, Boats, Man, and Tiffany, their maximum pure embedding rates are 1.947, 1.8433, 1.452, 1.002, 1.5292, 1.8122, 1.6755, and 1.7007 bpp whenr=3,r=3,r=2,r=2,r=3,r=3,r=2, andr=3, respectively. Figure 6 presents the embedding rate of different test images under differentr values. Asr increases, the embedding rate also increases and reaches maximum value whenr=2 orr=3. A biggerr means more pixels marked byL1 andL2 and then more auxiliary information should be recorded, which will decrease the pure embedding rate. In addition, the embedding rate and visual quality are both closely related to image contents. It is observed that smooth images will generally have bigger embedding rate and better visual quality than the textural images. That is the reason why the EC and PSNR of Barbara and Baboon are smaller than those of other test images.Table 3
Embedding rates and PSNR of the directly decrypted images withr=1.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  10410 10042 9587 27066 20310 10721 11374 23430 t 1  3470 3347 3196 9022 6770 3574 3791 7810 t 2  114 237 388 194 398 10 305 382 t 3  2533 2533 2536 2500 2515 2533 2533 2509 t 4  1093 1099 1308 3041 2209 1099 1162 2615 EC bit 244524 254928 254716 247387 250252 254928 254353 248828 bpp 0.9725 0.9724 0.9716 0.9437 0.9546 0.9724 0.9702 0.9492 PSNR(dB)  30.6759 32.3934 28.458 23.2063 32.1131 32.3676 30.2753 30.7629Table 4
Embedding rates and PSNR of the directly decrypted images withr=2.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  37311 46145 68543 114244 62886 38897 38894 52038 t 1  12437 15382 22848 38081 20962 12966 12965 17346 t 2  363 490 192 319 30 346 347 62 t 3  2482 2464 2419 2332 2431 2479 2479 2452 t 4  4728 5897 12091 32900 10396 5232 7294 7774 EC bit 446957 429677 380645 262780 393764 443345 439224 416982 bpp 1.705 1.6391 1.452 1.002 1.5021 1.6912 1.6755 1.5907 PSNR(dB)  23.78 23.4564 20.4752 16.9237 23.1429 23.3794 21.8245 21.6842Table 5
Embedding rates and PSNR of the directly decrypted images withr=3.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  105911 115441 151522 246246 145015 119466 133242 129437 t 1  35304 38480 50507 82082 48338 39822 44414 43146 t 2  24 432 181 350 302 114 130 374 t 3  2347 2329 2257 2074 2272 2320 2293 2302 t 4  19058 21356 41230 87028 29270 21717 26726 24569 EC bit 510394 483200 352385 25584 400871 475047 432504 445822 bpp 1.947 1.8433 1.3442 0.0975 1.5292 1.8122 1.6499 1.7007 PSNR(dB)  18.1015 18.5971 17.0775 14.771 17.3412 18.2071 17.295 16.6696Table 6
Embedding rates and PSNR of the directly decrypted images withr=4.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  222009 249026 - - 274612 224970 - 267648 t 1  74003 83009 - - 91537 74990 - 89216 t 2  237 447 - - 111 274 - 384 t 3  2119 2068 - - 2017 2116 - 2032 t 4  55427 64158 - - 73374 59165 - 72876 EC bit 299423 200822 - - 105808 277426 - 122896 bpp 1.1422 0.766 - - 0.404 1.0583 - 0.469 PSNR(dB)  14.0578 14.0551 - - 13.638 15.1664 - 13.8975Figure 6
Embedding rates of different test images under differentr values.Table7 lists the PSNRs of the eight decrypted images containing embedded data under different embedding rates whenr=1. Clearly, a high embedding rate will lead to a low PSNR. This is because more secret bits embedded will introduce more distortions on the encrypted images. Moreover, the PSNRs of the textural image Baboon are smaller than those of other test images. The reason is that the used prediction in our RDH algorithm is more effective in smooth images than textural images.Table 7
PSNRs under different embedding rates whenr=1 (dB).
Image Embedding rate (bpp) 0.005 0.01 0.05 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Lena 63.55 60.55 58.03 50.38 46.88 44.61 42.73 40.74 37.96 35.14 33.98 31.56 Airplane 68.39 63.24 59.90 55.56 51.54 48.99 46.47 45.21 43.07 40.92 38.18 34.73 Barbara 63.82 60.82 53.58 50.26 46.88 44.61 42.64 40.74 37.55 34.60 32.01 29.81 Baboon 58.10 54.46 46.11 42.87 38.32 35.39 32.70 30.08 28.14 26.22 24.80 23.63 Peppers 65.12 61.66 51.96 48.22 44.20 41.76 40.30 38.59 37.50 36.39 35.08 33.58 Boats 65.18 62.25 54.98 51.69 48.48 46.44 44.74 42.98 40.69 38.53 36.16 34.12 Man 68.89 65.29 55.76 50.89 46.94 43.54 41.40 39.38 37.54 35.66 33.88 31.96 Tiffany 63.64 61.11 50.40 48.17 43.46 41.44 39.75 38.43 37.05 35.59 33.92 32.06 Average 64.59 61.17 53.84 49.76 46.33 43.35 41.34 39.52 37.44 35.38 33.50 31.43


### 3.3. Performance Comparisons

In this section, we compare the proposed algorithm with some recent popular RDH algorithms [22, 26, 27, 30, 31]. Figure 7 is the PSNR comparison among the assessed algorithms under different test images whenr=1. It is observed that the PSNRs of the proposed algorithm are bigger than those of the compared algorithms [26, 27, 30] under any embedding rate for all test images. The RDH algorithm reported in [27] has lower performance than other algorithms due to the fact that it embeds several bits into hundreds of pixels. When the embedding rate is small, the PSNRs of the proposed algorithm are not always bigger than those of the compared algorithms [22, 31]. However, when the embedding rate is big, such as 0.8 and 0.9, the proposed algorithm will reach good performance. Specifically, for Lena, Peppers, and Tiffany, the PSNRs of the proposed algorithm are bigger than those of [22] when the embedding rate is bigger than 0.4 bpp. For Barbara, Baboon, Boats, and Man, the PSNRs of the proposed algorithm are bigger than those of [22] when the embedding rate exceeds 0.2 bpp. Moreover, the PSNRs of the proposed algorithm are bigger than those of [31] for all test images except Lena and Baboon.Figure 7
PSNR comparison under different test images.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyComparisons of the average PSNR of the eight test images among different algorithms are shown in Figure8. Clearly, our average PSNRs are all bigger than those of the compared algorithms [26, 27, 30, 31] under different embedding rates. Our average PSNRs are all bigger than those of the compared algorithm [22] when the embedding rate is bigger than 0.2 bpp. Our proposed algorithm has better performance than the compared algorithms in terms of PSNR. This is contributed by our efficient strategies as follows. Firstly, during preprocessing image generation, image pixels are classified into four regions, i.e., Ω1, Ω2, Ω3, and Ω4, and only those pixels in Ω1 and Ω4 will be changed and the pixels in Ω2 and Ω3 are kept unchanged. It is clear that fewer pixels changed will lead to better visual quality. Secondly, for those pixels in Ω4, data embedding is conducted by additive homomorphism, i.e., adding a numbers smaller than 2r to pixel, which will not greatly change the pixel value. For example, ifr=1,s is 0 or 1. Ifr=2,s may be 0, 1, 2, or 3. Thirdly, the location maps are compressed by arithmetic coding. This operation can reduce the amount of auxiliary information. Finally, auxiliary information is embedded into those pixels in Ω1 by the LSB replacement technique, which introduces slight distortion on the image.Figure 8
Average PSNR comparison under different embedding rates.Moreover, the RDH algorithm [22] is not secure enough. In this algorithm, the users include image provider, data-hider, and receiver. The image provider encrypts input image by block permutation and stream encipher, where the block permutation only scrambles pixel positions and does not change pixel value. This means that the histogram of the original image is preserved after block permutation. During data embedding, data-hider must firstly decrypt the encrypted image by stream decipher (a reverse process of stream encipher), then conducts data embedding, and finally performs stream encipher again. In practice, image provider and data-hider are different persons, and the image provider will generally expect that anyone including the data-hider cannot observe any information of the encrypted image. However, as data-hider can decrypt encrypted image by stream decipher, he/she can obtain a scrambled image whose histogram is the same as the original image. Consequently, he/she can further exploit those histogram-based image hashing algorithms [41, 42] to retrieve the original image of the scrambled image. This is a security loophole. For the proposed algorithm and other compared algorithms, image decryption is not needed during data embedding, and therefore there is no such security issue.Computational time of the assessed algorithms is also compared. All RDH algorithms are coded in MATLAB R2011a and run on a computer with an Intel i5 CPU with 3.40 GHz, 4.00 GB memory, and Windows 10 operating system. Table8 lists the running time of different algorithms under the different images. Note that the running time consists of image encryption, data embedding, image decryption, and secret extraction and image recovery for all the algorithms. From Table 8, it is found that the algorithm reported in [27] has the fastest speed and the algorithm reported in [30] has the lowest speed. The algorithm reported in [30] is time-consuming. This is due to the high complexity of Paillier encryption adopted in the algorithm [30]. The proposed algorithm and the algorithm in [26] have similar running time performances, which are both better than those of [22, 31].Table 8
Running time of the assessed algorithms (unit: second).
Algorithm Lena Airplane Barbara Baboon Peppers Boats Man Tiffany [22] 7.2546 6.1648 6.5787 8.9654 8.5644 6.2354 9.5578 7.2021 [26] 5.1344 4.2354 4.5441 5.6214 3.9241 5.6346 4.2364 5.3214  [27] 2.3547 2.1245 2.6544 2.4030 2.6456 2.2211 2.7895 2.5642 [30] 663.1231 664.145 665.1244 663.8789 664.564 665.2365 663.987 663.658 [31] 10.1244 9.2678 9.8641 10.9874 9.43241 10.2445 10.89741 9.3356 Proposed 5.3245 5.2345 5.5644 4.8645 4.6878 4.2156 4.3265 5.2364


## 3.1. Encryption Performance

Eight images sized 512×512 as shown in Figure3 are used to test the perceptual security and the statistical security of the proposed encryption scheme. For space limitation, we encrypt eight images withr=1 to obtain the encrypted versions, as shown in Figure 4. Clearly, the encrypted images are meaningless images, and we cannot observe any useful details of the original images from Figure 5. This verifies that the proposed encryption scheme is effective.Figure 3
Eight test images.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyFigure 4
The encrypted images withr=1.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyFigure 5
The directly decrypted images withr=1.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyTo quantitatively measure the performance of the proposed encryption scheme, the objective metrics including entropy and correlation coefficient are used. The information entropy is an important measure of randomness, which is defined as follows.(18)HE=-∑i=0L-1Peilog2Pe2whereE={e0,e1, …, eL-1} andP(ei) is the possibility of occurrence ofei. In general, the bigger the entropy, the more secure the algorithm. For grayscale images,L=256 and the theoretical maximum value of entropy is 8. Table 2 presents the entropies of the encrypted images. It is found that all values are close to 8. This means that our encryption scheme is secure.Table 2
Results of entropy and correlation coefficient.
Image Entropy Correlation coefficient Lena 7.9992 −0.0003 Airplane 7.9993 0.0022 Barbara 7.9994 0.0005 Baboon 7.9993 −0.0026 Peppers 7.9993 0.0007 Boats 7.9994 −0.0002 Man 7.9993 0.0002 Tiffany 7.9993 0.0009Here, the well-known correlation coefficient is exploited to measure correlation among an image pair. It is defined as(19)ρXY=CovX,YDXDYwhereX andY denote the matrices of the original image and the encrypted image, respectively, Cov means the covariance, andD means the variance. Table 2 illustrates the correlation coefficients between the original images and the encrypted images. It can be seen that the correlation coefficients are all almost 0. This means that there is almost no correlation between the encrypted image and the original image, indicating security of our encryption scheme.


## 3.2. Embedding Capacity and Visual Quality

WhenT=255, all pixels except those marked pixels byL1 andL2 in Ω4 of the encrypted image can be used for data hiding. Obviously, the maximum pure embedding capacity of each image is determined by the parameterr, as shown in (12). Tables 3–6 list the pure embedding rate and PSNR of the directly decrypted images with differentr values. For space limitation, the directly decrypted images withr=1 are shown in Figures 5(a)–5(h). It is found that their visual qualities are satisfactory and their PSNR values are 30.6759, 32.3934, 28.458, 23.2063, 32.1131, 32.3676, 30.2753, and 30.7629. It can be also seen that there exists a maximum embedding rate for each image. In Tables 3–6, the texts in bold are the maximum embedding rates of the test images. For Lena, Airplane, Barbara, Baboon, Peppers, Boats, Man, and Tiffany, their maximum pure embedding rates are 1.947, 1.8433, 1.452, 1.002, 1.5292, 1.8122, 1.6755, and 1.7007 bpp whenr=3,r=3,r=2,r=2,r=3,r=3,r=2, andr=3, respectively. Figure 6 presents the embedding rate of different test images under differentr values. Asr increases, the embedding rate also increases and reaches maximum value whenr=2 orr=3. A biggerr means more pixels marked byL1 andL2 and then more auxiliary information should be recorded, which will decrease the pure embedding rate. In addition, the embedding rate and visual quality are both closely related to image contents. It is observed that smooth images will generally have bigger embedding rate and better visual quality than the textural images. That is the reason why the EC and PSNR of Barbara and Baboon are smaller than those of other test images.Table 3
Embedding rates and PSNR of the directly decrypted images withr=1.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  10410 10042 9587 27066 20310 10721 11374 23430 t 1  3470 3347 3196 9022 6770 3574 3791 7810 t 2  114 237 388 194 398 10 305 382 t 3  2533 2533 2536 2500 2515 2533 2533 2509 t 4  1093 1099 1308 3041 2209 1099 1162 2615 EC bit 244524 254928 254716 247387 250252 254928 254353 248828 bpp 0.9725 0.9724 0.9716 0.9437 0.9546 0.9724 0.9702 0.9492 PSNR(dB)  30.6759 32.3934 28.458 23.2063 32.1131 32.3676 30.2753 30.7629Table 4
Embedding rates and PSNR of the directly decrypted images withr=2.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  37311 46145 68543 114244 62886 38897 38894 52038 t 1  12437 15382 22848 38081 20962 12966 12965 17346 t 2  363 490 192 319 30 346 347 62 t 3  2482 2464 2419 2332 2431 2479 2479 2452 t 4  4728 5897 12091 32900 10396 5232 7294 7774 EC bit 446957 429677 380645 262780 393764 443345 439224 416982 bpp 1.705 1.6391 1.452 1.002 1.5021 1.6912 1.6755 1.5907 PSNR(dB)  23.78 23.4564 20.4752 16.9237 23.1429 23.3794 21.8245 21.6842Table 5
Embedding rates and PSNR of the directly decrypted images withr=3.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  105911 115441 151522 246246 145015 119466 133242 129437 t 1  35304 38480 50507 82082 48338 39822 44414 43146 t 2  24 432 181 350 302 114 130 374 t 3  2347 2329 2257 2074 2272 2320 2293 2302 t 4  19058 21356 41230 87028 29270 21717 26726 24569 EC bit 510394 483200 352385 25584 400871 475047 432504 445822 bpp 1.947 1.8433 1.3442 0.0975 1.5292 1.8122 1.6499 1.7007 PSNR(dB)  18.1015 18.5971 17.0775 14.771 17.3412 18.2071 17.295 16.6696Table 6
Embedding rates and PSNR of the directly decrypted images withr=4.
Image  Lena Airplane Barbara Baboon Peppers Boats Man Tiffany t au  222009 249026 - - 274612 224970 - 267648 t 1  74003 83009 - - 91537 74990 - 89216 t 2  237 447 - - 111 274 - 384 t 3  2119 2068 - - 2017 2116 - 2032 t 4  55427 64158 - - 73374 59165 - 72876 EC bit 299423 200822 - - 105808 277426 - 122896 bpp 1.1422 0.766 - - 0.404 1.0583 - 0.469 PSNR(dB)  14.0578 14.0551 - - 13.638 15.1664 - 13.8975Figure 6
Embedding rates of different test images under differentr values.Table7 lists the PSNRs of the eight decrypted images containing embedded data under different embedding rates whenr=1. Clearly, a high embedding rate will lead to a low PSNR. This is because more secret bits embedded will introduce more distortions on the encrypted images. Moreover, the PSNRs of the textural image Baboon are smaller than those of other test images. The reason is that the used prediction in our RDH algorithm is more effective in smooth images than textural images.Table 7
PSNRs under different embedding rates whenr=1 (dB).
Image Embedding rate (bpp) 0.005 0.01 0.05 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Lena 63.55 60.55 58.03 50.38 46.88 44.61 42.73 40.74 37.96 35.14 33.98 31.56 Airplane 68.39 63.24 59.90 55.56 51.54 48.99 46.47 45.21 43.07 40.92 38.18 34.73 Barbara 63.82 60.82 53.58 50.26 46.88 44.61 42.64 40.74 37.55 34.60 32.01 29.81 Baboon 58.10 54.46 46.11 42.87 38.32 35.39 32.70 30.08 28.14 26.22 24.80 23.63 Peppers 65.12 61.66 51.96 48.22 44.20 41.76 40.30 38.59 37.50 36.39 35.08 33.58 Boats 65.18 62.25 54.98 51.69 48.48 46.44 44.74 42.98 40.69 38.53 36.16 34.12 Man 68.89 65.29 55.76 50.89 46.94 43.54 41.40 39.38 37.54 35.66 33.88 31.96 Tiffany 63.64 61.11 50.40 48.17 43.46 41.44 39.75 38.43 37.05 35.59 33.92 32.06 Average 64.59 61.17 53.84 49.76 46.33 43.35 41.34 39.52 37.44 35.38 33.50 31.43


## 3.3. Performance Comparisons

In this section, we compare the proposed algorithm with some recent popular RDH algorithms [22, 26, 27, 30, 31]. Figure 7 is the PSNR comparison among the assessed algorithms under different test images whenr=1. It is observed that the PSNRs of the proposed algorithm are bigger than those of the compared algorithms [26, 27, 30] under any embedding rate for all test images. The RDH algorithm reported in [27] has lower performance than other algorithms due to the fact that it embeds several bits into hundreds of pixels. When the embedding rate is small, the PSNRs of the proposed algorithm are not always bigger than those of the compared algorithms [22, 31]. However, when the embedding rate is big, such as 0.8 and 0.9, the proposed algorithm will reach good performance. Specifically, for Lena, Peppers, and Tiffany, the PSNRs of the proposed algorithm are bigger than those of [22] when the embedding rate is bigger than 0.4 bpp. For Barbara, Baboon, Boats, and Man, the PSNRs of the proposed algorithm are bigger than those of [22] when the embedding rate exceeds 0.2 bpp. Moreover, the PSNRs of the proposed algorithm are bigger than those of [31] for all test images except Lena and Baboon.Figure 7
PSNR comparison under different test images.
(a)
Lena (b)
Airplane (c)
Barbara (d)
Baboon (e)
Peppers (f)
Boats (g)
Man (h)
TiffanyComparisons of the average PSNR of the eight test images among different algorithms are shown in Figure8. Clearly, our average PSNRs are all bigger than those of the compared algorithms [26, 27, 30, 31] under different embedding rates. Our average PSNRs are all bigger than those of the compared algorithm [22] when the embedding rate is bigger than 0.2 bpp. Our proposed algorithm has better performance than the compared algorithms in terms of PSNR. This is contributed by our efficient strategies as follows. Firstly, during preprocessing image generation, image pixels are classified into four regions, i.e., Ω1, Ω2, Ω3, and Ω4, and only those pixels in Ω1 and Ω4 will be changed and the pixels in Ω2 and Ω3 are kept unchanged. It is clear that fewer pixels changed will lead to better visual quality. Secondly, for those pixels in Ω4, data embedding is conducted by additive homomorphism, i.e., adding a numbers smaller than 2r to pixel, which will not greatly change the pixel value. For example, ifr=1,s is 0 or 1. Ifr=2,s may be 0, 1, 2, or 3. Thirdly, the location maps are compressed by arithmetic coding. This operation can reduce the amount of auxiliary information. Finally, auxiliary information is embedded into those pixels in Ω1 by the LSB replacement technique, which introduces slight distortion on the image.Figure 8
Average PSNR comparison under different embedding rates.Moreover, the RDH algorithm [22] is not secure enough. In this algorithm, the users include image provider, data-hider, and receiver. The image provider encrypts input image by block permutation and stream encipher, where the block permutation only scrambles pixel positions and does not change pixel value. This means that the histogram of the original image is preserved after block permutation. During data embedding, data-hider must firstly decrypt the encrypted image by stream decipher (a reverse process of stream encipher), then conducts data embedding, and finally performs stream encipher again. In practice, image provider and data-hider are different persons, and the image provider will generally expect that anyone including the data-hider cannot observe any information of the encrypted image. However, as data-hider can decrypt encrypted image by stream decipher, he/she can obtain a scrambled image whose histogram is the same as the original image. Consequently, he/she can further exploit those histogram-based image hashing algorithms [41, 42] to retrieve the original image of the scrambled image. This is a security loophole. For the proposed algorithm and other compared algorithms, image decryption is not needed during data embedding, and therefore there is no such security issue.Computational time of the assessed algorithms is also compared. All RDH algorithms are coded in MATLAB R2011a and run on a computer with an Intel i5 CPU with 3.40 GHz, 4.00 GB memory, and Windows 10 operating system. Table8 lists the running time of different algorithms under the different images. Note that the running time consists of image encryption, data embedding, image decryption, and secret extraction and image recovery for all the algorithms. From Table 8, it is found that the algorithm reported in [27] has the fastest speed and the algorithm reported in [30] has the lowest speed. The algorithm reported in [30] is time-consuming. This is due to the high complexity of Paillier encryption adopted in the algorithm [30]. The proposed algorithm and the algorithm in [26] have similar running time performances, which are both better than those of [22, 31].Table 8
Running time of the assessed algorithms (unit: second).
Algorithm Lena Airplane Barbara Baboon Peppers Boats Man Tiffany [22] 7.2546 6.1648 6.5787 8.9654 8.5644 6.2354 9.5578 7.2021 [26] 5.1344 4.2354 4.5441 5.6214 3.9241 5.6346 4.2364 5.3214  [27] 2.3547 2.1245 2.6544 2.4030 2.6456 2.2211 2.7895 2.5642 [30] 663.1231 664.145 665.1244 663.8789 664.564 665.2365 663.987 663.658 [31] 10.1244 9.2678 9.8641 10.9874 9.43241 10.2445 10.89741 9.3356 Proposed 5.3245 5.2345 5.5644 4.8645 4.6878 4.2156 4.3265 5.2364


## 4. Conclusions

In this paper, a reversible data hiding with pixel prediction and additive homomorphism for encrypted image has been proposed. The proposed algorithm constructs a preprocessed image from the original image by using pixel prediction before encryption, then encrypts the preprocessed image by additive homomorphism, and embeds secret data into the encrypted image via modular 256 addition. The proposed algorithm uses homomorphic encryption, but it does not lead to data expansion. Experimental results have demonstrated that the proposed algorithm can accurately recover original image and reach high embedding capacity and good visual quality. Comparisons have shown that the proposed algorithm outperforms some recent RDH algorithms in embedding capacity and visual quality.



---

*Source: 9103418-2018-09-04.xml*