Data-Hiding Based on Sudoku and Generalized Exploiting Modification Direction

Jiin-Chiou Cheng, Wen-Chung Kuo, and Bo-Rong Su

Abstract—Division arithmetic and generalized exploiting modification direction (DA-GEMD) method has perfect efficiency in data-hiding. However, there exist some weaknesses in DA-GEMD. Because the benchmarks are their median of nine pixels in each block of cover-image, it will give a hint for the attacker to hack the stego-image. In the paper, we utilize the Sudoku table to randomize the benchmark for each 3×3 block of cover-image. It will mix up the pixels in each image block and prevent the secret information from being extracted. The proposed method still keeps the original efficiency as DA-GEMD while promoting the security for data-hiding.

1. Introduction

With advances in computer technology, the method and speed of data transfer are also growing rapidly. The advances in computer technology have many benefits, but they also bring disadvantages. The hacker using computer technology to make profits has been rising. How to prevent these problems is unworthy of discussion for us. On the contrary, information hiding is the most important for us.

Information hiding is part of information security technology. With advances in computer technology, the information value has gained more and more attention. Today, more and more users and organizations emphasize the safety of their own data. Once important information happens to be peeped or tampered, the impact caused would be difficult to estimate.

The main practice to hide information is to hide the secret information into cover-image which then becomes a stegoimage. Transmit the stego-image in the case of others undetectable, and thus the secret information hidden in the stego-image could be recovered on other systems. Because it cannot be perceived, security and privacy of information can be achieved[1]-[3].

Information hiding technology has two requirements—security and privacy. Security is to ensure the stego-image undetectable. Thus it cannot be perceived even being removed or tampered. In order to reduce the hidden information to be perceived, we need to increase the randomness to enhance the difficulty of the stego-image to be cracked. The conventional method for data-hiding is not flexible. There is not much chance to improve the security of data-hiding. They are guessed and cracked easily. Therefore, we need more technologies for randomizing and non-fixing. The paper presents a new approach to strengthen the existing methods.With Sudoku randomness and independence, we enhance the unpredictability for stego-image and improve the security to be perceived.

The structure of this paper is as follows: Section 2 recommends the conventional data-hiding techniques of least significant bit (LSB), exploiting modification direction (EMD),generalized exploiting modification direction (GEMD), and division arithmetic and generalized exploiting modification direction (DA-GEMD), which are relevant to our proposed method; Section 3 proposes the data-hiding method on the basis of Sudoku game and DA-GEMD; the discussion of experimental results and its conclusions are done in Sections 4 and 5, respectively.

2. Literature Study

2.1 Sudoku

Sudoku had already been developed in USA in 1970. At that time, it was called “Number Place”. It was spread to Japan in 1984, and was renamed as SudokuMore other playing methods about Sudoku were created later.

The main work for playing Sudoku is to fill nine numbers(1 to 9) into 3×3 grids. There is a limitation that the numbers in the columns, rows, and diagonals must be not the same. The numbers cannot be repeated in the nine palaces of 3×3 grids at the same time. The basic rule for playing Sudoku is as follows:

[Rule 1]: Sudoku grid is rectangle.

[Rule 2]: The size of Sudoku grid is all 3×3.

[Rule 3]: Each 3×3 grid can be filled in the number of 1 to 9 inside, each number can not be repeated.

[Rule 4]: In the 9×9 table of Sudoku game, its doses of column and row must be filled with the number of 1 to 9.

[Rule 5]: Each subgroup is independent in the table of Sudoku game.

The above rule causes Sudoku game to have very good randomness and independence. An example of Sudoku table is shown in Fig. 1.

Fig. 1. Example of Sudoku table.

2.2 Data-Hiding Based on LSB

Data-hiding based on LSB is to replace the lowest bit of every picture element in the image directly by secret information for reaching the hidden purpose of information[4]-[7].So the receiver acquires the stego-image, so long as the lowest bit is taken out from each picture element, and arranges these bits, the secret information will be recovered.

Clearly, data-hiding based on LSB is very easy to carry.Relatively, the data-hiding analyst can measure this method out by simple location detection. So the security issue should be careful due to using LSB technology.

2.3 EMD Data-Hiding

Data-hiding often needs to strike a balance between the amount of hidden information and the quality of stego-image.In other words, raising the information amount to be hidden will reduce the quality of stego-image, meanwhile, paying attention to the quality of stego-image will reduce the information amount to be hidden.

In 2006, EMD[8]-[10], which was proposed by Zhang and Wang, could reach the promotion of the hidden information amount and the maintenance of image quality at the same time.EMD regardsnpixels as one group. It hides the secret information by adjusting the value of the neighborhood pixel with the minimum difference. Certainly, it must convert the secret information to a (2n+1)-ary first before carrying out the procedure. Then, utilize the extract function (1) to adjust the corresponding picture elements for hiding the secret information into thenpixels:

A. Data-Hiding Steps

1) Takensuccessive pixels from the cover-image, and compute the value of the extract functionf(∙).

2) Convert the secret information to the (2n+1)-ary strings,and calculate the difference betweenf(∙) ands:

B. Data-Extracting Steps

1)nsuccessive pixels, which are regarded as one group, are taken from stego-image by order. The values of the extract functions for each group are computed separately.

2) Convert the value of the above computed function into the binary system. Then, the secret information can be obtained.

2.4 GEMD Data-Hiding

EMD data-hiding increases withnvalue, while the hiding amount will drop by a wide margin. In order to improve the hiding amount, and let the user decide the size of one group of the picture element arbitrarily, Kuo and Wang proposed a new coding function, which is named as GEMD method[11]. The function is described as follows:

A. Data-Hiding Steps

1) Take out three pixels from the cover-image, which are regarded as one group.

2) Through (4), the function valuetis computed.

Prepared the final version of the manuscript: Stenina-Adognravi O

3) Convert the secret informationsinto the decimal system.

4) Compute the different value:

5) Refer to Table 1. Ifδ=0, do nothing. If 0<δ<8, convertδinto a 4-digit binary number (b4b3b2b1). Then, takeg1=b1–b2,g2=b2–b3, andg3=b3–b4. Ifδ=8, take (g3g2g1) = (101). Ifδ>8,compute 2’s complement (b4b3b2b1) ofδfirst, then takeg1=b1–b2,g2=b2–b3, andg3=b3–b4.

6) Subtracting (g3g2g1) from the pixels of the cover-image by the order of group, the stego-image is acquired.

Table 1: Conversion table

B. Data-Extracting Steps

1) Take out three pixels from the stego-image by order,such as, which is one group of pixel.

2) Computes, which is the secret information, by utilizing

2.5 DA-GEMD Data-Hiding

In 2014, Kuoet al. proposed the DA-GEMD method[12],[13],which combines two methods of GEMD and LSB, to promote the quantity of hidden information and further improve the security of the original GEMD method. Its main procedure is to split the cover-image into the blocks with the size of 3×3 pixels. According to the distribution of pixels of every block,the relative hiding technology is adopted. The concrete steps of DA-GEMD data-hiding are as follows.

[Input]: Cover-imageCwith the size ofH×Wand secret informationM.

[Output]: Stego-imageS.

3) Select median EP inQijas benchmark:

5) According to the following steps [A] and [B], the secret informationmwithnbits is embedded into the cover-imageC.

6) Summarize the above step 5, the stego-imageSwill be obtained.

The data-hiding flowchart in DA-GEMD is shown in Fig. 2.B. Data-Extracting Steps

2) Divide the value of pixel inby 4. Then, we obtain the quote block

3) By (6), we could recover the medianthe benchmark in embedding the secret.

4) Compute

5) According to the following steps [A] and [B] withextract the secret informationmfrom the stego-imageS.

The data-extracting flowchart in DA-GEMD is shown in Fig. 3.

Fig. 2. Data-hiding flowchart in DA-GEMD.

Fig. 3. Data-extracting flowchart in DA-GEMD.

3. Data-Hiding Based on Sudoku and DA-GEMD

3.1 Principle

DA-GEMD adopts the median number of 3×3 pixel block as benchmark. Such strategy is simple and easy to implement.But it exists to be guessed and analyzed easily. For improving the weak, a variable benchmark is better policy.

In the paper, we lead the randomness of Sudoku to confuse the benchmark. In another word, while processing data-hiding,we will randomly appoint some numbers in Sudoku table with 3×3 grid as benchmark. By Sudoku table, it is hard to guess the benchmark correctly. So, it will improve the security in datahiding.

The proposed method will process data-hiding with DAGEMD. The followings are the detailed steps.

A. Data-Hiding Steps

1) Select Sudoku table with 9×9 arbitrarily, for example,Fig. 1.

2) Choose a numberpfrom the 3×3 block within the 9×9 Sudoku table, which is regarded as the benchmark in datahiding.

3) Cut out the cover-image into some 9×9 pixel blocks.Then, each block corresponds to a 9×9 Sudoku table.

4) Further, the 9×9 pixel block will be cut into nine smaller blocks with 3×3 pixels, such aswhich is object to be operated.

7) According to the value of, process the following procedure.

Fig. 4. Flowchart of the proposed data-hiding.

B. Data-Extracting Steps

1) Select the same Sudoku table like data-hiding, such as,Fig. 1.

2) Use the same number as the benchmark like data-hiding,such as 1. In the 9×9-grid Sudoku table, the number 1 is position-variable for each sub-Sudoku of 3×3-grid. In other words, each 3×3-pixel block of the stego-image corresponds to the position-variable benchmark.

3) Take the quote block of the stego-image, i.e.,

5) According to the value of, process the following procedure.

The flowchart of the proposed data-extracting is shown in Fig. 5.

Example:

[Input]:

Fig. 5. Flowchart of the proposed data-extracting.

4. Experimental Results

For convenience, transfer the original image with 512×512 pixels to the modified image with 504×504 pixels, which can be divided by 9. The secret information is the picture with 256×256 pixels. We use the popular pictures Lena (Fig. 6 (a)),Baboon (Fig. 6 (b)), F16 (Fig. 6 (c)), and Tiffany (Fig. 6 (d)) as the cover-images, and STUST logo (Fig. 7 (a)) and CHT logo(Fig. 7 (b)) as the secret information.

Fig. 6. Cover-images: (a) Lena, (b) Baboon, (c) F16, and (d)Tiffany.

Fig. 7. Secret information: (a) STUST and (b) CHT.

The experiments will be proceeded in the following four situations.

1) Nok-LSB method with fixed Sudoku table: NLSB.

2) Nok-LSB method with random Sudoku table: NLSBR.

3)k-LSB method with fixed Sudoku table: YLSB.

4)k-LSB method with random Sudoku table: YLSBR.

The experimental results are shown in Table 2.

Table 2: Maximum embedded amount and PSNR

We also give the comparison between Kuoet al.’s DAGEMD and ours using the peak signal-to-noise ratio(PSNR), which is shown in Table 3. Table 3 exhibits that the proposed method does not influence the efficiency of DAGEMD.

Table 3: Comparison between Chen’s DA-GEMD and ours in PSNR for CHT

5. Conclusions

The DA-GEMD data-hiding method has good efficiency.However, the obvious weaknesses exist in DA-GEMD. Each 3×3 block of cover-image adopts the median of nine pixels as its benchmark, which will expose the clue to be attacked easily.In the paper, we introduced Sudoku table to randomize the benchmark for each 3×3 block of cover-image. It could confuse the attacker and prevent the secret information from being extracted. The proposed method not only preserved the original efficiency of DA-GEMD, but also promoted the security of data-hiding.

The proposed data-hiding method could be improved further. In the paper, the same Sudoku table was sent to the extractor in advance, which could bring about the inconvenience. We could embed Sudoku table into the coverimage while hiding the secret information. The concrete practice is as follows: First, referring to Sudoku table, assign a number to be the benchmark for each 3×3-grid block; then embed these benchmarks into the cover-image; so the extractor can process data-extracting with the different Sudoku tables.