High-capacity reversible data hiding in encrypted images based on two-phase histogram shifting

1.   Introduction

Due to the extensive use of digital image, several technologies have been developed to protect the copyright and the integrity of the digital images, including image hashing ^[1] and data hiding. Data hiding is a technology that embeds additional information imperceptibly into the host media of various formats ^[2,3,4]. The embedded data can be extracted in a particular way for authentication or other purposes.

Reversible data hiding (RDH) is a sort of data hiding technology that makes it possible to reverse the embedding of the secret data, and the host media can be recovered after the data have been embedded. Recently, many RDH methods, such as difference expansion ^[5,6,7], histogram shifting ^[8,9,10], and pixel value ordering ^[11,12,13], have been developed for reversibly hiding data in plaintext images. By using the redundancy and spatial correlation, these methods can embed additional information into plaintext images with fully reversibility. For the encrypted image, the redundancy and spatial correlation are lost. So the plaintext image-based methods cannot be used in the encrypted domain.

With the development of cloud services, RDH in encrypted images (RDHEI) has been valued. Since cloud services are used extensively now in many different applications, continually increasing quantities of data are being stored and processed in the cloud instead of in the content owners' terminals. For privacy, the content owner always provides encrypted images instead of plaintext images. Therefore, it is a problem for the cloud service provider to process the encrypted image for reversible data hiding when the content of the image cannot be accessed.

To date, researchers have proposed several RDHEI methods that use different ways to embed additional data reversibly in the encrypted domain. Some methods perform bit flipping on the bit-wise encrypted image to embed additional data. To extract the embedded data and recover the image, the flipped bits are detected in the decrypted image depending on the spatial correlation in the decrypted domain. In ^[14], a 3-LSB (least significant bit) flipping scheme was designed to embed one additional bit into one block of the encrypted image. After decrypting the image, the flipped pixels in each block were detected by a designed smoothness estimator so the embedded bits could be extracted and the image could be recovered. The improved methods of ^[14] were proposed to be used in ^[15,16,17]. In ^[15], a side-match technology was used jointly with the smoothness estimator to enhance the reversibility. In ^[16], to improve the accuracy of image recovery, the author used a more precise block-smoothness estimator, and the blocks were recovered in descending order of their smoothness. In ^[17], the way in which data were embedded was improved for high visual quality, and an image content-based estimator was used to extract the data and recover the image. In ^[18], the encrypted image was divided randomly into same-size groups, and one additional bit was hidden in one group by flipping one bit of each pixel of the group. After the decryption of the image, the flipped pixels were detected by using prediction error.

Some methods use compression of the images to make additional room available in the encrypted image to accommodate the secret data. In ^[19], a matrix compression scheme was used to compress the LSBs of the encrypted image to accommodate additional data. In ^[20], the encrypted image was decomposed into blocks, and the blocks were classified as smooth blocks or complex blocks. A compression matrix was used to compress the LSBs of the smooth blocks to accommodate secret bits. In ^[21], according to the compression effect, one of the two compression schemes, which were a run-length coding scheme and a matrix compression scheme, was chosen to compress the blocks of the encrypted image respectively. In ^[22], by using the LDPC code for compression, the additional data can be placed in the fourth LSBs of the encrypted image. In ^[23], the MSBs of the encrypted image was encoded by using LDPC code to place additional bits.

Some methods partially maintain the spatial correlation in encrypted images by using a customized encryption schemes, e.g., the traditional RDH schemes, such as histogram shifting (HF) and pixel value ordering (PVO). In ^[24], the encrypted image was decomposed into cross blocks, and pixels in the same cross block were encrypted with the same encryption key by using the additive hormomorphic cryptosystem. Based on the encrypted cross blocks, the difference histogram was generated and a designed histogram shifting scheme was used for data embedding. In ^[25] and ^[26], the original images were encrypted at the level of $2 \times 2$ blocks. In ^[25], the additional data can be embedded into blocks by using an extended PVO scheme. In ^[26], a set of prediction errors is generated by using a block-level predictor, and an extended prediction error expansion scheme was designed to embed secret data.

In this paper, we propose a new RDHEI method that uses two-phase histogram shifting. By using a designed image division strategy and the RC4 cryptosystem, the method partially maintains the spatial correlation in the encrypted image. To achieve high embedding capacity, the process of data embedding consists of two embedding phases. In each embedding phase, a difference histogram can be obtained from the encrypted image; then, a designed histogram shifting scheme is used for data embedding based on the difference histogram. In summary, the merits of this paper are:

(1) Based on the division of the image and shifting the two-phase histogram, the proposed method can provide a high capacity for data embedding.

(2) The recovery of the image and the extraction of data can be performed in the encrypted domain or in the decrypted domain.

(3) The recovery of the image and the extraction of data are error-free.

The rest of the paper is organized as follows. In Section Ⅱ, the homomorphic cryptosystem and Li et al.'s method are described in detail. In Section Ⅲ, the proposed method is introduced. Section Ⅳ presents the experimental results and comparisons, Section 5 gives the conclusion of this paper.

2.   Related work

2.1.   Homomorphic cryptosystem

In 1978, Rivest et al. introduced the idea of hormomorphic encryption ^[27], and it commonly is defined as follows. If m₁ and m₂ are two words in the set of the plaintexts, for the encryption function E and any given encryption key, there is:

where ${ \odot _P}$ is a certain operator for plaintexts ${m_1}$ and ${m_2}$, ${ \odot _E}$ is a certain operator for ciphertexts $E({m_1})$ and $E({m_2})$, and $\leftarrow$ is "directly calculated from." By using the homomorphism, some special calculations can be performed on encrypted data without decryption.

The stream cipher RC4 is one of the well-known ciphers that are used for additive homomorphic encryption. If m and c denote the plaintext and the ciphertext, respectively, and k denotes the pseudo-random encryption key generated from a secret seed by using RC4, the encryption and decryption are performed as follows:

where n is a preset modulus. The encryption in Eq. (2) has the property of additive homomorphism. Noting that m₁ and m₂ are two plain values and that k₁ and k₂ are two corresponding encryption keys, then:

According to Eqs. (6) and (7), by using the property of homomorphism, the modular n addition operation can be performed on the encrypted data to modify the plain data without decryption.

2.2.   Li et al.'s method

Li et al. proposed an RDHEI method using cross division and additive homomorphism ^[24]. Due to additive homomorphism, data extraction can be performed in both the encrypted domain and the decrypted domain.

2.2.1.   Cross division and encryption ^[24]

Before encryption, cross division is used to divide the original image into cross-blocks. Each cross block consists of a 'central pixel' and all of the pixels that are adjacent to the central pixel. For an image, I, sized $M \times N$, the (x, y) coordinates of the central pixels are defined as:

Figure 1 shows an example of cross division. The black pixels are the central pixels of the cross-blocks, and the white pixels adjacent to the central pixels belong to the same cross-blocks. The gray pixels do not belong to any cross-block.

To encrypt the image I, the RC4 stream cipher is used to generate an encrypted matrix, K, with the size of $M \times N$. The encryption scheme is described as:

To keep the same difference between the neighboring pixels in the cross blocks, the encrypted matrix K is generated as follows: if ${p_{i1, j1}}$ and ${p_{i2, j2}}$ belong to the same cross-block, they should be encrypted by the same key, i.e., ${k_{i1, j1}} = {k_{i2, j2}}$.

2.2.2.   Data embedding of ^[24]

When the data hider receives the encrypted image, a difference histogram is generated from all of the cross-blocks of the encrypted image. For each cross-block with the encrypted central pixel ${e_{i, j}}$, the differences of the cross-block are generated as follows:

Note that the four differences are identical to the difference generated from the plain image. For example, ${d_{i - 1, j}}$ is computed from ${e_{i - 1, j}}$ and ${e_{i, j}}$, where ${e_{i - 1, j}} = ({p_{i - 1, j}} + {k_{i - 1, j}})\bmod256$, ${e_{i, j}} = ({p_{i, j}} + {k_{i, j}})\bmod256$, and ${k_{i - 1, j}} = {k_{i, j}}$, we have

Due to the spatial correlation, the neighboring pixels are likely to be similar. Therefore, most of the differences are close to 0 and 255.

After the differences of all of the cross-blocks were generated, the difference histogram was formed from all of the differences. Figure 2 shows an example of the difference histogram of the encrypted image, Lena (Figure 8(d)). The figure shows that most of the differences were close to the two sides.

Based on the difference histogram, a variant histogram shifting scheme is used for data embedding. The variant histogram shifting scheme shifts the bins from the two side to the middle (bin 127 and bin 128) to vacate room for embedding. The procedure of data embedding is given as follows:

Step 1: Shift bins 1–126 one step to their right neighboring bins, i.e., bin 1 is shifted to bin 2, bin 2 is shifted to bin 3, …, bin 126 is shifted to bin 127. The bins are shifted by performing modular 256 addition on the corresponding encrypted pixels. For example, if ${d_{i - 1, j}} = 1$ is one element of bin 1, ${d_{i - 1, j}}$ can be shifted to bin 2 as follows:

That is, the shifting can be performed by modifying ${e_{i - 1, j}}$ to $({e_{i - 1, j}} + 1)\bmod256$.

Then, bins 129–254 are shifted one step to the left neighboring bins, i.e., 128–253. The bins are shifted by performing modular 256 subtraction on the corresponding encrypted pixels. The processing is similar to the shifting of bins 1-126. For example, to shift the element ${d_{i - 1, j}} = 254$ to bin 253, ${e_{i - 1, j}}$ is modified to $({e_{i - 1, j}} - 1)\bmod 256$.

Step 2: A boundary map is generated to distinguish the new elements from the original elements in bins 127 and 128. The boundary map is a binary sequence. For all encrypted pixels that correspond to the elements in bins 127 and 128, the original pixels are denoted by 0 and the modified pixels are denoted by 1 in the boundary map.

Step 3: After Steps 1 and 2, bins 1 and 254 are empty. Then, bins 0 and 255 can be used for embeddding data. The length of the secret data is embedded first, and, then, the secret data and the boundary map are embedded. To embed a bit 1, the element in bin 0 is shifted to bin 1, or the element in bin 255 is shifted to bin 254. To embed a bit 0, do nothing. The processing of element shifting is the same as that in Step 1.

Step 4: Steps 1–3 can be performed many times until all of the secret data have been embedded. In the second round, bins 3–126 are shifted step to the right to bins 4–127, and bins 129–252 are shifted one step to the left to bins 128–251. Then, bin 2 and bin 253 are used for embedding data. In the third round, bins 5–126 and bins 129–250 are shifted, and bins 4 and 251 are used for embedding data. The boundary map should be generated and embedded in each round.

2.2.3.   Data extraction and image recovery ^[24]

When the receiver obtains the marked encrypted image, data extraction and image recovery can be performed in two ways: (1) Extract the secret data and recover the image in the encrypted domain; then, decrypt the encrypted image; (2) Perform image decryption first, then extract the embedded data and recover the image in the decrypted domain.

(1) Processing in the encrypted domain: Since the generation of the difference histogram and embedding data are processed directly on the encrypted image, data extraction and image recovery can be performed directly in the encrypted domain as follows:

Step 1: Generate the difference histogram from the marked encrypted image.

Step 2: Extract the length of the secret data from the elements in bin 0 and bin 255.

Step 3: Compute the round number according to the length of the secret data and the bins of the difference histogram.

Step 4: The reverse processing of data embedding is performed from the last round to the first round. In each round, first, the boundary map and the embedded data of the round are extracted, and the two bins used for embedding data are recovered; then, with the aid of the boundary map, the shifted bins are recovered to their initial positions in this round.

Step 5: Reorder all of the extracted data to obtain the secret data, and decrypt the recovered encrypted image to obtain the original image.

(2) Processing in the decrypted domain: The marked encrypted image can be directly decrypted to a marked decrypted image as follows:

The difference histogram can be generated from the decrypted image for data extraction and image recovery. Due to additive homomorphism, performing the modular 256 addition performed on the encrypted pixels is also performing that on the decrypted pixels. Taking ${e_{i - 1, j}}$ as an example, according to Eqs. (6) and (7), if $e_{i - 1, j}^m = (e_{i - 1, j}^{} + s)\bmod256$, then $e_{i - 1, j}^m$ is decrypted as:

According to Eq. (11),

Eq. (14) proves that the modification of the encrypted pixel is the same as that of the decrypted pixel, and Eq. (15) proves that the difference histogram of the marked decrypted image is the same as that of the marked encrypted image. Therefore, data extraction and image recovery in the decrypted domain are the same as they are in the encrypted domain, and the recovered image is identical to the original image.

3.   Proposed method

To improve the embedding capacity of Li et al.'s method ^[24], in this section, we propose a new RDHEI method based on two-phase histogram shifting. An overview of the proposed method is given in Figure 3. First, the image is decomposed into non-overlapping T-type blocks and encrypted. Then, the data hider performs two-phase histogram shifting for data embedding. In each phase, a difference histogram is generated for embedding data. Finally, the receiver can perform data extraction and image recovery in the encrypted domain or in the decrypted domain.

3.1.   T-type division and image encryption

We propose a T-type division scheme to divide the image into T-type blocks. Figure 4 shows an example of T-type division in which each T-type block consists of four pixels, i.e., the central pixel, which is in the center of the block (marked as 'c'); the up pixel, which is above the central pixel (marked as 'u'); the down pixel, which is below the central pixel (marked as 'd'); and the side pixel, which is to the left or right of the central pixel (marked as 's').

For an image I sized $M \times N$, the coordinates (x, y) of the central pixel of each of the T-type blocks are defined as:

For each block with the central pixel (x, y), the coordinate (sx, sy) of the side pixel are defined as:

After the image is divided, a pseudo-random matrix K is generated by using the RC4 steam cipher. Then, image, I, is encrypted by the matrix K, as follows:

To generate the difference histogram, pixels in the same T-type block should be encrypted by using the same encryption key. For example, if a T-type block consists of four pixels, i.e., ${p_{i, j}}$, ${p_{i - 1, j}}$, ${p_{i + 1, j}}$, and ${p_{i, j - 1}}$, the four corresponding encryption keys, ${k_{i, j}}$, ${k_{i - 1, j}}$, ${k_{i + 1, j}}$, and ${k_{i, j - 1}}$ should be identical. After encryption, the content owner send the encrypted image for data embedding.

3.2.   Embedding data

The process of embedding data consists of two phases. In the first phase, for each T-type block, the difference of the central pixel and one of its three neighboring pixels is computed. A 'small' difference histogram is formed with these differences, and difference histogram shifting is performed for a limited number of rounds to embed the secret data. The elements in the small difference histogram are shifted by modifying the values of the central pixels. In the second phase, for each T block, three differences are computed, i.e., the difference of the up pixel and the central pixel, the difference of the down pixel and the central pixel, and the difference of side pixel and the central pixel. A 'large' difference histogram is formed with these differences, and difference histogram shifting is performed for embedding data. The elements in the large difference histogram are shifted by modifying the values of the up pixels, the down pixels, and the side pixels.

3.2.1.   Histogram shifting in the first phase

In the first phase, the central pixels are used for embedding data. The process of embedding data in the first phase is proposed as follows:

Step 1: For each encrypted T-type block, denote the central pixel, the up pixel, the down pixel, and the side pixel as e_c, e_u, e_d, and e_s, and the three differences are computed by:

Step 2: After the differences of all the blocks have been computed, three small difference histograms are formed by using d_cu, d_cd, and d_cs, respectively.

Step 3: Compute the embedding capacities of the three small difference histograms and choose the one that can provide the largest capacity for embedding data.

Step 4: After histogram shifting, an additional two bits should be used to denote which small difference histogram is used for embedding data. The additional two bits are embedded into two LSBs of one denoted pixel that does not belong to any T-type block, and the two LSBs are embedded together with the secret data to recover the image. The denoted pixel can be chosen pseudo-randomly by using the data hiding key from all the pixels that does not belong to any T-type block.

Step 5: The difference histogram shifting scheme of Li et al. ^[24], described in Section 2.2.2, is performed a limited number of rounds for embedding data. The limited number of rounds should be set in advance. To shift the elements in the difference histogram, the new value of the central pixel is computed to replace the original value of the central pixel. For example, if the difference histogram formed by d_cu is used for embedding data, to shift the bin one step to the right, according to Eq. (12):

Therefore, the central pixel, e_c, is replaced with (e_c+1) mod 256 for histogram shifting.

The computation of the capacity of the small difference histogram in Step 2 depends on the set of the limited round number for the difference histogram shifting. For example, if the limited round number is set to 3, in the original difference histogram, bins 0 and 255 will be used for data embedding in the first round, bins 1 and 254 will be used in the second round, and bins 2 and 253 will be used in the last round. Therefore, the capacity of the difference histogram is equal to the number of all the elements in bins 0–2 and bins 253–255.

Figure 5 shows an example of data embedding in the first round. First, three difference histograms are generated from the encrypted image, Lena (Figure 8(d)). As shown in the figure, in each histogram, most of the differences also are closed on the two sides, so the difference histogram shifting scheme of Li et al. ^[24] can be used for embedding data. Then, the difference histogram formed by d_cu is chosen for embedding data, since it provides the largest capacity. Three rounds of difference histogram shifting are performed to embed the secret data.

3.2.2.   Histogram shifting in the second phase

In the second phase, the three neighboring pixels of the central pixel in each T-type block are used for embedding data. The process of embedding data in the second phase is proposed as follows:

Step 1: For each encrypted T-type block, denote the central pixel as $e_c^,$, and compute the three differences as:

Step 2: After the differences of all of the blocks have been computed, a large difference histogram is formed by using d_uc, d_dc, and d_sc together.

Step 3: Based on the large difference histogram, the data are embedded in the way that Li et al. ^[24] described in Section 2.2.2. To shift the bins one step in the difference histogram, e_u, e_d, and e_s are replaced with $({e_{\text{u}}} \pm 1)\bmod 256$, $({e_{\text{d}}} \pm 1)\bmod 256$, and $({e_{\text{s}}} \pm 1)\bmod 256$.

In the second phase, the first embedded bit is used to identify whether all the secret data have been embedded in the first phase. If there is no secret data to be embedded in the second phase, only a bit 0 is embedded in the second phase. Otherwise, a bit 1 is embedded first, then the rest secret data are embedded.

Figure 6 shows an example of embedding data in the second phase. The figure shows that, in the large difference histogram, most of the differences are still close to the two sides. Therefore, the difference histogram shifting of Li et al. ^[24] can be performed efficiently for embedding data.

3.2.3.   Data extraction and image recovery

After the marked encrypted image is transmitted, the receiver can extract the secret data and recover the image in the encrypted domain or the decrypted domain.

(1) Processing in the encrypted domain: Since the two-phase histogram shifting is performed directly on the encrypted image, the receiver can extract the embedded data and recover the encrypted image by performing the reverse processing of the two-phase histogram shifting as follows:

Step 1: Generate the large difference histogram according to Eq. (21).

Step 2: Based on the large difference histogram, extract the secret data that were embedded in the second phase of embedding data and recover the up pixel, e_u, the down pixel, e_d, and the side pixel, e_s, in each encrypted T-type block. The processes of data extraction and pixel recovery are the same as those of Li et al.'s method, as described in Section 2.2.3.

Step 3: Generate three small difference histogram according to Eq. (19) and then extract the additional two bits from the denoted pixel to determine the one that was used for embedding data.

Step 4: Based on the small difference histogram, extract the two LSBs and the secret data, shift the bins back to recover the central pixel e_c in each T type block, and replace the two LSBs to recover the denoted pixel. Finally, all of the embedded data and the recovered encrypted image, which is identical to the original image, are retrieved.

Step 5: Decrypt the recovered encrypted image to obtain the original plain image.

(2) Processing in the decrypted domain: The receiver can decrypt the marked encrypted image, I_ME, directly to obtain the marked decrypted image, which is very similar to the original image.

Figure 7 shows a comparison of the large and small difference histograms generated from the marked encrypted image and the marked decrypted image. As shown in the figure, the two difference histograms generated from the decrypted image are identical to those generated from the encrypted image. In addition, according to the Eq. (14), the modification of the marked encrypted pixel is the same as the modification of the marked decrypted pixel due to additive homomorphism. Therefore, the processes of data extraction and image recovery performed on the marked decrypted image are the same as those performed on the marked encrypted image.

4.   Experimental results

In this section, the proposed method is evaluated in terms of security, capacity, and visual quality. The two existing RDHEI methods, i.e., Li et al. ^[24] and Xiao et al. ^[25], are used for comparison. The six $512 \times 512$ standard grayscale test images used in the experiments are shown in Figure 8.

Figure 9 shows an example of the images in the process of the proposed method. Figure 9(b) shows the marked encrypted image with 0.5 bpp. The image appears as noise, so no meaningful content can be obtained. Figure 9(c) shows the decrypted version of Figure 9(b) with PSNR = 37.28 dB, and this version is similar to the original image. Figure 9(d) is the recovered image, which is identical to the original image.

Table 1 shows the PSNRs of the encrypted images and the correlation coefficients of the encrypted images with the plain images. The table shows that the PSNRs of the encrypted images are very low, and the correlation coefficients are almost zero. That means it was very hard to retrieve meaningful content from the encrypted image without the encryption key. For each $512 \times 512$ standard test image, the encryption key space of the encryption scheme in the proposed method is ${2^{255 \times 256 \times 256}}$. The encryption key space is very large so that the computational security can be achieved. Therefore the encryption scheme of the proposed method is secure.images and their correlation coefficients with the plain images.

Table 2 compares the embedding capacities of the proposed method and the two existing RDHEI methods. As shown in the table, compared with the competitors, the proposed method can provide a higher embedding capacity. Compared with Li et al. ^[24], the T-type division and the two-phase histogram shifting of the proposed method fully exploit the pixels to generate more differences for embedding data. That clearly indicates that the proposed method improves the capacity.

Figure 10 shows a comparison of the visual quality of the marked decrypted images with different embedding rates. As shown in the figure, the results of the proposed method is a little worse than that of Li et al.'s method ^[24] at the low embedding rates. However, as the embedding rate increased, the performance of the proposed method was very close to that of Li et al. ^[24]. For some images, such as Airplane and Barbara, the proposed method outperformed Li et al.'s ^[24] method at high embedding rates. In the proposed method, the elements of the bins at the two sides of the difference histogram are reduced, while the elements that are close to the two sides of the difference histogram are increased. When the embedding rate is low, Li et al.'s ^[24] technique requires performing fewer rounds of histogram shifting than the proposed method. However, when the embedding rate is high, the proposed method performs less rounds of histogram shifting than Li et al.'s scheme ^[24]. With the increase of the rounds of histogram shifting, the differences between the modified pixels and original pixels become larger. Performing more rounds of histogram shifting results in the greater distortion of the marked image. Therefore, as the embedding rate increases, the distortion of the image in the proposed method becomes close to that in Li et al. ^[24], and it may be even lower. In most cases, the performance of the proposed method was better than or similar to the performance of Xiao et al.'s method ^[25].

5.   Conclusion

In this paper, a new RDHEI method based on two-phase histogram shifting was proposed. To fully exploit the pixels to reserve embedding capacity, a T-type division scheme and the RC4 additive homomorphic cryptosystem are used to generate the encrypted image which maintains the spatial correlation. From the perspective of the data hider, embedding data is performed in two phases. In each phase, based on the encrypted image, a difference histogram is generated, and the difference histogram shifting is used for embedding data. The extraction of data and the recovery of the image can be performed in both the decrypted and encrypted domains. The embedded data can be extracted without errors, and the recovered image is identical to the original image. The experimental results proved that the proposed method can provide high capacity for data embedding and maintain the visual quality of the marked decrypted image.

The main limitation of the proposed method is the relatively low visual quality of marked images at the low embedding rate. In the future work, to overcome the limitation and improve the visual quality, we aim to design a new dynamic strategy for the proposed method, which can efficiently distribute the secret data to the two phases of the data embedding process.

Acknowledgments

This paper is supported by the Natural Science Foundation of Fujian Province, China (No. 2017J05104, 2019H0021), the National Natural Science Foundation of China (No. 61701191), and the Xiamen Foundation for Science and Technology (No. 3502Z20173028).

Conflict of interest

The authors declare no conflicts of interest.