## 2 Related Works  
### Adaptive MSB Prediction  
After the data hider receives the encrypted image, by adaptive MSB prediction the upper-left pixel is used as the target pixel for each pixel block, to predict the MSB shared among the remaining pixels, so that the remaining pixels can adaptively retain the remaining unshared bits to free up the embedding space, thereby increasing embedding capacity. In this section, the methods of [PERSON] et al. (2013) and [PERSON] et al. (2014) are introduced and analyzed. In (2013), the \(M~{}\times~{}N\) sized image is first divided into several non-overlapping 2 \(\times\) 2 sized pixel blocks. All the pixels in the block are decomposed into eight-bit binary pixels, and then the block-level encryption is performed, using the encryption key and the classic stream cipher, thereby maintaining the correlation between the pixels in the block, to a certain extent; \(b_{m}^{k}(i,j)\) denotes that the \(k\)th bit of the pixel at position \((i,j)\) in the pixel block is encrypted as through (1):  
\[e_{m}^{k}(i,j)=b_{m}^{k}(i,j)\oplus r^{k}(i,j),~{}k=0,1,\ldots,7 \tag{1}\]  
where \(r^{k}(i,j)\) denotes the \(k\)th value of the element at \((i,j)\) in the pseudo-random matrix. The final encrypted image is then obtained by permuting each 2 \(\times\) 2 sized image block, using the permutation key. Upon receiving the encrypted image, data-hiding will be implemented. Initially, the encrypted image is partitioned into several non-overlapping 2 \(\times\) 2 pixel blocks. Subsequently, pixel bit reconstruction is carried out, utilizing adaptive MSB prediction, which uses a 2 \(\times\) 2 pixel block as the processing unit. The structure of the 2 \(\times\) 2 pixel block is shown in Figure 1:  
Each pixel block contains four elements: \(P\), \(C_{1}\), \(C_{2}\), \(C_{3}\). \(P\) will be used to predict other pixels. The four pixels are decomposed into eight bits, then the three variables, \(d_{1}\), \(d_{2}\), \(d_{3}\), are obtained by (2):  
\[d_{i}=dif(P,C_{i}),~{}i=1,2,3 \tag{2}\]  
where \(dif(a,b)\) returns the maximum number of least significant bit differences between two pixel values. Subsequently, the computation of (3) yields the variable \(md\), which represents the MSBs shared by four pixels:  
\[md=8-\max(d_{1},d_{2},d_{3}) \tag{3}\]  
Pixel blocks with \(md>0\) are selected as usable blocks for embedding data. Note that since \(md\in[1,8]\), the value of \(MD=md\)-1 can be expressed as three bits. A binary matrix of size \(\left\lfloor\frac{M}{2}\right\rfloor\times\left\lfloor\frac{N}{2}\right\rfloor\) is employed as a location map, to differentiate between usable blocks and unusable blocks. Based on the binary values of \(P\), \(C_{1}\), \(C_{2}\), \(C_{3}\), and \(md\), the usable blocks are reconstructed in pixel bits, thus vacating space for embedding data and being able to reversibly recover elemental pixel values when reconstructing the image. The procedure is divided into three steps:  
1. Eight bits of the upper-left pixel \(P\) and three bits of \(MD\). 2. Arrange the prediction errors \(e_{i}\), respectively, where \(e_{i}\) (\(i=1,2,3\)) is the remainder of \(C_{i}\) after removing the shared MSBs. 3. The remaining three \(\times\)\(MD\) bits are the space available for data-hiding represented by \(n_{c}\). The result after pixel bit reconstruction is shown in Figure 2.  
Figure 1: The structure of the pixel block. In Figure 3, an example illustrates pixel bit reconstruction for a 2 \(\times\) 2 pixel block: \(P=162=(10100010)_{2}\), \(C_{1}=161=(10100001)_{2}\), \(C_{2}=162=(101000010)_{2}\), \(C_{3}=161=(10100001)_{2}\). Here, we can figure out that the \(md=6\), and then we can infer that \(MD=5=(101)_{2}\), \(e_{1}=(01)_{2}\), \(e_{2}=(10)_{2}\), \(e_{3}=(01)_{2}\), and the remaining \(3\times(md-1)\) bits are the space available for data-hiding represented by \(n_{c}\). Upon completion of pixel bit reconstruction, block permutation is executed, to rearrange the usable and unusable blocks in a raster scan order and reverse raster scan order, respectively.