Improving Data Hiding Capacity Based on Hamming Code

Abstract

Matrix encoding proposed by Crandall can be used in steganography data hiding methods. Hamming codes are kinds of cover codes. “Hamming + 1” proposed by Zhang et al. is an improved version of Matrix encoding steganography. The embedding efficiency of “Hamming + 1” is equal to (k + 1)2^k+1 − 1/(2^k+1 − 1), and embedding rate is (k + 1)/2^k. Our proposed “Hamming + 3” scheme has a slightly reduced embedding efficiency, but improve highly embedding rate. We therefore propose verifying the embedding rate during the embedding and extracting phase. Experimental results show that the reconstructed secret messages are the same as the original secret messages, and that the proposed scheme exhibits a good embedding rate compared to that of previous schemes.

80.1 Introduction

The purpose of data hiding [1, 2] is to facilitate covert communication in the form of concealed messages in a cover media to modify the media. In the case of a single carrier for an application, all secret information such as images, videos, and MP3 files is stored in the carrier. The goal of data hiding is to ensure that embedded data remain inviolate and recoverable. There are two issues with data hiding. One is to provide proof of the copyright, and the other is to provide assurance of content integrity. Therefore, the data should stay hidden in a host signal, even if that signal is subjected to manipulation or degrading such as filtering, re-sampling, cropping, or lossy data compression. However, data hiding generally shows weakness to such manipulation. There are trade-offs between the quantity of embedded data and the degree of immunity to host signal modification. As one increases, the other must decrease. Although this can be shown mathematically for some data-hiding systems such as a spread spectrum, it seems to hold true for all data-hiding systems. The goal of steganalysis is to detect (and possibly prevent) such communication. Generally, steganalysis tools can easily detect a stego image when the error rates are over about 10 % to conceal a message.

Crandall [3] proposed a new data hiding scheme called matrix encoding. The F5 algorithm [4] is based on matrix encoding and implemented by the Westfeld. We can the definition of the cover coding [5–7] in [4]. Matrix encoding was also used in large payload applications [8]. BCH codes were applied to achieve a tradeoff between embedding complexity and efficiency [9]. Westfeld showed matrix encoding using Hamming codes. The CPT method [10] shows the embedding efficiency by hiding messages based on the weighted value of a block. Matrix encoding and CPT can be applicable to LSB steganography. Zhang and Wang [11] showed the ternary Hamming codes using the concept of efficiency by exploiting the modification direction (EMD). The performance of “±steganography” was introduced by the [12]. Mielikainen [13] presented a method based on a pair of two consecutive secret bits. Chang et al. [14] proposed (7, 4) Hamming code for data hiding, which improves on the “Hamming + 1” scheme.

In this paper, we propose novel improving data hiding methods by extending the Hamming codes. Our proposed method can significantly improve the embedding rate of “Hamming + 1” scheme, and perform equally well, or even outperform.

The rest of this paper is organized as follows. In Sect. 80.2, we review current and related work. In Sect. 80.3, we introduce our proposed “Hamming + 3” for grayscale images. In Sect. 80.4, we explain the experimental results. Section 80.5 presents our conclusions.

80.2 Related Works

In Sect. 80.2.1, we will describe the concept of Hamming code and show how to apply Hamming codes to data hiding. In Sect. 80.2.2, the basic theory and efficiency of “Hamming + 1” is presented.

80.2.1 Hamming Codes

Linear codes with length n and dimension k will be described as [n, k] codes. Hamming codes are linear codes and will be described as a [n, k] q-ary Hamming code, where q is the size of the base field, F _q . A generator matrix G for an [n, k] linear code c (over any field F _q ) is a k-by-n matrix for which the row space is the given code. In other words $c = \{ xG|x \in F_{q}^{k} \}.$ Matrix encoding conceals messages with the parity check matrix of linear codes. If c is an [n, k] linear code, the dual to it is an [n, n − k] linear code. If H is the checker matrix for c, H is an (n − k) × k matrix the rows of which are orthogonal to c and {x | Hx ^T = 0} = c.

$$ (m_{1} , \ldots ,m_{k} )^{T} = H \cdot \left( {LSB(x_{1} ), \ldots ,LSB(x_{n} )} \right)^{T} $$

(80.1)

The Hamming codes function is to embed k bits $(m_{1} , \ldots ,m_{k} ) \in F_{k}^{2}$ in the LSBs of n pixel gray values $(x_{1} , \ldots ,x_{n} )$ by at most R changes in the following manner. Note that the covering radius R is the largest number of possible changes and the purpose of Hamming codes is to minimize the average number of embedding changes R _a . In other words, the goal is to maximize the embedding efficiency k/R _a depending on the embedding rate k/n. We note that to correct one error, the position of the erroneous bit must be determined. For an n-bit code, log₂ n bits are therefore required. Equation (80.2) shows the parity check matrix for a (7, 4) Hamming code:

$$ H = \left[ {\begin{array}{*{20}c} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} } \right] $$

(80.2)

For c to be a codeword, it must be in the null space of this matrix, i.e., Hc = 0. Let us assume there is a sequence of bits that have an error in the first bit position, e.g., 1101010 _b . We calculate the syndrome S with Eq. (80.1). c is a 7-bit binary number and T denote the transpose of a codeword c, that is, the syndrome is ([001])^T. A syndrome value that is not zero denotes the position of the erroneous bit. If one flips the bit at this position in the codeword, every bit of the codeword will be correct. Binary Hamming codes are [2^r − 1, 2^r − 1 − r] linear codes with a parity check matrix H of dimensions r × (2^r − 1) and whose columns are binary expansions of the numbers 1,…, 2^r − 1. For example, Eq. (80.3) shows the parity check matrix H for r = 4. Let us assume that the cover object is an image consisting of P × Q pixels.

$$ H = \left[ {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{array} } \right] $$

(80.3)

Example 1

We assume that the codeword c is [1101001]. It is easy to calculate the syndrome using Eq. (80.1) with the parity check matrix H and the codeword: S = H × (c)^T = ([000])^T. If the computed syndrome vector S is 0, as in this case, there is no error in the codeword. Otherwise, there is an error in the bit at position S in c.

80.2.2 “Hamming + 1” Scheme

The parity check matrix of a Hamming code yields a covering function COV (1, 2^k − 1, k), k ≥ 1, i.e., embed k bits $(m_{1} , \ldots ,m_{k} )$ into the LSBs of 2^k − 1 pixel gray values $(x_{1} , \ldots ,x_{{2^{k} - 1}} )$ using at most one change. This covering function is defined by $(m_{1} , \ldots ,m_{k} )^{T} = H \cdot (LSB(x_{1} ), \ldots ,LSB(x_{{2^{k} - 1}} ))^{T}$, where H is the parity check matrix of [2^k − 1, 2^k − 1 − k] Hamming code. Hamming covering function combines with one pixel to form “Hamming + 1” scheme, which embeds k + 1 bits into 2^k pixels gray values using at most one change:

$$ (m_{1} , \ldots ,m_{k} )^{T} = H \cdot (LSB(x_{1} ), \ldots ,LSB(x_{{2^{k} - 1}} ))^{T} $$

(80.4)

$$ m_{k + 1} = \left( {\left\lfloor {x_{1} /2} \right\rfloor + \cdots + \left\lfloor {x{}_{{2^{k} - 1}}/2} \right\rfloor + x{}_{{2^{k} }}} \right)\bmod 2 $$

(80.5)

The first k bits are embedded into LSBs of the first 2^k − 1 pixel values using the COV (1, 2^k − 1, k) Hamming covering function, and the (k + 1)-th bit is a function of all 2^k pixels including the appended one. Note that by adding or subtracting one to/from a pixel value x, its LSB(x) always becomes the same binary value LSB(x) ⊕ 1, however, $\left\lfloor {x/2} \right\rfloor \bmod \;2,$ which is the second least significant bit of x, can either be ‘0’ or ‘1’. Therefore, when Eq. (80.4) does not hold, one pixel value, say, x _i , 1 ≤ i ≤ 2^k − 1, has to be changed. By choosing x _i  + 1 or x _i  − 1, both Eqs. (80.4) and (80.5) can hold simultaneously without changing $x_{{2^{k} }}$.

On the other hand, when Eq. (80.4) holds but Eq. (80.5) does not, the first 2^k − 1 pixels need not to be changed, and “Hamming + 1” scheme can modify $x_{{2^{k} - 1}}$ by randomly increasing or decreasing one to satisfy Eq. (80.5). This means that “Hamming + 1” scheme can embed k + 1 bits of message in 2^k pixels with at most one change. This method shows that the embedding efficiency is equal to (k + 1)2^k+1/(2^k+1 − 1), and the embedding rate is (k + 1)/2^k.

80.3 Proposed Method

This section proposes new data hiding method, which is called “Hamming + 3”. Our proposed “Hamming + 3” improves the “Hamming + 1” scheme, which is a steganographic data hiding method, i.e., “Hamming + 1” scheme embeds k + 1 bits into 2^k pixels gray values using at most one change. Our proposed scheme improves the embedding rate compared to “Hamming + 1” scheme, i.e., “Hamming + 3” embeds k + 3 bits into 2^k − 1 pixels gray values using at most 2 change.

80.3.1 “Hamming + 3” Scheme

We propose the following “Hamming + 3” scheme by appending three pixel after the block of Hamming covering function. It embeds k + 3 bits $\left( {m_{1} , \ldots ,m_{k} ,{m_{k+1}} ,{m_{k+2}} ,{m_{k+3}} } \right)$ into 2^k − 1 pixel gray values $(x_{1} , \ldots ,x_{{2^{k} }} )$ using at most two change:

$$ (m_{1} , \ldots ,m_{k} )^{T} = H \cdot \left( {LSB(x_{1} ), \ldots ,LSB(x_{{2^{k} }} )} \right)^{T} $$

(80.6)

$$ (m_{k + 1} , \ldots ,m_{k + 3} )^{T} = H \cdot \left( {\left\lfloor {x_{1} /2} \right\rfloor \bmod 2, \ldots , + \cdots + \left\lfloor {x_{{2^{k} }} /2} \right\rfloor \bmod 2} \right) $$

(80.7)

The first k bits are embedded into LSBs of the first 2^k − 1 pixel values using the COV (1, 2^k − 1, k) Hamming covering function [see Eq. (80.6)], and k + 3 bits are embedded into second least significant bits using the COV (1, 2^k − 1, k) Hamming cover function [see Eq. (80.7)]. Therefore, when Eq. (80.6) does not hold, one pixel value, say, x _i , 1 ≤ i ≤ 2^k − 1, has to be changed. By choosing x _i  + 1 or x _i  − 1, both Eqs. (80.6) and (80.7) can hold simultaneously without changing $x_{{2^{k} }}$. On the other hand, when Eq. (80.6) holds but Eq. (80.6) does not, the first 2^k − 1 pixels need not to be changed, and “Hamming + 1” scheme can modify $x_{{2^{k} }}$ by randomly increasing or decreasing one to satisfy Eq. (80.6). This means that “Hamming + 1” scheme can embed k + 1 bits of message in 2^k pixels with at most one change. This method shows that the embedding efficiency is equal to (k + 1)2^k+1/(2^k+1 − 1), and the embedding rate is (k + 1)/2^k. [n, k] Hamming codes are now a linear space over a field of order q, prime. These q-ary codes are 1-error correcting, relying on the fact that each codeword is at a distance of at least 3 from any other codeword, which in turn relies on the construction of the matrix. Specifically, the fact that no two columns of the check matrix are linearly dependent means that the minimum distance between any two code-words is at least 3.

Proposition

Hamming Codes are 1-error correcting codes.

Proof

We need to check that

$$ |C| \cdot \frac{1}{i = 0}\left( {\begin{array}{*{20}c} x \\ y \\ \end{array} } \right)(q - 1)^{i} = |F_{q} |^{n} . $$

The right hand side of this is q ⁿ, where n = (q ^r − 1)/(q − 1). The left hand side is

$$ \begin{aligned} q^{n - r} (1 - n(q - 1)) & = q^{n - r} \left( {1 + \frac{{(q^{r} - 1)}}{(q - 1)}(q - 1)} \right) \\ & = q^{n - r} (1 + (q^{r} - 1)) \\ & = q^{n - r} (q^{r} ) \\ & = q^{n} . \\ \end{aligned} $$

80.3.2 Embedding Procedure

Our scheme is described below in terms of the embedding procedure for hiding secret data in a grayscale image. A cover image is divided into non-overlapping 7-pixel blocks. We present the embedding procedure step by step:

Input: Cover image I sized H × W, a binary secret message δ of maximum length H × W − 1, and the parity check matrix H

Output: A stego image I′ sized H × W

Step 1: Divide original images I into 1 × 2^k − 1 blocks, letting $c = (b(x_{ 1} ), \ldots ,b(x_{{2^{k} - 1}} )),$ where b(.) denote LSB of a pixel. Letting $c_{ 2} = (\left\lfloor {x_{1} /2} \right\rfloor \bmod \;2, \ldots ,\left\lfloor {x_{2}^{\text{k}} /2} \right\rfloor \bmod \;2).$ c and c ₂ denote code-words and a set of LSB and second LSB respectively.

Step 2: Read all pixels and secret messages into array variable x and δ respectively. $CNT = \left\lfloor {(H \times W)/7} \right\rfloor.$

Step 3: Calculate the syndrome S by applying Eq. (80.6) to the parity check matrix H and c, i.e., $S = H \cdot (b\left( {x_{i} } \right), \, \ldots ,b(x_{{2^{k} - 1}} ))^{T} ,$ where i = 1… n. Compute $S_{ 1} = S \oplus \delta_{j}^{k} ,$ where ⊕ is XOR operation and $j = 1\ldots n,\;j = j + k.$ As S ₁ is the position for 1-error correction, if S ₁ is 0 then no flipping any pixel, else flipping a value of $b(x_{{i + S_{1} }} ).$

Step 4: Calculate the syndrome S ₂ by applying Eq. (80.7) to the parity check matrix H and c ₂, i.e., $S_{ 2} = H(\left\lfloor {x_{1} /2} \right\rfloor \;\bmod \;2,\; \ldots \left\lfloor {x_{{2^{k} }} /2} \right\rfloor \;\bmod \;2)^{\text{T}} ,$ where i = 1… n, i = i + (2^k − 1). Calculate the syndrome value for messages, $S_{ 3} = S_{ 2} \oplus \delta_{j}^{k} ,$ where ⊕ is XOR operation and j = 1… n, j = j + k. If S₃ is 0, then no flipping any pixel, else flipping a value of $(\left\lfloor {x_{{i + S_{3} }} /2} \right\rfloor \bmod \;2).$

Step 5: Decrease CNT by 2^k − 1. If CNT is greater than 0, return to step 3 to continue the process until there are no more pixels of I.

Example 2

A detailed explanation of the reasons is included in this example. A linear pixels c = (67 79 83 88 91 93 95) is a 1 × 2^k − 1 block, reading from left to right and from top to bottom. The secret stream pixels are δ = (1 1 1 1 1 1), which is a k + 3 block. Calculate S = (H · (b(67) b(79) b(83) b(88) b(91) b(93) b(95))^T) mod 2 = (100). S is computation using LSB of a block of pixel. $S_{2} = S \oplus \delta_{j}^{k} = \left( {011} \right)$. Compute $c_{{D(S_{2} )}} - 1= 8 2$, where D(.) is a function of binary-to-decimal conversion. Next, we show how to conceal secret bits k into second LSB layers. Calculate $S_{ 3} = H \cdot ((\left\lfloor { 6 7/ 2} \right\rfloor \left\lfloor { 7 9/ 2} \right\rfloor \left\lfloor { 8 3/ 2} \right\rfloor \left\lfloor { 8 8/ 2} \right\rfloor \left\lfloor { 9 1/ 2} \right\rfloor \left\lfloor { 9 3/ 2} \right\rfloor \left\lfloor { 9 5/ 2} \right\rfloor )^{\text{T}} {\text{mod 2}})$ $= H\cdot\left( { 1 \, 1 \,1 \, 0\, 1\, 0\, 1} \right) \, = \, \left( {0\, 1 \,0} \right).{\text{ S}}_{ 4} = {\text{ S}}_{ 3} \oplus \delta_{j}^{k} = \, \left( { 1 \,0\, 1} \right)$. Compute $c_{{D(S_{4} )}} - 2= 8 9$.

80.3.3 Decoding Procedure

Our scheme is described below in terms of the extracting procedure of secret message bits from the stego image. A stego image is divided into non-overlapping 7-pixel blocks. We present the extracting procedure step by step:

Input: Stego image I′ sized H × W and the parity check matrix H

Output: A secret messages δ

Step 1: Divide stego images I′ into 1 × 2^k − 1 blocks, letting $c = ({\text{b}}\left( {x_{ 1} } \right), \ldots ,{\text{b}}(x_{{2^{k} - 1}} ))$, where b(.) denote LSB of a pixel. Letting $c_{ 2} = \, (\left\lfloor {x_{ 1} / 2} \right\rfloor {\text{mod 2}}, \ldots ,\left\lfloor {x_{{2^{k} }} /2} \right\rfloor \;\bmod \;2)$. c and c ₂ denote codewords and a set of LSB and second LSB, respectively.

Step 2: Read all pixels and secret messages into array variable x and δ respectively. $CNT = \left\lfloor {\left( {H \times W} \right)/ 2} \right\rfloor$.

Step 3: Calculate the syndrome S by applying Eq. (80.6) to the parity check matrix H and c, i.e., $S = H\cdot (b\left( {x_{i} } \right), \ldots ,b(x_{{2^{k} - 1}} ))^{T}$, where i = 1… n. Concatenate δ and S, i.e., δ = δ||S. A S denote extracted k bits.

Step 4: Calculate the syndrome S ₁ by applying Eq. (80.7) to the parity check matrix H and c ₂, i.e., $S_{ 1} = {\text{H}}\cdot (\left\lfloor {x_{ 1} / 2} \right\rfloor {\text{mod 2}}, \ldots ,\left\lfloor {x_{{2^{k} - 1}} /2} \right\rfloor {\text{mod 2}})^{T}$, where i = 1… n, i = i + (2^k − 1). Concatenate δ and S ₁, i.e., δ = δ||S ₁. A S ₁ denote extracted k bits. j = 1… n, j = j + k.

Step 5: Decrease CNT by 2^k − 1. If CNT is greater than 0, return to Step 3 to continue the process until there are no more pixels of I.

80.4 Experimental Results

We proposed a “Hamming + 3” method for data hiding. To prove our proposed scheme is correct, we performed an experiment to verify that it ensures the hidden image can be restored. In addition, the quality of stego image is very important for resisting detection from attackers. Therefore our method is feasible for making good quality stego images from the original grayscale image. To carry out our experiment, 512 × 512 grayscale images were used as cover images. Figure 80.1 is a cover image for experiment to verify our proposed scheme. In our experiments, the qualities of the stego images are measured by the peak-signal-to-noise ratio (PSNR) [14].

Fig. 80.1

512 × 512 grayscale cover images for data hiding experiment. a Lena. b Baboon. c Pepper. d Boat. e Barbara. f Airplane. g Goldhill. h Tiffany. i Zelda

The PSNR is the most popular criterion for measuring distortion between the original image and shadow images. It is defined as follows:

$$ PSNR = 10 \times \log_{10} (255^{2} /MSE) $$

(80.8)

where MSE is the mean square error between the original grayscale image and the shadow image:

$$ MSE = \frac{1}{m \times n}\sum\limits_{i}^{m} {\sum\limits_{j}^{n} {[I(i,j) - I^{\prime} (i,j)]^{2} } } $$

(80.9)

The symbols I(i, j) and I′(i, j) represent the pixel values of the original grayscale image and the stego image at position (i, j), respectively; m and n are the width and height of the original image, respectively.

$$ p = \frac{|\delta |}{m \times n}(bpp) $$

(80.10)

In Eq. (80.10), p denotes bits-per-pixel (bpp), which is an embedding payload. Our experiment compares how many secret bits can be carried by a cover pixel. |δ| is the number of bits of a secret message δ. There is a tradeoff between a payload and quality of an image. To increase the embedding rate, it is too obvious to require a sacrifice of image quality.

However, if it is possible to keep the balance between payload and quality of an image, we then accomplish our purpose from an aspect of steganography. Table 80.1 shows the visual quality of the stego images created by the matrix encoding, “Hamming + 1”, and “Hamming + 3”. Our proposed “Hamming + 3” method shows 0.86 bpp with a good visual quality (i.e., the PSNR value is higher than 48 dB). From Table 80.1, for the visual quality factor, the matrix coding scheme shows a higher visual quality outcome.

Table 80.1 The comparison result of the matrix encoding, Hamming + 1 scheme and proposed scheme

For embedding payload comparison, the proposed “Hamming + 3” show a high embedding payload outcome. Although the visual quality of stego images generated by the “Hamming + 1” scheme is better than the proposed scheme, some images’ quality were slightly lower than those of “Hamming + 3”. In this experiment, we verified that “Hamming + 3” is worth the steganography method, because our scheme shows reasonable embedding rate and quality as a data hiding scheme. As the PSNR of our scheme is over 48 dB, it is not easily detectable by attackers. Therefore, our scheme is highly suitable for various fields of steganography.

80.5 Conclusion

In this paper, we proposed a “Hamming + 3” method that uses both layers, i.e., LSB and second LSB, using cover codes [n, k]. “Hamming + 1” can embed COV (1, 2^k − 1, k) at the cost of 1/2^k + 1 changes. The embedding efficiency is (k + 1)2^k+1 − 1/(2^k+1 − 1). Our proposed scheme shows 0.86 bpp, so “Hamming + 3” has better performance than “Hamming + 1”. Moreover, stego images of “Hamming + 3” are over 48 dB, and it denotes that our scheme is a reasonably acceptable steganography method. Thus, we can conclude that the “Hamming + 3” is suitable for steganographic applications.