Separable Reversible Data Hiding in Encrypted Image Based on Two-Dimensional Permutation and Exploiting Modification Direction

Abstract

In this paper, we propose a separable reversible data hiding method in encrypted image (RDHEI) based on two-dimensional permutation and exploiting modification direction (EMD). The content owner uses two-dimensional permutation to encrypt original image through encryption key, which provides confidentiality for the original image. Then the data hider divides the encrypted image into a series of non-overlapping blocks and constructs histogram of adjacent encrypted pixel errors. Secret bits are embedded into a series of peak points of the histogram through EMD. Direct decryption, data extraction and image recovery can be performed separately by the receiver according to the availability of encryption key and data-hiding key. Different from some state-of-the-art RDHEI methods, visual quality of the directly decrypted image can be further improved by the receiver holding the encryption key. Experimental results demonstrate that the proposed method outperforms some state-of-the-art methods in embedding capacity and visual quality.

1. Introduction

In the era of big data, data transmission and exchange have become easier than ever before. However, meanwhile, data security is confronted with more risks [1,2]. Image is a common form of data and also suffers the same affliction. At present, there are two effective methods to protect image data, which are image encryption and image data hiding. Image encryption converts a meaningful original image into an unrecognized one to prevent information leakage [3,4]. Different from image encryption, image data hiding modifies the pixel values of a cover image imperceptibly to embed secret data into the cover image so that the transmission of stego-image does not attract attacker’s interest [5,6,7,8,9].

In general, the cover image will suffer distortion inevitably due to the modifying operation. However, for some image applications, e.g., military or medical images, the distortion is unacceptable even if it is very small. For the demand of recovering original image losslessly, reversible data hiding (RDH) was proposed, which can both recover the original image and extract secret data perfectly. In the literature, the existing RDH methods are generally classified into four categories: (1) The methods based on lossless compression [10,11], (2) the methods based on difference expansion (DE) [12,13], (3) the methods based on histogram shifting (HS) [14,15], and (4) the methods based on prediction-error expansion (PEE) [16,17,18]. Nowadays, PEE-based methods have attracted considerable research interest due to their large embedding capacity and high fidelity.

Recently, as cloud computing and cloud storage develop rapidly, RDH in encrypted image (RDHEI) draws more and more interest [19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]. RDHEI can be applied to the applications of ciphertext management of multimedia data, copyright protection and privacy protection. There are three users in RDHEI: the content owner, the data hider and the receiver. The content owner encrypts the original image according to encryption key and uploads it to the server. Then the data hider embeds some secret data into the encrypted image according to data-hiding key and cannot access the original image content without an encryption key. The receiver can obtain the original image, secret data or both under specific authority. Generally, there are mainly three RDHEI frameworks, namely reserving room before encryption (RRBE) [19,20,21,22,23,24,25], vacating room after encryption (VRAE) [26,27,28,29,30,31,32] and vacating room by encryption (VRBE) [33,34,35,36,37,38,39,40].

RRBE-based methods adopt RDH methods in plaintext domain or high pixel correlation to obtain embedding room before image encryption. For example, Ma et al. [19] exploited the traditional RDH method to achieve self-embedding before encryption so as to obtain room for data embedding. In Reference [20], some pixels are estimated before image encryption and secret data is embedded into the estimated errors. In Reference [21], small image blocks are compressed by sparse representation to vacate room. Shiu et al. [22] exploited DE to transform two adjacent pixels into two odd or even pixels, and then adopted Paillier encryption [41] to encrypt pixels. The homomorphism of Paillier encryption assists data extraction and image recovery. In Reference [23], the mean values are preserved before encryption. Due to mean value preservation, data extraction and image recovery can be performed perfectly. Yu et al. [24] encrypted the pre-processed image generated by prediction and conducted data hiding with additive homomorphism. Nguyen et al. [25] selected smooth pixels according to a given threshold and four neighboring pixels before encryption. The middle bit-planes of the selected smooth pixels of encrypted image are accommodated for secret data. The RRBE-based RDHEI schemes can achieve good embedding performance, but they require extra pre-processing before image encryption, which increases computational cost for the content owner.

VRAE based methods use standard Advanced Encryption Standard (AES), Rivest Cipher 4 (RC4) encryptions to encrypt the original image directly and do not require extra pre-processing before image encryption. Thus, the VRAE based methods have more widespread application than the RRBE-based methods. In References [26,27], the original image is encrypted directly by using the stream cipher and the encrypted image is divided into several blocks. Three least significant bits (LSB) of half of the pixels in a block are flipped to embed a secret bit. In the receiver side, data extraction and image recovery are conducted by designing a fluctuation function. Liao and Shu [28] adopted data hiding scheme [26] to embed a secret bit into a block. To improve the accuracy of extracted data and recovered image, the locations of different pixels of a block are considered to design an evaluation of block complexity in their method. Qin and Zhang [29] elaborated a pixel selection strategy so that data hiding is performed by flipping the LSBs of fewer pixels and the visual quality of decrypted image can be improved. In the above methods, the receiver is required to perform data extraction and image recovery simultaneously. It means that, for these VRAE based methods [26,27,28,29], if the receiver only holds data-hiding key, he or she cannot extract secret data. To separate data extraction from image recovery, Zhang [30] first proposed separable RDHEI method. In this method, the stream cipher is exploited to directly encrypt the original image and the room for accommodating secret data is vacated by compressing the LSBs of the encrypted image. Qian et al. [31] adopted distributed source coding to compress the encrypted image to improve embedding performance. Wu and Sun [32] embedded secret bits into the encrypted image by using most significant bit (MSB) replacement technique. At the receiver’s side, a prediction technique is utilized to perform data extraction and image recovery.

Since pixel spatial correlation is disorganized by the stream cipher which leads to the maximum entropy of the image, it is extraordinary difficult to vacate room from the encrypted image by the stream cipher. Consequently, VRAE based methods achieve low embedding rate. To achieve high embedding rate, some researchers have designed VRBE based methods. In these methods, some specific encryption algorithms provide confidentiality for the image while keeping spatial redundancy in the encrypted image. Room for data hiding can be vacated from the encrypted image. Because the encrypted image has spatial redundancy, some RDH methods proposed in the plain domain can be introduced into RDHEI by VRBE, which can achieve better embedding performance than BBRE and VRAE. For example, Yin et al. [33] encrypted image by changing pixel locations and embedded secret data by the HS method. This method exists security loophole in the encrypted image due to only changing pixel locations. Yi et al. [34] encrypted the original image by two stages involving block permutation and stream cipher. The data hider embeds secret bits into the permuted blocks by using PEE after performing stream decipher. Di et al. [35] divided an original image into a series of blocks and encrypted all the pixels of a block by using the same key. Every encrypted pixel is divided into two components and the HS is adopted for data hiding in these two components. Xiao et al. [36] divided original image into blocks sized 2×2 and encrypted all the pixels of each block with same key and additive homomorphism. The pixel value ordering (PVO) strategy realizes data hiding in each block. Yu et al. [37] adopted key transmission for image encryption and shifted the histogram of two-layer encrypted pixel errors to embed secret data reversibly. Tang et al. [38] divided the original image into several blocks and encrypted all the pixels in a block using the same number so that pixel spatial correlation in a block is preserved. The encrypted image is compressed to vacate room for data hiding. In References [39,40], redundant space is transferred from the original image to the encrypted image. Secret bits are embedded into vacated room by sparse matrix encoding. These two methods achieve high embedding rate.

In this paper, an RDHEI method based on two-dimensional permutation and EMD is proposed. It is a VRBE method that keeps pixel spatial correlation so that data hiding can be achieved by EMD to improve embedding capacity significantly. The rest of the paper is organized as follows. Section 2 presents our separable RDHEI method. Section 3 provides the experimental results and evaluates the performance of the proposed method. Finally, the paper is concluded in Section 4.

2. Proposed Method

In this section, an effective separable RDHEI method is presented. Figure 1 illustrates the block diagram of the proposed method. The content owner encrypts the original image by using two-dimensional permutation, which consists of bit-plane permutation and block permutation according to the encryption key. The bit-plane permutation is achieved by Arnold transformation. According to the data-hiding key, the data hider embeds secret bits into the encrypted image by using EMD to generate a marked encrypted image. After receiving the marked encrypted image, the receiver can perform different operations according to the availability of encryption key and data-hiding key. If only data hiding key is available, the receiver can only perform data extraction. If only encryption key is available, the receiver can directly perform decryption to obtain a directly decrypted image, which is analogous to a noisy image. It is noted that the quality of the directly decrypted image can be further improved by using noise removal method [42]. If both keys are available, the receiver extracts the secret bits and recovers the original image perfectly.

2.1. Image Encryption

In this stage, the content owner encrypts an original image by using two-dimensional permutation, which consists of bit-plane permutation and block permutation. Note that bit-plane permutation and block permutation aim to scramble the original pixel values and the original pixel positions, respectively.

2.1.1. Bit-Plane Permutation

Suppose that I is an 8-bit original image sized H×W and I_{i, j} denote one pixel value of I, where 0 ≤ I_i,j ≤ 255,1 ≤ I ≤ H, and 1 ≤ j ≤ W. Since a pixel consists of 8 bits, the content owner divides I_{i, j} into 4 Most Significant Bits (MSB) and 4 Least Significant Bits (LSB), and then converts the 4 MSBs and 4 LSBs into two decimal numbers denoted by x_{i, j} and y_{i, j}, respectively. The numbers x_{i, j} and y_{i, j} can be obtained by

$$\{\begin{array}{c}{y}_{i,j}=I_{i,j}\mathrm{mod}16\\ x_{i,j}=\left(I_{i,j}-y_{i,j}\right)\mathrm{mod}16\end{array}$$

(1)

where the “mod” denotes the modulo operation and 0 ≤ x_{i, j} ≤ 15, 0 ≤ y_{i, j} ≤ 15. Then Arnold transform is employed to scramble x_i,j and y_{i, j} as follows.

$$\left(\begin{array}{c}{x}_{i,j}^{\prime }\\ y_{i,j}^{\prime }\end{array}\right)=\left(\begin{array}{c}11\\ 12\end{array}\right)\left(\begin{array}{c}{x}_{i,j}\\ y_{i,j}\end{array}\right)\left(\mathrm{mod}16\right)$$

(2)

where $x_{i,j}^{\prime }$ and $y_{i,j}^{\prime }$ represent the transformed values of x_i,j and y_i,j, respectively. Let $x_{i,j}^k$ and $y_{i,j}^k$ be transformed values of x_{i, j} and y_{i, j} after the Equation (2) is iterated k times. Thus, the permutated pixel value $I_{i,j}^k$ can be calculated via

$$I_{i,j}^k=16\times x_{i,j}^k+y_{i,j}^k$$

(3)

It is well-known that the Arnold transform has periodicity. Specifically, the original image will reappear after a certain number of iterations. Additionally, Arnold transform period has been studied by Reference [43] and the period of Equation (2) is 12 from Reference [43]. Since the period of Equation (2) is 12, there are 11 permutated images, which have different scrambled effects due to different iterations. To achieve the best scrambled effect for image encryption, correlation coefficient is adopted to evaluate correlation between the original image and its bit-plane permutated version with different k (1 ≤ k ≤11). It is defined as

$${\rho }_k=\frac{Cov\left(X,Y_k\right)}{\sqrt{D\left(X\right)}\sqrt{D\left(Y_k\right)}}$$

(4)

where X and Y_k denote the matrices of the original image and its bit-plane permutated version after k times iteration, respectively. Cov(X, Y_k) represents the covariance between X and Y_k. Additionally, D(X) and D(Y_k) represents the variances of X and Y_k, respectively. Suppose that |ρ_n| is the smallest correlation coefficient among {|ρ₁|, |ρ₂|,.., |ρ₁₁|} (|·| is the absolute function) and its corresponding index is n, which is the optimal iteration. Consequently, a bit-plane permutated image is generated after all the original pixels are conducted by using the Equation (2) with n iterations.

2.1.2. Block Permutation

To further enhance security of image encryption, block permutation is adopted to scramble the positions of all pixels of the bit-plane permutated image. The block permutation consists of a coarse-grained and a fine-grained permutation. The coarse-grained permutation is exploited to permute blocks within the image according to a random key K_c and the fine-grained permutation is exploited to permute pixels within each block. Specially, the bit-plane permutated image is divided into a series of non-overlapping blocks sized t × (t+1), and the number of blocks is N = ⌊H/t⌋ × ⌊W/(t+1)⌋, where ⌊^.⌋ denotes the rounding down operation. Considering key space and encryption security, the value of t should not be too large. The appropriate value of t may be 4, 8 or 16, thus block sizes are 4 × 5, 8 × 9 or 16 × 17. For fine-grained permutation, we design four kinds of closed Hilbert orders C₁, C₂, C₃, C₄ as shown in Figure 2a–d, respectively.

Let B_i (1 ≤ I ≤ N) be a block after coarse-grained permutation and b_i,_x,_ybe one pixel of B_i, where x and y denote the coordinates of b_i,_x,_y (1 ≤ x ≤ t, 1 ≤ y≤ t+1) in B_i. As Figure 2 illustrated, there are four kinds of closed Hilbert orders for B_i, thus we select a kind of closed Hilbert order for B_i by the logistic chaotic map which is defined as follows

c_i+1 = rc_i(1-c_i), 0≤r≤4, c_i∈(0,1)

(5)

where r is a control parameter, and the logistic map is in the chaotic state when 3.569945972 < r <4. In our paper, r is set as 3.689945977 and the initial value c₀ is regarded as key. The Equation (5) is calculated calculate 2N times repeatedly to generated a chaotic sequence {c₁, c₂,…, c_2N }. Since 0 < c_i <1, a binary sequence {⌊c₁⌋, ⌊c₂⌋,…, ⌊c_2N⌋ } can be obtained. This binary sequence is transformed into a sequence of digits in 4-ary notational system, denoted by {q₁, q₂,…, q_N}. Then we select a kind of closed Hilbert order for B_i from Figure 2 according to q_i, where 0 ≤ q_i ≤3 and 1 ≤ I ≤N. Note that if q_i = 0, C₁ is selected for B_i. If q_i = 1, C₂ is selected for B_i. If q_i = 2, C₃ is selected for B_i. If q_i = 3, C₄ is selected for B_i. After selecting a closed Hilbert order, a step size f_i is generated for B_i according to a random key K_f, where 0 ≤ f_i ≤ t × (t+1). Then all the pixels of B_i are put forward f_i step beginning with b_i,₁,₁ according to the selected closed Hilbert order, which realizes fine-grained permutation. Suppose that the image blocks after block permutation are $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$. Consequently, the final encrypted image I_e can be constructed by $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$. The encryption keys consist of iteration number n, K_c, c₀ and K_f. Figure 3 shows the final encrypted version with two-dimensional permutation.

2.2. Data Hiding in Encrypted Image

The data hider embeds secret bits into I_e according to pixel spatial correlation within blocks of the encrypted image. Firstly, I_e is divided into N non-overlapping blocks sized t × (t+1) by the data hider, denoted by $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$. Note that bit-plane permutation and block permutation are able to preserve spatial correlation and relative position between two adjacent original pixels with the block, the data hider can calculate adjacent encrypted pixel errors to construct an error histogram which is used for data hiding with EMD. Similar with most reversible data hiding, some auxiliary information is also generated in the proposed method, which is described in the Section 2.2.1 in detail. The data hider divides $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$ into two parts $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_r^{\prime }\right\}$ and $\left\{B_{r+1}^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$. The LSBs of $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_r^{\prime }\right\}$ is extracted to obtain a binary sequence S_LSB and replaced by the auxiliary information. Then S_LSB and secret bits are concatenated to form the embedded data to be embedded into $\left\{B_{r+1}^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$.

2.2.1. Error Histogram Generation

In this part, an error histogram is generated by calculating adjacent encrypted pixel errors of each block. We take $B_i^{\prime }$ (r+1 ≤ I ≤ N) as an example to describe the error histogram generation. The data hider randomly selects a pixel $b_{i,x,y}^{\prime }$ from $B_i^{\prime }$ according to a random key K_h. Then the data hider scans $B_i^{\prime }$ beginning with $b_{i,x,y}^{\prime }$ in a selected closed Hilbert order determined by the sharing key c₀ to generate a pixel sequence denoted by P_i={p_i,1, p_i,2,…, p_{i, m}}, m = t × (t+1). Then the adjacent pixel errors of P_i are calculated by.

$$e_{i,j}=\{\begin{array}{ll}{p}_{i,j},& j=1\\ p_{i,j-1}-p_{i,j},& 2\le j\le m\end{array}$$

(6)

where −255 ≤ e_{i, j} ≤ 255. By the same way, the adjacent pixel errors of $\left\{B_{r+1}^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$ are calculated and are concatenated to generate an error sequence denoted by E = {e₁,e₂,…,e_d}, where d = m × (N−1). Note that e_i,1 (r+1 ≤ I ≤ N) is excluded for concatenating and data hiding. Consequently, the histogram of E is generated. Figure 4 shows the error histogram of the encrypted Lena.

It can be observed that there are a wide variety of peak bins and zero bins in the histogram from Figure 4. Assume that the histogram bins and their numbers are denoted by {b_-255,…,b₀,…,b₂₅₅} and {n_-255,…,n₀,…,n₂₅₅}, respectively. For convenient observation, we magnify some parts of Figure 4 to exhibit the bins and their numbers as shown in Figure 5. It is observed from Figure 5a that b₀ is a peak bin, while b_-1 and b₁ are two zeros bin adjacent with bin b₀. The b_-2 and b₂ are two peak bins, while b_-3 and b₃ are two zero bins which are adjacent with bin b_-2 and b₂, respectively. Similarly, it is observed from Figure 5b that b_-36 is a peak bin, while b_-37 and b_-35 are two zeros bin adjacent with bin b_-36. The b_-38 is a peak bin, while b_-39 is a zero bin which is adjacent with bin b_-38. The other bins of Figure 4 have same properties. It is concluded that there is one zero bin between two peak bins at least and there is one zero bin adjacent with one peak bin in the error histogram in most cases. Peak bins and zero bins occur alternatively. Consequently, these peak bins are accommodated for data hiding. According to the property of the histogram, secret bits can be embedded into the encrypted image via EMD without histogram shifting.

2.2.2. Data Hiding with EMD

For clarity, we construct a histogram—as shown in Figure 6—the property of which is analogous with that of Figure 5 to illustrate our data hiding. In this histogram, the bins b₂, b₄, b₆, b₈ are four peak bins which are expanded for data hiding, while the bins b₁, b₃, b₅, b₇, b₉ are five zero bins which are vacated room for reversible data hiding. Since every peak bin can be expanded rightward and leftward, there are a series of expanding schemes for these peak bins. Due to page limitation, we only give two expanding schemes E₁ and E₂ as shown in Figure 6a and Figure 6b, respectively. In Figure 6a, the peak bins b₄ and b₈ can be both expanded rightward and leftward for data hiding and the bin b₂ can be only expanded leftward. The peak bin b₆ is unchanged to avoid ambiguity. In Figure 6b, the peak bin b₈ can be both expanded rightward and leftward for data hiding and the peak bins b₂, b₄, b₆ are only expanded leftward for data hiding. No matter which scheme, the zero bins are marked by a location map for avoiding ambiguity.

Based on the above analysis, every peak bin has two directions or only one direction to be expanded. Consequently, secret bits can be embedded into the peak bins using EMD which uses directional modification of data hiding. In the EMD method, a group of n pixels has different possible directions to embed secret bits according to designed extraction function. Then, data hiding can be performed as follows.

For E = {e₁,e₂,…,e_d}, let the bin b_k be a candidate peak bin for data hiding. We extract all the errors the values of which are equal with b_k from E to embed secret bits. All these errors are permuted into a series of error-pairs according to a random K_d. Suppose that e_i and e_j are a pair of errors and their marked errors are e_i^′ and e_j^′, respectively. Since there are three expanding cases for embedding bin b_k which are only expanding leftward, only expanding rightward and expanding both leftward and rightward, there are three corresponding embedding methods as follows.

1. Only expanding leftward

If b_k is only expanded leftward, it means the errors whose values are equal with b_k can be decreased by 1 or unchanged during data hiding. For a pair (e_i, e_j), e_i = e_j = b_k, we embed two secret bits into (e_i, e_j). Two secret bits are transformed into a secret digit s (0 ≤ s ≤ 3). In this case, the extraction function f₁ is defined as

f₁(a,b)=(a+2×b) mod 4

(7)

If e_i^′ and e_j^′ satisfy the conditions s=f₁(e_i^′, e_j^′) and $\{\begin{array}{c}{b}_k-1\le e_i^{\prime }\le b_k\\ b_k-1\le e_j^{\prime }\le b_k\end{array}$, s can be embedded by f₁(a,b). Consequently, (e_i^′, e_j^′) can be obtained as follows.

① If s = f₁(e_i^′, e_j^′), e_i^′ = b_k and e_j^′ = b_k; ② If s = f₁(e_i^′–1, e_j^′), e_i^′ = b_k–1 and e_j^′ = b_k;

③ If s = f₁(e_i^′, e_j^′–1), e_i^′ = b_k and e_j^′ = b_k–1; ④ If s = f₁(e_i^′–1, e_j^′–1), e_i^′ = b_k–1 and e_j^′ = b_k–1;

By the same way, other secret bits can be embedded into other pairs.

2. Only expanding rightward

If b_k is only expanded rightward, it means the errors whose values are equal with b_k can be increased by 1 or unchanged during data hiding. For a pair of errors (e_i, e_j), e_i = e_j = b_k, we embed two secret bits into (e_i, e_j). Two secret bits are transformed into a secret digit s(0 ≤ s ≤ 3). In this case, Equation (7) is exploited as the extraction function. If e_i^′ and e_j^′ satisfy the conditions s = f₁(e_i^′, e_j^′) and $\{\begin{array}{c}{b}_k\le e_i^{\prime }\le b_k+1\\ b_k\le e_j^{\prime }\le b_k+1\end{array}$, s can be embedded by f₁(a,b). Consequently, (e_i^′,e_j^′) can be obtained as follows.

① If s = f₁(e_i^′, e_j^′), e_i^′ = b_k and e_j^′ = b_k; ② If s = f₁(e_i^′+1, e_j^′), e_i^′ = b_k+1 and e_j^′ = b_k;

③ If s = f₁(e_i^′, e_j^′+1), e_i^′ = b_k and e_j^′ = b_k+1; ④ If s = f₁(e_i^′+1, e_j^′+1), e_i^′ = b_k+1 and e_j^′ = b_k+1;

By the same way, other secret bits can be embedded into other pairs.

3. Expanding both leftward and rightward

If b_k can be both expanded leftward and rightward, it means the errors whose values are equal with b_k can be increased by 1, decreased by 1 or unchanged during data hiding. For a pair (e_i, e_j), e_i=e_j=b_k, we embed three secret bits into (e_i, e_j). Three secret bits are transformed into a secret digit s (0≤s≤7). According to the algorithm [7], the extraction function f₂ is defined as

f₂(a,b)=(a+3×b) mod 8

(8)

If e_i^′ and e_j^′ satisfy the conditions s=f₂(e_i^′, e_j^′) and $\{\begin{array}{c}{b}_k-1\le e_i^{\prime }\le b_k+1\\ b_k-1\le e_j^{\prime }\le b_k+1\end{array}$, s can be embedded by f₂(a,b). Consequently, (e_i^′,e_j^′) can be obtained as follows.

① If s= f₂(e_i^′, e_j^′), e_i^′= b_k and e_j^′= b_k; ② If s= f₂(e_i^′+1, e_j^′), e_i^′= b_k+1 and e_j^′= b_k;

③ If s= f₂(e_i^′–1, e_j^′), e_i^′= b_k–1 and e_j^′= b_k; ④ If s= f₂(e_i^′, e_j^′+1), e_i^′= b_k and e_j^′= b_k+1;

⑤ If s= f₁(e_i^′, e_j^′–1), e_i^′= b_k and e_j^′= b_k–1; ⑥ If s= f₁(e_i^′+1, e_j^′+1), e_i^′= b_k+1 and e_j^′= b_k+1;

⑦ If s= f₁(e_i^′+1, e_j^′–1), e_i^′= b_k+1 and e_j^′= b_k–1; ⑧ If s= f₁(e_i^′–1, e_j^′+1), e_i^′= b_k–1 and e_j^′= b_k+1;

By the same way, secret data can be embedded into other pairs.

Overall, if b_k is only expanded leftward or rightward, two secret bits can be embedded into a pair of errors. Otherwise, three secret bits can be embedded into a pair of errors. Consequently, we prefer to select the peak peaks with more numbers to be both expanded leftward and rightward for obtaining more embedding capacity as follows. The bin numbers {n_-255,…,n₀,…,n₂₅₅} are sorted in stable descending order to obtain {n_σ(1), n_σ(2),…, n_σ(511)} and their corresponding bins are {b_σ(1), b_σ(2),…, b_σ(511)}, where σ(i) ∈ {−255,−254,…,254,255} and σ:{1,2,…,511} → {1,2,…,511} is the unique one-to-one mapping such that: n_σ(1) ≥ n_σ(2) ≥…≥ n_σ(511). In order to achieve high payload, the bins with more numbers among {b_σ(1), b_σ(2),…, b_σ(511)} are selected to be both expanded leftward and rightward in priority. Let the embedding capacity be l_EC. First an empty set S is initiated and the expanded bins are stored in S which can be obtained by the following details. A counter c is used for calculating the payload and its initial value is 0. Beginning with i = 1, it is clear that the bin the bin b_σ(1) can be both expanded leftward and rightward and b_σ(1) is appended with S. c = c+3×n_σ(1)/2 and i = i+1. If i > 1, the expanding rules of b_σ(i) are determined by | b_σ(i) − b_σ(j) | and can be classified into three cases, where j = 1,2,…i-1.

1) If (∀j)| b_σ(i)–b_σ(j) | > 2, the bin b_σ(i) can be both expanded leftward and rightward and b_σ(i) is appended with S. Additionally, c = c +3×n_σ(i)/2.

2) If (∃j) | b_σ(i)–b_σ(j) | = 2 and (∀k) | b_σ(i)–b_σ(k) | > 2, where k = 1,2,…i and k ≠ j. The bin b_σ(i) can be expanded leftward or rightward. If b_σ(i) > b_σ(j), the bin b_σ(i) can be expanded rightward. Otherwise, the bin b_σ(i) can be expanded leftward. b_σ(i) is appended with S and c = c+n_σ(i).

3) If b_σ(i) does not satisfy the above condition, b_σ(i) is skipped.

Repeat the above process until c ≥ l_EC. We take Figure 6a as an example to illustrate the generation of S. It is clear that {n₈, n₄, n₂, n₆} and {n₃, n₅, n₁, n₇, n₉} are the peak bins and zero bins, respectively. The sorted bin numbers are {n₈, n₄, n₂, n₆, n₃, n₅, n₁, n₇, n₉} and the corresponding bins are {b₈, b₄, b₂, b₆, b₃, b₅, b₁, b₇, b₉}. According to the above expanding rules, the first peak bin b₈ can be both expanded leftward and rightward and b₈ is appended with S. For the second peak bin b₄, it is clear that b₈ − b₄ > 2, thus b₄ can be both expanded leftward and rightward and b₄ is appended with S. For the third peak bin b₂, there is a bin b₄ which satisfies b₄ − b₂ = 2. Thus, b₂ can be only expanded leftward and b₂ is appended with S. For the fourth bin b₆, there are b₄ and b₈ which satisfy the condition b₈ − b₆ = 2 and b₄ − b₆ = −2. Thus, b₆ remains unchanged. Consequently, S consists of b₈, b₄, b₂. After obtaining S, secret bits are embedded into the errors of E by expanding the bins from the set S in order according to the embedding method and suppose that the marked error sequence is E^′={e₁^′,e₂^′,…,e_d^′}. Then these marked errors can be mapped to the marked errors in each block. Consequently, the marked pixels in $\left\{B_{r+1}^{\prime \prime },B_2^{\prime \prime },\dots ,B_N^{\prime \prime }\right\}$ are generated by

$$p_{i,j}^{\prime }=\{\begin{array}{ll}{p}_{i,j},& j=1\\ p_{i,j-1}-e_{i,j}^{\prime },& 2\le j\le m\end{array}$$

(9)

where r+1 ≤ i ≤ N. In order to blind extraction, some auxiliary information is required to be embedded into the encrypted and it is described as follows. The overflow/underflow problem may occur since the pixel value 0 or 255 may be modified to −1 or 256, respectively. To address this problem, we utilize a location map LM with the same size of the encrypted image to mark those pixels with value 0 or 255. For each encrypted pixel, if its value is 0 or 255, it is marked with 1 in LM and skipped for data hiding. Otherwise, it is marked with 0 in LM. Meanwhile, the pixels with the zero bins are also marked with 1 in LM. To reduce the size of LM, LM is losslessly compressed and its compressed version is denoted as L_clm and the size of L_clm is l_clm. Since the peak bins vary from −255 to 255, each peak bin can be represented 9 bits and the first bit is a sign bit. The bins are almost evenly divided into the peak bins and zero bins as shown in Figure 6, thus the maximum size L_s of S is 9 × 255. Since most pixels of encrypted image are used for data hiding and three bits are embedded into two pixels, 3/2 × log₂HW bits are enough to represent the embedding capacity l_EC. In summary, the auxiliary information consists of three sections:

✶

The compressed location map L_clm (l_clm bits)

✶

The expanded bin set S (L_s bits)

✶

The embedding capacity l_EC (3/2 × log₂HW bits)

The auxiliary information is embedded into the LSBs of $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_r^{\prime }\right\}$ by using LSB replacement technique to generate the marked blocks $\left\{B_1^{\prime \prime },B_2^{\prime \prime },\dots ,B_r^{\prime \prime }\right\}$. Finally, a marked encrypted image I_w can be obtained by $\left\{B_1^{\prime \prime },B_2^{\prime \prime },\dots ,B_N^{\prime \prime }\right\}$.

2.3. Data Extraction and Image Recovery

With a marked encrypted image I_w, the receiver can perform different operations involving data extraction, image decryption and image recovery according to the availability of the encryption key and the data-hiding key.

If only encryption key is available for the receiver, he can directly decrypt I_w to obtain a noise-like image which can be filtered to generate an image with remarkable quality. Specifically, the receiver divides I_w into a series of non-overlapping blocks with t × (t+1) size. Since each original pixel is encrypted by iterating n times using Equation 2, the marked encrypted pixels can be decrypted by iterating 12-n times using Equation 2 to generate the directly decrypted pixels. After directly decrypting pixels, inverse coarse-grained permutation and fine-grained permutation are performed to recover the positions of those pixels. Consequently, a directly decrypted image is generated. Note that the encrypted pixels may increase by 1, decrease by 1 or keep unchanged during data hiding. Those marked encrypted pixels which keep unchanged can be decrypted to obtain corresponding original pixels without errors. While, the decrypted pixels by decrypting those marked, encrypted pixels directly which increase by 1 or decrease by 1 may be far away from the corresponding original pixels. We take an original pixel value 95 as an example for illustrating decryption. The original pixel value 95 is iterated 7 times using Arnold transform to generate the encrypted pixel value 75. Note that 75 may be modified as 74, 75 or 76 after data embedding. In direct decryption process, the marked pixel value 74, 75 or 76 is decrypted by iterating 5 times using Equation 2 to obtain 230, 95 or 200, respectively. It is clear that 95 is a desired decryption value, while 230 and 200 can be regarded as the noises which will bring large distortion for image. That is to say, our directly decrypted image may contain noises. Let the numbers of expanded bins with one direction in S be $\left\{n_1^1,n_2^1,\dots ,n_u^1\right\}$ and the numbers of expanded bins with two directions be $\left\{n_1^2,n_2^2,\dots ,n_v^2\right\}$. The number of noises in the directly decrypted image is estimated as

$$Q\approx \frac{1}{2}{\displaystyle \sum }_{i=1}^u{n}_i^1+\frac{5}{8}{\displaystyle \sum }_{i=1}^v{n}_i^2$$

(10)

where $\frac{1}{2}{\displaystyle \sum }_{i=1}^u{n}_i^1$ and $\frac{5}{8}{\displaystyle \sum }_{i=1}^v{n}_i^2$ are the noise estimations of expanded bins with one direction and two directions respectively according to our data hiding method. Our noise mode can be regarded as uniform impulse noise and can be detected with high detection rate [44]. For a directly decrypted image, different from the previous methods, we adopt an outstanding filter method [42] to improve visual quality of the directly decrypted image significantly.

If only data-hiding key is available for the receiver, he can extract the error-free secret bits from I_w and recover the encrypted image losslessly. The receiver also divides I_w into a series of non-overlapping blocks $\left\{B_1^{\prime \prime },B_2^{\prime \prime },\dots ,B_N^{\prime \prime }\right\}$ and retrieves the auxiliary information from the LSBs of the blocks $\left\{B_1^{\prime \prime },B_2^{\prime \prime },\dots ,B_r^{\prime \prime }\right\}$ to obtain the compressed location map L_clm, the expanded bin set S and the embedding capacity l_EC. L_clm is decompressed to generate LM. We also take $B_i^{\prime \prime }$ (r+1 ≤ i≤N) as an example to describe the marked error generation and data extraction. The receiver scans $B_i^{\prime \prime }$ beginning with $b_{i,x,y}^{\prime \prime }$ in a selected closed Hilbert order determining by the sharing key c₀ to generate a pixel sequence denoted by $P_i^{\prime }=\left\{p_{i,1}^{\prime },p_{i,2}^{\prime },\dots ,p_{i,m}^{\prime }\right\}$. If $p_{i,j}^{\prime }$ is marked with 1 in LM, $p_{i,j}^{\prime }$ is skipped for data extraction and the original pixel can be recovered as $p_{i,j}=p_{i,j}^{\prime }$. Otherwise $p_{i,j}^{\prime }$ is used for data extraction. The marked errors in $\left\{B_{r+1}^{\prime \prime },B_{r+2}^{\prime \prime },\dots ,B_N^{\prime \prime }\right\}$ are generated by

$$e_{i,j}^{\prime }=\{\begin{array}{ll}{p}_{i,j},& j=1\\ p_{i,j-1}-p_{i,j}^{\prime },& 2\le j\le m\end{array}$$

(11)

Then the expanded bins are selected from S to assist data extraction. The expanding method for the bin S_(k) can be decided by the expanding rules, where 1 ≤ k ≤ u+v. If the bin S_(k) can be only expanded leftward or expanded rightward and $e_{i,j}^{\prime }=\left\{S_{\left(k\right)},S_{\left(k\right)}-1\right\}$ or $e_{i,j}^{\prime }=\left\{S_{\left(k\right)},S_{\left(k\right)}+1\right\}$, the original error can be recovered as e_i,j = S_(k). If the bin S_(k) can be both expanded leftward and expanded rightward and $e_{i,j}^{\prime }=\left\{S_{\left(k\right)},S_{\left(k\right)}-1,S_{\left(k\right)}+1\right\}$, the original error can be recovered as e_i,j = S_(k). Then the original encrypted pixel can be recovered as

p_{i, j} = p_{i, j-1}- e_{i, j}

(12)

Thus, the encrypted pixels in $\left\{B_{r+1}^{\prime },B_{r+2}^{\prime },\dots ,B_N^{\prime }\right\}$ can be recovered losslessly. The marked error sequence E^′={e₁^′,e₂^′,…,e_d^′} for the $\left\{B_{r+1}^{\prime },B_{r+2}^{\prime },\dots ,B_N^{\prime }\right\}$ can be obtained using Equations (11–12). For a pair of extracted marked errors in this sequence, if the corresponding bin can be only expanded leftward or expanded rightward, a secret digit can be extracted by Equation (7). Otherwise, a secret digit can be extracted by Equation (8). After data extraction, the embedded data is split into S_LSB and the secret bits. The LSBs of $\left\{B_1^{\prime \prime },B_2^{\prime \prime },\dots ,B_r^{\prime \prime }\right\}$ is replaced by S_LSB to recover $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_r^{\prime }\right\}$. Consequently, the encrypted image can be recovered by $\left\{B_1^{\prime },B_2^{\prime },\dots ,B_N^{\prime }\right\}$.

If the data-hiding key and the encryption key are both available for the receiver, he or she extracts secret data from the marked encrypted image and recovers the encrypted image losslessly according to the data-hiding key. Then, with the encryption key, he or she is able to decrypt the encrypted image to obtain the original image.

3. Experimental Results

In this section, six 512 × 512 standard images as shown in Figure 7 are used to validate our encryption and embedding performances. The encryption performance is evaluated by key space and the statistical security. Additionally, the superiority of the directly decrypted image quality and embedding capacity are illustrated. Section 3.1 analyzes our image encryption performance and we set t=8 for illustrating it. Section 3.2 provides comparison results with other methods to evaluate our embedding performance.

3.1. Encryption Performance

The encryption security is decided by the size of key space. Generally, the larger the size of key space is, the more security the algorithm has. Our encryption key consists of iteration time n, K_p, c₀ and K_f, where K_p and K_f are two random keys and their precisions are both 64. It is obvious that the key space of iteration time is 11 in our paper. In coarse-grained permutation, the image blocks are permuted by the key K_p with 64 bits storage and the number of possible scenarios for block permutation is N!. If the block number N > 21, N! > 2⁶⁴ and the key space is 2⁶⁴. Otherwise, the key space is N!. Thus, the valid key space is min (2⁶⁴, N!) for coarse-grained permutation. Since c₀ is a floating number with 64 bits storage, the key space of c₀ is 2⁶⁴. In fine-grained permutation, there are four closed Hilbert orders for a block and the number of possible scenarios of closed Hilbert orders is 4^N, thus the valid key space is min (2⁶⁴, 2^N). Furthermore, all the pixels of one block are put forward f_i step decided by K_f, the number of selected step sizes is (t × (t+1))^N, the valid key space is min (2⁶⁴, (t × (t+1))^N). Overall, the whole key space of the proposed encryption method is 11 × (2⁶⁴, N!) × min (2⁶⁴, 4^N) × min (2⁶⁴, (t × (t+1))^N). For Lena in Figure 2, if t = 8, the number of blocks is N = 3584, the key space is 11 × 2⁶⁴ × 2⁶⁴ × 2⁶⁴ = 11 × 2¹⁹², which is able to resist brute-force attacks [4].

Histogram analysis for our encryption method is presented. An image histogram illustrates the distribution of the pixel values. The histograms of the original images and their encrypted versions are exhibited in Figure 8 and Figure 9, respectively. It is observed that the histogram of each encrypted version is entirely different from the histogram of corresponding original image. Consequently, our encryption method can withstand statistical attacks.

We use correlation coefficient and peak signal-to-noise ratio (PSNR) between the original image and the encrypted image to evaluate the quality of the encrypted image. Correlation coefficient is defined as Equation (4) and PNSR is defined as follows.

$$\mathrm{PSNR}=10\times lo{g}_{10}\left(\frac{{255}^2}{\mathrm{MSE}}\right)$$

(13)

Where MSE represents the mean square error between the original image and its encrypted version. The evaluated results are shown in

Table 1. Correlation coefficient, PSNR values between original and encrypted images using proposed scheme.

Image	PSNR	Correlation Coefficient
Lena	9.2405	−0.0039835
Boats	9.1853	−0.0068682
Peppers	8.4256	−0.003959
Airplane	7.9554	−0.000215
Barbara	9.1159	0.00063109
Baboon	9.5364	0.0013209

. Low PSNR demonstrates that no content of the original image can be retrieved from its encrypted version. The correlation coefficients are all closed to 0, which clearly demonstrate that the encrypted images are rarely correlated with the original images and no information leakage from the encrypted images in case of statistical attacks. Overall, these analyses demonstrate that the proposed encryption securely protects the content of the original image.

3.2. Embedding Performance Comparisons

The embedding performance of the proposed method is demonstrated by comparing it with some state of art RDHEI methods [19,25,30,34,35,36,37], where Ma’s method [19], Nguyen’s method [25] are based on RRBE framework and Zhang’s method [30] is based on VRAE framework. Yi’s method [34], Di’s method [35], Xiao’s method [36] and Yu’s method [37] are based on VRBE framework. The compared methods [19,25] use standard stream cipher to encrypt image after preprocess and the compared method [30] exploits standard stream cipher to directly encrypt image. The compared method [36] adopts standard homomorphic encryption to encrypt image. The other compared methods [34,35,37] designed specific encryption to encrypted image. Comparisons are performed from two aspects including the highest embedding capacity and the visual quality of directly decrypted image. If only the encryption key is available for the receiver, our method is able to improve the visual quality of directly decrypted image by filtering, while the other methods cannot. In aspect of comparison for the visual quality of directly decrypted image, we take our improved directly decrypted image for comparison.

In our paper, the block sizes have three cases, 4 × 5, 8 × 9, 16 × 17,

Table 2. Pure embedding capacity under different block sizes (bpp).

Image	4×5	8×9	16×17
Lena	1.2078	1.2406	1.2711
Boats	1.2032	1.2359	1.2625
Peppers	1.1754	1.2097	1.2397
Airplane	1.185	1.2214	1.253
Barbara	0.9723	1.009	1.0407
Baboon	0.7685	0.7534	0.8149

shows the pure embedding capacity of each image except the auxiliary information under different block sizes. It is observed that when block size is 16×17, the pure highest embedding capacity for each image can be obtained. This is because that one pixel of each encrypted block is excluded for data hiding. The smaller the block size is, the more pixels are excluded for data hiding. Consequently, the optimal size is 16×17 for embedding capacity. Moreover, the pure embedding capacity of an image is decided by the image content. The images with fewer textures (Lena, Boats et al.) will generate more peak bins and less zero bins which are recorded by the location map. The fewer the auxiliary information is, the higher the pure embedding capacity will be. The images with more textures (Baboon et al.) will generate more zero bins and more auxiliary information decreases the pure embedding capacity. Thus, the images with fewer textures achieve higher pure embedding capacities than the images with more textures (Baboon).

To demonstrate the embedding capacity advantage of the proposed method, we compare our highest embedding capacity with those of six methods and comparison results are shown in

Table 3. Highest embedding capacity comparisons among different methods (bpp).

Methods	Ma [19]	Nguyen [25]	Zhang [30]	Yi [34]	Di [35]	Xiao [36]	Yu [37]	Proposed
Lena	0.5	0.1570	0.033	0.5	0.8412	0.2368	0.5343	1.2711
Boats	0.5	0.1040	0.041	0.5	0.7515	0.1451	0.5875	1.2625
Peppers	0.5	0.1580	0.022	0.4	0.7250	0.2125	0.4587	1.2397
Airplane	0.4	0.2790	0.040	0.5	1.0349	0.2649	0.6914	1.2530
Barbara	0.5	0.1310	0.020	0.5	0.7268	0.1362	0.4990	1.0407
Baboon	0.5	0.0340	0.010	0.4	0.651	0.1012	0.2314	0.8149

. It demonstrates that the embedding capacity of the proposed method is highest and the embedding capacity of Zhang [30] is lowest among the compared methods. In Reference [30], an original image is encrypted directly by standard stream cipher which disorganizes spatial pixel correlation. Thus, the method [30] achieves lowest embedding capacity. For all test images excluding Baboon, the highest pure embedding capacity of the proposed method exceeds 1 bpp. For example, for Lena, the maximum EC is 1.2711 bpp. However, the highest embedding capacities of the other compared methods are all less than 1 bpp. The embedding capacity of Ma [19] is similar with that of Yi [34]. The methods of Di [35] and Xiao [36] are both based on block encryption and all pixels in a block are encrypted with same key. In Xiao’s method [36], PVO is adopted to calculate prediction errors and secret bits can be only embedded into the maximum value and the minimum value of a block. Thus, their embedding capacity is limited. Di et al. calculated the pixel errors between one pixel and other pixels in a block, secret bits can be embedded by prediction-error histogram shifting (PEHS). Since most pixels of one block can accommodate secret bits, they achieve more EC than Xiao et al.

From the aspect of comparison for directly decrypted image, the capacity-distortion curves are adopted for embedding performance comparison, as shown in Figure 10. The distortion of directly decrypted image is evaluated by PNSR. It is observed from Figure 10 that the embedding performance of the method [30] underperforms the other methods due to the limitation of VRAE framework. The embedding performance of the proposed method outperforms those of the compared methods [19,25,35,36,37] for Boat, Peppers and Barbara when embedding capacity exceeds 0.1 bpp. Moreover, with embedding capacity increases, our method achieves more advantage due to remarkable image recovery efficiency. For Airplane, our capacity-distortion performance outperforms the other compared methods except for Yi et al. [34]. However, the embedding capacity of Yi et al. is limited under 0.5 bpp. For Lena, if embedding capacity is 0.1 bpp, the PSNR of Xiao [36] is higher than ours. When EC exceeds 0.2 bpp, our embedding performance outperforms those of all the compared methods. For Baboon, our embedding performance underperforms some compared methods [19,25,34,36], especial for low embedding capacity. However, when embedding capacity exceeds 0.3 bpp, our method achieves more advantage. Although RRBE-based methods [19,25] can achieve a relatively good performance, the content owner need to conduct an extra preprocess before encryption to vacate room for secret bits. In fact, the content owner may not want to perform this extra preprocess during encryption and/or may not know that secret bits will be embedded into the encrypted image. Furthermore, vacating room from the plain image is effortless than the encrypted image due to the high correlation within pixels of the plain image and the low correlation within pixels of the encrypted image. The proposed method is based on VRBE and the superiority of improved directly decrypted image in our paper is ascribed to remarkable filtering method [42]. In short, Figure 10 demonstrates that the proposed method is better than the compared methods in embedding performance in most cases especially for large embedding capacity.

4. Conclusions

In this paper, a separable RDHEI method based on two-dimensional permutation and EMD has been proposed. We first design an image encryption method which consists of block permutation and bit-plane permutation. It provides confidentiality for image while keeping pixel correlation in the encrypted image. Then an error histogram with peak bins and zero bins occurring alternatively is constructed to accommodate for secret bits. Due to the property of the histogram, different EMD methods are adopted for hiding data without HS in order to improve embedding capacity significantly. Different from the previous methods, our method can significantly improve the quality of the directly decrypted image by using this remarkable filtering method. Experimental and comparison results show that the proposed method is better than the several compared methods in terms of the embedding rate and quality of the directly decrypted image.