## 1 Introduction  
Steganography is a technique for secret communication, in which secret messages are embedded into common digital media such as images, audios, and videos. The original media is called \"cover\", and the embedded media is called \"stego\". Of these media, images are the most popular because they are widely transmitted over the Internet. Many image-based steganography methods [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17] have been proposed and applied in raw [1; 2; 3; 4; 5], JPEG [6], VQ [7], and absolute moment block truncation coding (AMBTC) [8] images. However, the application in palette images [9; 10; 11; 12; 13; 14; 15; 16; 17] is limited. Palette images [18] have gained popularity. Graphics interchange format (GIF) is a type of palette image frequently used by young consumers to communicate and express themselves. GIF animations are widely used on social media platforms such as Tumblr, Twitter, Facebook, and Line [18; 19]. A palette image includes a palette and an index table. The palette consists of a few (generally no more than 256) colors. Each pixel is represented by a color in the palette, and the index table records each pixel's corresponding color index. In general, the order of colors in the palette is random. Because only limited colors are used in palette images, modifying a pixel's color index considerably distorts the pixel color. Thus, embedding data into a palette image is more challenging than in other image formats. Embedding methods are of two types. In pixel-based methods (PBMs) [9; 10; 11; 12; 13; 14], a pixel is used as a unit to embed secret data. In block-based methods (BBMs) [15; 16; 17], a block is used as a unit to embed secret data. [PERSON] [11] proposed a method in which the colors of a palette are partitioned into two sets with different parities (\(R+G+B\) mod 2) to represent one secret bit. The capacity of this method is 1 bit per pixel (bpp). Under the same embedding capacity, [PERSON] and [PERSON] [12] proposed an optimal parity assignment algorithm to improve image quality. [PERSON] et al. [13] proposed an adaptive data-hiding scheme for palette images based on local complexity. An embedding capacity of approximately 0.1 bpp is used for most images [20]. [PERSON] et al. [14] proposed an algorithm to partition colors into \(2^{k}\) sets. Each set represents one type of \(k\)-bit secret data. For each pixel, according to the secret data, the closest color in the corresponding set is determined to replace the pixel's color. The embedding capacity is increased to \(k\) bpp. In [9; 10; 11; 12; 14], each pixel was used to embed secret data in PBMs. Therefore, the embedding distortion for a pixel may be large. In [13], an adaptive scheme was provided to skip pixels with large distortions. However, this reduced the capacity. [PERSON] and [PERSON] [15] proposed a BBM to embed \(k\) bits into each \(3\times 3\) block. In this method, first, all colors in a palette are reordered according to the color Euclidean distance. Next, for each block, the sum of all color indices is calculated and divided by \(2^{k}\) to obtain a remainder. Then, some pixels in the block are selected, and their color indices are adjusted to obtain a remainder equal to the value of \(k\) embedding secret data bits with the least embedding distortion. The embedding capacity is \(k9\) bpp. [PERSON] and [PERSON] [16] adopted a block size of \(2\times 2\) to improve the embedding capacity of their previous method [15]. Subsequently, [PERSON] et al. [17] used a block size of \(1\times 2^{k-2}+1\) to improve the embedding capacity of the aforementioned method [16] and used the \(L^{*}a^{*}b\) color space to replace the \(RGB\) color space to improve image quality. In all of these BBMs [15; 16; 17], the palette of an image is first reordered. Then, for each block, under the consideration of minimum embedding distortion, several pixels are selected, and their color indices are modified by \(+1\) or \(-1\).