# Reversible Data Hiding in Encrypted Color Halftone Images with High Capacity
## 1 Introduction  
Data hiding refers to making the cover image imperceptibly and keeping the existence of the hidden data confidential. We call the hidden data a _watermark_. Reversible data hiding (RDH) is a technique that the cover image can be restored losslessly after the watermark is extracted [1]. This characteristic makes RDH suitable for high authentication scenarios, such as medical image processing or military communication. It is widely used in applications such as law forensics [2; 3; 4], military imagery, medical imagery [5], cloud storage [6; 7], copyright protection [8; 9; 10; 11], etc. The traditional RDH schemes can be classified into several categories such as lossless compression [12], difference expansion (DE) [13; 14], histogram shifting (HS) [15; 16], and pixel prediction [17]. Combined with image encryption schemes, many algorithms of RDH in encrypted domain (RDH-ED) have been proposed. According to whether the image decryption and data extraction procedures are separated, the RDH-ED algorithms can be categorized into two types: (1) inseparable algorithms; and (2) separable algorithms. For inseparable algorithms, [PERSON] et al. [18] applied RDH algorithms to encrypted images by embedding additional bits into pixels blocks encrypted by AES (Advanced Encryption Standard). In 2011, [PERSON] proposed an algorithm that flips the three least significant bits (LSBs) of half of the pixels in each block [19]. The embedded additional data can be extracted after the encrypted imagewith additional data being decrypted. [PERSON] et al. [20] improved [PERSON]'s algorithm [19] by adopting a better measurement method for the smoothness of blocks and using the side-match scheme to decrease the error rate of extraction. For separable algorithms, [PERSON] proposed a separable RDH-ED, in which image decryption and data extraction procedures are independent operations [21]. [PERSON] et al. introduced an algorithm that solved a problem of [PERSON]'s scheme [22], which cannot recover the original image completely. In [23], [PERSON] et al. proposed an improved embedding capacity algorithm that needed to reserve room before encryption. Besides, the embedding capacity of the encrypted image is improved. [PERSON] et al. [24] proposed an effective algorithm with adaptive encoding strategy. MSB (most significant bit) layers of embeddable blocks are adaptively compressed according to occurrence frequency of MSB in order to vacate room for data accommodation. As for halftone images, there are few RDH algorithms available in the literature. Since the redundancy left in halftone image is low, most RDH algorithms for continuous-tone images cannot be directly used in halftone images. Depending on whether the continuous-tone image is available to the embedding process, the RDH algorithms for halftone images can be classified into two categories:  
1. Only the halftone image joins the embedding process. [PERSON] and [PERSON] proposed RDH-EH algorithm by forced complementary toggling at pseudo-random locations if only the halftone image is available [25]. [PERSON] et al. introduced a high-capacity RDH method for ordered dithered halftone images, which applied dither matrix to pixel pairs so that abundant data can be hidden into these pixel pairs [26]. [PERSON] et al. proposed a separable RDH algorithm, which used Hamming codes to embed watermark [27]. 2. The continuous-tone image joins the embedding process. For the situation in which the original continuous-tone image is available, [PERSON] and [PERSON] proposed an algorithm that integrates the data hiding operation into the error diffusion process [25]. [PERSON] et al. 's algorithm embedded the binary data into the halftone images with reference to the original continuous-tone image by evaluating the absolute difference between the neighboring gray-level pixels [28]. This method is extended from that of [PERSON] and [PERSON] [25]. For the problem of RDH in encrypted halftone image, the remaining redundancy is very difficult to utilize.