Pauline Puteaux
email: pauline.puteaux@lirmm.fr

Simying Ong
email: simying.ong@um.edu.my

Koksheik Wong
email: wong.koksheik@monash.edu

William Puech
email: william.puech@lirmm.fr

A Survey of Reversible Data Hiding in Encrypted Images -The First 12 Years

Keywords: Multimedia security, image encryption, data hiding, signal processing in the encrypted domain

A C T

In the last few years, with the increasing popularity of cloud computing and the availability of mobile smart devices as well as ubiquitous network connections, more and more users are uploading their personal data to remote servers. However, this can lead to significant security breaches, where confidentiality, integrity and authentication are constantly threatened. To overcome these multiple problems, multimedia data must be secured, for example by means of encryption before transmission and storage. In this survey, we look into the issues involved in handling encrypted multimedia data, and more specifically we focus on reversible data hiding in encrypted images (RDHEI). The aim of this survey is to present the birth and evolution of RDHEI methods over the last 12 years. We first highlight different classes and characteristics of RDHEI, then describe representative RDHEI methods. A comparison table is presented to summarize the key features and achievements of each representative RDHEI method considered in this survey. Finally, we share the future outlook of emerging applications and open research topics relevant to RDHEI for the next 12 years and beyond.

Introduction

In the age of omnipresent network connectivity and the availability of powerful general computing resources at affordable prices, the digital image is certainly worth more than a thousand words. To put statistics into context, more than 147, 000 pictures are posted on Facebook alone every 60 seconds [START_REF] Aslam | Facebook by the numbers: Stats, demographics & fun facts[END_REF]. Furthermore, many email communications contain images as attachments and images are also sent via instant messaging platforms. Moreover, people often express themselves by using emoticons and short animated Graphics Interchange Format (aGIF) images, which add dynamism to the conventional text-based / message communication.

While the image has certainly revolutionized our daily lives, it is subject to various threats. Some of the classical examples include pictures of public figures (e.g. politicians) being edited to favor a particular group, pictures of celebrities' private lives being exposed to the public, copyrighted images (including books and documents) being copied then sold at lower prices, to name a few. Foreseeing these problems, researchers have proposed various techniques to protect digital images in general. One of the commonly researched approaches is called data hiding, where a data (payload) is embedded into a host image to serve a specific purpose. Here, the data content can be independent from the image (i.e. external), derived / extracted from the image, or a combination of both [START_REF] Tew | An overview of information hiding in H.264/AVC compressed video[END_REF]. One of the most extensively researched areas is watermarking, where the owner's copyright data is embedded into the image [START_REF] Cox | Digital watermarking and steganography[END_REF]. When there is any dispute over the unauthorized utilization of a watermarked image, the embedded data can be extracted to prove ownership. The embedded watermark data is designed to withstand various forms of attack. In other words, the watermarked image is rendered useless (i.e. with most details being destroyed) when the embedded watermark fails to be recovered from the processed image, essentially a lose-lose situation. Another application is fragile watermarking, where the embedded watermark serves as a verification code, such as an authenticity or integrity check [START_REF] Tew | Multi-layer authentication scheme for hevc video based on embedded statistics[END_REF]. When any part of the watermark-protected image show any discrepancies, those parts are subjected to investigation, i.e. could they be forged or tampered with. To cater for the scenario where the host image cannot afford any form of distortion (e.g. medical, military, rare artwork), reversible techniques are proposed so that the embedded data can be removed to perfectly restore the original image [START_REF] Ren | Reversible data hiding in encrypted binary images by pixel prediction[END_REF][START_REF] Qian | New framework of reversible data hiding in encrypted JPEG bitstreams[END_REF][START_REF] Xiang | Reversible data hiding in homomorphic encrypted domain by mirroring ciphertext group[END_REF][START_REF] Ge | A high capacity multi-level approach for reversible data hiding in encrypted images[END_REF][START_REF] He | A novel high-capacity reversible data hiding scheme for encrypted JPEG bitstreams[END_REF][START_REF] Chen | Reversible data hiding in encrypted images with additive and multiplicative public-key homomorphism[END_REF].

Encryption can also aim to conceal the perceptional meaning of an image. It aims to protect the image from unauthorized viewing, which promotes privacy and combats piracy. Almost all image encryption approaches rely on two basic building blocks, namely, permutation and substitution [START_REF] Shannon | Communication theory of secrecy systems[END_REF]. Some advanced image encryption techniques also make these operations dependent on the statistics / attributes of the input image, making cryptanalysis more challenging [START_REF] Coppersmith | A proposed mode for triple-DES encryption[END_REF][START_REF] Daemen | The design of Rijndael: AES -the Advanced Encryption Standard[END_REF]. In fact, in the case of images, the notion of security can be viewed from different perspectives. Specifically, in addition to the traditional cryptanalysis where the goal is to obtain the secret/private key, obtaining some idea of the plaintext image (e.g. outline) is sufficient [START_REF] Minemura | A novel sketch attack for H.264/AVC format-compliant encrypted video[END_REF]. In other words, the adversary does not need to get an exact copy of the original image, but a general outline may be sufficient. In any case, the practice of encrypting an image (as well as all other files) is becoming more common today due to online cloud storage services which are also available at no financial cost.

For many years, researchers in both fields have been making breakthroughs independently. However, both data hiding and encryption can be jointly deployed to provide extra features. One of the earliest efforts in combining data hiding and encryption has been proposed by Puech et al. in 2008 [15]. Researchers then started to invest in this direction, this is backed up by the increasing number of publications related to the unification of both data hiding and encryption. Fig. 1 depicts the number of publications regarding the joint deployment of data hiding and encryption in the last 12 years. Notably, the number of publications in 2019 is ∼40 times more than that of 2009. This drastic increase is driven by the needs of various applications, including:

1. Digital rights management (buyer-seller protocol): Prior to transmission, a content seller encrypts the content to avoid unauthorized viewing. To deter illegal distribution by the buyer, the seller watermarks the content as well as embedding the buyer's information (i.e. fingerprinting), making each sold content a unique copy for tracking and tracing purposes. However, it is possible that the seller can frame an honest buyer by embedding his fingerprint into the content and distribute it for free. In order to prevent framing, the buyer-seller protocol is put forward so that the seller embeds a watermark, in which the final form of the watermark is not known to the seller [START_REF] Poh | An efficient buyer-seller watermarking protocol based on chameleon encryption[END_REF]. A thorough treatment of encryption and fingerprinting in video can be found in [START_REF] Kundur | Video fingerprinting and encryption principles for digital rights management[END_REF].

2. Cloud storage: For privacy purposes, a user could encrypt his personal contents, including audio, image and video, prior to uploading them to a cloud for storage. For management purposes, the cloud administrator embeds data into the encrypted content, including data needed for indexing and statistics collection.This inspired the application of data hiding in encrypted content [START_REF] Karim | Universal data embedding in encrypted domain[END_REF].

3. Patient's privacy: In hospitals, diagnosis images / documents of a patient are encrypted to ensure privacy, and patient's information is embedded into these contents for identification purposes. The nurses handling these contents can extract the embedded information from the encrypted content. The same information can be considered to link contents of a particular patient. On the other hand, the doctors / specialists can have access to both the patient's identification information as well as the original (i.e. plaintext) diagnosis images / documents. 4. Classified information: In a military situation, an under-officer with a lower clearance (e.g. clerk) can extract the embedded labels from the encrypted files (e.g. videos, documents, audio) to administer the files (e.g. copy, archive, move, etc.). On the other hand, the senior officer with a higher clearance (e.g. general) can access both embedded labels and the original files.

5.

Reporter from the field: A reporter would encrypt an audio/image/video before transmitting it back to head quarters so that only the designated officers (especially not those from the rival news companies) can have access to the content for presenting exclusive coverage of the incident / event. Information such as the sender ID and Global Positioning System (GPS) location of the field reporter can be embedded for authentication purposes [START_REF] Wong | Data embedding for geo-tagging any contents in smart device[END_REF] to avoid content forgery (e.g. framing by rival companies).

6. Surveillance video recording: Video recording from a surveillance camera is selectively encrypted (e.g. region-of-interest masking) to avoid privacy infringement [START_REF] Sohn | Privacy protection in video surveillance systems: Analysis of subband-adaptive scrambling in JPEG XR[END_REF]. In addition, the camera ID, time, date, etc. are embedded because they are crucial information for authentication purposes, especially when the recording is presented during a court session as evidence.

7. Data analytic: Data is massively generated / collected nowadays thanks to the advent of data intensive science discovery [START_REF]The Fourth Paradigm: Data-Intensive Scientific Discovery[END_REF].

The data needs to be labelled, but at the same time some form of privacy / secrecy must be ensured. The joint adaptation method can be readily deployed to handle such information.

In general, data hiding and encryption can be used together in 4 different ways, namely: 1) Insert-then-encrypt (ITE), 2) Encryptthen-insert (ETI), 3) Insert-to-encrypt (I2E), and 4) Encrypt-to-insert (E2I) [START_REF] Ong | Data Insertion and Scrambling for Unified Scalable Information Hiding[END_REF]. In each of these cases, the output is an encrypted image with hidden data as illustrated in Fig. 2. ITE and ETI basically perform data hiding and encryption in a sequential manner. I2E aims to severely distort the quality of the image, which is going completely against the traditional principle of data hiding, i.e. to maintain the quality of the image [START_REF] Ong | A scalable reversible data embedding method with progressive quality degradation functionality[END_REF]. On the other hand, E2I restricts the operations in the conventional perceptual encryption technique, where the ciphertext image is generated based on the data to be hidden. For example, the notion of a 'natural' state of some selected elements (e.g. group of pixels) is identified. The elements are then processed (e.g. cycle-shift) and the distance between the Fig. 2: Four typical ways to deploy data hiding and encryption in an image: 1) Insert-then-encrypt (ITE), 2) Encrypt-then-insert (ETI), 3) Insert-to-encrypt (I2E), and 4) Encrypt-to-insert (E2I) [START_REF] Ong | Data Insertion and Scrambling for Unified Scalable Information Hiding[END_REF].

output state and the 'natural' state is exploited to hide data [START_REF] Ong | Progressive quality degradation in JPEG compressed image using DC block orientation with rewritable data embedding functionality[END_REF][START_REF] Ong | Scrambling-embedding for JPEG compressed image[END_REF]. For the purpose of this survey, we focus on ETI, because it is the most popular and natural way in combining data hiding and encryption. Unless specified otherwise, we use the terms secret message and payload data interchangeably. We also use the term marked image to indicate that the image contains embedded data.

The rest of this paper is organized as follows. Section 2 describes the different classes and characteristics of reversible data hiding in encrypted image (RDHEI) methods. A survey of the methods, including a classification, is then presented in Section 3. Section 4 reports the experimental results and comparisons with other state-of-the-art methods. Then, Section 5 gives some perspective works for the next 12 years. Finally, this paper is concluded in Section 6.

Different classes and characteristics

In recent years, many methods of RDHEI have been developed. Due to their diversity, several classes and characteristics can be defined. In Section 2.1, we start by defining the different properties that classify several state-of-the-art methods, namely: the trade-off between the payload and the quality of the reconstructed image, as well as the approaches that can be used for the encoding and decoding phases. We then describe the classical approaches for image encryption in RDHEI methods in Section 2.2. Indeed, while stream encryption is generally performed to protect the confidentiality of the original data in RDHEI methods, some RDHEI methods use block encryption with, for example, the Advanced Encryption Standard (AES) [START_REF] Daemen | The design of Rijndael: AES -the Advanced Encryption Standard[END_REF] algorithm, or employ a public-key cryptosystem, such as that defined by Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. Finally, in Section 2.3, we detail the criteria used to evaluate their performance.

In fact, a RDHEI method can be evaluated according to the number of embedded bits in terms of payload, the bit error rate (BER) during message extraction, and the visual quality after reconstruction in comparison to the original image. In addition, we also focus on assessing the visual security level of the marked encrypted image through in-depth statistical analysis.

Properties

The properties for defining and categorizing RDHEI methods are detailed in this section. The notion of trade-off between the payload and the quality of the reconstructed image are developed in Section 2.1.1. Then, the approaches for the encoding and decoding phases are described in Section 2.1.2 and Section 2.1.3, respectively.

Quality vs capacity: a real trade-off

In RDHEI methods, there is a trade-off between the number of secret bits embedded in the encrypted image and the quality of the reconstructed image after decryption of the marked encrypted image. Thus, two types of methods can be defined based on the number of bits (i.e. length of a secret message) that can be embedded. Specifically, low-capacity RDHEI methods are those with a payload of less than 0.5 bit-per-pixel (bpp). Conversely, a method is said to have a "high-capacity" when the payload is ≥ 1 bpp. We note that, until 2018, none of the state-of-the-art RDHEI methods could embed more than 1 bpp. In addition, after decryption of the marked encrypted image, some methods allow the secret message to remain in the decrypted (i.e. plaintext) image. In this case, the reconstructed image must be similar to the original plaintext image. In addition, a method is "fully reversible" when the original image can be reconstructed without any loss after the extraction of the secret message. Finally, it should be noted that longer secret messages imply a higher risk of quality degradation for the image reconstructed during the decoding phase, and vice versa.

Two approaches for the encoder

RDHEI methods can be divided into two categories based on the encoding process, namely approaches based on freeing up space for message embedding before encryption (RRBE, Reserving Room Before Encryption) or freeing space for message embedding after encryption (VRAE, Vacating Room After Encryption), as illustrated in Fig. 3. For the former, the original image is pre-processed by its owner before encryption, in order to release some space to hide a secret message. The image is then encrypted and another person, for example, the manager of a cloud server can embed parts of the secret message at the specific positions dedicated to this purpose [START_REF] Ma | Reversible data hiding in encrypted images by reserving room before encryption[END_REF][START_REF] Cao | High capacity reversible data hiding in encrypted images by patch-level sparse representation[END_REF][START_REF] Zhang | Lossless and reversible data hiding in encrypted images with public-key cryptography[END_REF][START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF]. For the latter, the content of the original image is encrypted directly by its owner without any pre-processing.

The manager of the cloud server then modifies the encrypted data in order to hide the secret message [START_REF] Puech | A reversible data hiding method for encrypted images[END_REF][START_REF] Hong | An improved reversible data hiding in encrypted images using side match[END_REF][START_REF] Zhang | Reversible data hiding in encrypted image[END_REF][START_REF] Zhang | Separable reversible data hiding in encrypted image[END_REF][START_REF] Qian | Reversible data hiding in encrypted JPEG bitstream[END_REF] recipient of the marked encrypted image must predict the content of the original image in order to reconstruct it. Therefore, the reconstructed image is usually an estimation of the original image and perfect reconstruction cannot be achieved. In addition, in order to minimize the introduced distortion, a large number of secret bits cannot be embedded.

Two approaches for the decoder

During the decoding phase, the extraction of a message and the reconstruction of an original image can be carried out jointly or separately, as shown in Fig. 4. If the decoding is joint, this means that the plaintext image cannot be obtained without knowing the data hiding key. Indeed, by using only the encryption key, only a degraded version of the original image can be obtained [START_REF] Puech | A reversible data hiding method for encrypted images[END_REF].

Furthermore, in some methods, knowing only the data hiding key does not allow us to extract the secret message [START_REF] Zhang | Reversible data hiding in encrypted image[END_REF]. However, if the decoding is separable, the operations required for extracting the message and reconstructing the original image can be performed independently. Here are the resulting two scenarios:

• A clear image with the embedded secret message is obtained. This image is very similar to the original image, but not identical [START_REF] Zhang | Separable reversible data hiding in encrypted image[END_REF];

• The original image can be perfectly reconstructed, which does not contain the secret message [START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF].

When a user only knows the data hiding key, they can extract the secret message directly from the encrypted image. Note that the secret message can also be extracted in the clear domain, if the method is designed to allow the secret message to be kept in the clear domain.

Classical encryption approaches

The most commonly used technique, which is stream encryption, is described in Section 2.

Stream encryption

In most recent state-of-the-art methods [START_REF] Zhang | Reversible data hiding in encrypted image[END_REF], the original image

I of size m × n pixels p(i, j) (0 ≤ i < m, 0 ≤ j < n) is encrypted
by using a stream encryption algorithm. As shown in Fig. 5, an encryption key K e is used as a seed to a pseudo random number generator (PRNG). This PRNG provides a sequence of pseudo-random numbers s(i, j) in the form of bytes. Thus, the encrypted pixels p e (i, j) are computed by performing bitwise exclusive-or (XOR, denoted by the symbol ⊕) operation using the binary sequence s(i, j) and the pixel value p(i, j):

p e (i, j) = s(i, j) ⊕ p(i, j). (1)
Since the encryption operation is completely reversible and does not cause any under/overflow, it is then possible to recover the clear image I from the encrypted image I e without any alteration. We note that the pseudo-random sequence can be generated by using a cryptographically secure pseudo random number generator (CSPRNG), a chaotic generator [START_REF] Li | On the dynamical degradation of digital piecewise linear chaotic maps[END_REF], or by using the AES algorithm [START_REF] Daemen | The design of Rijndael: AES -the Advanced Encryption Standard[END_REF] in output feedback (OFB) mode for example.

Symmetric block encryption

Some other state-of-the-art methods exploit the correlation within the pixel blocks of an image in the clear domain [START_REF] Puech | A reversible data hiding method for encrypted images[END_REF]. As a result, they use symmetric block encryption algorithms to preserve the structure of pixel blocks in the encrypted image. The most commonly used symmetric block encryption algorithm is AES [START_REF] Daemen | The design of Rijndael: AES -the Advanced Encryption Standard[END_REF]. It was designed in 1999 by Joan Daemen and Vincent Rijmen, and it consists of a set of operations, which are repeated over several iterations called rounds. The number of rounds depends on the size of the encryption key, for example, 10 repetition cycles for 128-bit keys, 12 repetition cycles for 192-bit keys, and 14 repetition cycles for 256-bit keys. In order to encrypt a 128-bit sequence, the AddRoundKey operation is first applied. Each byte in the sequence is combined with an associated block in the round key using the XOR operation. Then, during each round, four different steps are performed, namely, SubBytes, ShiftRows, MixColumns and AddRoundKey. The SubBytes operation is a non-linear substitution step, where each byte is substituted by another according to a conventionally defined table. The ShiftRows operation is a transposition step where the last three rows of the block are cyclically shifted. The MixColumns is a linear mixing operation that operates on the columns of the block, combining four bytes of each column. Finally, the last round consists of the same operations, but without performing the MixColumns. Furthermore, the AES algorithm can support different encryption modes, such as Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB) or Counter (CTR).

Homomorphic encryption

Many RDHEI methods exploit the probabilistic and homomorphic properties of public key cryptosystems. A function f (•) is said to be homomorphic if the following condition is verified:

f (x 1 x 2 ) = f (x 1 ) 2 f (x 2 ), (2)
where and 2 are some arithmetic operations.

By extension, an encryption algorithm E(•) (with associated decryption algorithm D(•)

) is said to be homomorphic if the encrypted versions of two plaintext messages m 1 and m 2 are known, then it is possible to obtain the encrypted version of the output for an operation between these two messages:

D(E(m 1 m 2 )) = D(E(m 1 )) 2 D(E(m 2 )). (3)
Note that and 2 can denote addition, subtraction or multiplication. They are not necessarily the same between plaintext messages and their encrypted versions.

Asymmetric cryptosystems are often homomorphic:

• River-Shamir-Adleman (RSA) [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] and El Gamal's cryptosystem are partially homomorphic to multiplication:

D(E(m 1 ) • E(m 2 )) = m 1 • m 2 , where D(•)
is the decryption algorithm associated to E(•).

• Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] is an additive homomorphism:

D(E(m 1 ) • E(m 2 )) = m 1 + m 2 .
The main advantage of the homomorphism property is that it allows operations to be performed in the encrypted domain without revealing any information about the content in the clear domain. Most RDHEI methods adopt Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] to encrypt the image. Specifically, to generate the public and private keys, two prime numbers p and q are chosen such that:

gcd(pq, (p -1)(q -1)) = 1, (4)
where gcd refers to greatest common divisor. The values η = pq and λ = lcm((p -1), (q -1)) are then computed, where lcm refers to the least common multiple. Next, an integer g ∈ (Z/η 2 Z) * is selected such as:

∃ µ | µ = (L(g λ mod (η 2 ))) -1 mod (η), (5)
where L(•) is defined as:

L(x) = x -1 η , where x ∈ N * . (6)
The public key is (η, g) and the private key is (λ, µ). Then, we consider a to-be-encrypted message ω such that 0 ≤ ω < η. In the case of image encryption, ω usually corresponds to a pixel or a pixel block. For the message encryption, a random number r is generated, with r ∈ (Z/ηZ) * . Note that choosing such r guarantees the non-determinism property of Paillier's cryptosystem. Finally, the encrypted message c is calculated:

c = E(ω) = g ω × r η mod (η 2 ), (7)
where E(•) is the encryption function of Paillier's cryptosystem. We note that the squaring of η leads to size expansion of two in the encrypted message when compared to its original counterpart.

From the encrypted message c, the original message in clear ω can be reconstructed:

ω = D(c) = L(c λ mod (η 2 )) × µ mod (η), (8)
where D(•) is the encryption function of Paillier's cryptosystem.

Evaluation criteria

In this section, we first discuss the differences between embedding capacity and payload (Section 2.3.1). Then, we describe the notion of bit error rate (Section 2.3.2). We also present the metrics commonly adopted for visual quality evaluation (Section 2.3.3).

Finally, the metrics used for visual security level are developed in Section 2.3.4.

Amount of embedded bits

The amount of embedded bits is expressed in bits-per-pixel (bpp). For an image whose pixels are encoded using 256 grey-levels, this quantity will be between 0 bpp and 8 bpp. Furthermore, we make a distinction between embedding capacity and payload.

Specifically, the embedding capacity refers to the total number of bits that can be embedded in an image using the RDHEI method.

Payload refers to the total number of bits of the message that can be embedded into an image. Therefore, the payload can be significantly less than the embedding capacity, especially when a RDHEI method needs to sacrifice some storage to encode additional information, such as information needed to handle overflow [START_REF] Huang | New framework for reversible data hiding in encrypted domain[END_REF], or to flag pixels that cannot be predicted correctly (i.e. large prediction errors) [START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF][START_REF] Rad | A unified data embedding and scrambling method[END_REF].

Bit error rate (BER)

The BER when extracting the message from the marked encrypted image (or the marked decrypted image when it can be obtained) is calculated by dividing the number of badly reconstructed bits by the total number of bits of the secret message. So, the BER must be as small as possible to ensure proper transmission of the secret data embedded in the encrypted image. In most recent state-of-the-art methods, the BER is zero, which means that the secret message is extracted without any errors.

Visual quality

The visual quality between the reconstructed image (i.e. decrypting the marked encrypted image) and its original counterpart can be assessed by using two commonly deployed metrics in image coding and compression, namely PSNR and SSIM. Note that the quality of the reconstructed image can be evaluated before and after the secret message extraction. Indeed, if the RDHEI method allows the message to remain in the decrypted image, it is interesting to evaluate the distortion introduced by embedding the message in the original image directly. Furthermore, it should be noted that some methods are not reversible and it is impossible to recover the original image without some alteration after extracting the secret message.

Peak-Signal-to-Noise Ratio (PSNR): PSNR is commonly used to measure the quality of the reconstructed image against the original image, which is computed as:

PSNR = 10 • log 10 (2 l -1) 2 1 m×n m-1 i=0 n-1 j=0 (p(i, j) -p (i, j)) 2 , ( 9
)
where p(i, j) is a pixel from the original image and p (i, j) is the corresponding pixel in the reconstructed image, both of the same size and whose pixels are encoded by using 2 l grey-level values. PSNR is measured in the unit of decibels (dB).

In general, images are encoded by using 256 grey-level values (l = 8) and hence 2 l -1 = 255. In this case, between two very different images, PSNR is about 10 dB, and between two similar but noise-altered images, PSNR is about 15 dB. On the other hand, when two images are highly similar, PSNR is more than 30 dB. Finally, in the case of a perfect reconstruction, i.e. when the two images are exactly the same, its value tends toward +∞. Note that many RDHEI methods are described as reversible although the value of PSNR is about 50 dB. The major drawback of PSNR is that it does not take into account the quality perception of the human visual system (HVS). Thus, it cannot be considered as a totally objective measure.

Structural Similarity (SSIM) [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]: SSIM allows the assessment of structural similarity between two images, rather than relying solely on pixel-to-pixel differences as in PSNR. The underlying assumption in SSIM is that the HVS is more sensitive to changes in image structure. In particular, it is modeled to detect changes in terms of loss of correlation, luminance distortion and contrast distortion between two images. Specifically, SSIM is computed as follows:

SSIM(x, y) = (2E(x)E(y) + γ 1 ) (2Cov(x, y) + γ 2 ) E(x) 2 + E(y) 2 + γ 1 V(x) 2 + V(y) 2 + γ 2 , (10)
where x and y are the windows of the two images, E(x) is the mean of the x set, V(x) the variance of the x set, Cov(x, y) the covariance between the x and y sets, γ 1 = (0, 01 × (2 l -1)) 2 , and

γ 2 = (0, 03 × (2 l -1)) 2 .
This formula is applied to the co-located windows (i.e. a block of pixels with the same coordinates) in both images, and the average of the values obtained for these co-located windows yields the final SSIM score. This score ranges between -1 and 1. It is equal to 1 when the two images are exactly the same. The value -1 is reached when one image is the complement (i.e. y = 255x)

to the other. However, for data hiding, the common range of observation ranges between 0 and 1. Note that it is often necessary to observe at least three decimal values for a significant SSIM measurement.

Visual security level

Until now, no specific metrics have been defined to evaluate the visual security level of marked encrypted images. Therefore, based on the work of Preishuber et al. [START_REF] Preishuber | Depreciating motivation and empirical security analysis of chaos-based image and video encryption[END_REF], we describe the metrics used in many papers 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 impact the security level of the encryption method. Nevertheless, if the embedded message is itself encrypted, embedding this message into an encrypted image is similar to embedding "noise into noise". So, the encrypted message cannot a priori be detected in the encrypted domain.

Correlation coefficient: A common metric is to observe the correlation between pixels in the horizontal, vertical and diagonal directions. M pairs of neighboring pixels (x i , y i ) in all three directions, with x i ∈ x and y i ∈ y, are thus chosen for the calculation of the correlation coefficient:

corr x, y = 1 M M i=1 (x i -E(x)) × (y i -E(y)) 1 M M i=1 (x i -E(x)) 2 1 M M i=1 (y i -E(y)) 2 . ( 11
)
where E(x) is the average of the set x.

The value of this correlation coefficient ranges from -1 to 1, where -1 and 1 indicate a high correlation while 0 indicates a lack of correlation. Since the neighboring pixel values in the clear domain are highly correlated, corr x, y is generally high in the original image. However, it should be close to zero in the encrypted domain.

Shannon entropy [START_REF] Shannon | A mathematical theory of communication[END_REF]: Shannon entropy is a measure of the amount of information commonly used to evaluate the randomness of the pixel distribution of a marked encrypted image. It is computed as follows:

H(I) = - N-1 k=0 P(α k ) log 2 (P(α k )), ( 12
)
where I is an image of m × n pixels encoded by using N values α k (0 ≤ k < N) and P(α k ) is the probability associated with α k .

The entropy value is expressed in bpp and it ranges from 0 bpp to log 2 (N) bpp, where the value of log 2 (N) is achieved only when the pixel distribution is perfectly uniform. In general, images are encoded by using 256 grey-level values and hence the maximum entropy is then log 2 (256) = 8 bpp. The entropy value of a marked encrypted image should be very close to the maximum entropy value, i.e., log 2 (N).

χ 2 -test: The uniformity of the pixel distribution of a marked encrypted image can also be assessed by using the chi-square (χ 2 -)

test, which is computed as:

χ 2 = N N-1 k=0 P(α k ) - 1 N 2 , ( 13
)
where the pixels of the image are coded by using N values α k (0 ≤ k < N) and P(α k ) is the probability associated with α k .

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

Number of Changing Pixel Rate (NPCR) [START_REF] Wu | NPCR and UACI randomness tests for image encryption[END_REF]: NPCR between two images of size m × n pixels p(i, j) and p (i, j) (0

≤ i < m, 0 ≤ j < n) is given by: NPCR = m-1 i=0 n-1 j=0 d(i, j) m × n × 100, (14)
where d(i, j) is defined as:

d(i, j) = 1, if p(i, j) p (i, j), 0, otherwise. (15)
It is expressed in % and is used to indicate how much a marked encrypted (or simply marked) image differs from the original image. Therefore, the closer its value is to 100%, the more mismatches between the two images and so the higher the level of visual security.

Unified Averaged Changed Intensity (UACI) [START_REF] Wu | NPCR and UACI randomness tests for image encryption[END_REF]: UACI is also used to measure the differences between two images of m × n pixels, where the pixels p(i, j) and p (i, j) (0 ≤ i < m, 0 ≤ j < n) are encoded by using 256 grey-level values. It is computed as follows:

UACI = 100 m × n m-1 i=0 n-1 j=0 |p(i, j) -p (i, j)| 255 . ( 16
)
Similar to NPCR, UACI is expressed in %, where the higher its value, the higher the level of visual security. Note that its ideal value depends on the tonal range of the image. This metric can also be used to test the sensitivity of the key used during encryption.

Specifically, the original image is encrypted by using two keys that differ by only one bit. The corresponding encrypted images are then compared. In this case, the optimal value of UACI is 33.33% [START_REF] Preishuber | Depreciating motivation and empirical security analysis of chaos-based image and video encryption[END_REF]. However, if UACI is used to compare an original image in clear and its marked encrypted version, the value is often lower. Note that there is no statistical decision criterion for this test, and the observation of optimal values is purely experimental.

Survey of the methods

This section aims to classify the existing RDHEI techniques based on the underlying image processing mechanisms involved.

Specifically, the classes include: image partition-based (Section 3.1), histogram shifting or pixel value ordering (PVO)-based (Section 3.2), re-encoding-based (Section 3.3), prediction-based (Section 3.4) and public-key cryptography-based (Section 3.5).

Image partition-based methods

In many RDHEI methods, the pixels in an image are divided into two groups. Specifically, the pixels in the first group are reserved to embed a secret message, while those in the second group are not marked, but used to reconstruct the original image.

Consequently, this image partitioning process is performed before or after encryption, depending on the method in use. Some authors perform partitioning in a pseudo-random way by using the embedding key [START_REF] Zhang | Reversible data hiding in encrypted image[END_REF]. Instead, other techniques analyze the properties of the pixels in the clear image [START_REF] Ma | Reversible data hiding in encrypted images by reserving room before encryption[END_REF].

Exploitation of the data hiding key [32]

In one of the earliest RDHEI methods, Zhang et al. proposed to encrypt an original image by using a stream encryption algorithm [START_REF] Zhang | Reversible data hiding in encrypted image[END_REF]. The encrypted image is further divided into non-overlapping blocks of s × s pixels, where one bit of the secret message is hidden into each block. Within each block, the pixels are then partitioned into two groups, namely, S 0 and S 1 using an embedding key. If the secret message bit to be embedded is '0' (resp. '1'), the three least significant bits (LSBs) of each pixel in S 0 (resp. S 1 ) are flipped. 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 planes (MSBs) are perfectly reconstructed and only the 3 LSBs are altered. Then, a function is used to evaluate the inconsistencies in the reconstructed pixels within the S 0 and S 1 groups. In this way, the secret message can be extracted, one bit per block, and the original configuration of each pixel block can be retrieved. Increasing the size of the blocks increases the chances of perfectly reconstructing the original image. However, Zhang's method is not reversible because it does not guarantee a perfect reconstruction of the original image. Furthermore, the payload is low (less than 0.1 bpp) since only one bit is embedded for each s × s block. Improvements to this method have then been made in the following literature [START_REF] Hong | An improved reversible data hiding in encrypted images using side match[END_REF][START_REF] Zhang | Separable reversible data hiding in encrypted image[END_REF].

Exploitation of a fluctuation function [27]

Ma et al. are the first to propose an RRBE method, taking the opposite line to all of the other state-of-the-art methods developed, up to this point in time [START_REF] Ma | Reversible data hiding in encrypted images by reserving room before encryption[END_REF]. The authors start by splitting the original image into blocks. Within each block, the correlation between the pixels is evaluated by using a fluctuation function. The blocks are further partitioned into two groups, namely, A and B.

Specifically, group A is composed of textured blocks while group B is composed of relatively homogeneous blocks. The blocks in group A are placed at the beginning of the image and those in B are placed afterwards. In order to release space for the secret message embedding, the LSB plane of A is embedded into pixels in group B in the clear by using histogram shifting. The resulting image is then encrypted by using a stream encryption algorithm and the number of pixels that can be marked is stored in the LSBs of the first A pixels. With this information, the secret message can be embedded simply by substituting the LSBs of the remaining pixels in A. We note that the first three LSBs of each pixel can be used. The total payload of the marked encrypted image can reach 0.5 bpp.

Therefore, in comparison to previous state-of-the-art methods, the payload is ten times greater. Finally, during the reconstruction phase, the secret message extraction and the original image reconstruction operations can be performed separately. Based on this idea, another method has been proposed by Zhang et al. [START_REF] Zhang | Reversibility improved data hiding in encrypted images[END_REF].

Histogram / PVO-based methods

Many RDHEI methods based on histogram shifting have been developed due to their simplicity in implementation and their ability to produce very high quality images after decrypting the marked encrypted image. In natural images in the clear domain, neighboring pixels are highly correlated. As a result, the distribution of differences between neighboring pixels is modelled by a zero-centered Laplacian distribution. In fact, most histogram-based methods [START_REF] Ong | Beyond format-compliant encryption for JPEG image[END_REF][START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF][START_REF] Xu | Separable and error-free reversible data hiding in encrypted images[END_REF] rely on this particular property.

Consequently, these statistical characteristics can be exploited during the secret message embedding phase in histogram shifting-based RDHEI methods [START_REF] Huang | New framework for reversible data hiding in encrypted domain[END_REF][START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF][START_REF] Ge | A high capacity multi-level approach for reversible data hiding in encrypted images[END_REF].

Pixel difference or prediction error histogram [37]

In 2016, Huang et al. discovered that the previously proposed algorithms for embedding secret data in the clear domain cannot be applied in the encrypted domain [START_REF] Huang | New framework for reversible data hiding in encrypted domain[END_REF]. Indeed, classical encryption methods do not allow the correlation between neighboring pixels to be maintained without introducing security flaws. In their work, the authors introduce a new strategy to encrypt an image with the objective being that the conventional data hiding algorithms designed in the clear domain can be deployed directly to embed data in the encrypted image. Specifically, the original image is split into non-overlapping blocks. Within each block, all pixels are encrypted by applying the XOR operation using the same pseudo-randomly generated byte. The encrypted blocks are then pseudo-randomly permuted. Note that pixels within the same block are not scrambled, but only the order of the blocks are changed.

With this encryption method, the statistical properties of the clear image, especially the histogram of pixel differences or prediction errors, are preserved. Therefore, the conventional data hiding algorithms in the clear domain can be applied in the encrypted domain, but the embedding capacity is limited by the handling of under/overflow problems.

Homomorphism and PVO [45]

Xiao et al. proposed to adapt the concept of PVO, defined in the clear domain by Li et al. [START_REF] Li | High-fidelity reversible data hiding scheme based on pixel-value-ordering and prediction-error expansion[END_REF], to embed data in the homomorphic encrypted domain [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF]. The authors start by arguing that by adapting the homomorphic encryption method, it is possible to obtain a histogram of the differences between pixels. The histogram follows a zero-centered Laplacian model in the encrypted domain, which is identical to the histogram obtained in the clear domain. Specifically, the encrypted image is split into 2 × 2 non-overlapping blocks.

The pixels in each block (4 in total) are collected and re-arranged in ascending order, which are denoted as c 1 , c 2 , c 3 , c 4 . Then, the pixel with the lowest (c 1 ) and highest (c 4 ) value are selected to embed data. Specifically, the difference ∆ = c 4c 3 is calculated, and data hiding is performed depending on d:

c z =                c z + w if ∆ = 1 c z + 1 if ∆ > 1 c z + w if ∆ = 0 c z + 1 if ∆ < 0, ( 17
)
where z is the sorted pixel index, c z is the embedded-encrypted pixel, and w ∈ {0, 1} is the secret message. Similar operations are applied for the lowest value, namely c 1 .

In this method, the pixel order remains unchanged after embedding data. Looking from the perspective of histogram, the difference bins of value '0' and '1' are expanded for data hiding while other bins are shifted. This method solves the inseparable and data expansion problems of other similar methods in the encrypted domain. Nevertheless, as reported in [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF], this method can only hide up to 0.2 bpp. In fact, one of the biggest drawbacks of histogram-based methods is the over/underflow problem after histogram modification. To mitigate this problem, the authors in [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF] employed a location map to record unusable blocks, which are skipped during data embedding. Hence, the introduction of a location map significantly impacts the effective payload of the proposed method.

Pixel value histogram [47]

In 2019, Ge et al. proposed a block-based histogram shifting method in encrypted domain [START_REF] Ge | A high capacity multi-level approach for reversible data hiding in encrypted images[END_REF] to enhance the embedding capacity of Xiao et al.'s method [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF]. Instead of using the histogram of pixel differences, they directly modify the pixel value by using two reference pixels within the block. Unlike Xiao et al.'s method [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF], their approach does not restrict the assignment of the reference pixels to be the lowest and highest values. Instead, the reference pixels are pseudo-randomly chosen based on the user's key.

Let c l and c h denote the two selected reference pixels in an encrypted block such that c l < c h . Then, for each of the non-reference pixels in the same block (denoted by ĉy ), data hiding is performed by using the following equation:

ĉ y =                    ĉy -1 if ĉy < c l ĉy -w if ĉy = c l ĉy if c l < ĉy < c h ĉy + w if ĉy = c h ĉy + 1 if ĉy < c h , ( 18
)
where ĉ y is the embedded-encrypted pixel with index y.

The same data hiding operation is performed on all the blocks in the entire image. In addition, multiple rounds of embedding can be performed on an encrypted image to further increase the embedding capacity.

For the comparison of single-level embedding, Ge et al. can only embed half the payload achieved by Xiao et al.'s method [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF], despite the implementation of a pixel-shifting strategy. Indeed, the size of the location map is more complex than that used in [START_REF] Xiao | Separable reversible data hiding in encrypted image based on pixel value ordering and additive homomorphism[END_REF],

because each pixel which causes overflow/underflow needs to be recorded. Nevertheless, in the multi-level embedding mode, it is possible to embed up to 0.8 bpp while sacrificing some image quality in the reconstructed image in the clear domain. Note that Long et al. further improved these results in [START_REF] Long | A separable reversible data hiding scheme for encrypted images based on Tromino scrambling and adaptive pixel value ordering[END_REF].

Re-encoding-based methods

As explained, in some state-of-the-art methods, re-encoding can be applied to the image data, before or after encryption, in order to optimize the number of bits needed for its representation. Thanks to this re-encoding phase, some gain in memory space is achieved. Thus, the released space is used to embed the secret message. A few algorithms implement re-encoding. In particular, Mustafa et al.'s method which is based on Golumb-Rice codewords [START_REF] Karim | Data embedding in random domain[END_REF], Qian et al. et al.'s method which is based on distributed source coding [START_REF] Qian | Reversible data hiding in encrypted images with distributed source encoding[END_REF], and Cao et al.'s method which is based on sparse coding [START_REF] Cao | High capacity reversible data hiding in encrypted images by patch-level sparse representation[END_REF], have shown interesting performances.

Golomb-Rice codewords [50]

Mustafa et al. proposed a novel data hiding method in which any encrypted (in fact, any) signal encoded in binary representation can be further processed to embed data [START_REF] Karim | Data embedding in random domain[END_REF]. This is an example of VRAE method. Specifically, given the bitstream of any content regardless if it is in plaintext and encrypted form, the bitstream is uniformly divided into segments of equal length len, and each segment (i.e. imaginary codeword) is mapped to a unique Golomb-Rice codeword (grc). Each grc consists of two parts, namely, the quotient part quo and the remainder part rem, which are separated by a delimiter δ. Each grc takes the general form of:

grc = quo | δ | rem, (19)
where '|' is the concatenation operator, quo is in unary representation, δ is a fixed character (e.g. '1'), and rem is coded raw in binary representation.

The first 6 grc's for a divisor rem = 2 2 = 4 are: 100, 101, 110, 111, 0100, and 0101, where the remainder is underlined.

The regular-pattern of grc (i.e. the quotient and delimiter parts) is exploited to embed data. Specifically, the quotient part of each codeword, which is the only part that has variable length, causes bit stream size increment. To maintain the original bit stream size, the quotient part of each codeword is extracted and treated as part of the secret message. The augmented secret data is then embedded by forming new codewords of constant length len. For each original codeword, each segment of the augmented data (with length len-length(rem)) becomes the new quotient quo and delimiter δ parts of the codeword, while the remainder part remains unchanged, essentially grc = quo | δ | rem. While Mustafa et al.'s method is applicable to any signal and completely reversible, it is neither separable nor commutative.

Distributed coding source [51]

In 2016, Qian et al. proposed to use distributed source coding in a RDHEI method [START_REF] Qian | Reversible data hiding in encrypted images with distributed source encoding[END_REF]. During the encoding phase, the original image is first encrypted by using a stream encryption algorithm. The encrypted image I e of pixels p e (i, j), with 0 ≤ i < m and 0 ≤ j < n, is then divided into four sub-images

I (k) e (1 ≤ k ≤ 4), whose pixels p (k) e (i, j), with 0 ≤ i < m 2 et 0 ≤ j < n 2 , are such that:                p (1)
e (i, j) = p e (2i -1, 2 j -1), p (2) e (i, j) = p e (2i -1, 2 j), p

e (i, j) = p e (2i, 2 j -1), p

e (i, j) = p e (2i, 2 j).

Note that the decryption of each of the I (k) e sub-images results in a thumbnail of the original image. After obtaining the sub-images

I (k)
e , three MSB planes of

I (2) e , I (3) e , and I (4)
e are first scrambled and then compressed with low-density parity-check codes (LDPC) [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]. This compression has the effect of generating some space for data hiding. Here, the decoding phase is completely separable. The sub-image I (1) e , which has not been modified, is decoded and up-sampled by using bilinear interpolation in order to obtain a reference image to reconstruct the marked image in the clear domain. Furthermore, to reconstruct the original image, the LDPC codes are decoded by a sum-product algorithm [START_REF] Liu | Efficient compression of encrypted grayscale images[END_REF].

Sparse coding [28]

In order to accommodate a large payload, Cao et al. suggest utilizing sparse coding in their RDHEI method [START_REF] Cao | High capacity reversible data hiding in encrypted images by patch-level sparse representation[END_REF]. The RRBE encoding phase consists of three stages. First, the original image is divided into patches, which are then represented by using a redundant dictionary, i.e. using sparse encoding. Next, the patches with the smallest residual errors (the homogeneous ones) are selected for data hiding, where they are represented by the sparse coefficients. At the same time, residual errors are encoded and concealed in the patches which are not selected for embedding by using a classical data hiding algorithm for images in clear. Finally, stream encryption is performed to protect the data in the clear domain. Once the image is encrypted, the secret message is divided into segments and embedded into the previously released space. Ultimately, the decoding phase is separable and reversible. The original image can also be reconstructed without any loss by using the residual errors extracted from the unmarked patches, and the secret message can be retrieved.

Prediction-based methods

In some state-of-the-art methods, during the encoding phase, selected bits of certain pixels of the encrypted image are substituted by segments of the secret message. Consequently, their original value is lost and has to be predicted during the decoding phase in order to achieve high quality reconstruction of the original image in the clear domain. This prediction can be achieved by exploiting the differences between a block of pixels in the clear domain and its encrypted version [START_REF] Puech | A reversible data hiding method for encrypted images[END_REF], or the strong correlation between a pixel and its neighborhood in the clear domain [START_REF] Wu | High-capacity reversible data hiding in encrypted images by prediction error[END_REF][START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF].

Prediction based on statistical analysis [15]

In 2008, Puech et al. proposed one of the first RDHEI methods [START_REF] Puech | A reversible data hiding method for encrypted images[END_REF]. During the encoding phase, the method opts for a VRAE approach. The original image is encrypted in blocks of 16 grey-level pixels (128 bits) using the AES algorithm in ECB mode. One bit of the secret message is then embedded into each block of the encrypted image, which translates to an embedding capacity of 0.0625 bpp. Note that a data hiding key is used as the seed for a PRNG to determine the to-be-marked pixels and the location of the bit which is substituted by a bit of the message. Accordingly, the marked encrypted image is obtained when all the blocks have been processed. During the decoding phase, the extraction of the message is carried out by reading, using the data hiding key, the bits of the pixels that have been marked. However, after extraction, the pixels are still marked with the bits of the message, making it difficult to decrypt the image. To overcome this problem, a local analysis of the standard deviation in each block is performed. For each block of the marked encrypted image, by using the data hiding key to seed the PRNG, the marked bit is located and substituted by the two possible values of the original bit (viz. 0 and 1). Two configurations are then obtained and decrypted, namely, one corresponds to the associated block in the original plaintext image, while the other is erroneous and has the appearance of a fully encrypted block.

The following hypothesis is then formulated: the standard deviation in an encrypted (incorrectly decrypted) block is greater than that of a clear (correctly decrypted) block. Consequently, the standard deviation associated with the two decrypted configurations is calculated. The configuration with the lower standard deviation value is considered to be the expected block in clear. Note that since the reconstruction of the original image requires the knowledge of the data hiding key, the decoding step is joint.

Prediction using interpolation [54]

Wu and Sun have developed a RDHEI method that can operate in two different ways, namely, joint approach, and separative approach [START_REF] Wu | High-capacity reversible data hiding in encrypted images by prediction error[END_REF]. In both approaches, the original image is first encrypted by using a stream encryption algorithm. Depending on the data hiding key, a subset of pixels is selected to perform data hiding. We note that the neighboring pixels of the selected pixels are used for prediction during the decoding phase. In the case of the joint approach, to embed one bit of the secret message, the LSBs of the selected pixels are flipped if the message bit is '1'. Otherwise they are kept unchanged if the message bit is '0'. During the decoding phase, the unmarked neighboring pixels are used to predict the original value of each marked pixel, as well as the value of the embedded bit. On the other hand, in the case of the separative approach, the LSBs of the selected pixels are substituted by one secret message bit. To reconstruct an approximation of the original image during the decoding phase, a median filter is then deployed. Subsequently, improvements have been made to both of these approaches [START_REF] Dragoi | Improved reversible data hiding in encrypted images based on reserving room after encryption and pixel prediction[END_REF][START_REF] Dragoi | Reversible data hiding in encrypted images based on reserving room after encryption and multiple predictors[END_REF]. [START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF] In 2018, Puteaux and Puech proposed to use the MSB values instead of the LSB values to embed a secret message [START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF]. In fact, they stated that MSB substitution does not introduce artifacts in the encrypted domain and MSB prediction is easier than LSB prediction. Based on these two assumptions, they proposed two different high capacity reversible data hiding (HCRDH) approaches, namely, "corrected prediction errors" (CPE) and "embedded prediction errors" (EPE). In both approaches, all pixels in the clear image which cannot be correctly predicted by using their neighbors are first identified. Specifically, in the case of the CPE-HCRDH approach, the original image is pre-processed to avoid all prediction errors (PE). The pre-processed image is then encrypted and the data hider can blindly substitute all MSB values of the encrypted image by the secret message, i.e. 1 secret message bit per encrypted pixel. In this case, payload is 1 bpp and the reconstructed image corresponds to the pre-processed image, which is very close to the original one (PSNR > 50 dB). However, in the case of the EPE-HCRDH approach, the original image is encrypted without any modification. After encryption, information about the location of all pixels which cannot be correctly predicted is embedded by MSB substitution by the content owner. Then, the data hider can detect all bits which can be marked and replaces them by bits of the secret message. In this case, the payload is slightly lower than 1 bpp but perfect reversibility is achieved.

Prediction using MSB values

Public-key encryption-based methods

RDHEI methods exploiting the homomorphic properties of public-key cryptosystems can be classified into two categories depending on the encryption approach in use. Consequently, a distinction can be made between methods whose encryption is based on the Paillier cryptosystem [START_REF] Chen | Encrypted signal-based reversible data hiding with public key cryptosystem[END_REF], and those based on post-quantic encryption and exploiting the Learning With Errors (LWE) problem [START_REF] Ke | Separable multiple bits reversible data hiding in encrypted domain[END_REF].

Paillier cryptosystem-based methods

In 2014, Chen et al. proposed the first RDHEI method based on the use of Paillier's cryptosystem [START_REF] Chen | Encrypted signal-based reversible data hiding with public key cryptosystem[END_REF]. Each pixel of the original image is divided into two distinct parts: the seven MSBs (hence, forming an integer value), and its LSB. Each part is then encrypted independently and one bit of the message is embedded into each pair of neighboring pixels. During the decoding phase, the receiver can reconstruct the entire secret message and the original image in clear by comparing all the decrypted pixel pairs. The main drawback of this method is that it does not handle the under/overflow problems. Shiu et al. then proposed a solution to this drawback [START_REF] Shiu | Encrypted image-based reversible data hiding with public key cryptography from difference expansion[END_REF], where they apply the concept of difference expansion to the homomorphic encrypted domain. We note that both methods are based on an RRBE approach.

VRAE methods relying on the use of the Paillier cryptosystem have been proposed by Wu et al. [START_REF] Wu | Reversible data hiding in Paillier cryptosystem[END_REF] and Zhang et al. [START_REF] Zhang | Lossless and reversible data hiding in encrypted images with public-key cryptography[END_REF].

The authors used the self-blinding property of the Paillier cryptosystem and value expansion in two algorithms. The first one allows data extraction in the encrypted domain. Conversely, in the other one, data extraction is achieved in the clear domain (after decryption). Furthermore, with the same objectives as Wu et al. [START_REF] Zhang | Lossless and reversible data hiding in encrypted images with public-key cryptography[END_REF], Zhang et al. also developed two different approaches: a lossless approach, where an embedded secret message can be extracted directly in the encrypted domain, and a separable approach, where it can be extracted from the clear reconstructed image. Moreover, Li and Li [START_REF] Li | Histogram shifting in encrypted images with public key cryptosystem for reversible data hiding[END_REF] suggested exploiting the homomorphic addition property of the Paillier cryptosystem and to resort to histogram shifting to perform data hiding steps. Xiang and Luo also proposed a separable homomorphic encryption-based method for RDHEI, involving the mirroring ciphertext group strategy [START_REF] Xiang | Reversible data hiding in homomorphic encrypted domain by mirroring ciphertext group[END_REF]. By using such an approach, there is no pixel over-saturation in the clear domain after decryption, but the computational cost is high. In 2019, Zheng et al. proposed a lossless data hiding method based on homomorphic cryptosystem which achieves a high embedding rate through efficient mapping and skillful utilization of the expanded pixel values [START_REF] Zheng | Lossless data hiding based on homomorphic cryptosystem[END_REF]. This method can realize a high embedding rate and low computational complexity, but it needs auxiliary data for the decoding step. Recently, Jiang and Pang presented an improved implementation of the Paillier cryptosystem based on the use of the Chinese Remainder Theorem [START_REF] Jiang | Encrypted images-based reversible data hiding in Paillier cryptosystem[END_REF]. This new implementation significantly improves the rapidity of encryption and decryption operations. After encryption, the authors observe the parity of the encrypted pixel pair to embed the secret message.

Post-quantic encryption-based methods

The first RDHEI method based on post-quantic encryption was proposed in 2016 by Ke et al. [START_REF] Ke | Separable multiple bits reversible data hiding in encrypted domain[END_REF]. The authors argued that using post-quantic encryption and exploiting the LWE problem allows one to achieve the following: high security level, simple and fast implementation, as well as controllable redundancy for data hiding. Then, they set the encryption parameters and described their approach to achieve multi-level RDHEI. The latter is based on recoding the redundancy in the encrypted domain by using homomorphic operations. The main disadvantage of this approach is that it is not completely separable. In [START_REF] Xiong | High-capacity reversible data hiding for encrypted multimedia data with somewhat homomorphic encryption[END_REF], Xiong et al. dealt

The next 12 years and beyond

High capacity RDHEI methods

In the last few years, several high capacity RDHEI methods have emerged. Indeed, in 2018, the method of Puteaux and Puech has taken the opposite line of all other modern state-of-the-art methods and achieves very good results, with a payload value equal (or very close) to 1 bpp and a perfect reversibility. As a result, many new methods have subsequently been inspired by this approach and have further increased payload. Puyang et al. proposed the first extension of the EPE-HCRDH approach [START_REF] Puyang | Reversible data hiding in encrypted images with two-MSB prediction[END_REF]. They suggested using a more efficient predictor, in order to limit the number of prediction errors. Moreover, they explain that the first and second MSB can be used for data hiding. By using the MSB, an average payload of 1.35 bpp is obtained. Yi et al. designed a method based on the labeling of a parametric binary tree, where the spatial correlation between pixels in the clear domain is maintained in the encrypted domain within small blocks [START_REF] Yi | Separable and reversible data hiding in encrypted images using parametric binary tree labeling[END_REF]. Selected pixels are used as reference values to compute the prediction errors which are then highlighted through the labeling of a parametric binary tree. To realize message embedding, the bits of a secret message are inserted by substitution while exploiting the spatial correlation between pixels. Using this process, the authors can reach a payload value in the order of 2 bpp. Wu et al. also improved work of Yi et al. by reserving room before encryption [START_REF] Wu | An improved reversible data hiding in encrypted images using parametric binary tree labeling[END_REF]. In their method [START_REF] Chen | High-capacity reversible data hiding in encrypted images based on extended run-length coding and block-based MSB plane rearrangement[END_REF], Chen and Chang perform a block rearrangement of the MSB planes. This allows them to transform the MSB planes of the original image into a binary sequence that can be compressed by using extended run-length encoding. With this rearrangement and compression, they can free up a large amount of space for data hiding. During the decoding phase, the embedded secret message can be extracted directly from the encrypted image with the help of the data hiding key and the clear marked image can be obtained with the encryption key. Some recent methods have proposed to recursively process all the bitplanes of an image, starting from the MSB plane [START_REF] Puteaux | EPE-based huge-capacity reversible data hiding in encrypted images[END_REF][START_REF] Puteaux | A recursive reversible data hiding in encrypted images method with a very high capacity[END_REF]. In this way, the high correlation between pixels in the clear domain is fully exploited and a payload of the order of 2.4 bpp can be achieved. Recently, there have been methods that focused on lossless compression of all the bitplanes of an image and they obtained a payload of more than 3 bpp [START_REF] Yin | Reversible data hiding in encrypted images based on multi-MSB prediction and Huffman coding[END_REF][START_REF] Yin | Reversible data hiding in encrypted images based on pixel prediction and bit-plane compression[END_REF]. In addition, current research is aimed at developing a high capacity RDHEI method based on exploiting the homomorphic properties of public key encryption approaches.

Extensions for other media

In this survey, we have focused exclusively on RDHEI methods applied to uncompressed digital images. Accordingly, it is important to note that some extensions are emerging for 2D vector graphics [START_REF] Peng | Separable robust reversible watermarking in encrypted 2D vector graphics[END_REF], compressed images [START_REF] Qian | Reversible data hiding in encrypted JPEG bitstream[END_REF], video [START_REF] Xu | Reversible data hiding in encrypted H. 264/AVC video streams[END_REF] and 3D objects [START_REF] Jiang | Reversible data hiding in encrypted three-dimensional mesh models[END_REF]. These formats make encryption and data hiding more challenging due to format compliance and size preservation necessities.

In fact, some RDHEI methods are proposed uniquely for JPEG. In 2014, Qian et al. proposed to encode a secret message using Error Correction Codes (ECC) [START_REF] Qian | Reversible data hiding in encrypted JPEG bitstream[END_REF]. Then, the same authors suggested to form a new JPEG bitstream with some blocks from the original image [START_REF] Qian | Separable reversible data hiding in encrypted JPEG bitstreams[END_REF], where the unused blocks are hidden in the JPEG header by using the same method as in JPEG XT [START_REF] Richter | JPEG XT: A new family of JPEG backward-compatible standards[END_REF]. Chang et al. proposed to reserve space for secret message embedding before bitstream encryption [START_REF] Chang | A separable reversible data hiding scheme for encrypted JPEG bitstreams[END_REF]. Recently, Qian et al. improved their previous scheme [START_REF] Qian | Separable reversible data hiding in encrypted JPEG bitstreams[END_REF] using a combination of code mapping and ordered embedding [START_REF] Qian | New framework of reversible data hiding in encrypted JPEG bitstreams[END_REF]. However, none of these methods allow us to achieve a large payload, even when using a high quality factor. Another issue lies in the fact that most of them are not fully JPEG format compliant. These drawbacks are important problems to be addressed in the future.

In addition, for video, Xu et al. designed a RDH method in encrypted H.264/AVC video streams [START_REF] Xu | Reversible data hiding in encrypted H. 264/AVC video streams[END_REF]. During H.264/AVC encoding, they proposed to encrypt intra-prediction mode (IPM), motion vector difference (MVD), and signs of residue coefficients.

Then, a secret message is embedded into the encrypted H.264/AVC video using histogram shifting. During the decoding phase, data extraction can be carried out either in the encrypted domain or in the clear domain (i.e from the marked reconstructed bitstream) and without any errors. In another method for H.264/AVC, Yao et al. used a similar encoding scheme, but also analyzed the inter-frame distortion drift introduced by data hiding [START_REF] Yao | Inter-frame distortion drift analysis for reversible data hiding in encrypted H. 264/AVC video bitstreams[END_REF]. Furthermore, Long et al. proposed an approach for RDH in encrypted HEVC video streams [START_REF] Long | Separable reversible data hiding and encryption for HEVC video[END_REF]. During the encoding phase, the signs and amplitudes of motion vector differences as well as the signs of residual coefficients are encrypted using RC4. The secret message is then embedded into non-zero AC residual coefficients. Moreover, Tew et al. [START_REF] Tew | Separable authentication in encrypted HEVC video[END_REF] proposed a separable authentication scheme for encrypted HEVC video. Syntax elements in HEVC are divided into two groups, where the first group is manipulated to embed authentication data, while the second group is encrypted to mask the video. In their work, authentication can take place in both the encrypted or clear domain, hence separately.

Only a few RDH methods are developed for encrypted 3D objects, despite their wide range of applications [START_REF] Jiang | Reversible data hiding in encrypted three-dimensional mesh models[END_REF][START_REF] Shah | Homomorphic encryption-based reversible data hiding for 3D mesh models[END_REF][START_REF] Yin | Separable reversible data hiding based on integer mapping and multi-MSB prediction for encrypted 3D mesh models[END_REF]. Among them, Jiang et al. map vertex coordinates of 3D meshes to integers using scaling and quantization [START_REF] Jiang | Reversible data hiding in encrypted three-dimensional mesh models[END_REF]. After this pre-processing stage, additional data is embedded by flipping several LSBs of encrypted coordinates. During the decoding phase, data extraction and original mesh reconstruction are jointly performed by using a smoothing measure function. Although data can be hidden into 3D encrypted objects, the performances of this method are quite poor, including small payload, bad quality of the reconstructed mesh and errors during secret message extraction. Also of interest, Shah et al. designed a method based on the use of the Paillier cryptosystem [START_REF] Shah | Homomorphic encryption-based reversible data hiding for 3D mesh models[END_REF][START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. Even if it is suitable for cloud data management, it is not practical due to a large size expansion after mesh encryption. Contrastingly, Yin et al. proposed to embed a secret message by slightly modifying the mesh vertices without changing the mesh topology [START_REF] Yin | Separable reversible data hiding based on integer mapping and multi-MSB prediction for encrypted 3D mesh models[END_REF]. However, the main drawback of this method is that the secret message cannot be preserved in the mesh after decryption. All in all, even if some recent papers proposed to embed a secret message into 3D encrypted objects, there is room for further improvement.

Finally, we anticipate future proposals for RDHEI/V where the image/video is encoded in new formats, such as JPEG XL and VVC that support high dynamic range and many other features.

Security evaluation

Even if some metrics can be used to evaluate the visual security level of encrypted images, there are still a lack of tools to perform the security evaluation of RDHEI methods. In addition to the metrics presented in Section 2.3, some perceptual metrics can be used to assess image confidentiality after encryption [START_REF] Le Philippe | Visual saliency-based confidentiality metric for selective crypto-compressed JPEG images[END_REF][START_REF] Guo | PEID: A perceptually encrypted image database for visual security evaluation[END_REF]. Furthermore, Preishuber et al. stated that passing classical statistical tests and those of the NIST test suite [START_REF] Rukhin | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF] are a necessary condition, but not sufficient enough to prove that an encryption scheme used in a RDHEI method is secure [START_REF] Preishuber | Depreciating motivation and empirical security analysis of chaos-based image and video encryption[END_REF]. Indeed, they do not reflect attackers that use knowledge of the encryption algorithm during their attack. Attack scenarios such as those employed in cryptanalysis have then to be considered. Note that some non-traditional forms of cryptanalysis of the marked encrypted content which is generated by RDHEI, such as obtaining a sketch [START_REF] Minemura | A novel sketch attack for H.264/AVC format-compliant encrypted video[END_REF] of the plain image instead of getting the encryption/decryption key, should also be taken into account for security evaluation. Finally, to the best of our knowledge, there are no methods designed to observe whether the secret message embedded in the encrypted domain is truly undetectable from a steganalysis point of view.

Conclusion

In this survey, we present the birth and evolution of RDHEI methods over the last 12 years. First, we detailed the motivations and applications of RDHEI methods. Then, the classes and characteristics of these approaches are presented. The state-of-the-art methods are then explained. With the aid of a comparison table of the representative methods, we are able to see that there is a clear trade-off between payload and reconstructed image quality. Indeed, only a few methods are able to obtain both a large payload and a perfect reconstruction of an original image. After that, we have discussed emerging applications and open research topics relevant to RDHEI for the next 12 years and beyond.

Over time, RDHEI has become a hot topic whilst still being an emerging technology. The research focusing on theory, framework, methodology and applications needs to be further investigated and developed thoroughly. Indeed, there is a real challenge to obtain the best possible trade-off between payload, reconstructed image quality and security level. Furthermore, specific methods have to be designed for new formats / containers, in particular extensions for images of the JPEG family.

The digital image is certainly worth more than a thousand words. However, recent advancement in Generative Adversarial Network (GAN) further complicates the situation [START_REF] Korshunova | Fast face-swap using convolutional neural networks[END_REF][START_REF] Nirkin | On face segmentation, face swapping, and face perception[END_REF]. In addition, privacy and piracy issues will persist for the foreseeable future. These problems will continue to drive research, development and innovation of RDHEI, or more generally the unification of data hiding and encryption, to protect images. How much data can be hidden by trading off the quality of the reconstructed image, robustness of the hidden data, and properties such as separable and commutative is the question that needs to be explored.

Fig. 1 :

 1 Fig. 1: History of the publications in RDHEI in the last 12 years.

Fig. 3 :

 3 Fig. 3: Two possible encoding schemes: a) Reserving room before encryption (RRBE), b) Vacating room after encryption (VRAE).

Fig. 4 :

 4 Fig. 4: Two possible decoding schemes for the extraction of the secret message and the reconstruction of the original image: a) Joint or b) Separable.

Fig. 5 :

 5 Fig. 5: Stream encryption.

  . Both approaches are effective, but each has certain limitations. Specifically, RRBE-based methods are able to embed longer secret messages in general, but a pre-processing phase is required prior to encryption. This can be a problem and is impractical if the image owner does not foresee that the encrypted image needs to be analyzed or processed later. Instead, for VRAE-based methods, the

		Secret keys
		K e and K dh
			Extracted
	Marked	Data extraction	message
	encrypted	and
	image I e-dh	image recovery	Reconstructed image Ĩ
		(a) Joint scheme.
		Data extraction	Extracted message
	Marked	Secret key K dh
	encrypted
	image I e-dh	Secret key K e
		Image recovery	Reconstructed image Ĩ
		(b) Separable scheme.

Table 1: Comparison of representative state-of-the-art methods according to the approach used for the encoding phase RRBE or VRAE, the type of decoding (joint or separable), reversibility (in the strict sense of the term, i.e. PSNR→ +∞), and of the payload (in bpp or in bpb for methods indicated by a * ). It is important to note that the use of Paillier or post-quantic cryptosystems implies an increase in the size of the image after encryption. Depending on the method used, if the pixels of the original image are encoded by using 8 bits, they can correspond to nearly 2048 bits in the encrypted domain, as highlighted by Ke et al. [START_REF] Ke | A multilevel reversible data hiding scheme in encrypted domain based on LWE[END_REF].

Comparisons and discussion

Table 1 compares state-of-the-art methods described in Section 3. More specifically, the methods are classified based on the following: year (from 2008 to 2019), the approach used during encoding (RRBE or VRAE), the type of decoding (joint or separable), reversibility, as well the achieved payload. First, we note that the pioneering methods all have the same characteristics, i.e. using a VRAE approach during the encoding phase, joint decoding, impossible to reconstruct the original image without error, and a very low payload (< 0.1 bpp). The first separable method was proposed by Zhang in 2012 [START_REF] Zhang | Separable reversible data hiding in encrypted image[END_REF]. We note that this property gives a more concrete application to RDHEI methods. Since 2013 and the method of Ma et al. [START_REF] Ma | Reversible data hiding in encrypted images by reserving room before encryption[END_REF], more and more methods opt for a VRAE approach for the encoding phase. This has resulted in a higher payload value (> 0.1 bpp), but still relatively low (< 0.5 bpp). Over the years, although many methods are proposed to achieve full reversibility in the reconstruction phase of the original image, only a few methods can achieve a higher capacity, i.e. a payload close to or greater than 0.1 bpp, such as [START_REF] Puteaux | An efficient MSB prediction-based method for high-capacity reversible data hiding in encrypted images[END_REF]. Furthermore, in Table 1, we indicate the methods which are based on public-key encryption by using a star ( * ). For these methods, their payload is expressed in bits-per-bit of the encrypted image (bpb) instead of bits-per-pixel (bpp). This unit is adopted because, due to the size expansion (Section 3.5), a direct comparison of the payload expressed in bpp is unsuitable and would lead to misinterpretation of the results.