Magic sheets:Visual cryptography with common shares

Naoki KitaKazunori Miyata

Abstract Visual cryptography(VC)is an encryption technique for hiding a secret image in distributed and shared images(referred to as shares).VC schemes are employed to encrypt multiple images as meaningless,noisy patterns or meaningful images.However,decrypting multiple secret images using a unique share is difficult with traditional VC.We propose an approach to hide multiple images in meaningful shares.We can decrypt multiple images simultaneously using a common share,which we refer to as a magic sheet. The magic sheet decrypts multiple secret images depending on a given share.The shares are printed on transparencies,and decryption is performed by physically superimposing the transparencies.We evaluate the proposed method using binary,grayscale,and color images.

Keywords visual cryptography(VC);information hiding;secret sharing

1 Introduction

Visual cryptography(VC)is a secret sharing scheme in which secrets are hidden in distributed and shared images. The secrets can be decrypted successfully if shared images(hereafter calledshares)printed on transparencies are stacked(superimposed).Decryption can be performed by the human visual system:computational resources are not required for decryption. VC applications include secret message sharing,authentication and identification,and watermarking.To encrypt secrets securely,the secrets should be split and embedded into shares with high quality images.VC has been studied extensively by the cryptography community,as well as computer vision and computer graphics communities.

In computer graphics,various approaches have been investigated for hiding images in a surface or display.In such approaches,a different image is displayed on the surface depending on the viewer’s perspective,or lighting conditions.Here the surface displays the hidden image itself or projects it onto a wall from an unstructured meaningless pattern or a different image shown on the surface.Such surprising behavior evokes a sense of wonder;therefore,the technique can be used in various entertainment applications.This is also true for a VC scheme(VCS).In other words,although VC is essentially a cryptography or steganography method,it can also be used in entertainment applications.

We propose an approach we callmagic sheets,an approach to hiding multiple images in sheets.The proposed method is based on a(k,n)-VCS,where a secret can be decrypted by stacking anykout ofnimages,whereas anyk?1 or fewer images cannot decrypt the secret successfully.In traditional(k,n)-VCS the shares are meaningless,noise-like images.In extended(k,n)-VCS((k,n)-EVCS),shares are composed of meaningful images.Magic sheetstakes three share images{I1,Ic,I2}and two secret images{IS1,IS2}as input and computes three output share images{S1,Sc,S2}such thatIS1andIS2can be decrypted by stackingS1andScandScandS2,respectively.This is similar to a(2,2)-EVCS.However,in the proposed approach,the shareScis acommon shareused to decrypt either of two secrets,which differentiates our approach from conventional EVCS(see Fig.1).

By printing the output shares on transparencies,we can physically decrypt secret images.This can be applied for various recreational purposes,such as cooperative games,in which a player with a share looks for a player with the other share to reveal secrets.

The primary contributions of this study are as follows:

?an EVCS that uses a unique common share to decrypt multiple secret images by employing a bitwise AND-like operation;

?a demonstration of the effectiveness of the proposed method using binary,grayscale,and color images;

?a demonstration of decryption by superimposing shares printed on transparencies.

Our aim is applications of VCS for entertainment purposes,i.e.,hiding and revealing images to evoke a sense of wonder.We do not focus on theoretical aspects,such as giving a security analysis of the proposed method.

In the next section,we brie fly review VC methods and methods for hiding multiple images.

Fig.1 Left:example of basic(2,2)-VCS.Middle:example of(2,2)-EVCS.Right:proposed EVCS with common shares.The share images(top row)are stacked(physically superimposed)to decrypt the secret images(bottom row).The proposed method can decrypt multiple images using a common share.Input images are 200×200 pixels and output images are 400×400 pixels.

2 Related work

2.1 Visual cryptography

VC was first proposed by Naor and Shamir[1].VC is a secret sharing scheme[2]in which a secret is encrypted,shared,and decrypted by participants.Encryption and decryption are performed by a computer.Alternatively,in some VCSs,the human visual system is used to decrypt the encrypted secret.Typically,VC schemes require complex computations.In other words,with such schemes,the human eyes can decrypt secrets easily where decryption would be difficult for a computer.In typical secret sharing schemes,the secret is either numbers or text,and in VCSs,the secret is an image.

In traditional VCSs,the inputs are binary images.However,methods that use grayscale or color input images have also been developed[3].In addition,more sophisticated approaches[4–6]that improve the visual quality of shares have been proposed.The traditional VCS,which encrypts only a single image,has been extended to handle multiple secrets using two circle shares and different rotation angles[7].Universal sharescan decrypt multiple images using a unique share[8,9].Among the various approaches,methods that employuniversal shares[8,9]are most closely related to our proposed approach:ourcommon shareis a type ofuniversal share. A comprehensive review of VCSs can be found in the literature[10].

Such previous methods have limitations:they generate meaningless shares and are based on Boolean operations,such as exclusive or(XOR)and bit shift operations,making it difficult to decrypt secrets physically.In contrast,the proposed method can encrypt multiple secrets in meaningful,physically realizable shares,because it is based on the physical superimposition of shares printed on transparencies,which corresponds to an AND operation.

2.2 Hiding multiple images

Recently,various approaches have been proposed to hide visual information in 2D images or 3D objects.Mitra and Pauly[11]proposedshadow art,which casts multiple images of a sculpture onto walls.Baran et al.[12]proposed layered attenuators that cast different colored shadow images under specific lighting conditions.Alexa and Matusik[13]proposed a method to create relief surfaces whose diffuse re flection approximates given images under known directional illumination.ShadowPixare surfaces that display multiple images using self-shadowing[14].Inemerging images[15]andcamou flage images[16],one or more figures are embedded into a busy apparent background and remain imperceptible.Papas et al.[17]proposed themagic lens,a passive display device that exposes hidden messages and images from seemingly random and structured source images.Other interesting approaches to hiding images have also been proposed,e.g.,hiding patterns on a metallic substrate[18]and on a level line Moir[19].

In most approaches,fabrication costs are significant because a high-resolution 3D printer or milling machine is required.In contrast,images produced by ourmagic sheetsmethod can be printed on inexpensive transparencies using consumer-grade printers.

3 Background

In this section,we brie fly describe the traditional(k,n)-VCS and the(k,n)-EVCS for binary,grayscale,and color images.

3.1 (k,n)-VCS

In(k,n)-VCS,a secret image is decomposed intonshares.The secret is decrypted by the human visual system ifkout ofnimages are physically superimposed;however,anyk?1 or fewer out of thenimages cannot decrypt the secret and there is no information leakage[1].Meaningless random dot patterns are used as shares in the traditional(k,n)-VCS.

Meaningless shares in the traditional(k,n)-VCS can be extended to meaningful images.Note that we can construct a(k,n)-EVCS using meaningful shares.Traditional schemes are only used for binary images,while grayscale images can be converted to binary images by halftoning.In addition,many color VCSs have been proposed.By employing a subtractive color model,such as the CMY model,a color image can be decomposed into CMY images and the traditional EVCS can be applied to each C-,M-,or Y-channel image.The individual channel images are then merged into a single color image.The resulting shares are not of high quality,and more sophisticated approaches are available[5].Developing color EVCSs remains a challenging problem[10].

3.2 Pixel representation

Here,we describe pixel(block)representations in a VCS with a focus on the(2,2)-VCS.Each of the following patterns is used to represent a white or black pixel in the output share images.

3.3 Example

Construction of a(2,2)-VCS is described in Table 1.

4 EVCS with common share

4.1 Preliminaries

In the proposed method,we use acommon shareto decrypt multiple(2,2)-EVCS images.One secret is decrypted by superimposing one share and the common share,and the other secret is decrypted by superimposing the other share and the common share.In this section,we describe the proposed EVCS with the common share approach.

Table 1 Construction of(2,2)-VCS.An input white or black pixel p in a share image I1 or I2 is enco′ded as a block p′composed of 2×2 subpixels.The stacked result S S p representing a pixel color in a secret

Table 1 Construction of(2,2)-VCS.An input white or black pixel p in a share image I1 or I2 is enco′ded as a block p′composed of 2×2 subpixels.The stacked result S S p representing a pixel color in a secret

p Input I1 White Black White Black I p S=White Output S p′1Input I p2 White White Black Black Output S p′2Stacked:S p′S=S p′1 ?S p′2Input I p1 White White Black Black Output S p′I p S=Black1Input I p2 White Black White Black Output S p′2Stacked:S p′S=S p′1 ?S p′2

4.2 Share combinations

First,we compute all possible share combinations.We represent a share combination in the following tabular form:

Here,the notation is the same as in Section 3.The top row represents a share combination comprising subpixelsp′of shareS1,common shareSc,shareS2,secretSS1,and secretSS2(in that order).For

4.3 Algorithm

Our method is given in Algorithm 1.Given input images(shareI1,common shareIc,shareI2,secretIS1,and secretIS2),we assignwhiteorblackto the corresponding output share imagesS1,Sc,andS2,whereI1,Ic,andI2have the same width and height,andS1,Sc,andS2have twice the width and height of the input.We simply apply the algorithm directly if the inputs are binary images.If the inputs are grayscale images,we first apply halftoning using Ostromoukhov’s error diffusion algorithm[20]to convert the images to binary images.We describe how to extend the method to color input images in Section 4.5.

To assignwhiteorblackto the output images,we obtainwhiteorblackcolors from the input images.Since the output images are twice the size of the input images,an(x,y)pixel in an input image corresponds to an(x′,y′),2×2 pixel block in the output image.Then,a block color pattern is constructed from the input colors(see Algorithm 1,line 3).We select a valid combination randomly from the LUT by querying the pattern(line 4).Finally,thewhiteorblackblocks are assigned to each output image(lines 5–7).

Fig.2 Number of possible share combinations for each share pattern.A share pattern is represented by five 0 or 1 digits(0 and 1 indicating

Algorithm 1 EVCSWITHCOMMONSHARE 1:for y←0:height do 2: for x←0:width do 3: P←{I1(x,y),I c(x,y),I2(x,y),I S1(x,y),I S2(x,y)}4: C←RANDOMSELECT(LUT[P])5: for k∈{1,c,2}do 6: ASSIGNCOLOR(S k(x′,y′),C)7: end for 8: end for 9:end for 10:return S1,S c,S2

4.4 Share optimization

After computing EVCSWITHCOMMONSHARE,we improve the visual quality of the output shares by applying a share optimization algorithm[6].For each pixel block,we rearrange thewhiteandblackso that the resulting shares have better visual quality while the stacking results remain unchanged.The algorithm is described in detail in the Appendix.Results are shown in Fig.3.

4.5 Extension to color images

The method can be extended to a color EVCS.As described in Section 3,we decompose the given images into C-,M-,and Y-channel images.We then apply Ostromoukhov’s error diffusion method[20]to convert the images to halftone images.We have also tried using structure-aware error diffusion[21];but it did not show significant improvement.Therefore,we use Ostromoukhov’s method,which is simple and faster.Contrast-aware halftoning[22]or other stateof-the-art error diffusion approaches[23]could also be employed for faster and better image preparation.For color EVCS,although it is not obvious that the proposed method can be incorporated,we can improve the visual quality of the output shares using a more sophisticated approach[5].However,color EVCS remains a challenging and open problem[10].

5 Results

5.1 Outputs

We have applied the proposed method to binary,grayscale,and color images.Results for binary images are shown in Fig.1.Figures 3 and 4 show results for grayscale images,and Figs.5,6,and 7 show color EVCS results.

We generated output results and printed them on transparencies using a Canon ImageRUNNER ADVANCE C3330i printer(see Figs.6(bottom)and 8).To improve contrast,we printed each share on two transparencies and superimposed them.As shown in Figs.6(right)and 8,crosstalkis observable in the decrypted images due to the in fluence of the transmitted background light;however,the secret images are revealed successfully,and the secret text is readable.

5.2 Visual evaluation

Figure 3 compares the source input images and output images with and without optimization.As can be seen in the optimized Lena result,for example,optimization results in the structures being better preserved and textureless areas being smoother.Although the quality improvements are not always obvious,optimized results have higher quality both visually and in quantitative evaluations.

Fig.3 Results of our proposed EVCS.Input images are 512×512 pixels while outputs are 1024×1024 pixels.Top:unoptimized results.Middle:optimized results.Bottom:close-ups of unoptimized and optimized S1.

5.3 Numerical evaluation

We followed previous approaches to quantitatively evaluate our results[6,21,22,24].We computed the mean structural similarity index measure(MSSIM)[25]and the peak signal-to-noise ratio(PSNR)to compare the input and output images with and without optimization.We measured the average MSSIM and PSNR over 10 runs.The color results were converted to grayscale images for evaluation.

The MSSIM and PSNR results are shown in Tables 2 and 3,respectively.Since the algorithm outputs binary images,we first applied Gaussian bluring with a kernel size of 5×5 and compared the outputs to the input source images;the input source images were scaled to the same size as the output images.Generally,the results with optimization achieved higher MSSIM and PSNR values.

Fig.4 EVCS results for grayscale images.The original images are 1200×750 pixels.The input images are shown in Fig.11(bottom)in the Appendix.

Fig.5 Top:input images;original images are 463×680 pixels.Bottom:proposed color EVCS results;the two portraits on the right are the computed superimposition results of a common share and the corresponding share.

Fig.6 Top:computed color EVCS results.Original images are 480×360 pixels.Bottom:output shares printed on transparencies.The two sheets on the right are the superimposition results of a common share and the corresponding share on the left.Input images are given in Fig.11(top)in the Appendix.

Although both MSSIM and PSNR values were higher after optimization,in the case shown in Fig.1(binary image)in Tables 2 and 3,the visual quality was worse,due to information leakage,as can be seen in Fig.9:there is a tradeoffbetween visual quality and MSSIM and PSNR values.Such visual artifacts resulting from the optimization procedure were only observed for binary images;optimized grayscale and color images did not demonstrate such artifacts.This is because,in the binary case,the content of the images has no textures in these images consisting of black and white regions with boundaries.Therefore,in a share image,boundaries from the other image are noticeable in the textureless regions in the optimized share images.In contrast,we did not notice such information leakage in the optimized share images in grayscale and color image results(see Figs.4 and 7)because these images have textures and a more busy appearance than the binary images.

Fig.7 EVCS results for color images.The original images are 1200×750 pixels.The input images are shown in Fig.11(bottom)in the Appendix.

Fig.8 Output shares printed on transparencies.

Table 2 MSSIM for original input shares and output shares with and without optimization.We applied Gaussian bluring with a kernel size of 5×5 to the output images and compared them to the source images

Table 3 PSNR for original input shares and output shares with and without optimization.We applied Gaussian bluring with a kernel size of 5×5 to the output images and compared them to the source images

However,as optimization is an optional process,we can simply omit this procedure when applying the proposed method to binary images,and only use optimization to improve visual quality for grayscale and color images. To improve optimization,a different objective function could be introduced in place of the current mean-squared-error and MSSIM-based function(see Eq.(1)in the Appendix).

Fig.9 Information leakage in images after applying optimization to output shares for binary input images(see Fig.1(right)).

5.4 Speed

We measured computation time on an Intel Core i5,2.9 GHz personal computer with 16 GB RAM.We implemented our algorithms in C++using OpenCV.Computation of all possible share combinations to prepare the look-up table(LUT)(see Section 4)took approximately 0.5 ms.Table 4 summarizes the computation time for the EVCSWITHCOMMONSHARE procedure with and without optimization.As can be seen,the optimization process is computationally expensive as calculating the MSSIM for each loop is computationally expensive;it may not be worth the cost.

Rather than using MSSIM,we could use another structural similarity measure;doing so will be the focus of future work.For color images,we simply compute EVCSWITHCOMMONSHARE for each CMY channel for color images,which can be parallelized,or we could employ a more sophisticated approach for a color EVCS.

Table 4 Time taken for EVCSWITHCOMMONSHARE with and without optimization

5.5 (2,n)-EVCS

In Section 4,we described the proposed method for the(k,n)-EVCS wherek=2 andn=2.Due to its simplicity and scalability,it is straightforward to extend the proposed method to greaternvalues.Results of a(2,4)-EVCS and a(2,5)-EVCS computed by the proposed method are shown in Fig.10.

6 Conclusions

We have presentedmagic sheets,a VCS that uses common shares(a type of universal share).With the common shares,we can decrypt multiple secrets simultaneously depending on a given share.Magic sheetshides secret images in meaningful shares and can be applied to binary,grayscale,and color images.Since the proposed method is based on a bitwise AND-like operation,we can physically realize shares on transparencies and retrieve secrets by superimposing these shares.

7 Future work

In this study,we applied the proposed method to a pair of(2,2)-EVCSs for both grayscale and color images,and we demonstrated a(2,n)-EVCS,wheren＞2.The proposed method can also be applied to pairs of general(k,n)-EVCSs.Although we employed 2×2 pixel expansion in the proposed method,it would be interesting to investigate an algorithm with no pixel expansion to achieve higher contrast while maintaining visual quality.In addition,the proposed method employs a simple optimization algorithm to improve the visual quality of the output shares,and this algorithm requires significant time.In future,we will investigate a faster approach.

In the color EVCS,we can observe some information leakage in the result of stackingS1andS2,i.e.,S1?S2,in Fig.7.Currently we have focused on entertainment purposes of the proposed method,so did not focus on security aspects,but in future it is important to analyze such aspects quantitatively.

Appendix

Share optimization

We minimize the following objective function:

Fig.11 Top:input images for Fig.6.The original images are 240×180 pixels.Bottom:input images for Figs.4 and 7.The original images are 600×375 pixels.From left to right,share I1,common share I c,share I2,secret I S1,and secret I S2.

whereEsandEcare structure and coherence terms,respectively,defined as follows.

Here,pis the pixel location in inputIandp′is the corresponding block of subpixels in the output shareS.

Structure term

The structure termEscomprises a tone similarity term and a structure similarity term[6,24].Tone similarity is measured byG(Ipk,Sp′k),whereIpandSp′are a local region,which is one-half the size of the pixel expansion plus one-half the size of the Gaussian kernel.G(·,·)measures the mean-squared-error of the Gaussian-blurred input images.Here we use an 11×11 Gaussian kernel.We employ MSSIM[25]:

Coherence term

The coherence termEcsmooths noise in textureless areas[6].Here,pandqare pixel locations in the inputI,andp′andq′are the corresponding blocks of subpixels in the output shareS.N(p)is the set of eight connected neighbor pixels ofp.The exponential term is used to attenuate the energy as the difference betweenIpkandIqkincreases,whileβcontrols the attenuation rate(β=5).We useλ=0.01 to balance the structure and coherence terms inEtotal.

Procedure

The optimization procedure is given in Algorithm 2.We attempt to optimize the output image quality by rearrangingwhiteandblackpixels into blocks.To do so,we employ simulated annealing.The temperatureTis initialized toT0and is gradually reduced by cooling factorcuntilT＜Tend.Here,T0=0.2 andc=0.95.At the beginning of the loop,the new arrangement ofwhiteandblackpixels in a block has higher probability of being accepted as a new arrangement even if the arrangement results in worse quality.This is helpful for us because we attempt to minimize error in local blocks:measuring global error in each loop is computationally expensive.

Algorithm 2 Optimization procedure 1:T←T0 2:repeat 3: for all p∈I do 4: E old ← E(I p,S p′)5: C←RANDOMSELECT(LUT[SHARECOMB(p)])6: for k∈{1,c,2}do 7: REARRANGE(S p′k,C)8: end for 9: E new ← E(I p,S p′)10: ?E=E new?E old 11: Sample r∈[0,1]at random 12: if r＜exp(min(0,??E/T))then 13: E old←E new 14: else 15: Undo rearrange S p′k,?k∈{1,c,2}16: end if 17: end for 18: T←c×T 19:until T＜T end 20:return S1,S c,S2

For each loop,we select a rearrangement candidate from the look-up table(LUT).Since we have already computed the share combination ofpin the EVCSWITHCOMMONSHARE procedure,we can retrieve the combination using SHARECOMB(p),and this combination is used as an LUT query to obtain a new arrangement. We calculate an objective function(see Eq.(1))for each local regionIpand the corresponding blockSp′before and after rearrangingSp′.Acceptance or rejection follows typical simulated annealing techniques.

Acknowledgements

We thank all reviewers for their helpful comments.This work was supported by JSPS KAKENHI Grant Nos.17J04232 and 16K12433.