1 Introduction

Reversible data hiding (RDH) in images is a technique, by which the original image can be losslessly recovered after the extraction of the secret data. This important technique can be applied to many scenarios, such as law forensics, military imagery and medical imagery, where no distortion of the original image is allowed. For this reason, RDH has attracted considerable research interest.

Many reversible data hiding methods have been proposed recently. In literature [7, 8, 15], the differences between two adjacent pixels is expanded to generate a new LSB plane for accommodating secret data. In literature[10, 13, 14], spare space is saved for data embedding by shifting the histogram of cover data from its peak point towards its zero points. Another strategy for RDH is based on lossless compression, in which a data hider makes use of redundancy of the original cover to create a blank space for embedding the secret data [1, 12].

With the increasing demand of privacy protection, encryption [2, 3, 16] becomes an effective and popular means, which converts original image into unintelligible one. There are some applications while RDH can be applied for encrypted images. For instance [18], to protect the privacy of the patient, the medical images should have been encrypted, a database administrator may aim to embed the personal data into encrypted medical images. With the personal data, the database administrator can manage the images without knowing the original content. On the other hand, a doctor, having both the data-hiding and the encryption keys, can extract the personal data and recover the original content without any error. That means a RDH scheme for encrypted image is attractive.

Some attempts on RDH for encrypted images have been proposed. In literature [11], AES algorithm was applied to encrypt original image, and each block of an encrypted image can carry one secret bit by simple substitution, at the decryption stage, an analysis of local standard deviation of the marked encrypted image is used to extract the embedded data. However, the embedding capacity is low and the quality of image decrypted from the marked encrypted version is unsatisfactory. In literature [18], a data hider divided the encrypted image into several blocks, by flipping 3 LSBs of specific pixels in each block, one secret bit can be embedded into each block. The data extraction and image recovery proceed with the aid of spatial correlation in natural image. Hong et al. [6] improved the method in literature [18] by further exploiting the spatial correlation using a different estimation equation and side match technique to reduce the error rate. However, in literature [6, 18], encrypted image should be decrypted first before data extraction, that is, if a receiver has the data-hiding key only, he can not extract any data from the marked encrypted image. Aiming for separating data extraction from image decryption, Zhang [19] compressed the LSBs of encrypted image by finding the syndromes of a low-density parity check matrix to create an extra space for secret data. These methods achieve low embedding capacity or generate marked decrypted image with poor quality for high embedding capacity. Besides that, all of them are subject to some error rates on data extraction and /or image recovery [6, 18, 19]. In [20], Zhang embedded the additional data into various bit planes by using a reversible manner, and a parameter optimization method is used to ensure a good payload- distortion performance. the data insertion/extraction can be performed in both the plain and encrypted domains.

Since it is difficult to losslessly vacate room from the encrypted images. Ma et al. [9] and Zhang [21] both emptied out room before image encryption, and achieved excellent performance. However, the operating of image encryption and data embedding is inseparable, which can not satisfy the application requirement of privacy protection.

This paper proposes a novel RDH for encrypted images based on lossless compression with high capacity. Not only does the proposed method separate data extraction from image decryption but also achieves excellent performance in two different prospects:

  1. 1.

    Reversibility is realized, that is, data extraction and image recovery are free of any error. Moreover, image encryption and data hidden process is separable in the proposed method, which meets the demand of digital image for privacy protection.

  2. 2.

    For given embedding rates, the PSNR of marked decrypted image is significantly improved; and for acceptable PSNR, the range of embedding rates is greatly enlarged.

The rest of the paper is organized as follows. The scheme of the proposed method is elaborated in Section 2. Experimental results with analysis and comparison are shown in Section 3. The paper is concluded in Section 4.

2 Proposed method

To enable data embedding in the encrypted image, we propose a novel method to significantly improve the performance in terms of the data embedding capacity and image quality of the marked decrypted image by using the Hamming distance to compress the encrypted image for data embedding. In this proposed scheme, we vacate room after encryption.

The procedure of reversible data hiding in encrypted images is composed of three steps: image encryption, data hiding, data extraction and image recovery, as illustrated in Fig. 1. The content owner first converts the original image A into its encrypted version B with encryption key r 0. Then the data hider compresses the LSBs of B with data-hiding key k 0 to reserve blank space for additional data, and the data hider produces marked encrypted image C. At the receiver side, since the data hiding only affects the LSBs, decryption without data extraction can result in a marked decrypted image similar to A. With k 0, the secret data can be extracted successfully. With both of k 0 and r 0, the additional data can be correctly extracted and the original image can be exactly recovered.

Fig. 1
figure 1

The procedure of reversible data hiding for encrypted image

Full size image

2.1 Image encryption

Chaos [4] has several good properties including the ease of its generation, its sensitive dependence on initial condition and noise like, so that it is very suitable for image encryption. Meanwhile, it also indicate the trait of certainty, and can be completely reconstructed for image decryption as long as the system parameters and initial conditions are the same.

Logistic mapping is a classical model, which is used to studying the behavior of complex system of dynamic system, chaos, fractal ect. the encryption key as a initial value of Logistic mapping, a chaotic sequence is produced, and after the corresponding treatment, each element of the chaotic sequence is between 0 and 255.

Furthermore, the exclusive-or operation has reversibility. Combined with the Logistic mapping and the exclusive-or operation, a substitute encryption method is designed [5, 17].

In encryption phase, assume the original image A with a size of N 1×N 2 is in uncompressed format and each pixel with gray value falling into [0,255] is represented by 8 bits. Denote the bits of pixel as b i, j (0), b i, j (1),..., b i, j (7) where 1 ≤ i ≤ N 1, 1 ≤ j ≤ N 2, the gray value as p(i, j), and the number of pixels as N(N = N 1×N 2). Thus

$$ {b_{i,j}}\left( k \right) = \left\lfloor {\frac{{p\left( {i,j} \right)}}{{{2^{k}}}}} \right\rfloor \text{mod}\, 2,0 \le k \le 7 $$
(1)

The encrypted bits \({b^{\prime }_{i,j}}\left (k \right )\) can be calculated through exclusive-or operation

$$ {b^{\prime}_{i,j}}\left( k \right) = {b_{i,j}}\left( k \right) \oplus {r_{i,j}}\left( k \right) $$
(2)

where r i, j (k) are created using the Logistic mapping with the encryption key r 0. Then, \({b^{\prime }_{i,j}}\left (k \right )\) are concatenated orderly as the encrypted data.Chaos system can be used here to ensure that anyone without r 0, such as a potential attacker or a data hider, can not obtain any data about original content from the encrypted data.

2.2 Data hiding

In data hiding phase, once the data hider acquires the encrypted image B, he can embed secret data into it by modifying a proportion of encrypted data without having any information about the original image content, as shown in Fig. 2. The detailed procedure of data hiding is given as follows:

  1. 1.

    First, segment B into a number of non-overlapping blocks with the size of l × l, l is a positive integer. Then, with the data-hiding key k 0, a random sequence is generated, and select t image blocks by using random interval method or random permutation method. t is a positive integer less than ⌊N/l 2⌋.

  2. 2.

    For each block B i (1 ≤ i ≤ t), extract m LSBs from per pixel to generate a sequence X i = {x i1, x i2, ..., x i n }, n = (m × l × l)/3, x i j is composed of each three consecutive bits of X i , j ∈ [1, n]. Then a corresponding sequence Y i = {y i1, y i2,..., y i n } is generated, which should meet the condition that Hamming distance between x i j and y i j is no more than 1. Here Y i is introduced as auxiliary bit sequence. For example, if X i = {000,001,010,100}, a corresponding sequence Y i = {001,001,011,100}, that is to say, if x i j = {000}, a corresponding stream y i j = {000}. m is a small positive integer less than 4.

  3. 3.

    The following (3) defines a set, denoted by C o s e t1−4, in which a stream containing two bits can replace two types of stream, each of them including three bits and the Hamming distance between them is three. On the basis of C o s e t1 − 4, x i j can be compressed as two bits, so the third bit of x i j is to leave for secret bit. Repeat this way, n bits are embedded into each block at most. For example, if x i j = {000}, the compressed x i j is {00−}, shown in Fig. 2c.

  4. 4.

    Repeat above process until all the secert bits are embedded, a marked encrypted image is generated, denoted by C.

$$ \begin{array}{l} \begin{array}{cc} {C{\mathrm{o}}set1}\\ {\left( {00} \right)} \end{array} = \left\{ {\begin{array}{cc} {000}\\ {111} \end{array}} \right\} \begin{array}{cc} C{\mathrm{o}}set2\\ \left( {01} \right) \end{array} = \left\{ {\begin{array}{cc} 001\\ 110 \end{array}} \right\}\\ \begin{array}{cc} C{\mathrm{o}}set3\\ \left( {10} \right) \end{array} = \left\{ {\begin{array}{cc} 010\\ 101 \end{array}} \right\} \begin{array}{cc} C{\mathrm{o}}set4\\ \left( {11} \right) \end{array} = \left\{ {\begin{array}{cc} 100\\ 011 \end{array}} \right\} \end{array} $$
(3)

In practice, C o s e t1−4 plays an important role in data embedment and image recovery process. Since the total t × n bits can be accommodated in all blocks at best, the maximum embedding rate, a ratio between the bit amount of secret data and the total number of cover pixels, is (4).

$$ R_{\max } = \frac{{t \times n}}{N} = \frac{\left( N / ({l \times l}) \right) \times \left( \left( m \times l \times l \right)/3 \right)}{N} = \frac{m}{3} $$
(4)
Fig. 2
figure 2

The sample of proposed method (l = 3, m = 3, the shadows represent secret bits).(a) the encrypted image, (b) the 3 LSBs of each pixel, (c) the 2 LSBs after compression, (d) the 3 LSBs containing secret bit, (e) the marked encrypted image

Full size image

With the data-hiding key k 0 , the data hider randomly selects the blocks and makes proper extraction, thus anyone who does not possess the data-hiding key could not extract secret data.

2.3 Data extraction and image recovery

In this phase, since data extraction is completely independent from image decryption, there are three cases that a receiver has only the data-hiding key k 0, only the decryption key, here r 0, and both k 0 and r 0, respectively, demonstrated in Fig. 3.

Fig. 3
figure 3

Three cases in receiving terminal

Full size image

Case 1

Data extraction from C

To manage and update personal information and ensure clients’ privacy, a receiver may only get access to k 0. The operation of data extraction before image decryption ensures the feasibility of our work in this case. The receiver should do following three steps:

  1. 1.

    Divide the received image into blocks with the size of l × l,according to the same way in data hiding phase.

  2. 2.

    With k 0, select blocks for data extraction by exploiting random interval method or random permutation method.

  3. 3.

    For each block, extract m LSBs from all pixels, generate a sequence \(X^{\prime }_{i} = \left \{ {x^{\prime }_{i1} ,x^{\prime }_{i2} ,...,x^{\prime }_{in} } \right \}\) which is the same as the generation of X i in data hiding phase and extract bit from the third bit of \(x^{\prime }_{ij}\) successively. Finally, concatenate the extracted bits to form the secret bits. The whole process avoids the leakage of original image content.

  4. 4.

    Repeat the third step mentioned above, until all the secret data is extracted.

    Furthermore, because each encrypted block is randomly selected and recombined, which makes any malicious attackers cannot obtain the embedded data under the absence of k 0.

Case 2

Generating the marked decrypted image D

Consider the case that the receiver has only r 0, he can generate r i, j (k) by Logistic mapping and r 0, and calculate the exclusive-or r i, j (k) and received data to decrypt the received image. The gray values of marked decrypted pixels \({p^{\prime \prime \prime }_{i,j}}\left (k \right )\) can be calculated by (5).

$$ p^{\prime\prime\prime}\left( {i,j} \right) = \sum\limits_{k = 0}^{7} {{{b^{\prime\prime\prime}}_{i,j}}\left( k \right)} \cdot {2^{k}} $$
(5)

where \({b^{\prime \prime \prime }_{i,j}}\left (k \right )\) are the binary bits of D.

Since the (8−m) most significant bits (MSBs) of D are kept unchanged in data hidden process. Clearly, the original (8−m) MSBs are retrieved correctly, the content of D is similar to the original image. However, the receiver is unable to obtain the secret data.

Case 3

Data extraction and image restoration

With the marked encrypted image C, if the receiver has both k 0 and r 0, he can further extract the secret data and recover the original image.

The data extraction process is essentially identical to Case 1, and the receiver can extract the secrte data successfully. After extracting the secret data, the receiver need to recover the original image, the following outlines the specific steps:

  1. 1.

    After data extraction, segment the remaining bits of \(X^{\prime }_{i}\) into a number of streams \(x^{\prime \prime }_{ij}\) successively, \(x^{\prime \prime }_{ij}\) containing two bits. Then, find the corresponding streams x(i,1) and x(i, 2) in C o s e t1−4, and the Hamming distance between x(i,1) and x(i, 2) is three.

  2. 2.

    According to the corresponding sequence y i j , the receiver need to calculate the Hamming distance between y i j and x(i,1), x(i, 2), respectively.

  3. 3.

    If the Hamming distance between x(i,1) and y i j is no more than 1, x(i,1) is the bits of encrypted pixels; Similarly, if the Hamming distance between x(i, 2) and y i j is less than or equal to 1, x(i, 2) is the bits of encrypted pixels.

  4. 4.

    Continue doing Step1 to Step3 and merger all encrypted bits to form the encrypted image.

  5. 5.

    With the encrypted image and r 0, obtain the original pixels via (2) and (5).

3 Experiments and comparisons

The proposed method will be tested on a number of standard images, which include Baboon, Boat, Barbara, Lake, Man and Lena. The size of all images is 512×512. The criteria PSNR is used to evaluate the quality of marked decrypted image. Moreover, the embedding rate is employed to evaluate the amount of the additional data. Note that in this section, the listed PSNR is the PSNR of the marked decrypted image versus the original image.

The standard image Lena shown in Fig. 4a is used as the original image in the experiment. Figure 4b is the encrypted image. Then, we let m = 1, l = 40, and embed 1.1×104 additional bits into the encrypted image, the marked encrypted image is given as Fig. 4c, and the embedding rate is 0.041 bit per pixel (b p p). With the marked encrypted image, we can generate the marked decrypted image using the encryption key, the PSNR of the marked decrypted image is 55.00d B. The marked decrypted image is illustrated in Fig. 4d. Figure 4e depicts the recovery image which is identical to the original image. By both using the data-hiding and encryption keys, the embedded data can be successfully extracted and the original image can be recovered from the marked encrypted image.

Fig. 4
figure 4

(a) Original Lena, (b) its encrypted image, (c) marked encrypted image, (d) marked decrypted image, (e) recovery image

Full size image

Without loss of generality, the use of multiple LSBs takes into account the fact that the values of PSNR can be reduced with an increase in embedding rates. For different standard images, the comparison results measured by PSNR for three different choices of LSBs, i.e. the number of LSBs m, are presented in Table 1, where the embedding rate is measured by bits per pixel (bpp). It is observed that when embedding rate is small, one or two LSBs can be introduced. With a growing embedding rate, we prefer using three LSBs to single one. In practice, we can flexibility choose m in the light of the length of secret bits for acceptable PSNR.

Table 1 PSNR comparison for three different the number of LSBs m choice under various embedding rates
Full size table

In the proposed scheme, the higher the embedding rate, the worse the quality of the marked decrypted image, therefore, we should not only improve the embedding capacity but also ensure good quality of the marked decrypted image. The quality of marked decrypted images is compared in the term of PSNR. Figure 5 plots the PSNR of different marked decrypted images under given embedding rates. We modify the embedding way and embedding positions of the secret data: we randomly select a certain number of encrypted blocks with the size of 40×40. In the following, according to C o s e t1−4, every 3 LSBs of encrypted pixels are compressed as two bits, and a blank space is generated for secret data. At the same time, 5 MSBs of each encrypted pixel are kept unchanged. We have compared the proposed method with the state-of-the-art work [6, 18, 19]. In Fig. 5, the X-coordinate represents the embedding rate R, the Y-coordinate is the PSNR of the marked decrypted images. Take standard image Baboon for instance, the PSNR of the marked decrypted image using our method is about 15.36 dB higher than the methods in [6, 18, 19]. From Fig. 5, it can be observed that all range of the embedding rates, the PSNR of marked decrypted image is improved about 15 dB than the methods in [6, 18, 19]. The gain in terms of PSNR is significantly higher at same embedding rate than state-of-the-art reversible data hiding algorithms [6, 18, 19]. In addition, another advantage of the proposed method is the much wider range of embedding rate for acceptable PSNRs. In fact, the proposed method can embed more than 5 times as large capacity for the same acceptable PSNR, e.g., PSNR=45dB, as the methods in [6, 18, 19].

Fig. 5
figure 5

Performance comparison of different algorithms for PSNR under given embedding rates

Full size image

In [6, 18], schemes of reversible data hiding for encrypted images are proposed. [6] made improvement on the basis of the work in [18] in order to achieve much lower error rate. these two methods only accommodated one secret bit in each block. However, our proposed method can embed one secret bit into each pixel at most. In [19], the least significant bits of the encrypted image are compressed to create a sparse space to accommodate the additional data, the embedding rate is relatively low, and with the decrease of block size, the original image can not be recovered perfectly.

As mentioned in Section 1, all methods in [6, 18, 19] maybe introduce some error on data extraction and/or image restoration, while the proposed method is free of any error for a number of images.

Our algorithm not only can hide a large number of the secret data, but also can recover the original image losslessly. Whats more, the operation sequence in receiving terminal is flexible, meanwhile it meets the requirement of privacy protection. All these make the proposed algorithm has better competitiveness.

4 Conclusion

A novel scheme for reversible data hiding for encrypted images based on lossless compression with a high capacity is presented, which consists of image encryption, data hiding, and data extraction/image recovery phases. In encryption phase, a chaotic sequence is used to encrypt the original bits. In data hiding phase, although the data hider does not get access to the original image, he makes use of the Hamming distance between streams to generate a blank space for secret data. With marked encrypted image, since the data hiding only affects LSBs, a decrypted version with the decryption key is similar to the original image. According to the data-hiding key, secret data can be correctly extracted. When using both of the data-hiding and the decryption keys, the secret data can be correctly extracted and the original image can be restored perfectly. Experimental results show that the proposed method can achieve reversibility, separate data extraction from image decryption, and effectively improvement on the embedding rate and the quality of marked decrypted images. In this work, one secret bit can be embedded into one encrypted pixel at most.