7.3.1.1. Capacity/quality trade-off

In data hiding methods, there is a real trade-off between the number of secret bits inserted in the encrypted image and the quality of the reconstructed image obtained after decrypting the marked encrypted image. A distinction may be made between two types of methods, depending on the quantity of bits of a secret message that can be inserted. Data hiding methods with a payload of less than half a bit per pixel are said to be low capacity. Conversely, a method is said to be high capacity when the payload is close to or in excess of one bit per pixel. No state-of-the-art methods offered the capacity to insert more than one bit per pixel until 2018. Some methods allow the message to be kept secret when the clear image is decrypted: in these cases, it is essential for the reconstructed image to be similar to the original clear image. A method is said to be fully reversible when the original image can be reconstructed without loss after the message has been extracted. Finally, note that the higher the number of bits to insert in the secret message, the more likely it is that the reconstructed image produced during the decoding phase will be degraded.

7.3.1.2. Two approaches to encoding

In terms of encoding approaches, data hiding methods may be grouped into two categories: those in which space is freed up for message embedding before encryption (reserving room before encryption, RRBE) and those in which space is made available for the message after encryption (vacating room after encryption, VRAE). These two approaches are shown in Figure 7.4. In RRBE methods, the original image is pre-processed by the owner before encryption in order to leave space for the bits of a secret message. The image is then encrypted and another person – such as a cloud server manager – may insert the bits of a secret message into the specific positions reserved for this purpose (Ma et al. 2013; Cao et al. 2016; Zhang et al. 2016; Puteaux and Puech 2018a). In VRAE methods, the content of the original image is directly encrypted by the owner with no pre-processing. The cloud server manager then modifies the encrypted data in order to embed the bits of the secret message (Puech et al. 2008; Hong et al. 2012; Zhang 2011, 2012; Qian et al. 2014). Both approaches are effective, but both present certain drawbacks. RRBE methods allow a larger number of bits to be embedded but require pre-processing before encryption. This may be difficult in practice if the owner of the image is not aware that the encrypted image needs to be analyzed or processed at a later stage. In VRAE methods, the person receiving the marked encrypted image must be able to predict the contents of the original image in order to reconstruct it. This means that the retrieved image is generally an estimation of the original, and perfect reversibility is not possible. Furthermore, the number of secret bits embedded must remain low in order to minimize distortion.

7.3.1.3. Two approaches to decryption

The extraction of a secret message and the reconstruction of the original image may be carried out jointly or separately during the decryption phase, as shown in Figure 7.5. In the joint case, the clear image cannot be obtained without knowing the data hiding key. Using the encryption key alone, it is only possible to obtain a degraded version of the original image (Puech et al. 2008). Furthermore, in certain methods, knowledge of the data hiding key alone is not sufficient to extract the message (Zhang 2011). In the case of separate operations, the message can be extracted and the original image can be reconstructed separately, i.e. by two different people. If a user only knows the encryption key, two cases are possible:

• – a clear image, marked with the secret message but very similar to the original, may be obtained (Zhang 2012);
• – the original image may be reconstructed perfectly, without being marked by the secret message (Puteaux and Puech 2018a).

Using the data hiding key alone, users may extract the secret message directly from the encrypted image. Note that the message can also be extracted in the clear domain if the chosen method allows this message to be preserved within the clear image.

7.3.2.1. Stream encryption

In most state-of-the-art methods (Zhang 2011), the original image I is stream encrypted. As we see from Figure 7.6, an encryption key K_e is used as the seed for a pseudo-random number generator (PRNG). This PRNG is used to obtain a sequence of pseudo-random bytes s(i, j). The encrypted pixels p_e(i, j) are then calculated using an exclusive-or with the values of s(i, j):

[7.1]

As the encryption operation is fully reversible and causes no overflow, the original image I can be retrieved from the encrypted image I_e with no alterations. Note that the pseudo-random sequence may be generated using a cryptographically secure pseudo-random number generator (CSPRNG), a chaotic generator (Li et al. 2005), or even the AES algorithm (Daemen and Rijmen 1999) in OFB mode.

7.3.2.2. Symmetrical block encryption

Certain methods in the state of the art exploit the correlation within the pixel blocks of images in the clear domain (Puech et al. 2008). They thus use symmetrical block encryption to preserve the block structure of pixels in the encrypted image. The most commonly used method is the Advanced Encryption Standard (AES) (Daemen and Rijmen 1999). Designed in 1999 by Joan Daemen and Vincent Rijmen, AES is composed of a set of operations, repeated over several repetition cycles, or rounds. The number of rounds depends on the size of the encryption key: 10 cycles for 128-bit keys, 12 cycles for 192-bit keys or 14 cycles for 256-bit keys. The first stage in encrypting a 128-bit sequence is to apply the AddRoundKey operation. Each byte in the sequence is combined with an associated block in the round key using an exclusive-or operation. Next, four different operations are performed during each round: SubBytes, ShiftRows, MixColumns and AddRoundKey. The SubBytes operation is a nonlinear substitution step where each byte is substituted with another according to a conventionally defined table. The ShiftRows operation is a transposition step where the last three lines of the block undergo a cyclical shift. MixColumns is a linear shuffle operation that operates on the columns of the block, combining the four bytes of each column. The last round consists of the same operations with the exception of MixColumns. The AES algorithm has the capacity to support different encryption modes, such as ECB (Electronic Code Book), CBC (Cipher Block Chaining), CFB (Cipher Feedback), OFB (Output Feedback) or CTR (Counter), for example.

7.3.2.3. Public key encryption

Many data hiding methods that draw on the probabilistic and homomorphic properties of public key cryptosystems use Paillier’s cryptosystem to encrypt the original image. Paillier’s system, introduced in 1999 (Paillier 1999), involves the following steps. First, to generate the public and private keys, two prime numbers p and q are chosen such that:

[7.2]

Values n and λ are then calculated:

[7.3]

A number is selected such that:

[7.4]

where L(·) is the application defined by:

[7.5]

The public key is thus (n, g) and the private key is (λ, μ). Given a message to encrypt m, with 0 ≤ m < n, in the case of image encryption, m generally corresponds to a pixel block. To encrypt this message, a random number r is generated, with r ∈ . Note that choosing r in this way guarantees that the Paillier cryptosystem will be non-deterministic.

The final step is to calculate the encrypted message c:

[7.6]

where E(·) is the encryption function of the Paillier ecosystem.

Note here that squaring n results in an inflation of the size of the encrypted message in relation to the clear message.

The original clear message m can then be reconstructed from the encrypted message c:

[7.7]

where D(·) is the encryption function of the Paillier cryptosystem.

Furthermore, Paillier’s cryptosystem possesses a homomorphic property in that decrypting the product of two encrypted messages corresponds to summing the two corresponding messages m₁ and m₂ in the clear domain:

[7.8]

7.3.3.1. Quantity of embedded bits

The quantity of bits embedded in a message is expressed in bits per pixel. For an image with pixels encoded over 256 levels of gray, this quantity is thus between 0 and 8 bpp. A distinction can be made between embedding capacity and payload. Embedding capacity relates to the total number of bits that can be inserted into an image by applying the data hiding method. The payload denotes the total number of bits in a message that can be inserted into the image. Thus, the payload may be significantly lower than the embedding capacity, notably when the chosen data hiding method requires some of the capacity to be sacrificed to leave space for additional information, for example for overflow management (Huang et al. 2016) or for pixels that are hard to predict (Puteaux and Puech 2018a).

7.3.3.2. Bit error rate

When extracting the message from the marked encrypted image (or the marked decrypted image, where applicable), the bit error rate is calculated by dividing the number of erroneously reconstructed bits by the total number of bits in the secret message. The resulting number of bits must be as low as possible to ensure proper transmission of the secret data inserted into the encrypted image. In most of the state-of-the-art methods, the bit error rate is zero, indicating that the secret message is extracted without error.

7.3.3.3. Visual quality

The visual quality of the image that is reconstructed by decrypting the marked encrypted image compared to the original clear image can be evaluated using two different metrics, both widely used in image coding and compression. Note that the quality of the reconstructed image can be evaluated both before and after message extraction. If the chosen data hiding method allows the secret message to be retained in the decoded image, we may evaluate the distortion resulting from message insertion in the original image. However, it is important to realize that some methods are irreversible, and the original image cannot be recovered without alteration after the message has been extracted.

7.3.3.3.1. Peak signal-to-noise ratio

Peak signal-to-noise ratio (PSNR) is used to measure the quality of a reconstructed image with respect to the original image. The following formula is used:

[7.9]

where is a pixel in the original image and p′(i, j) is the corresponding pixel in the reconstructed image, both of size m × n pixels coded on 255 levels of gray.

PSNR is measured in decibels (dB). The PSNR between two images with entirely different content is around 10 dB. For two images which are similar but affected by noise, it is around 15 dB. If the two images are very similar, the value is above 30 dB. Finally, in cases of perfect reconstruction, that is, when the two images are strictly identical, the value of the PSNR tends toward Note that many data hiding methods that are considered reversible have a PSNR value of around 50 dB. The major drawback of PSNR is that it fails to take account of the visual quality of the reconstructed image; as such, it cannot be considered to be fully objective. For this reason, another metric – structural similarity (SSIM) – is also used.

7.3.3.3.2. Structural similarity

SSIM is used to evaluate the similarity between the structures of two images, rather than between corresponding pixels, as in the case of PSNR (Wang et al. 2004). The underlying hypothesis is that the human visual system is more sensitive to changes in the structure of an image. The formula used is as follows:

[7.10]

where x and y are windows in the two images, E(x) is the mean of the set x, V (x) is its variance, Cov(x, y) is the covariance between sets x and y, γ₁ = (0.01 × 255)² and γ₂ = (0.03 × 255)².

This formula is applied to different windows in the two images to be compared. The average between the different values obtained is then calculated to obtain the global SSIM value. This value is between 0 and 1; a value of 1 indicates that the two images are strictly identical. Note that it is often necessary to observe at least three decimal places for the SSIM value to be significant.

7.3.3.4. Visual security level

No metric has yet been defined specifically to evaluate the visual security level of marked encrypted images. As such, we shall draw on the work of Preishuber et al. (2018) to describe the metrics used by many authors to experimentally demonstrate the visual security of image encryption methods. We conclude that a good level of visual security is achieved in the marked encrypted image when the message embedding phase does not affect the security level of the encryption method. On the other hand, if the embedded message is itself encrypted, embedding this message into an encrypted image amounts to hiding “noise in noise”; thus, the encrypted message cannot, a priori, be detected in the encrypted domain.

7.3.3.4.1. Correlation coefficient

One classic approach is to observe the correlation between pixels in horizontal, vertical and diagonal directions. M pairs of neighboring pixels (x_i, y_i) are chosen in all three directions, with x_i ∈ x and y_i ∈ y, in order to calculate the correlation coefficient:

[7.11]

where E(x) is the mean of set x.

The value of this correlation coefficient falls between – 1 and 1, with – 1 and 1 indicating strong correlation and 0 an absence of correlation. As the values of neighboring pixels in the clear domain are strongly correlated, corr_{x, y} is generally high for the original image. However, it should be close to zero in the encrypted domain.

7.3.3.4.2. Shannon entropy

Shannon entropy is a measure of the quantity of information used to evaluate the randomness of the distribution of pixels in a marked encrypted image (Shannon 1948):

[7.12]

where I is an image of m × n pixels coded on N values is the probability associated with α_k.

The entropy value is expressed in bits per pixel (bpp) and falls between 0 bpp and log₂(N) bpp, when the pixel distribution is perfectly uniform. Generally speaking, grayscale images are coded on 256 values. In this case, the maximum entropy is log₂(256) = 8 bpp. The entropy value of a marked encrypted image should be very close to the maximum entropy value.

7.3.3.4.3. χ² test

The uniformity of the pixel distribution in a marked encrypted image can also be evaluated using the chi-square test, defined as:

[7.13]

where the pixels in the image are coded on N values is the probability associated with α_k.

The lower the value obtained, the closer the pixel distribution of the marked encrypted image is to a uniform distribution, indicating a higher level of visual security. Note that the square root of the χ² value is often used.

7.3.3.4.4. Number of changing pixel rate

The number of changing pixel rate (NPCR) between two images of size m × n pixels, p(i, j) and is given by Wu et al. (2011):

[7.14]

where d(i, j) is defined by:

[7.15]

This value is expressed in % and is used to determine the extent to which an encrypted (or marked encrypted) image differs from the original. Thus, the closer the value is to 100%, the larger the difference between the two images, and the higher the level of visual security.

7.3.3.4.5. Unified averaged changed intensity

Unified averaged changed intensity (UACI) is also used to measure the difference between two images of m × n pixels, of which pixels p(i, j) and are coded on 256 grayscale values (Wu et al. 2011):

[7.16]

This value is also expressed as a percentage. The higher the value, the higher the visual security level. Note that the ideal value depends on the range of tones used in the image. This metric can be used to test the sensitivity of the encryption key. The original image is encrypted using two keys with only one different bit, and the resulting images are then compared. In this case, the optimum value of the UACI is 33.33% (Preishuber et al. 2018). However, the UACI value is often lower when used to compare an original clear image and its marked encrypted counterpart. Note that there is no statistical decision criterion for this test; optimal values are determined on a purely experimental basis.

7.4.1.1. Use of the data hiding key

In one of the very first data hiding methods, Zhang (2011) proposed a stream-based approach to encrypting the original image. The encrypted image is then divided into blocks of s × s pixels, with the aim of hiding one bit of the secret message in each block. The pixels in each block are then partitioned into two groups, S₀ and S₁, using the data hiding key. If the bit of the secret message to be inserted is 0 (respectively, 1), the three least significant bits (LSB) of each pixel in S₀ (respectively, S₁) are inverted. During the decoding phase, the marked encrypted image is decrypted in order to obtain an approximation of the original image. The five most significant bit (MSB) planes are perfectly reconstructed, and only the LSB may be altered. A fluctuation function is then used to evaluate the irregularities in the S₀ and S₁ groups of reconstructed pixels. The bits of the secret message can then be extracted and the original configuration of each block can be recovered. However, while the chances of perfectly reconstructing the original image can be improved by increasing the size of the blocks, Zhang’s method is not reversible as perfect reconstruction is not guaranteed. Moreover, the payload is low (less than 0.1 bpp) since only one bit is inserted per block. Improvements to this method have been proposed in the literature (Zhang 2011; Hong et al. 2012).

7.4.1.2. Use of a fluctuation function

Ma et al. (2013) were the first to propose a RRBE approach, in a radical break from existing methods. The authors began by dividing the original image into blocks. The correlation between pixels in each block was evaluated using a fluctuation function. The blocks were then partitioned into two groups, A and B: A is composed of textured blocks and B of relatively homogeneous blocks. Blocks from group A are placed at the beginning of the image and blocks from group B are placed at the end. To free up space for a secret message, the bits of the LSB planes of A are inserted, by histogram shifting, into the clear domain in the group B pixels. The resulting image is then stream-encrypted and the number of pixels that can be marked is stored in the LSB of the first pixels of A. Using this information, a secret message can be embedded by simply substituting the LSBs of the other pixels of A. Note that the first three LSB planes of each pixel can be used. The total payload of the marked encrypted image can thus reach 0.5 bpp: a payload 10 times higher than that offered by previous state-of-the-art methods. Finally, in the reconstruction phase, message extraction and original image reconstruction can be performed separately.

7.4.2.1. Pixel difference or prediction error histograms

Huang et al. (2016) noted that existing data hiding algorithms designed for the clear domain cannot be applied in the encrypted domain. This is due to the fact that classical encryption methods are unable to maintain the correlation between neighboring pixels without creating a security risk. The authors thus developed a new strategy for image encryption that is robust with respect to the application of classic data hiding methods in the clear domain. First, the original image is divided into non-overlapping blocks. All pixels in each block are encrypted by applying an exclusive-or with the same pseudo-randomly generated byte. Next, the blocks in the resulting image are pseudo-randomly swapped. Note that pixels within the same block are not swapped: only the order of the blocks changes. Using this encryption method, the statistical properties of the clear image, notably pixel difference or prediction error histograms, are preserved. This means that existing data hiding algorithms designed for the clear domain can now be applied directly in the encrypted domain. However, embedding capacity is limited by the need to manage overflow problems.

7.4.2.2. Homomorphism and pixel value ordering

Xiao et al. (2017) proposed an adaptation of the pixel value ordering concept, defined for the clear domain by Li et al. (2013), for the homomorphic encrypted domain. The authors began by noting that, by adapting the encryption method, it was possible to obtain a histogram of pixel differences with a zero-centered Laplacian distribution, identical to that of the clear domain, in the encrypted domain. After encryption, the image is divided into non-overlapping blocks of 2 × 2 pixels. The four pixels in each block are then rearranged into ascending order, noted The pixel with the highest value (p_e4) is then selected for data hiding. This operation is carried out by calculating the difference d between p_e4 and p_e3. A bit b ∈ {0, 1} is then inserted into p_e4 as a function of the value of d, resulting in a marked version p_e−m4 such that:

[7.17]

Note that a similar operation can also be applied to embed a bit in the pixel with the lowest value p_e1. In this method, the order of the pixels remains unchanged after the data hiding. In terms of the histogram, this operation is equivalent to expanding the bins associated with the difference values of 0 and 1, and shifting the other bins. This method offers a solution to the data expansion problem encountered with many similar methods in the encrypted domain. Nevertheless, the embedding capacity is limited: 0.2 bpp. This is due to the fact that the marked encrypted image needs to store a location map of blocks that are prone to overflow, resulting in a significant payload reduction.

7.4.2.3. Pixel value histogram

Ge et al. (2019) recently proposed a data hiding method based on a shift in the pixel value histogram. Instead of using the pixel difference or prediction error histogram, as in Huang et al. (2016), the authors suggest modifying pixel values directly within a block. Unlike Xiao et al. (2017), the pixels used for data hiding are not necessarily those with the highest, or lowest, value in the block. Two reference pixels, p_ei and p_ej , with p_ei < p_ej , are selected in a pseudo-random manner using a data hiding key. All other pixels p_ek in the block are then modified to p_e−mk in order to embed a bit b of the secret message:

[7.18]

This operation is applied to all blocks in the image. Furthermore, secret data can be embedded several times throughout the image: this has the effect of increasing the embedding capacity. With a single pass over the image, the Ge et al. (2019) method embeds half of the payload obtained in the Xiao et al. (2017) approach, since the size of the location map for blocks subject to overflow problems is larger. If several passes are performed, on the other hand, a payload of 0.8 bpp can be reached if a degradation in the quality of the original image is acceptable.

7.4.3.1. Distributed source encoding

Qian and Zhang (2016) proposed the use of distributed source encoding in a data hiding method. During the encoding phase, the original image is first encrypted using a stream approach. The encrypted image I_e with pixels p_e(i, j), with 0 ≤ i < m and 0 ≤ j < n, is then split into four sub-images of which the pixels are such that:

[7.19]

Note that the decryption of each of the sub-images produces a miniature copy of the original image. Once the sub-images have been obtained, bits from the three MSB planes of are permutated and compressed using LDPC codes (Slepian and Wolf 1973). This compression vacates space to embed a secret message. The decoding phase is fully separable. The unmodified sub-image is decrypted then oversampled by bilinear interpolation in order to obtain a reference image to reconstruct the clear version of the marked image. For reconstruction purposes, LDPC codes are decoded using a sum-product algorithm (Liu et al. 2009).

7.4.3.2. Sparse coding

Cao et al. (2016) developed a data hiding method using sparse coding with the aim of permitting a high payload. A three-step RRBE encoding approach is used. First, the original image is divided into patches. These patches are then represented using a redundant dictionary with sparse coding. Next, the most homogeneous patches with the smallest residual errors are selected as the location for secret message insertion and are represented using sparse coefficients. The residual errors are encoded and embedded in patches that are not selected for data hiding, using a classic data hiding algorithm for clear images. Finally, stream encryption is used to protect the clear data. Once the image has been encrypted, bits of a secret message can be inserted into the designated space. In this case, the decoding phase is separative and reversible. The original image can be losslessly reconstructed, using the residual errors extracted from the unmarked patches. This means that the secret message can also be found.

7.4.4.1. Prediction based on local standard deviation

Puech et al. (2008) proposed one of the very first data hiding methods in an article published in 2008. This method uses a VRAE approach for encoding. The original image is encrypted in blocks of 16 pixels in grayscale (128 bits) using the AES algorithm in ECB mode. One bit of the secret message is then embedded in each block of the encrypted image, corresponding to an embedding capacity of 0.0625 bpp. Note that a data hiding key is used as the seed for a pseudo-random generator to identify the pixel to mark and the location of the bit to replace with a bit from the secret message. The marked encrypted image is obtained once all blocks have been traversed. During the decoding phase, the message is extracted by using the data hiding key to read the bits of the pixels that have been marked. However, after extraction, the pixels are still marked by the message bits, which makes the image difficult to decode. To overcome this problem, local analysis of the standard deviation in each block is performed. For each block of the marked encrypted image, the marked bit is located using the data hiding key, then replaced by the two possible values of the substituted original bit (0 and 1). This gives us two decrypted configurations: one corresponds to the original clear image block, while the other is erroneous and looks like a fully encrypted block. The hypothesis that the standard deviation in an encrypted (wrongly decrypted) block is greater than that in a clear (correctly decrypted) block is then used. The standard deviation associated with the two decrypted configurations is calculated and the pattern with the lower standard deviation value is selected as the clear block. Note that, as the data hiding key is required to reconstruct the original image, extraction and decoding must be carried out jointly.

7.4.4.2. Prediction by interpolation

Wu and Sun (2014) developed a data hiding method in two different forms: a joint approach and a separative approach. In both cases, the first step is a stream encryption of the original image. A subset of pixels is then selected, as a function of the data hiding key, to insert a hidden message. Note that the neighbors of the selected pixels will be used to predict these pixels during decoding. In the joint approach, to insert a hidden bit, the LSB of the selected pixels are inverted if the message bit is equal to 1, or left unchanged if the message bit is 0. During decoding, unmarked neighboring pixels are interpolated to predict the original value of each marked pixel and the value of the inserted bit. In the separative approach, the LSB of the selected pixels are replaced by the value of a bit in the secret message. An approximation of the original image is reconstructed during decoding using a median filter. Improvements to these approaches have since been proposed (Dragoi et al. 2017; Dragoi and Coltuc 2018).

7.4.5.1. Methods based on Pailler’s cryptosystem

Chen et al. (2014) proposed the first data hiding method based on the use of the Paillier cryptosystem. Each pixel in the original image is split into two distinct parts: an even integer, made up of the seven MSB, and the LSB. Each part is encrypted independently, and a bit from the message is embedded into each pair of neighboring pixels. During decoding, all of the pairs of decrypted pixels are compared in order to reconstruct the whole of the secret message and the original clear image. The main drawback in this approach is the fact that overflow problems are not managed. Shiu et al. (2015) proposed a solution to this problem, applying the concept of difference expansion to the homomorphic encrypted domain. Note that both of these methods rely on an RRBE approach. Methods using the Paillier cryptosystem with VRAE have since been proposed by Wu et al. (2016) and Zhang et al. (2016).

7.4.5.2. Methods based on LWE encryption

The first data hiding method using LWE encryption was proposed by Ke et al. (2016). The authors indicate that the use of an LWE algorithm offers a high level of security, simple and fast implementation, and controllable redundancy for hidden data insertion. They established parameters for the LWE encryption and described their multi-level data hiding approach, based on recoding the redundancy in the encrypted domain using homomorphic operations. The main drawback of this approach is that it is not fully separative.

7.6.1.1. Encoding

The encoding phase consists of three steps: detection of prediction errors in the MSBs, accounting for prediction errors combined with image encryption, and embedding of the secret message by replacing the MSBs. An outline diagram of the encoding method is shown in Figure 7.7.

In this method, since the secret message is embedded by MSB substitution, the original MSB values are lost after the secret message is embedded. Thus, it is important to be able to predict these values without error during the decoding phase. To recover the original image, the previously reconstructed pixels are used to predict the current pixel value. The first step is thus to analyze the content of the original image to detect any prediction errors:

• – consider the current pixel p(i, j), with and its inverse value, As the difference between these two values is 128, the inverse value corresponds to the original value of p(i, j) but with an inversed MSB;
• – using the values of the neighbors of p(i, j), we calculate the value pred(i, j), regarded as a predictor in the decoding phase;
• – we calculate the absolute difference between pred(i, j) and p(i, j) and between pred(i, j) and inv(i, j). The resulting values are noted Δ and Δ^inv and are such that:

[7.20]

• – we then compare the values of Δ and Δ^inv. If Δ < Δ^inv, then there is no prediction error, since the original value of p(i, j) is closer to the predictor than the inverse value. Otherwise, an error is identified and its location will be specified in a binary error location map, as shown in Figure 7.7.

Depending on the chosen approach, the binary error location map may be used in one of two ways. The original image may be pre-processed to correct prediction errors, resulting in an image I′, which is very similar to the original. The other option is to indicate the location of prediction errors in the encrypted domain after encrypting the original image, instead of correcting them.

In both cases, the clear image is encrypted using a stream approach, as described in section 7.3.2. This results in the encrypted pixels p_e(i, j):

[7.21]

where s(i, j) is the byte corresponding to p(i, j) in a pseudo-random binary sequence and ⊕ is the exclusive-or operation.

Note that in the case of the error signaling approach, the encrypted image will be modified.

During the message insertion phase, using the data hiding key K_m, the secret message is encrypted to prevent it from being detected in the marked encrypted image. Next, the pixels in the encrypted image are passed through in scanline order (left to right and top to bottom), and the MSB of each available pixel is replaced with a bit b_k, with 0 ≤ k < m × n, from the secret message in order to obtain the corresponding pixel p_e−m(i, j):

[7.22]

Note that only the first pixel cannot be marked, since its value cannot be predicted: this pixel is therefore left unchanged.

7.6.1.2. Decoding

Since the method is separable, the secret message can be extracted and the original clear image can be reconstructed independently during the decoding phase. is strictly identical to the original image I or to the pre-processed image I′, which is very similar to the original image, depending on the chosen approach. There are then three possible scenarios for the recipient of the data:

1. 1) the recipient only has the data hiding key K_m;
2. 2) the recipient only has the encryption key K_e;
3. 3) the recipient has both keys.

A general outline of the decoding phase is shown in Figure 7.8.

If the recipient of the data only has the data hiding key K_m, the pixels in the marked encrypted image will be read in scanline order and the MSB of each pixel will be extracted to obtain the bits of the encrypted secret message:

[7.23]

where 0 ≤ k < m × n and relates to the index of the extracted message bit.

The corresponding clear version of the secret message is then obtained using the data hiding key.

In the second case, if the recipient of the data holds only the encryption key K_e, image can be reconstructed in the form it had prior to message insertion and encryption:

1. 1) the encryption key K_e is used to generate a pseudo-random binary sequence of m × n bytes s(i, j);
2. 2) the pixels in the marked encrypted image are read in scanline order, and the seven LSB of each pixel are reconstructed by applying an exclusive-or between the marked encrypted value p_e−m(i, j) and the corresponding byte s(i, j) in the pseudo-random binary sequence:
   [7.24]

   where ⊕ is the exclusive-or operation;

3. 3) the value of the MSB is predicted in the following manner:
   • - the value of the predictor pred(i, j) is calculated using the values of neighboring pixels that have already been reconstructed;
   • - the two possible values of the original pixel are generated, with MSB = 0 and MSB = 1. The differences between these two values and pred(i, j) are calculated and noted Δ⁰ and Δ¹:
     [7.25]
   • - the lowest value from Δ⁰ and Δ¹ gives us the desired value of the original pixel:

[7.26]

7.6.2.1. Choice of predictor

As we saw in section 7.6.1.1, the value of the current pixel is predicted using those of the previous pixels. In this approach, the mean value of the pixel to the left and the pixel above the current pixel is used as the predictor pred(i, j):

[7.27]

Note that a specific treatment is used for pixels in the first line and the first column.

Using the mean value as a predictor minimized the modification in the value of the current pixel in cases of error, notably when the difference between the value of the current pixel and that of one of its neighbors is large.

7.6.2.2. Image pre-processing

Once prediction errors have been detected, the original image I is pre-processed to generate an image I′ free from prediction errors. The value of the prediction error is observed for all pixels concerned, then the minimum modification required to correct the error in the current pixel is calculated. The modification used to eliminate all errors during the decoding phase is given in equation [7.28]:

[7.28]

The pre-processing steps applied to the original image to correct all prediction errors are shown in Algorithm 7.1.

The predicted image I′ is then encrypted. The secret message is inserted by replacing the MSB of each pixel in the encrypted image with a message bit, following equation [7.22]. Finally, the marked encrypted image is obtained, with a maximum payload of 1 bpp.

7.6.2.3. Message extraction and image reconstruction

During decoding, to extract the secret message, the marked encrypted image is read and the MSB for each pixel is simply extracted using equation [7.23]. The original preprocessed image I′ can also be reconstructed without loss. To do this, the marked encrypted image is decrypted to give the seven LSB of each pixel (equation [7.24]), then the value of the MSB is predicted by applying equations [7.25] and [7.26]. Note that the reconstructed image is very similar to the original image.

7.6.3.1. Predictor choice

For each pixel, two neighboring pixels may be used as predictors: the pixel on the left p(i, j − 1) and the pixel directly above p(i − 1, j). To identify which of these pixels to use as the predictor, the absolute value of their difference with the current pixel p(i, j) is calculated and the nearest value is selected:

[7.29]

In certain cases, the other value may be used to predict the inverse of the pixel inv(i, j) during error prediction, but the result remains the same. Note that the mean of the left and upper pixel may also be used as the predictor, as in the CPE-HCRDH approach, but the results obtained experimentally in this case were not as good.

7.6.3.2. Signaling the location of errors

During the prediction error detection stage, the locations of errors are indicated in a binary error location map, as described in section 7.6.1.1. Next, the original image I is encrypted, and the encrypted image I_e is adapted prior to data hiding in order to eliminate prediction errors. The image is divided into blocks of 8 pixels then read in scanline order. If there is at least one prediction error in a block, according to the binary error location map, the current block is flagged on both sides by replacing the MSB of each pixel in the previous and following blocks with a 1. In the current block, the MSB is replaced by a value of 1 if there is a prediction error and by 0 otherwise, as shown in Figure 7.11. If there are no errors in the current block and if it is not used for flagging purposes, then all eight pixels in this block will be used for message embedding, as described in section 7.6.1.1. If errors are found in two adjacent blocks, the flag indicating the end of the error is shifted to the next error-free block. This reduces the payload loss since flags may be used for more than one prediction error. Note that smaller blocks may be used, but the statistical risk of part of the secret message being identified as a flag is increased. Using blocks of eight pixels gives a good tradeoff between payload loss and the risk of false alarms. Few pixels cannot be marked with bits of the secret message, and the probability of part of the message being mistaken for a flag is very low

This method produces an encrypted image with embedded prediction errors. With this type of processing, during the insertion phase, the MSB values of each pixel can be extracted and the error location information can be used to detect which pixels can be marked with secret message bits (i.e. in all blocks where there are no prediction errors and that are not used as flags). All available pixels are then marked to obtain the encrypted marked image I_e−m, using equation [7.22].

7.6.3.3. Message extraction and image reconstruction

The secret message can be extracted during the decoding process using the following steps:

• – the pixels of the marked encrypted image I_e−m are read and the MSB value for each pixel is extracted, following equation [7.23], and stored. All bits extracted up until the first sequence of 8 bits equal to 1 are considered to belong to the secret message;
• – a sequence of 8 bits equal to 1 indicates the start of a sequence that includes prediction errors. Given that the following pixels were not marked during the message insertion phase, pixels will be skipped over up until the next sequence of eight MSBs equal to 1, which indicates the end of the error sequence;
• – this process is repeated throughout the whole image.

Furthermore, since this method is entirely reversible, the original image I is perfectly reconstructed. The marked encrypted image I_e−m is first decrypted to obtain the seven LSBs for each pixel using equation [7.24]. The values of the MSB of each pixel are then predicted using equations [7.25] and [7.26].