Block-Permutation-Based Encryption Scheme with Enhanced Color Scrambling

Abstract

This paper proposes an extension of block-permutation-based encryption (BPBE) for the encryption-then-compression (ETC) system, which is more robust against some possible attacks compared to the conventional BPBE schemes. After dividing the original image into multiple blocks, the conventional schemes generate an encrypted image through four processes: positional scrambling, block rotation/inversion, negative-positive transformation, and color component shuffling. The proposed scheme achieves enhanced color scrambling by extending three of the four processes. The resilience against jigsaw puzzle solving problems can be consequently increased. The key space against brute-force attacks has also been expanded exponentially. Our scheme can maintain approximately the same compression efficiency compared with that of the conventional schemes.

1 Introduction

Due to the rapid progress of information and communications technology, privacy and copyright protection for digital images has been a serious concern in cloud services, social networking services, and so forth. One of the traditional techniques to securely transmit images is a compression-then-encryption (CTE) system, which performs compression before encryption. However, the image owner has to disclose the image content to a network provider in the CTE system. For this reason, another technique for secure image transmission, that is, an encryption-then-compression (ETC) system, has been studied as the framework where encryption is performed by the image owner before compression/transmission [1,2,3]. The symmetric key cryptosystems, such as AES and Triple DES, are frequently used for image protection. However, there is a trade-off between security and additional signal processing in the encryption domain for image transmission systems. Because of this, soft encryption schemes have also been studied.

Block-permutation-based encryption (BPBE) [4,5,6] first divides the original image into definite size blocks and performs four processes: positional scrambling, block rotation/inversion, negative-positive transformation, and color component shuffling. However, it processes the R, G, and B components identically in each process, and the color distribution of the original image strongly affects that of its encrypted image.

Jigsaw puzzle solvers (JPSs) [7,8,9,10] are attacks that aim to retrieve the original image from a large number of pieces by utilizing the correlation among them. Because BPBE images consist of multiple blocks, those blocks can be assumed to be the puzzle pieces, and JPSs should be considered as one type of attacks for BPBE schemes. It has been reported that a jigsaw puzzle consisting of 30,745 pieces can be solved completely by using the conventional JPS [9]. Another JPS has successfully solved a puzzle where the directional information of each piece was not known [10]. It has been confirmed that some encryption schemes, where the key spaces are large enough to protect against brute-force attacks, are still vulnerable to JPSs [11]. On the other hand, it has been confirmed that conventional JPSs can hardly ever solve a jigsaw puzzle where the color distribution is modified.

In this paper, we propose an extended BPBE algorithm to deal with the above problem. The proposed scheme processes the three color components independently in each process. As a consequence, the color distribution of the original image does not severely affect that of its encrypted image in our scheme. Owing to the proposed algorithm, the security against some possible attacks can be improved. We confirm that the compression efficiency of JPEG-LS [12] in the proposed scheme is approximately the same as that of the conventional schemes.

2 Block-Permutation-Based Encryption [4,5,6]

By encrypting the original images before sending them to the provider, the image owner does not need to disclose the image content to a network provider. As shown in Fig. 1, the conventional BPBE algorithms [4,5,6] first divide the original image into definite size blocks and then execute four processes: positional scrambling, block rotation/inversion, negative-positive transformation, and color component shuffling. Finally, they integrate the blocks into one encrypted image. The noteworthy advantage of BPBE is that the compression efficiency of the encrypted images can be maintained high compared to that of the original images. The BPBE schemes can also control the quality of the encrypted image and the encryption strength by changing the block size. The encryption procedure is as follows.

Fig. 1.

Block-permutation-based encryption procedure.

 

Step 1: :

Divide an original image $I =\{I_R, I_G, I_B\}$ with $M \times N$ pixels into multiple blocks with $B_x \times B_y$ pixels.

Step 2: :

Scramble the position of each block using a random number generated by key $K_1$.

Step 3: :

Rotate and invert each block using random numbers generated by keys $K_2$ and $K_3$.

Step 4: :

Perform negative-positive transformation on each block using a random number generated by key $K_4$.

Step 5: :

Shuffle the R, G, and B components in each block using a random number generated by key $K_5$.

Step 6: :

Integrate all the blocks and generate the encrypted image.

 

Note that the keys $K_1$, $K_2$, $K_3$, and $K_4$ are commonly used for the three color components in the conventional schemes. We explain the main four processes in detail below.

2.1 Positional Scrambling

According to a random number generated by key $K_1$, the positions of the divided blocks are shuffled. Note that the R, G, and B components in each block are identically shuffled by commonly using $K_1$.

2.2 Block Rotation and Inversion

As shown in Fig. 2(a), each block, where $B_x = B_y$ is supposed, is rotated 0, 90, 180, or 270 degrees using a random number generated by key $K_2$. Figure 2(b) shows the block inversion process. Each block is decided to be inverted horizontally and/or vertically or is not inverted according to a random number generated by key $K_3$. Note that the R, G, and B components in each block are identically rotated and inverted by commonly using $K_2$ and $K_3$.

Fig. 2.

Block rotation and inversion.

2.3 Negative-Positive Transformation

The negative-positive transformation reverses all of the pixel values in a block according to a random number of either zero or one, which is generated by key $K_4$. The transformed pixel value $p'$ is obtained by

$$\begin{aligned} p'=\left\{ \begin{array}{ll} p &{} (r(i)=0) \\ 255-p &{} (r(i)=1), \\ \end{array} \right. \end{aligned}$$

(1)

where p is the original pixel value and r(i) is a random integer given for the i-th block by using $K_4$. Note that the R, G, and B components in each block are identically transformed by commonly using $K_4$.

2.4 Color Component Shuffling

The color component shuffling is the operation that changes the R, G, and B components in each block according to a random number in the range of zero to five, which is generated by key $K_5$. It is operated as shown in Table 1.

Table 1. Color component shuffling.

Fig. 3.

Encrypted image obtained by conventional scheme [5].

Figure 3 shows the original image and its encrypted image where all of the operated blocks have been integrated. The conventional schemes not only change the spatial positions and directions but also reverse the pixel values and changes the three color components in each block. However, the color distribution of the original image directly affects that of the encrypted image. It is assumed to be vulnerable to jigsaw puzzle solvers (JPSs). In the next section, we propose an extended BPBE approach to decrease the effect of the color distribution of the original image.

3 Proposed Scheme

We propose an extended BPBE scheme to improve security against some possible attacks. In the conventional schemes [4,5,6], the color distribution of the original image strongly affects that of its encrypted image. The proposed scheme aims to solve the above problem by expanding the number of random numbers used in three of the four processes, namely, positional scrambling, block rotation/inversion, and negative-positive transformation, without severe degradation of the compression efficiency. Note that the procedure of the BPBE is the same as that of the conventional schemes, which is shown in Fig. 1.

Fig. 4.

Negative-positive transformation in conventional schemes [4,5,6] where $\{x_R, x_G, x_B\} = \{255, 255, 255\}$.

Fig. 5.

Negative-positive transformation in proposed scheme where $\{x_R, x_G, x_B\} = \{255, 255, 255\}$.

As described in Sect. 2, the keys $K_1$, $K_2$, $K_3$, and $K_4$ for the three processes are commonly used for the R, G, and B components in the conventional schemes. In other words, the three color components in each block are identically operated. The proposed scheme prepares three keys for each process, e.g., $K_{1,R}$, $K_{1,G}$, and $K_{1,B}$ for positional scrambling and independently operates the three color components. We give a detailed account using the negative-positive transformation as follows.

Here, we make a concrete example of the negative-positive transformation. In the conventional schemes, this transformation is identically operated for the three color components by using a random number of either zero or one, which is generated by key $K_4$. In the case when pixel x has the values $\{x_R, x_G, x_B\} = \{255, 255, 255\}$, they are changed to $\{x'_R, x'_G, x'_B\} = \{0, 0, 0\}$ or are not changed, that is, $\{x'_R, x'_G, x'_B\} = \{255, 255, 255\}$, as shown in Fig. 4. On the other hand, the proposed scheme prepares three random numbers of either zero or one, which are generated by three keys $K_{4,R}$, $K_{4,G}$, and $K_{4,B}$. The three color components are operated independently according to the random numbers. In the case of the above example where $\{x_R, x_G, x_B\} = \{255, 255, 255\}$, they could be changed to $\{x'_R, x'_G, x'_B\} = \{0, 0, 0\}$, $\{255, 0, 0\}$, $\{0, 255, 0\}$, $\{0, 0, 255\}$, $\{255, 255, 0\}$, $\{255, 0,$ $255\}$, $\{0, 255, 255\}$, or $\{255, 255, 255\}$, as shown in Fig. 5.

In the proposed scheme, the color information is consequently more scrambled than in the conventional schemes. In the next section, we will demonstrate and evaluate the effectiveness of our algorithm.

4 Experimental Results and Analysis

We evaluate the proposed BPBE algorithm from the aspects of the color scrambling, compression efficiency, and resilience against brute-force attacks/JPSs. The four $512 \times 512$ images, which are shown in Fig. 6(a), were used as test images. Figures 6(b) and (c) demonstrate the encrypted images obtained by the proposed and the conventional [4,5,6] schemes, respectively, where the divided block size is $16 \times 16$ pixels.

Fig. 6.

Test images and their encrypted images obtained by proposed and conventional [4,5,6] schemes.

4.1 Color Scrambling

Table 2 indicates the entropies of the original and the encrypted images shown in Fig. 6. The entropy H(A) is defined as

$$\begin{aligned} H(A) = -\sum ^{2^{24}}_{i=1}p(a_i)\log _{2}p(a_i), \end{aligned}$$

(2)

where A represents the finite set of 24-bit colors $a_i~(i = 1, 2, ..., 2_{24})$, that is, $A = \{a_1, a_2, ..., a_{2^{24}}\}$, and $p(a_i)$ is the occurrence probability of $a_i$. The entropies of the encrypted images obtained by the proposed scheme are higher than those of the original images and the encrypted images obtained by the conventional schemes.

Table 2. Entropies of original and encrypted images shown in Fig. 6.

Fig. 7.

Comparison of color distribution (Lena).

We also compare the color distributions in the original image and its encrypted images obtained by the proposed and the conventional schemes. Figure 7 shows the histograms of the test image ‘Lena’, where the vertical/horizontal axes represent the saturation/hue values, respectively. The encrypted image produced by the proposed scheme exhibits a wider distribution than the original image and the encrypted image produced by the conventional schemes.

From those results, it is verified that the color information of the encrypted images produced by the proposed scheme could become more scrambled relative to that produced by the conventional schemes.

Fig. 8.

Comparison of compression efficiency.

4.2 Compression Efficiency

We compare the compression efficiency of JPEG-LS [12] among the original images and their encrypted images produced by the proposed and the conventional schemes. The compression efficiency is compared by calculating the bit rates.

$$\begin{aligned} { {Bit\, rate} \mathrm (bpp)} = \frac{{Size\ of\ image\ file}}{{Number\ of\ pixels\ in\ image ( M \times N )}} \end{aligned}$$

(3)

where M and N are the vertical/horizontal sizes of the image.

Figure 8 shows the comparative results for two of the test images, that is, Airplane and Lena. The sizes of the divided blocks are $4 \times 4$, $8 \times 8$, $16 \times 16$, and $32 \times 32$ pixels in the figure. The results for the other two test images have shown analogous lines. It is certified that the proposed scheme can maintain approximately the same compression efficiency as that of the conventional schemes.

4.3 Resilience Against Brute-Force Attacks

We discuss the key space for resilience against brute-force attacks in this section. In the proposed scheme, the four encryption processes are carried out independently from each other. The total key space can be obtained by multiplying the key spaces for the four processes. In the case of dividing a $M \times N$ image into $B_x \times B_y$ blocks, the number of divided blocks L is given as

$$\begin{aligned} L = \lfloor \frac{M}{B_x} \rfloor \times \lfloor \frac{N}{B_y} \rfloor . \end{aligned}$$

(4)

The key space $N_P$ of the positional scrambling, which is the number of all the scrambling patterns of L blocks, is calculated by

$$\begin{aligned} N_{P} = ({}_L P_L)^3 = (L!)^3. \end{aligned}$$

(5)

As shown in Fig. 2, the number of all patterns for both the block rotation and the block inversion is four. When combining those two processes, some combinations correspond to other combinations. Therefore, the number of total patterns for the block rotation/inversion becomes eight. The combined key space of the block rotation and inversion $N_{D}$ is obtained by

$$\begin{aligned} N_{D} = (8^L)^3 = 512^L. \end{aligned}$$

(6)

In the negative-positive transformation and the color component shuffling, the key spaces $N_{N}$ and $N_{C}$ are given by

$$\begin{aligned} N_{N}&= (2^L)^3 = 8^L, \end{aligned}$$

(7)

$$\begin{aligned} N_{C}&= 6^L. \end{aligned}$$

(8)

Consequently, the total key space $N_{A}$ in the proposed scheme can be represented by

$$\begin{aligned} N_{A}&= N_{P} \times N_{D} \times N_{N} \times N_{C} \nonumber \\&= (L!)^3 \times 512^L \times 8^L \times 6^L, \end{aligned}$$

(9)

while the total key space in the conventional schemes $N_{A, Conv}$ is given as

$$\begin{aligned} N_{A, Conv}&= N_{P, Conv} \times N_{D, Conv} \times N_{N, Conv} \times N_{C, Conv} \nonumber \\&= L! \times 8^L \times 2^L \times 6^L, \end{aligned}$$

(10)

where $N_{P, Conv}$, $N_{D, Conv}$, $N_{N, Conv}$, and $N_{C, Conv}$ are the key spaces for the four encryption processes in the conventional schemes.

4.4 Resilience Against Jigsaw Puzzle Solvers [7,8,9,10]

Jigsaw puzzle solvers (JPSs) [7,8,9,10] are a kind of possible attack that attempts to retrieve the original image from a large number of pieces by using the correlation among them. JPSs have been actively studied in the area of computer vision and pattern recognition. They could be considered as possible attacks for the BPBE schemes because a BPBE image consists of multiple blocks. According to [11], the encrypted images obtained by the conventional schemes [4,5,6] have a great risk of being maliciously decrypted, even though they keep a sufficiently large key space, as described in Sect. 4.3.

On the other hand, it has also been demonstrated that the restorability of images attacked by JPSs can be greatly decreased in the case when the color information of the encrypted image has been modified. This is because it would be difficult for the conventional JPSs to solve the puzzle when the color correlation among the pieces becomes low. Therefore, it is assumed that the proposed algorithm, which can fully scramble the color information of the encrypted images, would be effective against JPSs.

5 Conclusion

We proposed an extended BPBE algorithm, where the color scrambling of the encrypted images has been enhanced relative to that of the conventional schemes. Consequently, it is effective for increasing the resilience against both brute-force attacks and JPSs. Furthermore, the compression efficiency using JPEG-LS can be maintained to be approximately the same as that of the conventional schemes.