# An Improved Product Code-Based Data Hiding Scheme
## 1 Introduction  
Data (or information) hiding is one kind of steganographic technique to embed the secret information into a cover host, such as an image. Usually, the naked eye cannot perceive any change when the image is modified slightly. In 1998, [PERSON] [1] first introduced the idea of matrix embedding. The technique of matrix embedding was deeply studied in [2; 3; 4] by utilizing the characteristic of the strong algebraic structure of one-dimensional (1-D) linear code. Matrix embedding is also termed as syndrome coding and 1-D linear code is categorized as one kind of data hiding code [3; 4]. The idea of product code-based data hiding was introduced in [5; 6; 7; 8]. Basically, it can be considered as an extension of the previous works [1; 2; 3; 4] by taking a cover matrix block, not a cover sequence, for embedding on each time. They divided the cover image into disjoint matrix blocks of \((2^{y}-1)\times(2^{x}-1)\) pixels and applying the 1-D linear code-based embedding algorithm in each row and the first \(2^{x-1}-1\) columns. During each column embedding, it is very likely that the pixel modification to some row mustbe adjusted with more pixels changed to ensure the correct extraction of the secret information. Although, it will induce higher distortion in image quality, the amount of embedded information can be increased. The product code is a two-dimensional (2-D) linear code that is composed of two 1-D linear codes. Although, the embedding concepts for both the 1-D and 2-D linear code-based data hiding schemes are similar in respectively adopting the technique of 1-D syndrome coding and 2-D syndrome coding, the embedding efficiency of the latter is much higher. However, due to the tremendous computational complexity in finding a coset leader [9; 10] of a 2-D linear code, only sub-optimal approaches with moderate computational complexity were presented in the literature [5; 6; 7; 8; 11; 12]. In [5; 6; 7; 8; 12], the authors still utilized the 1-D toggle syndrome coding technique to solve the product code-based data hiding problem, whereas the authors of [11] directly utilized the concept of the 2-D toggle syndrome and proposed a sub-optimal approach with better embedding efficiency and low computational complexity. Therefore, in essence, each of the schemes that were proposed in [5; 6; 7; 8; 12] is not considered to be one kind of product code-based data hiding scheme. Data hiding with multiple embedding channels is the practice of hiding messages into hidden media many times. Usually, divide and conquer is a good technique to solve a hard problem. In this paper, instead of directly utilizing the concept of the 2-D toggle syndrome, eventually a hybrid 1-D/2-D toggle syndrome-based embedding scheme is proposed with good embedding efficiency and low computational complexity. We first propose a 1-D toggle syndrome-based scheme with two embedding channels. In this scheme, a one-off decision technique is presented to determine the locations of the required modification bits and the amount of modification will be reduced by utilizing the characteristics of the linear code. Next, to integrate the technique of [11] into our proposed scheme, we continue to propose another 1-D toggle syndrome-based scheme with three embedding channels. Since the resultant toggle array is more suitable for being assigned as the initial toggle array in the weighted approximation embedding scheme, thus a better solution is found. Further, there almost exists at least one bit 1 in each row of the toggle array of the proposed 1-D/2-D toggle syndrome-based embedding scheme. Hence, the embedding efficiency can be further and significantly enhanced when combined with the strategy of Hamming+1. This paper is organized as follows. Section 2 briefly introduces the concept of matrix embedding. The product code-based data hiding schemes are reviewed in Section 3. The proposed scheme is presented in Section 4. Section 5 presents the proposed Scheme combined with the technique of Hamming+1. Experimental results are shown in Section 6.