A New Visual Multi-Secrets Sharing Scheme by Random Grids

Abstract

In (2, 2)-visual secret sharing (VSS) schemes, a common type of (k, n)-threshold VSS schemes, secret information can be decoded directly through only two shares by using a human vision system. Several studies have analyzed methods of simplifying the decoding process and refining encoding to pass more secret images through two identical shares. However, limited secret images are retrieved, and the quality of the recovered images is low. This paper proposes an advanced (2, 2)-VSS scheme that can embed N secret images into two rectangular shares. Compared with other related VSS schemes, more secret images can be encrypted and the distortion is adjustable in the proposed scheme, yielding more flexibility in theory and practice.

1. Introduction

The rapid growth of network technology has enabled the convenient transmission of images through the Internet. However, under certain unknown conditions, images may be vulnerable to attacks. In recent years, image encryption has been an emergent topic. Traditional techniques of cryptography provide numerous means of protecting secret information, but most of these techniques incur additional cost in the decryption phase. However, to avoid the use of complex calculations for decrypting a message, a human vision system seems to the best solution, and visual secret sharing (VSS) is exactly such a scheme. The two main techniques to achieve VSS are random grid (RG) and visual cryptography (VC) approaches.

In 1987, the first concept of RG was proposed by Kafri and Keren [1]. Their method can encode a binary image into two RGs. Given a sufficient difference in light transmission between black and white pixels, secret information can be directly obtained through human vision systems. With this advantage, secret messages can be revealed simply by superimposing the two shares. Therefore, no computation cost is involved in decoding. In 1995, Noar and Shamir proposed a VC approach [2] that entails encrypting a secret image into n (≥ 2) share images. The secret image can be recovered by collecting more than k (≤ n) share images. This approach provides a general (k, n)-threshold VSS scheme. However, the approach is accompanied by problems of pixel expansion and the necessity of a codebook. Compared with VC, RG is the superior approach because it does not exhibit these two drawbacks of VC. In 2009, Shyu proposed RG-based VSS schemes for binary, gray-level, and color images [3]. Further research on VSS schemes has been presented extensively [4,5].

From the perspective of time cost, encoding more than one image at the same time can increase the time-cost efficiency. Several visual multi-secret sharing (VMSS) schemes have been discussed in the past few years. Studies [6,7,8,9,10,11,12] have demonstrated methods for encrypting several images simultaneously. In 2008, Chen et al. [6] proposed a VMSS scheme that involves using an RG to encrypt two secret images into two shares. In 2010, Chang et al. [7] proposed a method that entails using shifting RGs to embed two secret images; this method can reduce the distortion to 1/2p. An improved VMSS scheme proposed by Chen et al. [8] uses appropriate angles ($0°$,$90°,180°,\mathrm{and}270°$) to embed four secret images into two shares. In 2012, Chang and Juan [9] proposed extended VMSS schemes that have the property of adjustable distortion and can encrypt three secret images simultaneously. In 2014, Salehi and Balafar proposed several VMSS schemes using a cylindrical RG [10]. They provided two recovery operations, OR and XOR; the XOR operation yields a better restored quality than the OR operation does. However, the XOR operation requires more computation and cannot be used without a computer. By contrast, the OR operation does not require computation, and the secret image can be recovered by stacking two shares directly. Moreover, the distortions of their VMSS schemes are fixed according to the number of secret images. In 2015, Tsao et al. proposed another VMSS scheme for a general access structure [11]; this scheme can serve special cases such as (2, n), (n, n), and (k, n). They also outlined the method to extend the scheme for multiple secrets. In their scheme, multiple secrets can be encrypted into multiple shares. However, any two shares cannot recover two different secret images. Actually, suppose that a secret image cannot be encrypted into any individual share; their scheme can only encrypt one secret image for two participants (signifying that only two shares must be made). Accordingly, this scheme is identical to Kafri and Keren’s scheme [1] when encrypting one secret into two shares. In 2016, Reddy and Prasad proposed an efficient share generation method of multi-secret sharing schemes that provides a lossless recovery of multiple secrets [12]. However, their method uses the XOR operation, and the number of shares must be three times the number of secrets.

The aforementioned studies [6,7,8,9,10,11,12], have their own unique features, and we can observe that none of them can satisfactorily deal with the concerns of encoding of more than two secret images into two shares simultaneously while possessing adjustable distortion. In this paper, we provide a general shifting approach that can embed N (≥ 2) secret images simultaneously with adjustable distortion. The rest of this paper is organized as follows: The related works and our proposed scheme are presented in Section 2 and Section 3, respectively. The experimental results are presented in Section 4. Discussions and conclusions are presented in the last two sections.

2. Related Works

In 1987, Kafri and Keren [1] proposed the first concept of RG, in which each RG pixel is defined to be black or white, with 0 representing white and 1 representing black. The light transmittance of an image G (denoted as T(G)) is defined as the ratio of the number of white pixels to all pixels in the image. Through random processing, the light transmittance of each RG can be determined to be 1/2. That is, the number of black pixels in one RG is the same as the number of white pixels. Furthermore, three algorithms were proposed to encode a binary secret image G with size w × h (w pixels width and h pixels height) into two shares R₁ and R₂ in [1]. Because these algorithms are well established, we only demonstrate the following Algorithm 1 adopted in our main algorithm:

Algorithm 1. Encoding a binary secret image into two random grids (KK)

Input: The secret image S0 with size w × h pixels Output: The cipher shares G1 and G2  Generate an w × h random grid R1, where the light transmittance is 1/2  For (int i = 0; i < w; i++)   For (int j = 0; j < h; j ++)    If G(i, j) == 0     then R2(i, j) = random(0, 1);    else R2(i, j) = 1 − R1(i, j);  Return R1 and R2

After these two cipher shares are collected, restored images can be easily decoded by superimposing the two shares according to the stacking rules shown in

Table 1. Stacking rules of two pixels.

p1	p2	p1 ⊕ p2
0	0	0
0	1	1
1	0	1
1	1	1

. The stacking value of two pixels p₁ and p₂ is presented as p₁ ⊕ p₂, where ⊕ stands for the OR operation under Boolean law.

Next, to improve efficiency, VMSS schemes are commonly used. In 2010, Chang et al. [7] provided an approach that can embed two secret images into two shares and reduce the distortion to 1/2p, where p is a positive factor of w (can be determined by the user). Distortion is defined as the ratio of the number of pixels that are not considered during encryption to the number of all pixels in secret images. In the encryption phase, each image is subjected to the encryption process randomly; therefore, the distortion can be distributed over each restored image. Furthermore, the higher the value of p is, the lower the distortion becomes. Notably, users can choose a suitable value of p according to their requirements.

Salehi and Balafar [10] proposed a scheme that can encode multiple images into multiple shares at the same time. By using a concept similar to shifting an RG, we can rotate the shares cylindrically to restore all the secret messages. During the encryption of m secrets images, the first share is randomly generated. Then, a secret image is randomly selected for each pixel of the second share. The corresponding pixel in the first share and the selected secret image decide the value of this second share pixel. Thus, we can observe that only 1/m parts are to be encrypted for each secret image. Although Salehi and Balafar provided two recovery operations, OR and XOR, for their scheme, we consider only the OR operation in this paper because the calculation of OR corresponds to the procedure of VC and can recover the secret image with no extra computation apart from human vision. We compare our result with this scheme in Section 5.

3. Proposed Scheme

To encrypt N secret images simultaneously, we present three functions to develop our main algorithm, Algorithm 2. The main concept of our approach is as follows: First, we number all the secret images from 0 to N − 1 and then select a random pair in (0, 1), (1, 2), …, (N − 2, N − 1), (N − 1, 0). Next, we use the function f_p to pick up a pixel to be the basis of the encryption process. Subsequently, f_RG and f_ORG encode the corresponding pixels in the chosen pair. Finally, we repeat the same steps as mentioned previously until all the cipher pixels of two shares are generated. Accordingly, all the input secret images are evenly distributed into two shares, and the distortion is ((N − 2)p + 1)/Np. In VSS, secret images can be restored using the human vision system. Given two cipher shares G₁ and G₂, we can easily reconstruct all the images through Algorithm 3. Notably, during the practical execution of Algorithm 3, the share G₂ can be rolled into a cylinder instead of being divided or swapped. All the functions and algorithms are structured as follows. Our approach is relatively flexible because of its capacity to encode more secret images simultaneously and to achieve adjustable distortion.

Function 1. (fp)

Input: A secret image S with size w × h pixels Output: One pixel of the input secret image S(i, j)  i = random(0, w − 1);  j = random(0, h − 1);  Return S(i, j)

Function 2. (fRG)

Input: The pixel of secret image S(i, j) Output: The pixels of shares G1(i, j) and G2(i, j)  G1(i, j) = random(0, 1);  If S(i, j) == 0   then G2(i, j) = random(0, 1);  else G2(i, j) = 1 − G1(i, j);  Return G1(i, j) and G2(i, j)

Function 3. (fORG)

Input: The pixel of secret image S(i, j) and the pixel of one share G1(i, j) Output: The pixels of the other share G2(i, j)  If S(i, j) == 0   then G2(i, j) = random(0, 1);  else G2(i, j) = 1 − G1(i, j);  Return G2(i, j)

Algorithm 2. Visual Multi-Secrets Sharing Scheme (VMSSS)

Input: The secret images S0, S1, …, SN−1 with size w × h pixels, and positive integer p Output: The cipher shares G1 and G2  Repeat   A = random(0, N − 1);   SA(i, j) ← fp(SA)   G1(i, j) and G2((i + A × w/p) mod w, j) ← fRG(SA(i, j));   For (int k = 0; k < p − 1; k++)    int A’ = (A + k + 1) mod p;    G2((i + A’ × w/p) mod w, j) ← fORG(SA+1((i + k × w/p) mod w, j),G1((i + k $\times$ w/p) mod w, j);    G1((i + (k + 1) × w/p) mod w, j) ← fORG(SA((I + (k + 1) × w/p) mod w, j),G2((i + A’ $\times$ w/p) mod w, j)  Until all the cipher-pixels of two cipher shares are generated

Algorithm 3. The inverse operation of VMSSS

Input: The two cipher shares G1 and G2 Output: The reconstructed secret images Ri for 0 ≤ i ≤ N − 1  First of all, divide G2 into two parts, the first i/p and the remaining part, according to the value of p.  Second, reshape G2 by swapping two parts.  Finally, superimpose G1 and G2 to decode the secret image Ri.

4. Experimental Results

We designed five experiments to demonstrate our scheme through simulations. Experiment 1 entailed encoding four secret images, and Experiment 2 involved encrypting five secret images. In Experiments 3–5, six input secret images were encoded into two shares by using Algorithm VMSSS. All the input secret images measured 540 × 540 pixels, see Figure 1.

Experiment 1.

Encoding four secret images into two shares by using Algorithm VMSSS.

In this experiment, we set the value of p to 10. In the decryption phase, the first restored image was obtained by stacking two shares together. The second, third, and fourth restored image were decoded using the reshaped G₂ described in Algorithm 3 with G₁. Figure 2a–d shows the decoded input secret images, and Figure 2e,f shows the two cipher shares.

Experiment 2.

Encoding five secret images into two shares by using Algorithm VMSSS.

Figure 3a–g illustrates the implementation results of the Algorithm VMSSS, where the parameter p was set to 9. Through decryption, the second, third, fourth, and fifth secret images could be reconstructed by superimposing G₂ with horizontally shifting 1/9, 2/9, 3/9, and 4/9 (×540 pixels), respectively, to the left and G₁. Additionally, stacking two shares G₁ and G₂ together could restore the first input image.

Experiments 3–5.

Encoding six secret images into two shares by using Algorithm VMSSS.

In these three experiments, we used six secret images to conduct the simulations. In particular, the set values of p in Experiments 3, 4, and 5 were 9, 18, and 27, respectively. These values were set to study the influence of p on the quality of the restored images. The results of the three experiments are presented in Figure 4, Figure 5 and Figure 6. Similarly, all of the secret images could be easily restored through the steps described in Algorithm 3.

5. Discussion

From the five experiments presented in Section 4, we observed that the original secret could be identified from the recovered image. None of the shares generated using Algorithm VMSSS revealed any secret information about the input images. Among the schemes discussed in Section 1, those proposed by Chang et al. [7,9] are equipped with adjustable distortion but cannot encrypt more secret images compared with our scheme. The approach proposed in [8] can embed four secret images simultaneously, but it cannot increase the number of input images. Salehi and Balafar [10] presented two operations (XOR and OR) for recovery. Notably, the XOR operation is an indirect method for restoring images, whereas the OR operation can recover secret images by printing two shares on a transparency and stacking them together directly. Nevertheless, for the OR operation (i.e., the direct method for recovery) presented in [10], the quality of the restored images is relatively poor. The restored quality of images is unsatisfactory through the direct method for recovery in [10] (OR operation). The VMSS scheme proposed in [11] can prevent the extraction of secret images by stacking some specific shares. However, any two shares cannot recover two different secret images. Moreover, that scheme cannot encrypt more than one secret image into two shares. The XOR operation recovery used in [12] indicates only the indirect method of decoding. Furthermore, the ratio of the number of shares to the number of secret images must be fixed at 3. Therefore, regarding the number of secret images, the number of shares, quality adjustable, and any rectangle secret images, our method was determined to demonstrate excellent performance, see

Table 2. Comparison among related schemes.

Scheme	Number of Secret Images	Number of Shares	Quality Adjustable	Any Rectangle Secret Images	Direct Recovery Operation
The proposed scheme	s ≥ 2	2	Yes	Yes	Yes
Reddy et al., 2016 [12]	s ≥ 2	3s	No	Yes	No
Tsao et al., 2015 [11]	2n − n − 1 ≥ s ≥ 1	n	No	Yes	Yes
Salehi et al., 2014 [10]	s ≥ 2	n	No	Yes	Yes/No
Chang et al., 2012 [9]	3	2	Yes	Yes	Yes
Chen et al., 2012 [8]	4	2	No	No	Yes
Chang et al., 2010 [7]	2	2	Yes	Yes	Yes
Chen et al., 2008 [6]	2	2	No	No	Yes

. The visual analysis and security analysis of our scheme are explained in Section 5.1 and Section 5.2, respectively.

5.1. Visual Analysis

For high-capacity use, the quality of restored images and the security of the encryption scheme are critical. Let T(G[X₀]) be the average transmittance of the area in an image G, which corresponds to the white area in image X, and T(G[X₁]) be the average transmittance of the area in an image G, which corresponds to the black area of image X. Through the design of function f_RG, the probability of displaying black and white pixels can be determined to be 1/2. This signifies that the average light transmittance levels of white and black pixels contributed by every secret image in each share are equal, thus preventing the revelation of any secret message in the two cipher shares. As discussed in Section 3, all secret images are classified into N pairs, where N is the number of the input secret images, and the encryption process is divided into p parts, where p is a positive factor of w (image width). With this design of the main algorithm, the average light transmittance of white and black pixels in each restored image can be calculated as follows: Let T(R[S_i,0]) and T(R[S_i,1]) be the average light transmittance of the areas in the restored image R, which correspond to the white and black areas, respectively, of the secret image S_i, for 0 ≤ i ≤ N − 1.

$$T\left(R\left[S_{i,1}\right]\right)=\frac{1}{N}\times 0+\frac{1}{N}\times \left(\frac{p-1}{p}\times 0+\frac{1}{p}\times \frac{1}{4}\right)+\frac{N-2}{N}\times \frac{1}{4}=\frac{\left(N-2\right)p+1}{4Np}$$

$$T\left(R\left[S_{i, 0}\right]\right)=\frac{1}{N}\times \frac{1}{2}+\frac{1}{N}\times \left(\frac{p-1}{p}\times \frac{1}{2}+\frac{1}{p}\times \frac{1}{4}\right)+\frac{N-2}{N}\times \frac{1}{4}=\frac{\left(N-2\right)p+4p-1}{4Np}$$

As discussed in [3], $T\left(R\left[S_{i,0}\right]\right)>T\left(R\left[S_{i, 1}\right]\right)$, where p ≥ 1; therefore, the areas of white and black pixels in each secret image can be visually distinguished (or the information of secret images can be observed) from the restored image R. Additionally, if the reconstructed image is recognizable as the input secret image, then the contrast (denoted by σ) should be higher than 0, as presented in [11]. In our scheme, the contrast of each share can be computed as follows:

$$\sigma =\frac{T\left(R\left[S_{i,0}\right]\right)-T\left(R\left[S_{i,1}\right]\right)}{1+T\left(R\left[S_{i,1}\right]\right)}=\frac{4p-2}{4Np+Np-2p+1}=\frac{2\left(2p-1\right)}{5Np-2p+1}=\frac{2\left(2p-1\right)}{\left(5N-2\right)p+1}$$

The boundary conditions N ≥ 2 and p ≥ 1 can be used to ensure that σ > 0. Therefore, all the reconstructed images can have sufficient contrast to be recognized as the input images, and the two shares generated through our scheme would not disclose any secret message.

Our scheme can now be compared with the scheme proposed by Salehi and Balafar [10] for encrypting N images into two shares. The average light transmittance of their scheme, T_SB(R[S_i,0]) and T_SB(R[S_i,1]), of the areas in the restored image R, which correspond to the white and black areas, respectively, in the secret image S_i, for 0 ≤ i ≤ N − 1, can be calculated as follows:

$$T_{\mathrm{SB}}\left(R\left[S_{i,1}\right]\right)=\frac{1}{N}\times 0+\frac{N-1}{N}\times \frac{1}{4}=\frac{N-1}{4N}$$

$$T_{\mathrm{SB}}\left(R\left[S_{i, 0}\right]\right)=\frac{1}{N}\times \frac{1}{2}+\frac{N-1}{N}\times \frac{1}{4}=\frac{N+1}{4N}$$

Therefore, the contrast of each share can be computed as follows:

$${\sigma }_{\mathrm{SB}}=\frac{T_{\mathrm{SB}}\left(R\left[S_{i,0}\right]\right)-T_{\mathrm{SB}}\left(R\left[S_{i,1}\right]\right)}{1+T_{\mathrm{SB}}\left(R\left[S_{i,1}\right]\right)}=\frac{\left(N+1\right)-\left(N-1\right)}{4N+\left(N-1\right)}=\frac{2}{5N-1}$$

Because 4 − 2/p ≥ 2 and 5N − (2 − 1/p) ≤ 5N − 1 for p ≥ 1, the contrast generated by our scheme is always higher than generated by the scheme of Salehi and Balafar [10]. This proves the performance levels of our scheme to be higher than those of the scheme presented in [10] for identical conditions (number of secret images and shares and recovery of secret images by staking the shares directly).

5.2. Security Analysis

A correlation test was used to evaluate the security of our proposed scheme. This test has been widely used in secret image sharing [4,5]. Through this test, we could clearly determine whether high correlations exist among pixels in each share in our proposed scheme. Usually, four types of correlations in input secret images and shares are computed: The correlations between two horizontally adjacent pixels, two vertically adjacent pixels, two diagonally adjacent pixels, and two vice-diagonally adjacent pixels. The correlation coefficient of two adjacent pixels R(x, y) can be obtained using the following formula, where x and y are the values of two adjacent pixels in one image and w × h is the number of the pair of two adjacent pixels:

$$R\left(x,y\right)=\frac{S_{xy}}{S_x\times S_y}, S_{xy}=\frac{1}{w\times h}{\displaystyle \sum }_{i=1}^{w\times h}\left(x_i-E\left(x\right)\right)\times \left(y_i-E\left(y\right)\right)$$

$$S_x=\sqrt{\frac{1}{w\times h}{\displaystyle \sum }_{i=1}^{w\times h}{\left(x_i-E\left(x\right)\right)}^2},E\left(x\right)=\frac{1}{w\times h}{\displaystyle \sum }_{i=1}^{w\times h}{x}_i$$

$$S_y=\sqrt{\frac{1}{w\times h}{\displaystyle \sum }_{i=1}^{w\times h}{\left(y_i-E\left(y\right)\right)}^2},E\left(y\right)=\frac{1}{w\times h}{\displaystyle \sum }_{i=1}^{w\times h}{y}_i$$

The correlation test involved 540 × 539 (or 539 × 539) pairs of two neighboring pixels (including two horizontally adjacent pixels, two vertically adjacent pixels, two adjacent diagonal pixels, and two vice-diagonal adjacent pixels). For the first experiment stated in Section 4, four images were encoded into two shares, with p being set to 10, and the correlation coefficients are presented in

Table 3. The correlation coefficients of two adjacent pixels in Experiment 1.

p	Image	Horizontal	Vertical	Diagonal	Vice-Diagonal
-	Secret image S0	0.98295	0.98462	0.96997	0.97720
	Secret image S1	0.98522	0.98563	0.97789	0.97012
	Secret image S2	0.99021	0.98745	0.97654	0.96665
	Secret image S3	0.99127	0.99042	0.96134	0.96522
p = 10	Share image G1	0.00103	0.00325	0.00069	0.00106
	Share image G2	0.00073	0.00045	−0.00131	0.00156

.

As shown in Table 3, the correlation coefficients of the two shares were nearly 0 (irrespective of whether the value was negative or positive), indicating that all the pixels in each share were weakly correlated. Therefore, the shares can be viewed as random shares. As shown by the results, no sufficient information of the input image was revealed from each share. Correlation test results from Experiments 3–5 are presented in

Table 4. The correlation coefficients of two adjacent pixels in Experiment 3~5.

p	Image	Horizontal	Vertical	Diagonal	Vice-Diagonal
-	Secret image S4	0.99455	0.98215	0.97774	0.96412
	Secret image S5	0.99033	0.98771	0.98821	0.97655
p = 9	Share image G1	0.00042	0.00022	0.00041	0.00016
	Share image G2	0.00035	0.00019	0.00034	0.00072
p = 18	Share image G1	0.00054	0.00010	0.00078	0.00123
	Share image G2	0.00069	−0.00032	0.00037	0.00024
p = 27	Share image G1	0.00025	0.00058	0.00157	−0.00032
	Share image G2	0.00145	0.00058	0.00012	0.00013

. Notably, the first four secret images were identical to those in Experiment 1 in Table 3. From these correlation tests, we strongly believe that the two shares generated by our scheme were merely noise-like, thus demonstrating that the secret message could not be revealed from each share.

Furthermore, if someone obtained one of the shares, they could still hardly decode the secret information. To demonstrate this security, consider two cases (G₁ and G₂). A total of ${\left(1/2\right)}^{\left(w \times h\right)}$ combinations would be required to restore input information. All the pixels in G₁ can be generated by random colors (either black or white), with w and h representing the width and height of an input image, respectively. Similarly, for the share G₂, ${\left(1/2\right)}^{\left(w \times h\right)}$ combinations would be required to decode secret messages. We conclude that it is difficult to extract the full information in a limited time.

6. Conclusions

This paper presents an extended VSS scheme, which can encode N secret images into two shares simultaneously. The shape of the input image can be rectangular. The proposed scheme was demonstrated to be correct and secure, as discussed in Section 5. Furthermore, users can select the value of p according to their requirements. When reconstructing the secret images, we can directly superimpose two shares to decode the first image, and the other image can be restored through the three steps described in Algorithm 3. Through Algorithm VMSSS, secret images can be distributed into two shares almost equally, and the distortion can be reduced to ((N − 2)p + 1)/Np. The distortion is thus close to (N − 2)/N when the value of p is high. In addition, the higher the value of p is, the lower the distortion. Without restrictions on the width and height of secret images, more secret images can be encoded simultaneously along with adjustable distortion. Accordingly, our scheme demonstrates high flexibility not only in theory but also in practice.