A New Visual Multi-Secrets Sharing Scheme by Random Grids

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.

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. 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.

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.

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.

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.

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.

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.

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. The visual analysis and security analysis of our scheme are explained in Section 5.1 and Section 5.2, respectively.

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.