Reversible Data Hiding in Encrypted Image Based on Block Classification Permutation

Qun Mo, Heng Yao, Fang Cao, Zheng Chang and Chuan Qin,

Abstract: Recently, reversible data hiding in encrypted image (RDHEI) has attracted extensive attention, which can be used in secure cloud computing and privacy protection effectively. In this paper, a novel RDHEI scheme based on block classification and permutation is proposed. Content owner first divides original image into non-overlapping blocks and then set a threshold to classify these blocks into smooth and non-smooth blocks respectively. After block classification, content owner utilizes a specific encryption method, including stream cipher encryption and block permutation to protect image content securely. For the encrypted image, data hider embeds additional secret information in the most significant bits (MSB) of the encrypted pixels in smooth blocks and the final marked image can be obtained. At the receiver side, secret data will be extracted correctly with data-hiding key. When receiver only has encryption key, after stream cipher decryption, block scrambling decryption and MSB error prediction with threshold, decrypted image will be achieved. When data hiding key and encryption key are both obtained, receiver can find the smooth and non-smooth blocks correctly and MSB in smooth blocks will be predicted correctly, hence, receiver can recover marked image losslessly. Experimental results demonstrate that our scheme can achieve better rate-distortion performance than some of state-of-the-art schemes.

Keywords: Reversible data hiding, image encryption, image recovery.

1 Introduction

Digital image security is one of the important research topics in many fields, such as medical, military and some forensic images. In the past few decades, digital image has become a popular way for communication. Many schemes have been proposed for plaintext images. Generative model [Duan, Song, Qin et al. (2018)], optimal iterative BTC [Qin, Ji, Chang et al. (2018)] and image hashing [Qin, Chen, Luo et al. (2018)] are applied for image security. However, in some important areas, such as military and medical fields, we not only need to protect the security of secret information, but also need to recover original image on the receiver side, which is called as reversible data hiding (RDH). Different from robust watermarking, RDH emphasizes the extraction of secret data and high quality of image recovery [Yu, Zhu, Li et al. (2013); Zhou, Sun,Dong et al. (2015)]. A lot of RDH schemes for plaintext images have already been designed, such as difference expansion [Tian (2003); Thodi and Rodriguez (2007)] and histogram shifting [Ni, Shi, Ansari et al. (2006)] schemes. More recently, to improve embedding capacity, some schemes were proposed: prediction-error expansion [Ou, Li,Zhao et al. (2013)], multiple histograms modification [Li, Zhang, Gui et al. (2015)] and histogram shifting mechanism for inpainting-assisted reversible steganographic scheme[Qin, Chang, Huang et al. (2013)] were all applied for plaintext image. In 2014, Qin et al.[Qin, Chang and Chui (2014)] proposed a scheme which realized data hiding and compression at the same time. However, these schemes cannot be applied in encrypted image because the redundancy in original image is rare. To solve this problem, RDH in encrypted image allows the data hider to embed additional data into the encrypted image and realize data hiding and protect the privacy of content owner simultaneously.

In 2011, reversible data hiding in encrypted image (RDH-EI) was proposed by Zhang[Zhang (2011)], in which the three least significant bits (LSB) were flipped to hide the additional secret data. Later, improved schemes based on this scheme began to emerge.Among them, the error rate of extraction was improved, and some schemes [Hong, Chen and Wu (2012); Liao and Shu (2015)] were proposed, the capacity of embedding was increased, and some schemes proposed to embed additional data in compressed encrypted images and realize lossy compression for selective encrypted image with image inpainting [Qin, Zhou, Cao et al. (2018)].

Generally speaking, existing schemes are classified into two categories: 1) vacating room after encryption and 2) vacating room before encryption. In 2012 [Zhang (2012)], a separable RDH-EI scheme was proposed, original image was encrypted by bitwise XOR operation by an encryption key, the data-hider compressed the LSB of encrypted image to create spare space to embed additional data. This scheme can achieve data extraction,image decryption with high quality and recovered image. However, when the amount of additional data was larger than 0.04 bit per pixel (bpp), it was difficult to recover original image correctly. In 2013, Ma et al. [Ma, Zhang, Zhao et al. (2013)] proposed a separable scheme with good quality of recovery and embedding rate, however, before the encryption, a pre-processing operation by the sender should be applied, and the scheme was actually a conventional RDH in plaintext image. In 2014, Wu et al. [Wu and Sun(2014)] proposed a RDH-EI scheme based on prediction error, additional data was embedded in the most significant bit (MSB) of encrypted image. The problems of this scheme were: (1) the quality of decrypted image is low, even if the payload was 0.016 bpp, PSNR value was about 35 dB for Lena and 24 dB for Baboon; (2) for the texture image, such as Baboon, the quality of recovered image was very low. Later, Qian et al.[Qian and Zhang (2016); Qian, Zhang and Feng (2016)] used distributed source encoding and progressive recovery to realize reversible data hiding in encrypted images,respectively. In 2018, Qin et al. [Qin, Zhang, Cao et al. (2018)] proposed a novel scheme via block selection to embed secret data in encrypted images.

In summary, the above schemes cannot guarantee high embedding rate together with a high quality of recovered image. To solve this problem, this work proposes a new scheme based on block classification permutation, in which original image is divided into non-overlapping blocks and all blocks are classified into smooth blocks and non-smooth blocks according to threshold. The classification permutation aims to scramble the pixel positions and make the data-hider classify the smooth and non-smooth blocks easily.Secret data are embedded in the MSB of encrypted pixels in smooth blocks. At the receiver side, if the receiver only has data hiding key, secret information will be extracted correctly. When encryption key is possessed, MSB in all blocks will be predicted with threshold and decrypted image can be achieved. When data hiding key and encryption key are both obtained, receiver can find the smooth and non-smooth blocks correctly and MSB in smooth blocks will be predicted correctly and final recovered image will be obtained. Experimental results demonstrate that the quality of recovered image and embedding rate of our scheme outperform those of the above schemes.

The rest of the paper is organized as follows. The proposed scheme is described in detail in Section 2. Section 3 provides experimental results and analysis. Finally, the conclusion is drawn and future work is mentioned in the last part.

2 Proposed scheme

2.1 Overview

The schematic diagram of the proposed scheme is shown in Fig. 1. For the content owner,block classification, block permutation and image encryption are conducted on original image; for the data hider, data embedding with MSB substitution is conducted on smooth blocks of encrypted image; for the receiver, secret information, decrypted image and recovered image can be obtained with different keys.

2.2 Block classification and permutation

2.2.1 Block classification

Assume the original imageIwith a size of M×N pixels and each pixelIx,ywith gray value falling into [0, 255] is represented by 8 bits, where both M and N are power of 2, and 1

where Dzrepresents the difference between pmaxand pminin the z-th block. We set a same threshold DTfor all blocks, if Dz

2.2.2 Block permutation

After block classification, for the sake of security, Josephus traversing permutation is applied on image blocks, which contains three parameters, including the number of blocks of original imageIrecorded as n, starting position Js, and the counting period Jc.With these three parameters, imageI' can be obtained with a Josephus block permutation:

To provide an example, assuming n=9, Jsand Jcare set as 2 and 3, respectively andthe total initial sequence can be represented as:

whereBirepresents the i-th block of the original imageI(i=0, 1, ..., 8). Apply our parameters to Eq. (2), i.e.,I'=J (9, 2, 3), a scrambled sequence is produced:

According to the new imageI' after block scrambling, a new mark matrixU' can be obtained, where n=(M/K)×(N/K), Jsand Jcis set by the encrypted key. Fig. 2 shows an example, in which 4×4 blocks are shown, where K=4, DT=10 and J=(16, 2, 3). These 16 blocks are classified into smooth and non-smooth blocks according to DT, after permutation, a new imageI' with block classification and permutation is generated.

Figure 2: Example of block classification permutation. (a) Initial blocks of original image I, (b) Mark matrix U, (c) Blocks after permutation of image I', (d) Mark matrix U'

2.3 Image encryption

2.3.1 Stream cipher encryption

After block classification and permutation, a new imageI' is generated. In order to make the imageI' indistinguishably, we encrypt it by using an encryption key: ke=(c, x0). The elements of this key are used as parameters of chaotic generator. First, the image owner turns the new imageI' into plain bits by decomposing each pixel into 8 bits as:

where I'x,yis the pixel of imageI' with coordinate (x, y). By using this chaotic generator, a sequence of pseudo-random bytes sx,y,uis obtained and bitstream of the encrypted image can be calculated through exclusive-or(XOR) operation:

Accordingly, an encrypted imageEcan be constructed by:

where Ex,yis the pixel of encrypted image with coordinate (x, y).

2.3.2 Self-embedding of U'

In order to extract embedded secret information correctly and recover the original image losslessly, mark matrixU' needs to be embedded in the encrypted image. The p-th element of mark matrixU' is stored in the LSB of encrypted pixel with coordinate (K2, K2)of the p-th block, where 0

2.4 Data embedding

After image encryption, with the embedded mark matrixU', the data hider can classify all divided blocks into smooth and non-smooth blocks respectively. For smooth blocks,MSB of each pixel in addition to the first pixel of smooth blocks are substituted by bkwith:

2.5 Data extraction

In the data extraction phase, firstly, if the receiver only has data-hiding key, the receiver can classify the marked imageE' into K×K non-overlapping blocks and LSB of each pixel with coordinates (K2, K2) in the current block can be obtained. In other words, the concrete position and number of smooth blocks and non-smooth blocks can be acquired,the number of smooth blocks is recorded as n1and the number of non-smooth blocks is recorded as n2, meanwhile, the MSB of each pixel of smooth blocks are extracted by:

where 0

2.6 Image decryption and recovery

2.6.1 Image decryption

When the receiver only has the encryption key (stream ciphers key and scrambling encryption key), the receiver can obtain the decrypted imageId, the specific steps are as follows:

Step 1: The stream cipher key keis used to generate the sequence s(x,y), with M×N pseudo-random bytes. The pixels of the marked encrypted image are browsed in the scan line order and all pixels are decrypted by conducting XOR for the value ex,y,uwith the associated binary sequence sx,y,uin the pseudo-random stream:

Accordingly, a decrypted imageIdcan be constructed by:

Note that, secret data is embedded in the MSB of pixels in smooth blocks, and their MSB cannot be decrypted correctly.

Step 2: In the case where the scramble key is known, blocks before permutation can be achieved. We can get the imageIdbefore block classification permutation in which there are some pixels whose MSB may be error in smooth blocks. To obtain the decrypted image with high quality, the pixel values of smooth blocks are adjusted by estimating its MSB.Step 3: The decrypted image is divided into K×K non-overlapping blocks, for each block,difference between each pixel and the first pixel can be calculated and recorded as. If, i.e., other pixel value is larger than the first pixel value in the current block, whenthe current decrypted pixel value can be calculated by:

In this way, the decrypted imageIdcan be obtained.

2.6.2 Image recovery

If the receiver both has data hiding key and encryption key, the original imageIcan be recovered with high quality. When data hiding key is achieved, smooth and non-smooth blocks can be achieved. For pixels in non-smooth blocks, the pixel values remain unchanged, and for those pixel values in smooth blocks, we calculate difference between each pixel value and the first pixel value and the differences are recorded as. If, i.e., other pixel value is larger than the first pixel in the current block, whenthe current recovered pixel value can be calculated by:

In this way, the recovered imageIcan be obtained.

For example, Fig. 3 shows an example, in which the process of MSB prediction and image recovery is shown. Fig. 3(a) shows the image after stream ciphers decryption and block permutation decryption. It contains 64 blocks, each block includes 4×4 pixel values.The smoothness corresponding to each block is shown in Fig. 3(b), in which, 0 represents smooth blocks and 1 represents non-smooth blocks. We mark the non-smooth blocks with gray and use white to mark the smooth blocks. Pixel values in non-smooth blocks are kept unchanged. With Eq. (14) and Eq. (15), the MSB value can be recovered correctly. Five blocks identified in red is used as a concrete example, the pixel values in the five blocks are shown in Fig. 3(c). When threshold DT=15, by calculating the difference, we correct the MSB value of pixel in current smooth block. After correcting all pixel values, we can get the recovered image with high quality.

Figure 3: (a) Initial blocks after encryption and classification rearrangement, (b) Mark matrix U', (c) Pixels in blocks marked with red, (d) Pixels after MSB prediction

3 Experimental results and comparisons

In this section, we present the obtained experimental results, Section 3.1 gives a full example for different test images and shows the obtained results. Then, in Section 3.2 we analysis performance of our proposed scheme from different statistical metrics. Finally,in Section 3.3, we compare embedding rate and recovered image quality of our proposed scheme and other three state-of-the-art schemes.

3.1 Results of our scheme

We first applied our scheme on four different test original images of 512×512 pixels,illustrated in Fig. 4. Fig. 5 gives an example of our proposed scheme for Lena sized 512×512. Fig. 5(a) shows encrypted image Lena. Fig. 5(b) is the marked image with secret bits embedded. Fig. 5(c) is the decrypted image and Fig. 5(d) is the recovered image.

Figure 4: Test image. (a) Lena, (b) Baboon, (c) Peppers, (d)Airplane

Figure 5: An example of the proposed scheme with K=4 and the threshold DT is 15. (a)The encrypted image after classification and permutation, (b) Marked image with 111489 bits embedded, (c) Decrypted image after MSB prediction with PSNR=31.72 dB, (d) The losslessly recovered image

3.2 Performance analysis

We perform an analysis to evaluate performance of our proposed scheme. We use different statistical metrics: horizontal, vertical and diagonal correlation coefficients;Shannon entropy; PSNR between the original image and decrypted and recovered image and embedding rate of secret information.

(a) Shannon entropy:

where β denotes the source consisting of h symbols, i.e., β1, β2, …, βh; P(βi) denotes the probability of the symbol βi.

(b) Horizontal, vertical and diagonal correlation coefficients:

where ciand diare two data sequence of adjacent pixels including horizontal, vertical and diagonal directions of the plain image and encrypted image, respectively. S is the sequence length.

(c) Peak-signal-to noise ratio (PSNR):

whereIdis the decrypted image andIis original image(d) Embedding rate:

Embedding rate is expressed in bit per pixel, where n1represents the number of smooth blocks and K represents the block size. The embedding amount of mark matrixUand the original LSB values embedded as extra secret information should be considered.

Shannon’s entropy provides a standard to evaluate randomness of image, which can be calculated with Eq. (16). The entropy should be close to 8 for an ideal random image with 256 grey levels. The information entropies of original image and encrypted image are shown in Tab. 1.

We can find that the calculated entropies of encrypted images are extremely close to the ideal value 8. Meanwhile, the correlation between two adjacent pixels in encrypted image is also a good standard to evaluate good encryption performance. Correlation coefficients will be calculated with Eq. (17) and the results are shown in Tab. 2, we can find that the correlation coefficients of adjacent pixels of plain image are close to 1, while the correlation coefficients of adjacent pixels of encrypted image are close to 0, which indicates that our proposed scheme have a good encryption performance.

Table 1: Entropy analysis of our proposed scheme

Table 2: Correlation analysis of our proposed scheme

Table 3: PSNR values and embedding rate of decrypted and recovered image Lena

Table 4: PSNR values and embedding rate of decrypted and recovered image Baboon

Table 5: PSNR values and embedding rate of decrypted and recovered image Peppers

In the process of encryption, the original image is divided into K×K blocks. We set a threshold DTto classify smooth and non-smooth blocks. The size of image block and threshold will directly affect the quality of decrypted image. We test PSNR values and embedding rate of the decrypted and recovered image under different K and threshold.The results are shown in Tab. 3, Tab. 4, Tab. 5 and Tab. 6. For decrypted image, when K remains unchanged, the embedding rate becomes larger as the threshold increases, while PSNR value decreases. When threshold value remains unchanged, both embedding rate and PSNR value decrease with the increase of K. For the four test images, complete reversibility can be obtained by our proposed scheme. Therefore, according to different images, setting a reasonable threshold and block size K will achieve a good balance between embedding rate and PSNR values of decrypted image.

Table 6: PSNR values and embedding rate of decrypted and recovered image Airplane

3.3 Comparisons with three state-of-the-art schemes

We conduct some comparisons in terms of embedding rate and PSNR of recovered image between our scheme and three schemes including Zhang’s scheme [Zhang (2011)], Wu et al.’s scheme [Wu and Sun (2014)] and Liao et al.’s scheme [Liao and Shu (2015)]. First of all, Fig. 6 shows comparison results of rate-distortion curves for the relationship between embedding rate and visual quality of recovered image. It can be found that, our scheme can acquire better rate-distortion performance than other three schemes for the four test images sized 512×512, including Lena, Baboon, Peppers and Airplane. For the recovered image, our scheme allows us to have a higher embedding rate and PSNR value than other schemes. Under the same PSNR value, the embedding rate of our scheme is higher than other three schemes.

Figure 6: Comparisons rate-distortion curves for recovered image among the proposed scheme and other three schemes. (a) Lena. (b) Baboon. (c) Peppers. (d) Airplane

4 Conclusions

In this paper, a novel scheme of reversible data hiding in encrypted image based on block classification and permutation is proposed. Before encryption, we set a threshold to classify original image into smooth and non-smooth blocks, respectively. Then all blocks are permuted according to Josephus scrambling and mark matrixUis generated to mark the smooth and non-smooth blocks respectively. In the encryption process, the image is encrypted with the stream cipher. In data embedding process, secret data is embedded in the MSB of each encrypted pixel expect the first pixel in current smooth blocks. At the receiver side, when data-hiding key is possessed, secret data can be extracted correctly.When encryption key is possessed, MSB in all blocks will be predicted with threshold and decrypted image can be achieved. In order to recover the original image reversibly,the receiver should both has data hiding key and encryption key. Compared with three proposed schemes, the rate-distortion performance of our proposed scheme is better. In the future work, the storage space of the mark matrix should be decreased and the quality of decrypted image should be further improved.

Acknowledgement:This work was supported by the National Natural Science Foundation of China (61672354, 61702332). The authors would like to thank the anonymous reviewers for their valuable suggestions.