Abstract
Traditional digital image authentication is usually based on signature or fragile watermarks. This performs authentication without any secret hidden data. Until now, many image authentication schemes with error detection based on watermarks or signatures have been proposed. Tampering attack can be detected but the areas tampered with cannot be determined for these schemes. In order to improve this shortcoming, a verifiable data hiding scheme is proposed for digital images in this paper. The main idea of the proposed scheme is combining multi-bit encoding function and multi-group data hiding scheme to increase embedding capacity and strengthen security with parity check to verify the tampering of digital images having embedded secret messages. Therefore, there are three major contributions in our proposed scheme. First, it can achieve image tamper detection and find what has been modified. Second, it resists collage attack. Third, it can increase the embedding capacity. These contributions are discussed according to experimental results. The proposed scheme includes a high security to reduce detection of hidden data and the MSE analysis also proves this scheme has good image quality.
Introduction
In a security system, authentication is paramount, especially over a public network like the Internet. Recent advances in networking services and capacity allow almost everything to be digitized especially as photos and images. Information transmission over the Internet can be achieved by using the cryptography or steganography. For cryptography, methods such as RSA, AES or MD5 are employed to encrypt the digital image, thus any change will be detected. Similarly, in the decryption phase, the secret data will show errors if the image is modified. Cryptography scheme is a good candidate for image authentication, but image is completely distorted, and transmission of this type into the Internet may attract interest towards the hidden data and consequential tampering.
For the past few years, many image authentication methods have been proposed [1–7]. According to image authentication research, it can be classified into two main types [8]: one is signature-based schemes [9–12] and the other is watermark-based schemes [6, 13–23]. In the signature-based schemes, the process phase is like traditional cryptography system for encryption and decryption. In other words, a hash function, public key, private key and trusted third party are necessary. The signature-based scheme is complex and not trivial to achieve. In watermark schemes, a mark is embedded into the cover image to get a watermarked image called the stego image. In watermark schemes, there are two main classifications: visible watermark and imperceptible watermark [24]. In general, imperceptible watermark satisfies the requirement of the image authentication. Thus, two watermark schemes such as the fragile watermark [6, 21] and the semi-fragile watermark [6, 25–26] were proposed. These allow a watermark to be extracted from the image to detect tampered areas when the image is authenticated.
Many image authentication schemes based on watermark or signatures have common issues, such as error detection. For example, if the image authentication uses the LSB scheme [6] for watermarking, the error detection is vulnerable to attacks such as collage attack. It means that the tampering can be detected. However, the areas tampered cannot be determined. The adaptive image authentication scheme for vector quantization compressed image is proposed by [27]. For this scheme, the block size can be any size. So, all indices are used to embed secret codes in the index table when the block size equals 1×1. However, the stego image quality is poor. That is to say, detection accuracy is inversely proportional to stego image quality in ref [27].
In order to improve the above shortcomings, a precise detection scheme must be proposed. Therefore, a novel image authentication scheme for digital images will be proposed in this paper. There are three major characteristics in our proposed scheme which compares to the two main topics of image authentication (1) It can achieve image tamper detection and find what has been modified. (2) It resists collage attack. (3) It can increase the embedding capacity. According to the simulation results, the proposed scheme includes a high security to reduce detection of hidden data and the MSE analysis also proves this scheme has good image quality.
In Section 2, we review previous works such as multi-bit encoding, GEMD map [28] and parity check. Section 3 gives a detailed introduction of the proposed method. Experiments are given in Section 4. Finally, some conclusions are given in Section 5.
Related work
In this section, the three related concepts of multi-bit encoding, GEMD map and parity check are described, respectively.
Multi-bit encoding function - general multi-EMD
In 2006, Zhang and Wang proposed a new data hiding scheme based on EMD (Exploiting Modification Direction) [29] to enhance the embedding capacity. Since then, in order to enhance the data hiding technology’s security or increase stego image quality, many EMD-type schemes [13, 31] have been proposed. Recently, a new extraction function of general EMD (GEMD) is proposed by Kuo and Wang [32] in 2013 as Equation (1):
where p
i
is the i-th pixel in adjacent pixels, n is the number of pixels. According to [32], more than one secret bit on average is better than original EMD scheme [29]. Lately, a general multi-EMD (GMEMD) scheme in order to improve the embedding capacity is proposed by Kuo et al. [28]. As far as we know, it has the best capacity and maintains good image quality. Specifically, more than two secret bits on average can be embedded by using the GMEMD scheme. Its extraction function is:
where k is the number of embedding bits and the weight value of c
i
is
In fact, the extract function of GEMD is the special case of Equation (2) when k = 1.
In order to enhance embedded data security and reduce spatial redundancy, a multi-group data hiding scheme based on GEMD (general-EMD) map was proposed by Kuo et al. (KCC-scheme) [30] in 2014. In KCC-scheme, OGEMDSEC(•) is used to obtain n1-tuples in group Gsp and n2-tuples in group Gdp by partitioning image IC into non-overlapping n1 + n2-pixel for each block. This is done by scanning left to right and top-down (raster scan), as shown in Fig. 1 [30]. Similarly, OGEMDSEC-s(•) is defined to obtain (n1 + n2 + 2) binary data from partitioning the secret binary data stream for each block. Then, they combine Gsp and Gdp with (n1 + n2 + 2) binary secret data from OGEMDSEC-s(•) to setup the embedding table such as Table 1 when n1 = 2 and n2 = 2. In Table 1, the values of sp and dp are the secret information want to be embedded by using GEMD method with two groups; Gsp and Gdp, respectively.

The embedding data sequence for KCC-scheme.
The proposed scheme
In order to describe the KCC-scheme roughly, we give the example 1.
Modify G’sp = (121, 125) and G’dp = (127, 122) according to the algorithm of the KCC-scheme.
Parity check [33] is a well-known method to check the data in a bit stream and avoid transmission errors. There are two rules as following, For the even parity: if the counts of bit ′1′ is odd/even, the parity bit is set to 1/0. For the odd parity: if the counts of bit ′1′ is odd/even, the parity bit is set to 0/1. It shows as Ex.2.
Therefore, it ensures accurate data transmission between nodes during communication. When the source is send to receiver, the transmit data and parity bits are checked and verified at the destination.
In the proposed scheme, the parity check function will produce a parity check table assigning a parity bit to each block in the cover image representing odd or even block parity. So, the parity check table acts as a secret key between sender and receiver.
In this section, our authenticated secure data hiding scheme will be proposed. There are three major benefits such as supporting authentication of the embedded data, increasing the embedding capacity and enhancing the embedding data security in this proposed scheme. Specifically, comparing with traditional image authentication scheme [1–4, 29], the major detection capacity of this proposed scheme is which modified from the tampered areas in the stego image to the tampered data in the stego image has been hidden. In order to achieve the authentication goal, we use the parity check function to add a parity bit on the right side of the secret data in this paper. The receiver can authenticate or prove if the stego image is the same from the sender or tampered. The parity check is a simple method to check data, and adding a parity bit on the right side of the secret data can maintain the quality of the stego image. Thus, the parity check is the suitable choice used to do the authentication. The second major advantage is embedding capacity increases because our proposed scheme uses the GMEMD scheme to embed secret data. According to the simulation results, the embedding rate of the proposed scheme is close to 2.6 bpp (when n1 = 2, n2 = 3, k1 = 3 and k2 = 2). Finally, the third benefit is security. The embedding table is used to match and shift the secret data indices into another set of indices. For example, with secret (001000)2, the embedding table (Table 1) gives dp = 7 and sp = 0 which matches the calculated index of the initial pixel data. In addition, the embedding table cannot guess because the secret data are arranged randomly. Since the embedding table is pre-agreed upon by the receiver and sender, the secret data can only recover by the intended receiver. Intercepting the shifted data without the pre-agreed upon table does not allow for obtaining the secret data.
There are four phases in the proposed scheme: initial phase, parity check phase; transmission phase and embedding phase. The flowchart of the proposed scheme is shown as Fig. 2.
Phase 1 (Initial phase): Given the parameters n1, n2, k1 and k2, we can generate the embedding table which size are 2n1k1+1 × 2n2k2+1. Next, overflow is checked for all pixels by raster scan order.

The flowchart of authenticated secure data hiding scheme.
Phase 2 (Parity check phase): For each block, we get (n1k1 + n2k2 + 1) binary secret data bits and then determine the parity bit by using the parity check function.
Phase 3 (Transmission phase): Find the referenced embedding indices from the embedding table with the parity secret data. In other words, we get the reference embedding indices (sp, dp) in this phase.
Phase 4 (Embedding phase): Use the algorithm 1 to embed the secret into the cover image to produce an authenticated stego image.
cover image and secret messages stego image Divide the cover image into (n1 + n2) non-overlapping pixels for each block. Next, check overflow. If either occurs, it decreases max (2k1-1, 2k2-1) for each pixel to compensate. For each block, compute the value of the extraction functions t1 = f1 (p1, p2, …, p
n
1
) and t2 = f2 (pn1+1, pn1+2, …, pn1+n2) from the Equation (2). Get (n1k1 + n2k2 + 1) bits from the secret message and one parity bit from parity check table. Then, find the reference embedding indices (sp, dp) from the embedding table. Compute the difference values D1 and D2 between (sp, dp) and (t1, t2), i.e., D1 = (sp - t1) mod 2n1k1+1 and D2 = (sp - t2) mod 2n2k2+1.
For i = 1 or 2, do
{
If D i = 0, then cover-pixels do not change;
else if D i = 2 nk , then and.
else if D
i
< 2
nk
, then transform
else if D
i
> 2
nk
, then transform
}
Here, we give an example to explain this proposed scheme.
According to D1 and D2, modify the cover pixels (84, 170, 166, 167, 166) of the cover image. The stego pixels (84, 167, 165, 167, 164) come from the algorithm 1.
In this section, we use our proposed scheme to show experimental simulations and performance discussion. The experiment hardware environment is a personal computer with an Intel CoroTM i7-2600 CPU @ 3.40 GHz having 16 G RAM. The operating system is Windows 7 Professional and the experiment software is MATLAB. The performance discussions including the MSE analysis, tamper test and collage attack are to probe our experimental results of the verifiability data hiding scheme.
MSE analysis
The major concerns for data hiding scheme analysis are capacity and image quality. Peak signal to noise ratio (PSNR) measures stego image quality. As a rule, the higher the PSNR, the more similar the stego image is to the cover image. In general, if PSNR is lower than 30 dB, the stego image can be visually distinguished from the cover image as different. The formulas of PSNR Equation (4) and mean square error (MSE) Equation (5) calculation are defined below:
where the M and N are the length and width of image, and I (i, j) and represent the pixel values of the cover image and the stego image at position (i, j), respectively.
In order to demonstrate the stego image quality of the proposed scheme, we propose formula Equation (6) to calculate the theoretical value of MSE for different n1, n2, k1 and k2.
where vn i ,k i is the weight as define as Equation (7):
We also take eight well known 512×512 grayscale images (Airplane, Baboon, Boat, Elaine, Goldhill, Lena, Peppers, and Tiffany) to test in our proposed scheme. Next, the original cover images and the simulation results of the stego images (n1 = 2, n2 = 3, k1 = 3 and k2 = 2) are shown in Figs. 3 and 4, respectively. According to simulation results, there are perceivable differences between the cover images and stego images from human eye inspection when any n1 and n2 with corresponding k1 and k2 are adjusted arbitrarily. Here, we summarize the stego images’ PSNR and capacity in the Tables 2 and 3.

Eight 512×512 cover images.

Eight 512×512 stego images.
Simulation Results (when n1 = 2, n2 = 3, k1 = 3 and k2 = 2)
Simulation Results (when n1 = 3, n2 = 2, k1 = 2 and k2 = 3)
From the Table 2, average MSE(2,3),(3,2) = 7.3804 and PSNR(2,3),(3,2) = 39.45dB for n1 = 2, k1 = 3,
n2 = 3 and k2 = 2. From the Table 3, average MSE(2,3),(3,2) = 7.3827 and PSNR(2,3)(3,2) = 39.44dB for n1 = 3, k1 = 2, n2 = 2 and k2 = 3. Therefore, these analysis results are similar to the theoretical results in the example 4.
In this subsection, we will demonstrate the proposed scheme can detect the tampering attack and where it occurs in the stego image. There are many reasons for tampering. For example, it may be from image processing software such as Adobe PhotoShop or PhotoImpact; the result of image compression such as JPEG (Joint Photographic Experts Group) or VQ-compressed (Vector Quantization). However, any tampering will be detected by the parity check table. A tampered image is Tiffany shown in Fig. 5(b), and the gray YUNTECH logo is the inserted object (Fig. 5c). From the result of Fig. 6, it allows the receiver to detect this stego image has been tampered with the proposed scheme. Specifically, it can roughly detect and show the tampered area. In the compressed VQ and JPEG formats, the resulting in a simulated of JPEG can detect the tampered area, but VQ cannot to do, as shown in Fig. 7. Because one index is modified in VQ, one block is changed. It makes too much influence to detect the real modified location.

(a) The original stego image (b) The tampered stego image.

Roughly detected image.

Detect the stego image.
In addition, we also use two images to embed into the cover image, and the YUNTECH logo is the inserted image. That is to say, two 100×100 secret images such as Fig. 9 will be embedded into the original cover image (Fig. 5a) and the tampered stego image shown as Fig. 8(a). Simulation results are shown as Figs. 10 and 11, respectively. From Fig. 10, we can extract these two tampered secret images from the Fig. 8(b). Then, the parity check table is used to determine the tampered location as shown in Fig. 11. Finally, we can get the complete secret images or tampered secret images through the proposed scheme.

(a) The tampered stego image (b) The YUNTECH logo.

Secret images.

Extract secret images from the stego image.

Roughly detected image.
In this subsection, we will introduce and simulate the collage attack. For the collage attack, if two different images are hiding the same secret information with the same conditions, we can copy one or more areas from stego image A to the same locations of stego image B to generate an attack. For simulation, we use two test stego images of Lena and Elaine (Fig. 12). In Fig. 13, the collage attacks are added. In other words, we cut and past two small blocks from Fig. 12(a) to (b). According to our proposed scheme, it can prevent the collage attack and verify the authority of secret data from Fig. 14. However, this attack cannot be detected in many image authentication schemes [6, 26].

Two test stego images.

The collage attack image.

Simulate results.
Finally, we give a summarized comparison table shown as Table 4. There are five points we would like to stress from Table 4. From viewpoint of goals, the major goal of our proposed scheme, is a data hiding scheme and authenticates secret data secrecy. From the domain operation, our proposed scheme not only uses the spatial domain but also uses formulas to embed the secret data and authenticate it. From the simulation results, our scheme proposes an authentication operation for data hiding schemes, and also prevents collage attack. In addition, the proposed scheme embeds a secret message, which can be verfied. In scheme processing, our proposed scheme and others [6, 26] only use one formula to do embedding and extracting. From the embedding capacity, the proposed scheme has higher capacity more than other schemes and maintains good image quality.
Comparison table
As a whole, the proposed scheme embeds a secret message, while also carrying authentication information.
Until now, many image authentication schemes based on signatures or watermarks have been proposed. In this paper, we have shown a novel image authentication scheme with four characteristics: (1) The stego image is an authenticated stego image. (2) It can determine if the embedded data is tampered or not. (3) The detection in proposed scheme can resist the collage attack. (4) The proposed scheme has good image quality provided by the simulation results and MSE analysis.
Footnotes
Acknowledgments
This work was supported in part by the Ministry of Science and Technology of the Republic of China under Contract No. MOST 106-3114-E-492 -001 - and MOST 106-3114-E-110 -001 -.
