{'fraction_non_alphanumeric': 0.032846882291047166, 'fraction_numerical': 0.01308385562011071, 'mean_word_length': 4.507684555303603, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A novel reversible data hiding in encrypted images based on polynomial arithmetic

Reversible data hiding in encrypted images is an effective technology for data hiding and protecting image privacy. Although there are many high-capacity methods have been presented in recent year, most of them need a pre-processing phase to reserve room in the original image before encryption. It may be unpractical, because the image provider has to analyze the content of the image and accomplish additional operations. In this paper, we propose a new robust vacate room after encryption schema based on polynomial arithmetic, which achieves a high embedding capacity with the perfect recovery of the original image. An efficient symmetric encryption method is applied to protect the privacy of the original image. One polynomial is generated by the encryption key and a group of the encrypted pixel, and the secret data is mapped into another polynomial. Through the arithmetic of these two polynomials, we can extract secret data and recover origin image, separately. Experimental results demonstrate that our solution has a stable and good performance on various images (include rough texture image). Compared with some typical methods, the proposed method can get better decrypted image quality with a large embedding capacity.


Introduction
Reversible data hiding (RDH) is a technology that enables the exact recovery of the original image when extracting embedded information. Due to the feature of lossless data hiding, it has gradually become a very active research area in the field of data hiding. The feature is desirable when highly sensitive data is embedding into an image, e.g., in military, medical, and legal imaging applications. The first RDH technique [1] was proposed by Barton in 2000 to address this concern. To date, various methods have been presented to achieve data hiding in images, in which difference expansion [2] and histogram shift [3] have far-reaching influence. Difference expansion is proposed by Tian in [2], the secret message is embedded by expanding the difference between adjacent pixels.
In the histogram shifting method [3], the histogram of the original image is first generated, then it embeds messages by slightly modifying the pixel grayscale values of zero and the minimum point of the histogram. Subsequently, some schemes [4,5,6,7] are introduced to improve the payload and reconstructed image quality based on them. Furthermore, to get better performance, methods such as lossless compression [8] and prediction error [9,10] have been presented later.
As a great growth of cloud services and people's increasing attention for privacy protection, reversible data hiding in encrypted image (RDHEI) has drawn much interest from the research community. It can not only extract the secret message and recover the original image without error but also preserves the privacy of the original image. This concept was first proposed by Zhang [11] in 2011, there are three roles in the scenario, the image provider uses the encryption key to encrypt the image to protect the privacy of original images; a data hider embeds data by using the data hiding key without knowing the original image content; when having both above keys, the receiver is able to obtain the secret message and origin image correctly. It is helpful in some situations involving data privacy. For instance, in the cloud computing scenario, the user uploads an encrypted image, and an inferior assistant hopes to embed some message without access to the origin content.
Shi et al. [12] classify the existing RDHEI methods into two categories: vacating room before encryption (VRBE) and vacating room after encryption (VRAE). In VRBE methods [13,14,15], an extra preprocessing is performed before encryption to vacate space for data embedding. Ma et al. [13] apply a traditional RDH method of histogram shifting to reserve room before encryption. The LSB of certain pixels is embedded into other pixels, which produces a pre-processed image. By substituting the LSB values of these vacated pixels in the encrypted image, the secret message can be embedded. The method can provide a larger payload (0.5 bpp) than previous methods with PSNR = 40 dB. In [14], based on the prediction technique, some pixels are estimated through the rest pixels before encryption. The secret message can be embedded by modifying the prediction errors instead of embedding data directly in encrypted images. By exploiting the correlation between neighbor pixels in nature images, Cao et al. [15] use a sparse coding technique to free up a large space. The leading residual errors produced by sparse coding are encoded and then embedded into the original image. More secret message can be embedded into the vacated room in the encrypted image. In [16], a new schema is proposed based on a double linear regression prediction model, which further improves the prediction accuracy and provides a large embedding capacity. Referring to the difference between current pixel and its predicted value, the secret message can be embeded. And they construct a prediction error map to record error positions for lossless recovering the original image.
As VRBE is able to takes full use of spatial correlation between adjacent pixels, several high-cacity methods based on VRBE have been proposed [17,18,19] by compressing or using prediction error recently. For a pixel, Puteaux et al. [17] substitute the MSB (most significant bit) values to embed secret data.
Then current pixel is predict by the decrypted previous ones. There may be some error in the recovered pixels, thus an error map is embeded to correctly reconstruct origin pixels. In [18], Chen et al. divide the image into blocks firstly.
Duo to the spatial correlation of images, the MSB planes of a block have a large amount of consecutive 0s or 1s. Thus they design an algorithm called extend the run-length coding to compress MSB planes before encryption. In this way, the secret message can be embeded into the compressed planes. Yin et al. [19] use the common bits between a pixel and its predict value to embed message, and pixel labeling is applied to recover the orgin pixel from the predict value.
A label map is recorded by using Huffman coding. Then the Huffman coding rule and the label map are sent as the auxiliary information. Finally, a high capacity can be achieved by by multi-MSB substitution.
For VRAE methods, the image provider directly encrypts the origin image, then the secret message are embedded into the encrypted image. The first VRAE method [11] is proposed by Zhang, the original image is firstly encrypted by a stream cipher, then the data hider divides the encrypted image into blocks and embeds secret bits by modifying a small proportion of encrypted data. The receiver can extract secret messages and recover the origin image perfectly by using the spatial correlation in natural images. Zhang [20] proposes a novel separable method, the exclusive-or operation is applied to encrypt the origin image, a sparse space to accommodate the secret data is created by compressing the least significant bits of the encrypted image. Qian and Zhang [21] propose a novel method using distributed source coding. The image provider encrypts the image by using a stream cipher, then some bits selected from the encrypted image are compressed to make space for secret bits.
In existing RDHEI methods, the VRBE methods can provide a really high payload. However, an extra pre-processing operation is required before encryption for image provider. It may be unpractical, because the content owner needs to care about the the content of the origin image. And for most traditional reversible data hiding methods, data redundancy in natural images is applied to hide secret messages. Thus, it is difficult to embed messages into the encrypted image for VRAE method, since the correlation between a pixel and its adjacent neighbors is disappeared after encrypted. As expected, previous VRAE methods get limited embedding capacity or fail to recover the origin image. On the other hand, the performance of many exist methods is relate to the content of the image, they show a poor generalization performance on complex images (like Baboon image). In general, it is a challenge for RDHEI to achieve a high embedding capacity while recover the original image perfectly and have a stable performance on varies images.
Facing the challenge, we propose a new robust VRAE schema based on polynomial arithmetic. Our work is dedicated to finding a good solution not only in the recovery of the original image, but also in the embedding capacity. For the encryption of images, we design an efficient symmetric encryption method with support for correct data extraction and perfect image recovery in the RDHEI.
The cipher of pixels in an image is generated via a univariate polynomial math expression f (x), in which the coefficients of f (x) are associated with both pixels and the encryption key, and the degree of f (x) is the number of the pixels. The secret data is also mapped into another polynomial math expression g(x). These expressions support polynomial addition, subtraction, and modulo operations to achieve data extraction and image recovery.
The rest of this paper is organized as follows. The proposed scheme is elaborated in Section 2. Abundant experimental results with the comparison and analysis are presented in Section 3. Finally, the conclusion is drawn in Section 4.

Proposed Scheme
In the section, based on polynomial arithmetic, a novel solution is proposed to hide secret bits in pixels of origin image with low computational complexity and a high payload (the maximal payload could be 1.333 bpp for Lena). The overview of this process is shown in Fig. 1. There are three entities: an image provider, a data hider and a receiver. Stream encryption is applied to encrypted origin image firstly. Then the image is divided into blocks with the size of 2 × 1.
For each group, the two pixels are converted with the key k e by the provider as a polynomial f (x). Similarly, the hider using its key k w can encode two secret bits as a polynomial g(x) with the same degree. Through the transaction of . Note that the encrypted pixels hiding secret bits are coefficients of H(x). Based on coefficients of H(x) and the keys k e and k w , the receiver can extract the secret bits and recover pixels of the original image perfectly.

Image Encryption
Assume that k e is an encryption key and k w is a data hiding key, where the former is shared between the provider and the receiver, the latter is shared between the hider and the receiver. And a public identity ID is shared with everyone.
Without loss of generality, assume the original image is of size m × n. In this phase, a pseudo-random matrix C sized m × n is first generated by using k e . For current pixel x i,j and its corresponding c i,j , we convert them into the 8-bit binary sequence according to Eq. (1), denoted as x k i,j and c k i,j .
Then, current pixel is encrypted by following encryption operation.
Where 0 ≤ i < M , 0 ≤ j < N , I k i,j is the 8-bit binary sequence after encryption, and ⊕ denotes the exclusive-or(XOR) operation. Eventually, the encryped pixel can be obtained by Eq. (3).
Next, divide the encryped image I into blocks with the size of 2 × 1. Given a data list (p 2 , p 1 ) of two elements, where pixels p i (i = 1, 2) are selected from the above blocks. With a public identity ID, a polynomial f (x) is constructed as follows and the coefficient of function f will be sent as the encrypted data. That is, In this way, we get the final encrypted image. (2) Replace the LSB of the first 4 pixels in encrypted image to save public identity bitstream l.
(3) Skip 4 pixels, β will be embedded into the rest pixels by using our data embedding procedure.

Data Embedding
In data embedding phase, the first 8 pixels are used to embed side information, then the boundary between first part and rest part can be obtained. The secret message will be embedded into second part of encrypted image without knowing the encryption key k e . When having the encrypted image a, the data hider first uses the k w to encrypt secret message (m 2 , m 1 ) : where k i are obtained by k w using a standard stream cipher. Then they embed the encrypted secret bits (s 2 , s 1 ) into a. Specifically, a polynomial g(x) is generated as follows, Then, the encrypted image embedded above secret bits is represented as = (a 2 + s 2 )x 2 + a 1 x + a 0 + s 1 (mod 256) Note that a = (a 2 , a 1 , a 0 ). That is,

Data extraction and image recovery
Upon receiving the encrypted image embedded secret bits, the receiver extracts the secret bits and then recovers the original image. Specifically, the receiver works as follows, (1) Getting three pixels (c 2 , c 1 , c 0 ) from the encrypted image embedded secret bits, she/he constructs a polynomial H(x) = c 2 x 2 + c 1 x + c 0 (mod 256).
(2) Collect LSB of first 4 pixels in the marked image, and the binary sequence is converted to decimal to get public identity ID. (11) When having k e , the original pixels can be recovered free of error as As previously mentioned, the encrypted image and encrypted secret data could be split by using ID, thus we can reconstrut the origin image and extract secret message separately. With different secret keys the receiver owns, there are three possible cases: 1. The receiver only has the encryption key k e : After obtaining the split encrypted image, a same pseudo-random matrix C sized m × n is first generated by using the encryption key, then each origin pixel can be recovered according to step (11).
2. The receiver only has the data hiding key k w : With the data hiding key k w , the receiver decrypts the split encryped message to extract the origin secret message correctly.
3. The receiver has both the encryption key k e and the data hiding key k w : We can recover origin image perfectly and extract secret message correctly.
Notice. In step (4), for correctly extracting secret message, the value of ID is limited: From the above inequations, it concluded that two bits can be embeded into each coefficient of f at most. The details cases are as follows: 1. when embedding 1 bits, s i ∈ [0, 1] (i = 1, 2) and ID ∈ [2, 15].
2. when embedding 2 bits, s i ∈ [0, 3] (i = 1, 2) and ID ∈ [4,9]. In this case, secret message need to be extra processed during different phase. Before data hiding, the data hider have to divide the secret bits into a group of 2 bits, and then convert them to decimal similar to Eq. (3). Furthermore, in data extraction phase, the receiver needs to convert the extracted decimal secret data to origin secret bits, as indicated in Fig. 2.
Example 1. Fig. 3 shows the sketch of this example. For an 8-bit image, given two pixels (132,35) and k e = 12, the image provider firstly generates a pseudorandom list (95,121) by k e . The original pixels are encrypted as (219,90) by

Experimental results
In this section, based on the embedding capacity (payload) and reconstructed image quality, we evaluate the performance of the proposed method. The method is tested on the uncompressed 512×512 gray-scale images chosen from the USC-SIPI image database [22]. To validate the proposed scheme, experiments are done with a variety of standard test gray-scale images. Some are presented in Fig. 4 namely Lena, Boat, Baboon, and Airplane. The comparisons between the existing methods and ours are shown in Fig. 5 and 6, according to the embedding rate (EC) and the peak-signal-to-noise ratio (PSNR) of images. Here, EC is adopted to evaluate the embedding capacity, and it calculated as EC = T otal embedded bits T otal number of pixels in a image .
Again, the PSNR is applied to evaluate the reconstructed image quality in comparison to the original image, which is computed as follows.
where n is the total number of pixels, p i and p i denote the pixel values of origin and recovered images, respectively. Finally, we would compare our schema with some related works, and discuss their efficiency.

Performance Analysis
The proposed method can perfectly recover the original images from the corresponding encrypted images as shown in Fig. 4.  Table 1.
Moreover, we make a performance testing by a random selection of 1000 grayscale images with size 512x512 on BOWS-2 [23] and BOSSbase [24] datasets.
The test results for these images are shown in Table 2. For embedding capacity, the best case is 1.333 bpp, and 1.333 bpp in the worst case. It is clear that the worst EC equal to the best EC. And the average EC can be also reach 1.333 bpp, which indicate that the payload of all image is 1.333 bpp. Certainly, each original image could be reconstructed free of error (satisfy PSNR→ +∞ and SSIM=1). From the above analysis, it indicates that the proposed method has stable and good performance.
We now compare the performance of our approach with some classic design [11,13,15,16,20]. Our experiments are based upon the two typical images of Lena and Baboon. Then, their embedding capacity and PSNR are estimated through (10) and (11). The results are summarized in Fig. 5 and Fig. 6,  [15] and Li et al [16]. These show that our approach provides a good trade-off between the embedding capacity and PSNR.
To prove the robustness of the proposed scheme, we compare our approach with some state-of-the-art high-capacity VRBE methods [17,19,25,18,26] on complex image Baboon. For all these methods can recover origin image losslessly (PSNR→ +∞), we only need to make comparasion on embedding rate(ER) here. The result is illustrated in the Fig. 7. The ER of the proposed method can reach 1.333 bpp. It can be seen that these high-capacity methods get lower ER than the proposed schema. In these high-capacity methods, a pre-processing is required to vacate room for data embedding, thus the ER is closely relate to the content of origin image. It can lead to poor performance of these methods on complex images. In contrast, the proposed method directly encrypt origin image and has a very stable performance on all images. This validates that the proposed method is robust.

Security Analysis
In the proposed method, it is able to protect the security of the origin image and secret message by using effective encryption algorithm. To prove the security of the proposed schema, we will mainly focus on the applied encryption method and statistical analysis including histogram and correlation analysis in this section. In the image encryption phase, the origin image is directly encrypted with a stream cipher. For a image of size m × n, a random matrix C is first generated. Each element of C is converted into an eight-bit binary number, thus the guessing probability of the secret key is 1 2 8×m×n , which is too low to predict the correct secret key. As for secret message, it can be encrypted with a stream cipher like image encryption or any secure symmetric encryption algorithms. Hence, it is impossible to get the origin image or secret message without corresponding secret key.
Take Lena image to illustrate security analysis. Fig. 4 (a) is the origin image and Fig. 4 (b) is the marked encrypted image. It is clear that the encrypted image is noise-like and no useful information can be obtained from the image. From these histograms, it can be found that the histogram of the origin image has meaningful information, while the pixel distribution of the encrypted image and the marked image are both uniform compare with the original image . It is difficult to obtain the origin image from the useless statistical feature. This validates that the proposed method is guaranteed a high security level.

Data Expansion
Besides, to measure the efficiency of the proposed schema, we make a comparison with other schemas on data expansion. The result is given in Table 3.
Data expansion indicates the encrypted image is bigger than the original image.
We denote the number of origin pixels as N . There are some methods [20,27] using stream cipher encryption to encrypt images, which adopt exclusive-or operation to encrypt images. It obviously does not cause data expansion. For those methods [28,29] using Paillier homomorphic encryption, a 512-bits or 1024-bits secret key is customarily used to encrypt 8-bits pixels. After encrypted by the Paillier encryption, the origin 8-bits pixel is at least expanded to 1024-bits, thus the encrypted pixel is further expanded. The rest schemas [30,31] apply secret sharing to encrypt images, method [31] would expand the original image to two or more times. In method [30], they improve secret sharing into multi-secret sharing to prevent data expansion. As for our approach based on polynomial arithmetic, two pixels would be encrypted into three pixels, so the encrypted image expands 1.5 times.

Conclusion
In this work, a new method of reversible data hiding in encrypted images based on polynomial arithmetic is presented, which achieves a good balance between embedding capacity and reconstructed image quality. Since the correlation of adjacent pixels is disappear after encryption, thus various methods proposed is trying to preserve the feature to vacate room for embedding message.
Specially, we propose a new method to avoid utilizing the correlation of adjacent pixels in nature images, thus our methods is robust and has good performance on all images. Through arithmetic of the two polynomials, a high capacity can be obtained while the reconstructed image is the same as the original image.
However, data expansion may raise storage costs for encrypted images. In the future, we will try to solve the problem of data expansion and design more efficient polynomials to further improve the embedding capacity.
List of Figures   Fig. 1: Overview of the proposed schema