{'fraction_non_alphanumeric': 0.0410641989589358, 'fraction_numerical': 0.013953152111046849, 'mean_word_length': 4.370801786060959, 'pattern_counts': {'":': 0, '<': 3, '<?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': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reversible Data Hiding in Encrypted Images Using MSBs Modulation and Histogram Modification

This paper presents a reversible data hiding in encrypted image that employs based notions of the RDH in plain-image schemes including histogram modification and prediction-error computation. In the proposed method, original image may be encrypted by desire encryption algorithm. Most significant bit (MSB) of encrypted pixels are modulated to vacate room for embedding data bits. Modulated ones will be more resistant against failure of reconstruction if they modify for embedding data bits. At the recipient, we employ chess-board predictor for lossless reconstruction of the original image by the aim of prediction-error analysis. Comparing to existent RDHEI algorithms, not only we propose a separable method to extract data bits, but also content-owner may attain a perfect reconstruction of the original image without having data hider key. Experimental results confirm that the proposed algorithm outperforms state of the art ones.

INTRODUCTION eversible data hiding in plain-image (RDHPI) is drastically developed by many researchers in recent years [1]. In RDHPI secret data imperceptibly is embedded in a plain-image in a way that original image can be losslessly recovered after secret data extraction. More developed papers in RDHPI drive from three main notions that are difference expansion, histogram modification and lossless compression respectively pioneered by [2], [3] and [4]. These papers also employ prediction-error to improve hiding capacity in a determined level of distortion. Whatever more accurate prediction is attained, there is sharper histogram of the errors that can be modified to embed secret data. For example, [5] and [6] exploit gradient-adjusted prediction (GAP) and median edge detector (MED) predictors that firstly are introduced in [7] and [8], respectively. Tsai et al. [9] present a predictor, may be denoted local difference (LD) predictor, that computes difference between pixels intensities in a local area of the image and most central one in the area to bring out prediction-errors. They embed secret data via histogram modification of the predictionerrors. Sachnev et al. [10] further present cross-dot predictor that divides image into two "cross" and "dot" sets. Dot set may be predicted using cross one and vice versa. Cross-dot predictor is also represented as chess-board (CB) predictor in [11].
Besides RDHPI, reversible data hiding in encrypted image (RDHEI) is a new need of cloud computing attracted intensive attention of the researchers. In RDHEI there are three parties: image-owner, data hider and recipient. Image-owner may not trust a channel administrator (or inferior assistant) so the imageowner encrypts the image before uploading to cloud server while he/she is not motivated to compress image before encryption. On the other side, data hider, i.e. the channel administrator, is not allowed to have original-content but authorized to embed some handy data in the encrypted image. The approach should guarantee lossless original image reconstruction and error-free data extraction at the recipient. These challenges are the cause of developing RDHEI.
In RRBE there is a pre-processing before encryption that enables data hider to embed data bits in the encrypted image.
Most notions in VRBE are attained by encrypting some pixels intensities in a local area of the image using same cipher bytes. The approach preserves correlation of the pixels employed to embed data bits by data hider. Thus, some information remains disclosed in VRBE.
The schemes presented in RRBE and VRBE are separable means extraction of the data bits at the recipient are not tied to decrypted information. On the other hand, in joint ones data extraction can be realized just using decrypted marked image.
In VRAE schemes, data hider is completely blind to original information. After image encryption, data hider vacates rooms to embed data bits without any knowledge of original-content . The approach provides more level of security that protects image-owner privacy more than two other ones. Some methods in VRAE are joint [28,30,31] and some others are separable [27,29]. In [32], two different joint and separable procedure are introduced. The separable approaches in VRAE are more functional than joint ones and further they are more functional than RRBE and VRBE. However, achieving high embedding capacity is more challengeable in VRAE than RRBE and VRBE.
In general kind of view, similar to RDHPI, most schemes in RDHEI employ correlation of neighboring pixels in an image and further they employ based idea or procedure of RDHPI such as histogram modification, difference expansion and prediction-error computation.
On the security term in using secret keys, Chen et al. [15] classify three different schemes: namely share independent secret keys (SIK), shared one key (SOK) [15] and share no secret keys (SNK) [12,17]. In SIK there are two data hider ( ) and image-owner ( ) keys that are shared with recipient independently while in SOK there is just one key and in SNK there is no key to be shared. Most [15,17] exploit difference expansion and further [12] employs histogram modification of the predictionerrors to reserve room before encryption. Huang et al. [24] present new framework in RDHEI that makes possible using most notions of RDH in plain-image for encrypted one. In this self-contained scheme any kind of prediction technique, including GAP, MED, CB and LD may be used to bring out prediction-errors.
Schemes [19] and [20] use idea of LD predictor to embed data in the encrypted image. They realize lossless reconstruction (LR) of the original image and error-free extraction of data bits. Also, scheme [29] employs local correlation of neighboring pixels to reconstruct original one at the recipient. Using MED predictor, Yin et al. [14] bring out some labels for almost all pixels before encryption. These labels then are compressed via Huffman coding to be embedded along with data bits. They improve [19] and [20] naturally with the aim of source coding.
Fallahpour and Sedaaghi [33] present a RDHPI method that apply scheme [3] in non-overlapped blocks of the plain-image to embed data using histogram modification of pixels in a block. In the same approach, Ge et al. [25] introduce a RDHEI method that employs histogram modification ( [3]) in non-overlapped blocks of the encrypted one to vacate room for embedding data bits.
As discussed, there are several schemes in RDHEI that employ based notions of RDHPI to embed data in the encrypted image. As well, we present a new scheme in RDHEI that uses based idea of the histogram modification to vacate room after encryption. Data bits just are embedded in MSBs of target pixels that are modulated to be prepared for histogram modification. Target pixels are the ones used to embed data bits. Regarding another notion that is employed in RDHPI methods, we use CB predictor for LR of the original image at the recipient. We use independent secret keys, and to encrypt original image and data bits, respectively.
In our scheme, not only data bits perfectly are extracted but also it is separated from original image reconstruction. This scheme can be considered as an applicable one that improves state of the art RDHEI schemes.

RELATED WORKS
Proposed method is inspired from histogram modification. Besides, we employ CB predictor to reconstruct original image at the recipient by analyzing prediction-error. They are discussed in more details in this section.

A. Histogram modification
As discussed, Ni et al. [3] present a RDHPI scheme using histogram modification of the original image. In the approach, they embed data bits in peak point of the histogram that is a pixel with most frequent in the image. Accordingly, they vacate room by histogram modification (VRHM) to provide empty position used for embedding data. In the approach, reversible reconstructing of the original image is possible. For the example, peak point in the histogram of Lena (Fig. 1a) is "155". One to vacate room adds all intensities of the image more than "155" by 1 (Fig. 1b).
In the proposed procedure, we apply the idea of VRHM in the encrypted image. The CB predictor, i.e. non-causal, can provide prediction better than the causal ones, MED and GAP. As shown in Fig. 2 in CB predictor a black/white pixel may be predicted using white/black neighbors. For example, prediction of a white pixel employing neighboring black ones { , , , } is done by

B. Chess-board predictor
where ⌊ . ⌉ is the round function. Using ̃ and , the prediction-error is computed by more specifically let's denote the prediction of a white pixel by neighboring black ones as white plus prediction (WPP). In addition, a central black pixel ( ) can be predicted using neighboring black ones, , , , , by Similarly, in BCP, prediction-error is calculated by

C. Prediction-error analysis
According to (2) or (4), having a prediction-error and a predicted value of an original pixel, definitely, it can be reconstructed. However, in [19] we prove that even having a range of the prediction-error, it still be possible reconstructing some bits of the original pixel. In other words, by this information, some more significant bits of the original pixel are retrievable at the recipient. To be more clarified, let's assume a prediction-error ( ) that is computed subtracting the original pixel ( ) and predicted one ( ).

− =
In [19] we confirm that, particularly, a bit embedding capacity (EC) will be provided in MSB of the pixel " " when the error satisfies To gain a better insight, let's assume a pixel, = , that describes eight bits including LSB, , to MSB, . Having (6), may be replaced by a bit data so that can be retrieved at the recipient.
Employing the better predictor causes to realize the less prediction-error and accordingly provides the more pixels in the image that verify (6). Thus, the more MSB of the pixels can be exploited to be modified for embedding data bits.
In Fig. 3, histograms of prediction-errors provided by MED, GAP, BCP and WPP predictors for Baboon image are demonstrated. BCP and WPP predictors are employed for all pixels. As shown, WPP provides sensibly a sharper histogram than others. In addition, as seems GAP makes sharper histogram than MED and BCP.
In meanwhile, the more important subject is that how many prediction-errors exist which their absolute values are greater than 64. They can not exploit to embed even one data bit because they do not verify (6). Let's denote " " as the number of prediction-errors do not confirm (6) and " " as the all prediction-errors in an image. Accordingly, we define as a probability of failure in reconstruction of a reformed MSB of the pixel that is randomly picked up. Accordingly, we have = 0.0017, = 0.021, = 0.014 and = 0.016 for Baboon image. Although significantly is less than others, there is still a probability of failure in using WPP. As a solution diminishing risk of failure, we get together MSBs of the target pixels. Therefore, ones of the MSBs are modulated and so modulated one is used to carry data bit.
It can be proved that there is always a can be taken to guarantee LR of the original image. The amount of computed . depends not only on the kind of an employed predictor but also the type of a chosen image. The lower the entropy may be provided by an image, the lower the probability of the failure in reconstructing can be attained. In other words, generally, smoother images have less . . For example, unlike Baboon, Lena and F16 have = 0. Accordingly, in the proposed method we employ WPP predictor. We may also exploit BCP to achieve more EC.

PROPOSED SCHEME
In this section, we introduce our proposed method in details including image encryption, simple scrambling and unscrambling, embedding and extracting data bits, recovering the original image and overall view of the proposed scheme.

A. Image encryption
Encryption of the original image is done using content-owner secret key, . However, for encryption, not only any method of encryption but also any standard encryption algorithm can be exploited. The only restriction is no change in positions of the image pixels during encryption. If it occurs, data hider will have knowledge of the new positions to realize proposed procedure. Therefore, in term of security, content-owner can chose a desire encryption algorithm.

C. MSB modulation, demodulation and embedding data bits
In this section, we demonstrate procedure of embedding data bits in the modulated MSBs of the encrypted pixels. MSB modulation gives more intensive value prevents failure of reconstruction. In other words, employing modulation, several MSBs must be changed instead of just one MSB to embed data bit that provides more resistant against failure of reconstruction. This modulation is done by a new binary representation of -bits of MSBs that take different positions. It represents a whole number less than 2 . Using the histogram modification of the modulated MSBs some rooms are vacated to realize RDHEI.
Let's assume, ̂ = ̂( , ) … ̂( , ) … ̂( , ) , as a bitwise demonstration of an encrypted pixel, i.e. from LSB, ̂( , ) , to MSB, ̂( , ) . As mentioned when (6)  Regarding the nature of the encrypted image, the histogram of ℳ demonstrates a uniform distribution. We should vacate rooms employing histogram modification to embed data bits. The approach is a shrinking process that shifts each less than 2 to a larger one. The shrunken ones, = { , , … , , … , }, 2 ≤ < 2 , is achieved using Algorithm 1. In this algorithm, if < 2 , it is reformed to what has most bitwise mutation than . In other words, is replaced with its 1's complement.
Data bits may be encrypted using . Vacating rooms by the shrinking, ( + 1) bits of the encrypted data, = { , , … , , … , }, may be embedded in employing Algorithm 2. Consequently, we have carrier ones, = , , … , , … , . In this algorithm, to embed a encrypted data bit with value "1" in , it is replaced by its 1's complement and to embed a one with value "0" it is remained intact.

D. Extracting data bits
For extracting data bits, we just need data hider key, . Firstly, MSBs of the target pixels in the marked encrypted image are picked up, denoted . In this paper, reconstructed sets or pixels are in bold.
In the following, summation of amounts of errors is achieved by Accordingly, ℰ is attained by (10) where ′ ( ) is replaced with ′′ ( ) . Finally, the original pixels belong to or are retrieved by comparing ℰ and ℰ employing Algorithm 4.
Accordingly, for each , if ℰ ≤ ℰ the recovered pixels belong to -pixels of and in vice versa they belong to . Eventually, the recovered ones are = { , , … , , … , }.
If ℰ and ℰ are close together it will be a high risk in LR of the original pixels. Therefore, risk of LR may be analyzed by computing difference between ℰ and ℰ .
The larger ℛ may be calculated, the lower risk of LR can be achieved and vice versa. Employing ℛ and in Algorithm 5, we can define 4 classes of risk: namely high risk (HR), median risk (MR), low risk (LR) and very low risk (VLR). Therefore, in reconstruction of each -pixels set we have a measurement of risk. The bigger is chosen, the more accurate evaluation of risk is realized.

F. Overall view of the proposed method
In Fig. 5a, we depict general diagram of the proposed scheme. As shown, at first, embedding is done on EWTP as demonstrated in Subsection C. Then, in a similar way it can be continued by EBTP, = ̂ , ̂ , … , ̂ , … , ̂ to increase EC. In more explanation, by choosing -bits, modulation can also be done for = { ̂ , , ̂ , , … , ̂ , , … , ̂ , }. generally is considered bigger than because WPP predictor can predict better than BCP one, as discussed. Thus, modulated ones = { , , … , , … , }, 0 ≤ < 2 , = , are  (9). Thus, marked encrypted image, including marked EWTPs and EBTPs, is created. Meanwhile, BRPs just are encrypted without any more modification. They will be employed to reconstruct other pixels at the recipient. They form 25% of the image.
Let's assume an original image in size ℙ × ℚ so regarding a set of preferred { , } and employing all target pixels including black and white, EC in bits is achieved by choosing { = 1, = 1} most possible EC, (ℙ × ℚ), is achieved. In Fig. 5b, extracting data bits and reconstruction of the original image are shown that can be done in a separable procedure.
Extracting data from marked EBTP, , similar to marked EWTP may be done (Subsection D).
Reconstructing the image is initiated by decryption of the marked encrypted image using . Therefore, BRPs are completely recovered just by decryption. Using BRPs, BTPs may be recovered in a similar procedure described in Subsection E except using (3) and (4) instead of (1) and (2) respectively to predict errors. Having black pixels, BPs, WTPs are recovered as also discussed in Subsection E. Risk of LR for -pixels/ -pixels can be computed in meanwhile of recovering.
The closer the pixels are the more correlation they have. By breaking the correlation, we can diminish risk of LR at the recipient. The approach may be realized by scrambling of MSB of target pixels before modulation. In other words, the scrambling prevents modulation of MSBs belong to near rough regions to keep together. Although, the scrambling can randomly be performed using , for less complexity, in this scheme, we scramble the encrypted MSBs, / , in a simple way (Subsection B). Thus, presenting more efficient procedure, the scrambled MSBs are modulated, marked and finally unscrambled to form the corresponding marked encrypted pixels. If MSBs of target pixels are scrambled by data hider to embed data bits, MSBs of encrypted target pixels will scramble as well in the same approach for extracting data. Accordingly, at the recipient, for original image reconstruction, we must scramble prediction-errors before computing / amounts of the prediction-errors. Therefore, in Algorithm 4, we should consider corresponding pixels of the scrambled predictionerrors for reconstructing original ones.

EXPERIMENTAL RESULT
The performance of the proposed separable VRAE algorithm is confirmed designing several experiments. Twelve grayscale images F16, Lena, Splash, Splash, House, Boat, Elaine, Lake, Peppers, Baboon, Stream, Aerial and APC from the USC-SIPI database are used as test images. Also, BOWS2 original database, including 10000 greyscale images, are employed to verify that the proposed algorithm can achieve LR of the original image and error-free extraction of the data bits. All test images are 512×512 in size. In experiments, the first and the last two rows and columns of the image are ignored in data embedding process. Peak signal-to-noise ratio (PSNR) is used to estimate the quality of a recovered image. PSNR= ∞ means LR of the original image. Choosing a set of { , } may be tied to entropy of an image. The greater the entropy of the image is estimated, the greater the value of { , } must be selected for LR. However, the more { , } is preferred, the less EC is attained. Therefore, there is a tradeoff between EC and PSNR of the reconstructed image. In Table I, the precise / for LR of the test images is inserted. By taking { = 1, = 1} for Elaine the most possible EC in the proposed method, 193548 bits, is achieved. In the other side, Stream image provides lowest EC. In this image, the lowest possible / for LR is { = 2, = 4} that definitely may be employed for LR of the other test images. Also, in the table, risk of LR is evaluated by computing the number of -pixels that take HR or MR. Although F16, Peppers and Baboon are reconstructed perfectly, they respectively include 4, 8 and 5 high risk sets of -pixels. About reconstruction of -pixels, Baboon and Elaine take 13 and 1 sets of high risk, respectively. Considering the number of HR and MR sets, generally, Baboon have most risk of LR. However, by choosing { = 3, = 5 } for embedding data in Baboon, no set of HR is left. It is attained by paying the cost of diminishing EC to 55913 bits.
On the other hand, we assume that the proposed scheme is completely blind to original-content so we can not find out the least possible precise { , } for LR. However, in the next subsection we confirm that a set of { , } may be always found out for LR.
In the proposed scheme, error-free extraction of data bits is realized for all test images under any circumstances.

A. Lossless retrieval
In Fig. 6 we demonstrate performance of the proposed scheme in LR and error-free extraction of data bits using 10000 test images of BOWS2 original database. As shown, for various { , } we accomplished the proposed algorithm to bring out the number of failure in LR. For example, in { = 2, = 6}, from 10000 test images there is 11 images that are not perfectly reconstructed so the failure rate is = 0.0011. As shown, the more { , } is preferred, the less EC and the less failure are provided. In { = 4, = 6}, is zero. Thus, there is permanently a set of { , } to achieve LR.
As demonstrated in the figure, modification of affects EC and more tangible than . As instance, in = 6, increasing from 2 to 3 diminishes EC and as much as 21506 bits and 0.0249, respectively while in = 3, increment of has no noticeable impact on EC and . Implementing the proposed algorithm by { = 3, = 6}, we descendingly sort all 10000 reconstructed images by the number of their -pixels that are HR. The first six sorted images are listed in Table II. As discussed, in this implementation, there are 11 failures. In the table, PSNR demonstrates four images that is not reconstructed losslessly and so 4 out of all 11 failures include in first six sorted images. It proves risk analysis is a proper assessment for evaluation LR, i.e. all 11 failures are included in 50 first sorted images.
In any failure, there is some deformed MSBs that can not be recovered correctly. The number of deformed MSBs are tabulated for images. The maximum one is just 12 bits for 6501.pgm image so there is not much error rate of bits when LR does not realized. Fig. 7 is a visual demonstration of the proposed procedure including original, encrypted, marked encrypted and reconstructed images with their depicted histograms. We optionally employ AES in counter mode, i.e. a stream cipher procedure, to encrypt the test image, Lena. As shown in Fig. 7b, after encryption there is no knowledge of the original image that remains discovered. As a proof, its histogram is uniformly distributed. We guarantee the security of the proposed algorithm because of having two important property in the represented algorithm. 1-There is no feature or knowledge of the original-content that remains disclosed. 2-Choosing a desire encryption algorithm is possible regarding its pros and cons including the security. Since our method is completely blind to the original-content, it absolutely preserves contentowner privacy. Moreover, content owner can encrypt original-  )  161290 161290 161290 161290  86021  193548 96774  161290  86021  80645  86021 96774  1  1  1  1  2  1  2  1  2  2  2  2  2  2  2  2  3  1  2  2  3  4  3   content using any key-based encryption algorithm including symmetric or asymmetric and in the symmetric one stream cipher or block cipher. Fig. 7c is a description of the marked encrypted image. The histogram still has a uniform distribution. sOriginal image is losslessly reconstructed as shown in Fig. 7d.

C. Comparison with other schemes
Separable VRAE methods are more functional than others. The proposed scheme is an only one of separable VRAE methods that makes possible LR of the original image just by having secret key. There is some experiments to confirm it.
In Table III, we compare proposed scheme with other separable VRAE schemes. Schemes [27] and [29] compress some bits of encrypted pixels to vacate room in order to embed data bits. Meanwhile, they employ some parameters can be used to form a tradeoff between EC and lossless recovery. Their functionality is similar to / . For fairness comparison between our method and [27] and [29] we employ these parameters so that LR of the all test images is accomplished. In the approach, we apply parameters { = 4, = 2, = 271}, { = 0.1} and { = 2, = 3} to [27], [29], and the proposed one, respectively. It should be noted that by choosing less , and , both EC and risk of LR are enlarged respectively in [27], [29] and ours. It generally leads more probability of failure in LR.
In [29], for LR at the recipient side information is needed that can be available employing . Therefore, as presented in Table  III, for this scheme just a high quality version of the original image can be retrieved without having while in the proposed scheme LR of the original image can be accomplished independent of data extraction. Besides, our algorithm can achieve more EC than [29].
As described in Table III, in comparison with [27] we significantly improve EC. Similar to [29] their algorithm is dependent to having for LR of the original image. In [32] scheme, using data hider key, they prefer some target pixels in the encrypted image to embed data bits and employ a predictor may be denote a modified WPP predictor to reconstruct original image at the recipient. Their methods do not guarantee LR, although it may be possible by diminishing the number of selected target pixels. In this experiment, we consider the most number of target pixels may be chosen in this scheme. In the approach, their algorithm fails in perfect reconstruction of the original image for five test images. As described in Table III, we improve their algorithm designing a procedure to guarantee LR realized by employing histogram modification and MSBs modulation. However, we pay the cost by less EC. All discussed schemes and ours provide an errorfree data bits extraction In Fig. 8 we compare our scheme with [16], [30], [27], [29] and [32] in quality of the reconstructed original image. In this experiment for reconstructing we suppose [30] and [32] have both encryption and data hider keys while others just have encryption key. In [30] method, original image reconstruction and data bits extraction are joint while our scheme is a separable one. In comparison, we improve not only EC but also image quality. To embed data bits, [16] reserves rooms before encryption aim of patch-level sparse representation. Generally, achieved EC in the proposed scheme is comparable with this scheme. In their scheme, a preprocessing is allowed before encryption while we absolutely are blind to original-content.
In Peppers and Lena we improve EC in comparison with [32]. In Lake, Peppers and Baboon they achieve a PSNR less than 55 dB even by using both keys while we realize LR.

CONCLUSION
In this paper, by comparing different predictors, we show that WPP is the better one used to diminish probability of failure in reconstruction of the original image. Moreover, BCP predictor is employed to increase embedding capacity. By predictionerror analysis, we just choose MSB of encrypted target pixels to embed data bits. These MSBs are modulated to be more resistant against failure of reconstruction when they are modified to embed data bits. Employing histogram modification of the modulated ones, we vacate rooms to embed data bits. At the recipient, in a separable way data bits are extracted and original image is reconstructed. We employ the risk measurement to have a probability of LR.
The proposed method improves other separable VRAE schemes by aim of MSBs modulation and histogram modification. We are the only one that realizes LR without having .