A Novel(n,n)Secret Image Sharing Scheme Based on Sudoku

Zhi-Hui Wang,Cheng Guo,and Chin-Chen Chang

1.Introduction

A secret sharing scheme is a technique to share secret data among a group of participants.It is mainly used to protect secret information from being lost,destroyed,or modified.In 1979,the first(t,n)threshold secret sharing schemes,based on Lagrange interpolating and linear project geometry,were proposed by Shamir[1]and Blakley[2],respectively.In the(t,n)threshold schemes,at least t honest participants can reconstruct the shared secret,but(t-1)or fewer participants can obtain nothing about the secret.

With the rapid development of computer networking and digital multi-media technology,transmitting digital images over the Internet has become convenient and popular.However,some important images,such as military maps,medical images,and commercial images,must be kept secret.But the Internet is an open environment,which means that it is vulnerable to a variety of attacks.For example,the transmitted image can be tampered or stolen.

Recently,many image-protection techniques,such as data hiding and data encryption,have been developed.It is well known that the secret-sharing mechanism has been applied extensively to protect secret data.The purpose of secret sharing is to recover the important information when some shadows are lost or tampered by a malicious attacker.Therefore,the secret-sharing technique can be utilized to design a mechanism to protect important images.

In 1995,Naor and Shamir[3]designed a visual,secret-sharing mechanism called visual cryptography(VC).In their scheme,the shadow data can be photocopied on transparencies,and the secret image can be decoded visually through the human visual system only by stacking a sufficient number of transparencies.The interested reader can find more on visual cryptography in [4]–[8].However,the shadow images consist of many noisy,black dots,and they are meaningless.In 2003,Thien and Lin[9]utilized the Lagrange-interpolating,polynomial-based,Shamir’s secretsharing scheme to embed the secret image into a cover image.The generated shadow images are meaningful,and the distortion between the shadow image and the cover image is imperceptible.In 2004,Lin and Tsai[10]proposed a new secret image sharing scheme in which the shared bits and the authentication bit are embedded in a four-pixel block.Lin and Tsai’s scheme combined steganography and authentication features.In 2007,Yang,Chen,Yu,and Wang[11]presented an improved secret sharing scheme for images that improved the ability to authenticate the shadow images and improved the quality of the shadow images compared to that of Lin and Tsai’s scheme.In 2008,Chang,Hsieh,and Lin[12]also proposed a novel secret image sharing scheme combining steganography and authentication based on the Chinese remainder theorem(CRT).Their scheme improved the ability to authenticate the shadow images and enhanced their visual quality.In 2009,Lin,Lee,and Chang[13]proposed a new secret image sharing scheme that utilized the modulus operator to embed the secret image into a cover image.In their scheme,the secret image can be reconstructed losslessly,and the cover image also can be recovered without distortion.Their method can be used for calligraphy images,which often lead to underflow or overflow in image processing.In 2010,Lin and Chan[14]proposed an invertible secret image sharing scheme.They were able to retrieve the lossless secret image and reverse the shadow image to the cover image without distortion.And,their scheme achieved an excellent combination of embedding capacity and quality of the shadow images.Secret image sharing has been studied further in recent research[15]–[18].

In 2010,Chang,Lin,Wang,and Li[19]proposed a Sudoku-based secret image sharing scheme.Their scheme utilized the concept of Sudoku and Shamir’s secret sharing scheme to embed the secret image into the cover image for the purpose of generating shadow images.In their scheme,the secret image can be retrieved without distortion,and the cover image also can be recovered losslessly.Their proposed reversible secret image sharing scheme offered a large embedding capacity compared with related camouflage image sharing schemes.Furthermore,due to the fact that the camouflaged pixel pair ranged within the Sudoku block,i.e.,the pixel values are limited in the grayscale boundary,their scheme solved the overflow and underflow problem effectively.

In this paper,we propose a novel Sudoku-based(n,n)secret image sharing scheme with high quality shadow images and large embedding capacity.In the proposed scheme,(n,n)secret image sharing works by deriving n shadow images from the secret image and the n cover images by using a sharing method in which the n cover images can be different.Given n shadow images,the secret image can be reconstructed losslessly.And,n-1 or fewer shadow images cannot cooperate to obtain any information about the secret image.The key features of our proposed secret image sharing scheme are summarized below.

1)The secret image can be reconstructed without distortion.

2)The embedding capacity is large.

3)The shadow images are meaningful,and the visual quality of the shadow images is satisfactory.

4)The secret image can be embedded into different cover images for the purpose of generating different meaningful shadow images.

5)The proposed scheme can solve the overflow and underflow problem.

The rest of the paper is organized as follows.In Section 2,the basic definition of Sudoku is introduced.The proposed scheme is presented in Section 3.Section 4 presents some experimental results and discussion.Our conclusions are presented in Section 5.

2.Preliminary

In this section,we briefly introduce the definition of Sudoku,which is the major building block of our proposed scheme.

Sudoku is a logic-based number placement puzzle,which is most frequently a 9×9 grid that is made up of 3×3 sub-grids called “regions” or “blocks.” Some cells already contain numbers,known as “givens.” The goal is to place one number in each of the empty cells so that every column,row,and region contain the digits from 1 to 9 exactly once.Fig.1 shows an example of Sudoku from Wikipedia.Fig.1(a)is an original Sudoku grid in which some elements have been assigned by digits within 1 to 9,and Fig.1(b)is one of the Sudoku solutions of Fig.1(a).

The Sudoku puzzle was invented by Garns in 1979,and Dell Magazines published it under the name “Number Place.” Sudoku was made popular in Japan in 1986 by the publisher Nikoli,and the Sudoku puzzle became popular internationally in 2005.In 2005,Felgenhauer and Javis[20]showed that the total number of possible solutions in a classic 9×9 Sudoku is 6,670,903,752,021,072,936,960≈6.671×1021.In 2007,Russell and Jarvis illustrated that if the various possible symmetric solutions are removed,the total number of fundamental solutions of a classic 9×9 Sudoku is still 5,472,730,538.Therefore,there is an extremely large number of possible solutions to the Sudoku puzzle.Based on the characteristics of the Sudoku puzzle,some researchers developed some novel methods[21]–[23]to embed secret information into the host image.

Fig.1.Example of a 9×9 Sudoku puzzle:(a)an 9×9 Sudoku puzzle and(b)one of the solutions of(a).

3.Proposed Scheme

In this section,we propose a novel(n,n)secret image sharing scheme based on Sudoku.In our scheme,a dealer is responsible for generating n shadow images from a secret image and n different cover images.And then,only given n shadow images,the secret image can be reconstructed without distortion.

In our scheme,let O=｛O1,O2,…,On｝ denote a set of cover images.Each Onpossesses M×N pixels,Oi=｛Oi,1,Oi,2,…,Oi,M×N｝.Assume that an Ms×Nssecret image S is to be shared among n shadow imagesof size M×N.Let S={sj| j=1,2,…,MS×NS}.

The proposed scheme consists of three phases:1)the preliminary phase,2)the secret image sharing phase,and 3)the secret image retrieving phase.

3.1 Preliminary Phase

In the proposed scheme,we utilize Sudoku to embed the secret image into n cover images.

Step 1.The dealer selects a Sudoku grid with size 16×16,and divides it into sixteen 4×4 blocks.The dealer fills these grids using the digits from 0 to 15.Fig.2 demonstrates an instance of a 16×16 Sudoku grid.

Step 2.The dealer transforms all pixels of the secret image into binary representation.For instance,if the pixel value of the secret image is sj=54,we obtain the binary representation as sj=(00110110).

Step 3.The dealer divides the binary representation of the pixel values of the secret image sjinto two equal portions.And then,the dealer transforms each portion into base-16 representation.For instance,if sj=(00110110),first,we divide the sjinto two equal portions,such as sj=(0011||0110),sj1=(0011),and sj2=(0110).Then,we obtain sj1=(3)16and sj2=(6)16,and sjcan be represented as sj=(3||6)16.Then,S={ sj| j=1,2,…,MS×NS}can be transformed into a base-16 digits stream,i.e.,S={ s′j| j=1,2,…,2 ×MS×NS} where s′jdenotes base-16 numeral system digits.

Fig.2.Instance of 16×16 Sudoku grid using the digits from 0 to 15.

3.2 Secret Image Sharing Phase

Without loss of generality,assume that we want to embed a base-16 digit streaminto n different cover images to generate n shadow images.The dealer performs the following steps.

Step 1.First,the dealer constructs a matrix M with the size of 256×256 consisting of Sudoku grids with the size 16×16,as shown in Fig.2.Fig.3 shows an instance of a 256×256 matrix M.

Step 3.We can obtain the value m of the Sudoku digit by mapping the row Oiaand column Oibat the matrix M.In the proposed scheme,we denote C as the mapping function from the pixel pair （Oia,Oib） to a Sudoku digit.

Then,we select a Sudoku digit m′ that is equal toand for which the Euclidean distance between the Sudoku digit m′ and m is the shortest.

Step 4.We define the function C-1as

From the located Sudoku digit m′,we can obtain a new embedded pairby using the mapping function C-1.Then,the corresponding pixel pair of the shadow image is.

Fig.4 illustrates an example of the camouflage process.Assume that the pixel pair of the cover image （Oia,Oib）is(10,6)and that.We can obtain a base-16 digit 12 by mapping 12=C(10,6).We locate this point in this Sudoku grid and then we can find a Sudoku digit m′ that is equal to 10 and for which the distance between the digit 12 and the Sudoku digit m′ is the shortest.We can obtain a new pixel pair for the shadow image by mapping(11,5)=C-1(m′).

Fig.3.Instance of 256×256 matrix M.

Fig.4.Instance of camouflage results.

Step 6.Repeat the above steps until all pixel values of the secret image are camouflaged.

3.3 Secret Image Retrieving Phase

In the proposed(n,n)secret image sharing scheme,given n shadow images,the shared secret image can be reconstructed losslessly.We must retrieve the base-16 digits from all shadow images.The details are as follows.

Step 1.First,we obtain the first pixel pairfrom the first shadow imageand compute a Sudoku digit s11by mapping s11=C(O11′,O11′).Then,we compute s12from the second shadow image O2′ by mapping

Step 2.We transform s11and s12into their binary representations and merge them into a binary number.Then,we transform this binary number into base-10 representation.The obtained number is the first pixel value of the secret image.

Step 3.Repeat the above steps until all pixel values of the secret image are extracted.

4.Experimental Results and Analysis

In this section,we present the results of some experiments that were conducted to evaluate the performance of the proposed(n,n)secret image sharing scheme.Herein,we set the system parameter as n = 2.

4.1 Simulation Results

We used 15 grayscale images with size of 512×512 pixels as the test images,as shown in Fig.5.Fig.6 shows the two secret images with 256×256 pixels and 512×256 pixels,respectively.To estimate the visual quality of the shadow images,the peak signal-to-noise ratio(PSNR)was used:

The mean square error(MSE)between the cover image with M×N pixels and the shadow image is defined as

where Oi,jis the pixel value of the ith cover image,andis the pixel value of the corresponding shadow image.

Fig.5.Test images(512×512):(a)Airplane,(b)Cameraman,(c)Clown,(d)Couple,(e)Elaine,(f)Goldhill,(g)House,(h)Lena,(i)Mandrill,(j)Peppers,(k)Sailboat,(l)Splash,(m)Tiffany,(n)Toys,and(o)Zelda.

Fig.6.Secret images.

Table 1:PSNR of the shadow images of(2,2)secret sharing scheme for various images(capacity=256×256×8 bits)

Table 1 lists the visual qualities of the shadow images with various test images and the 256×256 pixels secret image using the(2,2)secret image sharing scheme.It is clear that,regardless of what we use as the cover images,the PSNR values of the shadow images remain satisfactory.

Table 2 displays the visual qualities of the shadow images with various test images.Since more secret bits are embedded into the cover images,the PSNR values of the shadow images are slightly lower than those of the last experiment.However,it is obvious that when we embedded the secret image with size of 512×256 pixels,the PSNR values of the shadow images were still satisfactory.

In order to demonstrate the visual perception of the shadow images,we utilized ‘Lena and House’ as the cover images.Fig.7(a)to Fig.7(d)show the cover images and the shadow images,and Fig.7(e)shows the reconstructed secret image with 256×256 pixels.We can see that the distortions are slight,and it is difficult to distinguish between the cover images and the shadow images.

Table 2:PSNR of the shadow images of(2,2)secret sharing scheme for various images(capacity=512×256×8 bits)

Fig.8 shows the case in which we embedded the secret image with 512×256 pixels into the cover images ‘Lena’and ‘House’.Judging from the visual perception of these two shadow images and the two cover images,our scheme can successfully camouflage shadow images.

Fig.7.Results of Lena and House as cover images for 256×256 sized secret image:(a)original cover image 1,(b)original cover image 2(c)shadow image1,PSNR= 48.80 dB,(d)shadow image 2,PSNR= 48.85 dB,and(e)extracted secret image.

Fig.8.Results of Lena and House as cover images for 512×256 pixels sized secret image:(a)original cover image 1,(b)original cover image 2,(c)shadow image 1,PSNR= 45.84 dB,(d)shadow image 2,PSNR= 45.84 dB,and(e)extracted secret image.

Fig.9.Secret capacity (n×H ×W)/4(pixels)with different n,where H=512,W=512 in this figure.

Fig.10.Shadow image quality obtained by sharing 256×256 sized secret image with different test images.

4.2 Discussion

In this section,we address embedding capacity and compare the visual quality of the shadow images of our scheme with those of related works[10]–[12],[19].

In a secret image sharing scheme,an embedding capacity is an important consideration.According to the embedding mechanism of the proposed scheme,the embedding capacity is proportional to the increase of n.Fig.9 compares the capacity of the embedded data for [10]–[12],[19]with that of our scheme for n=2,3,…,16.It is clear that the proposed scheme has a larger embedding capacity than the related schemes.

Fig.10 compares the PSNR values of the shadow images of our proposed(n,n)secret image sharing scheme with those of related works.The figure shows that our proposed scheme results in better visual quality than other schemes[10]–[12],[19].

5.Conclusions

In this paper,based on Sudoku,we propose a novel(n,n)secret image sharing scheme.We extended Chang et al.’s(t,n)secret image sharing scheme,in which only one cover image can be used to camouflage the secret image.In our scheme,we can generate n shadow images by embedding the secret image into n different cover images.Given only these n shadow images,the secret image can be reconstructed losslessly.The experimental results demonstrated that the proposed scheme offers a large embedding capacity compared with related secret image sharing schemes,and the visual quality of the shadow images is satisfactory.

[1]A.Shamir,“How to share a secret,” Communications of the ACM,vol.22,no.11,pp.612–613,1979.

[2]G.Blakley,“Safeguarding cryptographic keys,” in Proc.of the National Computer Conf.,Montvale,1979,pp.313–317.

[3]N.Noar and A.Shamir,“Visual cryptography,” in Proc.of Eurocrypt'94,Perugia,1995,pp.1–12.

[4]C.-C.Thien and J.-C.Lin,“Secret image sharing,”Computers & Graphics,vol.26,no.5,pp.765–770,2002.

[5]C.-N.Yang,“New visual secret sharing schemes using probabilistic method,” Pattern Recognition Letters,vol.25,no.4,pp.481–494,2004.

[6]R.-Z.Wang and C.-H.Su,“Secret image sharing with smaller shadow images,” Pattern Recognition Letters,vol.27,no.6,pp.551–555,2006.

[7]D.Wang,L.Zhang,N.Ma,and X.Li,“Two secret sharing schemes based on Boolean operations,” Pattern Recognition,vol.40,no.10,pp.2776–2785,2007.

[8]C.-C.Chang,C.-C.Lin,T.H.N.Le,and H.-B.Le,“Sharing a verifiable secret image using two shadows,” Pattern Recognition,vol.42,no.11,pp.3097–3114,2009.

[9]C.-C.Thien and J.-C.Lin,“An image-sharing method with user-friendly shadow images,” IEEE Trans.on Circuits and Systems for Video Technology,vol.13,no.12,pp.1161–1169,2003.

[10]C.Lin and W.Tsai,“Secret image sharing with steganography and authentication,” The Journal of Systems and Software,vol.73,no.3,pp.405–414,2004.

[11]C.-N.Yang,T.-S.Chen,K.-H.Yu,and C.-C.Wang,“Improvements of image sharing with steganography and authentication,” The Journal of Systems and Software,vol.80,no.7,pp.1070–1076,2007.

[12]C.-C.Chang,Y.-P.Hsieh,and C.-H.Lin,“Sharing secrets in stego images with authentication,” Pattern Recognition,vol.41,no.10,pp.3130–3137,2008.

[13]P.-Y.Lin,J.-S.Lee,and C.-C.Chang,“Distortion-free secret image sharing mechanism using modulus operator,” Pattern Recognition,vol.42,no.5,pp.886–895,2009.

[14]P.-Y.Lin and C.-S.Chan,“Invertible secret image sharing with steganography,” Pattern Recognition Letters,vol.31,no.13,pp.1887–1893,2010.

[15]C.-S.Tsai,C.-C.Chang,and T.-S.Chen,“Sharing multiple secrets in digital images,” The Journal of Systems and Software,vol.64,no.2,pp.163–170,2002.

[16]J.-B.Feng,H.-C.Wu,and C.-S.Tsai,“A new multi-secret images sharing scheme using Largrange’s interpolation,”The Journal of Systems and Software,vol.76,no.3,pp.327–359,2005.

[17]Z.Eslami,S.H.Razzaghi,and J.Z.Ahmadabadi,“Secret image sharing based on cellular automata and steganography,” Pattern Recognition,vol.43,no.1,pp.397–404,2010.

[18]Z.Eslami and J.Z.Ahmadabadi,“Secret image sharing with authentication-chaining and dynamic embedding,” The Journal of Systems and Software,vol.84,no.5,pp.803–809,2011.

[19]C.-C.Chang,P.-Y.Lin,Z.-H.Wang,and M.-C.Li,“A Sudoku-based secret image sharing scheme with reversibility,” Journal of Communications,vol.5,no.1,pp.5–12,2010.

[20]B.Felgenhauer and F.Jarvis,“Mathematics of Sudoku,”Mathematical Spectrum,vol.39,no.1,pp.15–22,2006.

[21]C.-C.Chang,Y.-C.Chou,and T.-D.Kieu,“An information hiding scheme using Sudoku,” in Proc.of the 3rd Int.Conf.on Innovative Computing Information and Control,Dalian,2008,pp.17–21.

[22]W.Hong,T.-S.Chen,and C.-W.Shiu,“Steganography using Sudoku revisited,” in Proc.of the Second Int.Symposium on Intelligent Information Technology Application,Shanghai,2008,pp.935–939.

[23]C.-C.Chang,Y.-C.Chou,and T.-D.Kieu,“Embedding data and sharing original image in two stego images using Sudoku,” in Proc.of the 2010 IET Int.Conf.on Frontier Computing,Theory,Technologies and Applications,Taichung,2010,pp.163–168.