# Reversible Data Hiding Scheme in Homomorphic Encrypted Image Based on EC-EG
## 1 Introduction
The above RDH-EI algorithms need to vacate room after encryption (VRAE) for data hiding, resulting in lower embedding capacity of the algorithm and higher error rate in the data extraction process. [PERSON] et al. [16] proposed a RDH-EI algorithm by vacating room before encryption (VRBE). [PERSON] et al. [17] improved reversibility, embedding capacity, and image quality by exploiting prediction errors in data embedding. The RDH-EI algorithms mentioned above are to encrypt images with symmetric cryptography because symmetric cryptography has lower computational complexity and faster encryption and decryption speed. However, because of using symmetric cryptography, each pair of senders and receivers must have different keys, which are required in the context of current multi-party cloud computing services. The amount of keys is huge, which makes it difficult to manage keys. For example, in a communication network with \(n\) users, each user must use \(n-1\) keys to communicate with the remaining \(n-1\) users, and the total number of keys in the system will be up to \(C^{2}n=n(n-1)/2\). Such a large amount of keys will have insecurities in the various aspects of saving, transferring, using and destroying. In addition, both parties using symmetric cryptography must use the same key for encryption and decryption, thus the key must be transmitted over the secure channel before communication. If the key is stolen during the delivery process, or either party leaks the key, the encrypted data will be insecure. Because symmetric cryptography has the above shortcomings of designing the RDH-EI algorithms, we naturally use public key cryptography into the RDH-EI algorithms. The key amount of the public key cryptography is greatly reduced, and the key does not need to be transferred in advance. More importantly, with public key cryptography, we can perform homomorphic addition and homomorphic multiplication in the encrypted domain, which makes the embedding process of additional data more secure. Differing from RDH-EI, [PERSON] et al. [18] firstly proposed encrypted image-based reversible data hiding with public key cryptography (EIRDH-P). In EIRDH-P, the characteristics of public key cryptography overcome the shortcoming that symmetric encryption requires the safe channel to pass the key in advance. The algorithm embeds the \(1\)-bit information into a pair of adjacent encrypted pixels. According to the homomorphic characteristics of the Paillier cryptosystem, the receiver obtains the secret information by comparing all the decrypted pixel pairs. The disadvantage of the [PERSON]'s method is that there is an inherent overflow problem. Subsequently, [PERSON] et al. [19] and [PERSON] et al. [20] improved [PERSON]'s method by solving the overflow problem. The above inseparable algorithms limit the application scenario and scope of the algorithms, and the separable algorithms have more application scenarios. The receiver's privilege determines different operations it can perform, for example the receiver can only extract additional data, the receiver can only decrypt the image, and the receiver can both decrypt the image and extract additional data. In 2016, [PERSON] et al. [21] first proposed a separable EIRDH-P algorithm, which combines wet paper code (WPC) [22] with Paillier homomorphic encryption. [PERSON]'s method vacates room by histogram shrinking and uses WPC to embed additional data. [PERSON] et al. [23] proposed a RDH-EI algorithm based on mirroring ciphertext groups (MCGs) by using the homomorphic and probabilistic characteristics of the Paillier cryptosystem. In summary, using the homomorphic characteristics of public key cryptography for RDH-EI is the latest research hotspot, which we call reversible data hiding in homomorphic encrypted image (RDH-HEI). This paper proposes a RDH-HEI scheme based on EC-EG. Firstly, the cover image is segmented. The square grid pixel group randomly selected by the image owner has one reference pixel and eight target pixels.