# Reversible Data Hiding in Encrypted Image Based on Multi-MSB Embedding Strategy
## 2 Proposed Method
### Data Extraction and Image Recovery  
In the decoding phase, the recipient can perform different operations according to the availability of encryption key and data hiding key. There are three possible scenarios:  
1. The recipient only has the data hiding key \(K_{h}\). 2. The recipient only has the encryption key \(K_{e}\). 3. The recipient has both the data hiding key \(K_{h}\) and encryption key \(K_{e}\). An overview of the process of decoding phase is presented in Figure 5.  
In the first scenario, the recipient has the right to use the data hiding key to extracted data in the encrypted domain. First of all, the auxiliary information is extracted from the pixels in \(I_{ED}\) of the encrypted image. The recipient can obtain the position of the marked pixels according to data hiding key. Then \((8-m)\) bits data can be extracted from marked pixels as follows:  
\[d_{l-m}=\left|\frac{E_{h}^{\prime}(i,j)}{2^{l-1}}\right|\text{mod }2,\ l=m+1,..,8 \tag{13}\]  
After every marked pixel is processed completely, all the data are extracted. Obviously, since the entire process is performed in the encrypted domain, it can effectively avoid the contents of the original image being leaked. In the second scenario, if the recipient only has encryption key \(K_{e}\), then the reconstructed image \(\overline{I}\) can be obtain, and the detailed process is as follows. **Step 1:** The auxiliary information is extracted from the pixels in \(I_{ED}\) of the encrypted image. **Step 2:** The pixels of the encrypted image are decrypted directly by using the encryption key:  
\[D_{l}(i,j)=E_{l}^{\prime}(i,j)\oplus p_{l}(i,j),l=1,2,\ldots,8 \tag{14}\]  
Then the pixel values after decryption are calculated as:  
\[D(i,j)=\sum_{l=1}^{8}D_{l}(i,j)\times 2^{l-1} \tag{15}\]  
where \(E_{l}^{\prime}(i,j)\) and \(D_{l}(i,j)\) are the \(l\)th bit values of the marked pixel and decrypted pixel, respectively. Figure 5: Overview of the decoding phase. **Step 3:** The pixels are arranged to their original position. The process is as follows. 1) According to the previous scan order, the pixels of \(I_{B}\) and \(I_{ED}\) can be arranged to the original position. 2) The original positions of pixels in \(I_{W}\) are scanned according to raster scanning mode, and then \(\Delta(i,j)\) is calculated one by one according to Equation (1). If \(\Delta(i,j)\)\(>\)\(T\), then the pixel in this position belongs to \(I_{W}^{C}\). By doing so, we can know the total number of pixels in \(I_{W}^{C}\), and these pixels are rearranged in front of the pixels in \(I_{ED}\); thus, it is easy to get the pixel positions in \(I_{W}^{C}\) in the rearranged image. Then the pixels in \(I_{W}^{C}\) can be arranged to original positions one by one, and the remaining positions of pixels in \(I_{W}\) belong to \(I_{W}^{S}\). 3) From the auxiliary information, the compressed \(LM\) is decompressed to get the positions of the pixels in \(I_{W}^{S^{\prime}}\). Then the pixels are arranged to their original positions according to the location map. Hence, the other positions belong to the pixels of \(I_{W}^{S^{\prime}}\). Therefore, all pixels can be arranged to their original position. **Step 4:** Since some pixels in \(I_{W}^{S^{\prime}}\) are embedded with data and some pixels in \(I_{ED}\) are replaced by auxiliary information, the pixels of these two parts cannot be restored to original values after direct decryption. For the marked pixels in \(I_{W}^{S^{\prime}}\), their surrounding pixels in \(I_{B}\) have been restored after direct decryption. Then these surrounding pixels can be used to recover the original value of the pixels in \(I_{W}^{S^{\prime}}\), which has been introduced in Section 2.1. For the pixels in \(I_{ED}\) which are replaced by auxiliary information, their original pixel values cannot be restored without errors in this scenario. Therefore, we use the average value of their surrounding black pixels to restore the edged pixels in \(I_{ED}\). Finally, the reconstructed image \(\overline{I}\) is obtained.