Keywords

1 Introduction

Visual cryptography scheme (VCS) also called visual secret sharing (VSS)[1, 2] shares user data into different shares (also called shadows) and distributes them among multiple participants. The decryption of VSS is based on stacking without the needs of cryptographic knowledge and computational devices. It has attracted the attention from scientists and engineers.

Naor and Shamir [1] first proposed the threshold-based VCS [2,3,4,5,6,7,8,9]. In their scheme, a binary secret image is shared by generating corresponding n noise-like shadow images. And any k or more noise-like shadow images are stacking to recover the secret image visually based on human visual system (HVS). However, less than k participants cannot reveal any information of the secret image by inspecting their shares. The main advantage of VCS by [1] is simple recovery, which means the decryption of secret image is completely based on stacking or HVS without any cryptographic computation. However, the scheme suffers from codebook (basic matrices) design and pixel expansion [2]. In order to solve the pixel expansion problem, some previous VCSs without the pixel expansion were proposed. Ito et al. [10] proposed the probabilistic VCS by equally selecting a column from corresponding basic matrix. Probabilistic VCS for different thresholds was presented by Yang [4]. Cimato et al. [5] further extended the generalization probabilistic VCS.

VSS by random grids (RG) [11,12,13,14,15,16,17,18] has gained much attention since it can avoid the pixel expansion problem as well as requires no codebook design. Encryption of binary secret images based on RG was first presented by Kafri and Keren  [19], each of which is generated into two noise-like RGs (also called shadow images or share images) that have the same size as the original secret image. The decryption operation is the same as traditional VCS. However, the relative RG-based VSS schemes [19,20,21] are only for cases (2, 2), (2, n) or (n, n).

To achieve the case (k, n), Chen and Tsao [22] proposed a RG-based (k, n) threshold VSS by applying (2, 2) RG-based VSS repeatedly for the first k bits and generating the last \(n-k\) bits randomly. Unfortunately, Chen and Tsao’s scheme has the limitation of low visual quality of recovered secret image. Then, following Chen and Tsao’s work, some RG-based VSS schemes were given to improve the visual quality [15, 16, 18, 23]. Specifically, Guo et al. [23] applied (k, k) threshold for every k bits and\(~N_k = \left\lfloor {n/k} \right\rfloor ~\)times, and set the last\(~n - N_k \times k~\) bits randomly. However, since both the last\(~n - N_k \times k~\) bits in Guo et al.’s scheme [23] and the last\(~n - k~\) bits in Chen and Tsao’s scheme [22] are random, darker reconstructed secrets, poor and unprogressive visual quality will be illustrated when more shares are stacked. Furthermore, in their schemes, (k, k) threshold is generated by serial computation, which may lead to low computational efficiency.

In this paper, a new RG-based VSS approach with improved visual quality is proposed. First, in our design, we performed the (k, k) threshold in parallel to obtain the first k bits. Then, to improve the visual quality, to decrease the darkness as well as to achieve progressive visual quality of the reconstructed secret image, in the proposed scheme, the last\(~n - k~\) bits are set to be equal to the first k bits or white (0). Experimental results and analyses show the effectiveness of the proposed scheme.

The result obtained by the proposed scheme is overall better than those obtained by [22, 23]. In addition, the idea of our scheme may be suitable for other schemes.

The rest of the paper is organized as follows. Section 2 introduces some basic requirements and related works for the proposed scheme. In Sect. 3, the proposed scheme is presented in detail. Section 4 is devoted to experimental results. Finally, Sect. 5 concludes this paper.

2 Preliminaries

In this section, we give some preliminaries and related works, i.e., RG-based [22, 23] VSS, as the basis for the proposed scheme. In what follows, symbols \( \oplus ~\)and\(~\otimes ~\)denote the Boolean XOR and OR operations. \(\overline{b}\) is a bit-wise complementary operation of a bit b. The binary secret image S is shared among n shadow images, while the recovered secret image \(S'\) is recovered from \(t (2 \le t \le n,t \in Z^ + )\) shadow images by stacking. In RG-based VSS, shadow images covered secret after sharing are denoted as\(~S{{C}_{p}}\). Here 0 denotes a white pixel and 1 denotes a black pixel.

For a certain pixel x in binary image X with size of \( M\times N~\), the probability of pixel color is transparent or white (0), is denoted as\(~P(x = 0)~\), and the same for pixel color is opaque or black (1). Besides,\(~P(S = 0) = 1 - \frac{1}{MN}\sum \limits _{i = 1}^M {\sum \limits _{j = 1}^N {S(i,j)} },1 \le i \le M,1 \le j \le N \). AS0 (resp., AS1) denotes the white (resp., black) area of original secret image S defined as \(AS0 = \{(i,j)\vert S(i,j) = 0,1 \le i \le M,1 \le j \le N\}\) (resp., \(AS1 = \{(i,j)\vert S(i,j) = 1,1 \le i \le M,1 \le j \le N\}\)).

Definition 1

(Contrast). The visual quality, which will decide how well human eyes could recognize the recovered image, of the recovered secret image \(S'\) corresponding to the original secret image S is evaluated by contrast defined as follows [24]:

$$\begin{aligned} \alpha =\frac{P_0 - P_1 }{1 + P_1 } = \frac{P({S}'\left[ {AS0} \right] = 0) - P({S}'\left[ {AS1} \right] = 0)}{1 + P({S}'\left[ {AS1} \right] = 0)} \end{aligned}$$
(1)

where \(\alpha \) denotes contrast,\(~P_0~\)(resp.,\(~P_1\)) is the appearance probability of white pixels in the recovered image\(~{S}' \) in the corresponding white (resp., black) area of original secret image S, that is,\(~P_0~\)is the correctly decrypted probability corresponding to the white area of original secret image S, and \(~P_1~\)is the wrongly decrypted probability corresponding to the black area of original secret image S.

Definition 2

(Visually recognizable). The recovered secret image \(S'\) could be recognized as the corresponding original secret image S if\(~\alpha > 0~\)when\(~t \ge k~\)[1].

Definition 3

(Security). The scheme is secure if \(~\alpha = 0~\)when\(~t < k~\)[1], which means no information of S could be recognized through\(~{S}'\).

Generally speaking, a valid VC construction should satisfy two conditions:

  1. (1)

    Security condition corresponding to Definition 3: Security condition means that insufficient shares give no clue about secret, i.e.,\(~{{P}_{0}}={{P}_{1}}\).

  2. (2)

    Contrast condition corresponding to Definition 2: Contrast condition indicates that sufficient shares reveal the secret, i.e., \(~\alpha >0\).

In addition, traditional VSS has the property of All-or-Nothing, i.e. the secret information could be revealed only when k or more shares are stacked together, and nothing if less than k shares are obtained. In many applications like pay-per-view videos, Pay- TV/Music and art-work image vending, video on demand (VoD), the following feature namely “progressive” is very useful. Progressive visual secret sharing (PVSS) can improve the clarity of a secret image progressively by stacking more and more shares. Although some PVSS schemes [25, 26] were proposed, the progressivity is evaluated only by HVS from the image illustration, the formal definition and evaluation metrics are laked. Thus, the formal definition and evaluation of progressive secret sharing (PSS) will be introduced here based on mathematical differential and expectations, which can be referred by related studies.

Definition 4

(PSS). A secret sharing scheme is progressive on t in interval \([T_1,T_2]\), if\(~f(x,t_2)>f(x,t_1) > 0~\)when \(T_1 \le t_1<t_2 \le T_2\).

where \(f\left( x, {t} \right) \) denotes the quality of the recovered secret image with t shadow images and x indicates other parameters, such as: k or n.

Definition 5

(Progressive rate). The progressive rate, which will decide how much the quality of the recovered secret image can increase, is defined as follows:

$$\begin{aligned} r(x,t) = \frac{{\partial f\left( {x,t} \right) }}{{\partial t}} \end{aligned}$$
(2)

In Definition 5, for mathematical analysis, we assume that\(~f\left( x, {t} \right) \) is derivable at t although it is not continuous in VSS.

For a certain threshold case x, e.g. (k, n), a scheme may owe different quality of the recovered secret image when t is different, thus we may utilize the contrast mathematical expectations to evaluate the quality of the recovered secret image for case x with t shadow images.

Definition 6

(Quality expectation). \(f\left( {x} \right) = \sum \limits _{t = 2}^n {P\left( {x,t} \right) f\left( {x,t} \right) }\)

where P(x, t) denotes the probability for t, which can be set according to the importance in applications.

In particular, for (k, n) RG-based VSS, we may have \(f\left( x, {t} \right) =f\left( k,n, {t} \right) = \alpha (k,n,t)\),  \(r(x,t) = r(k,n,t) = (\alpha (k,n,t+1)-\alpha (k,n,t))/1 = \alpha (k,n,t+1)-\alpha (k,n,t)\). From experience, when \(r(k,n,t) \ge 0.05\) we may say \(~\alpha (k,n,t)\) achieves good progressive performance on  t. And \(P(x,t)=P(k,n,t)\). If we assume \(P(k,n,t)= \frac{1}{{n - k + 1}}\), i.e., different  t  has the same importance, then \( \alpha \left( {k,n} \right) = \frac{{\sum \limits _{t = k}^n {\alpha \left( {k,n,t} \right) } }}{{n - k + 1}}\).

The generation and recovery phases of original (2, 2) RG-based VSS are described below.

Step 1: Randomly generate 1 RG\(~SC_1\).

Step 2: Compute\(~SC_2~\)as in Eq. (3).

Recovery:\(~{S}' = SC_1 \otimes SC_2~\)as in Eq. (4). If a certain secret pixel\(~s = S(i,j)~\)of S is 1, the recovery result\(~SC_1 \otimes SC_2 = 1~\)is always black. If a certain secret pixel is 0, the recovery result\(~SC_1 \otimes SC_2 = SC_1 (i,j) \otimes SC_1 (i,j)~\)has half chance to be black or white since\(~SC_1~\)are generated randomly.

$$\begin{aligned} SC_2 (i,j) = \left\{ \begin{array}{l} SC_1 (i,j)\;\;\;\;\;\;\;if\;S(i,j) = 0\; \\ \overline{SC_1 (i,j)} \;\;\;\;\;\;\;if\;S(i,j) = 1 \\ \end{array} \right. \end{aligned}$$
(3)
$$\begin{aligned} S'(i,j) = SC_1 (i,j) \otimes SC_2 (i,j) = \left\{ \begin{array}{l} SC_1 (i,j) \otimes SC_1 (i,j)\;\;\;\;\;\;\;\;\;\;\;if\;S(i,j) = 0\; \\ SC_1 (i,j) \otimes \overline{SC_1 (i,j)} \; = 1\;\;\;\;\;\;if\;S(i,j) = 1 \\ \end{array} \right. \end{aligned}$$
(4)

In fact, Eq. (3) is equal to\(~sc_2 = sc_1 \oplus s~\)or \(~s = sc_1 \oplus sc_2~\). Since if \(s = 0 \Rightarrow sc_2 = sc_1 \oplus 0 \Rightarrow sc_2 = sc_1~\), and if\(~s = 1 \Rightarrow sc_2 = sc_1 \oplus 1 \Rightarrow sc_2 = \overline{sc_1 }~\). The same equation could be extended to\(~s = sc_1 \oplus sc_2 \oplus \cdots \oplus sc_k~\)and the same approach can be extended to (k, n) threshold scheme by applying the above process repeatedly for the first k bits and generating the last n - k bits randomly. (k, n) RG-based VSS is described as follows:

figure a

In addition, Guo et al. [23] improve the visual quality of Chen and Tsao’s scheme by computing every k bits by applying (k, k) mechanism for\(~N_k = \left\lfloor {n/k} \right\rfloor ~\)times, and setting the last\(~n - N_k \times k~\) bits randomly. Guo et al.’s scheme [23] is described as follows:

figure b

Based on the above RG-based VSS schemes, both the last\(~n - N_k \times k~\)bits in Guo et al.’s scheme [23] and the last\(~n - k~\) bits in Chen and Tsao’s scheme [22] are random, which may lead to darker reconstructed secrets, poor and unprogressive visual quality when more shares are stacked. In addition, (k, k) threshold is generated by serial computation, which may obviously lead to low computational efficiency in their schemes. In this paper, these random bits will be utilized to improve the visual quality by setting them to be equal to the first k bits or white (0), among which (k, k) threshold will be performed by parallel.

3 The Proposed Scheme

There are some random bits, such as the middle \((N_k - 1)\times k\) bits and the last \(n-k\) bits in the previous schemes [22, 23], which are applied for improving the visual quality in the proposed scheme. Thus the proposed scheme can improve the visual quality.

Fig. 1.
figure 1

Shadow images generation architecture of the proposed scheme

Full size image

The shadow images generation architecture of the proposed scheme is illustrated in Fig. 1, consists of three phases.

  1. 1.

    Generate (k, k) threshold in parallel.

  2. 2.

    Set the next \(N_k \times k - k + 2\) bits to be distinct one of the first k bits, the last \(n-N_k \times k- 1\) to be 0.

  3. 3.

    Rearrange the generated n bits randomly to corresponding n shadow images bits

The algorithmic steps are described below.

figure c

The secret recovery of the proposed scheme is also based on stacking \(( \otimes )\) or HVS.

The idea of our Algorithm is described precisely as follows:

There are random bits in the last\(~n-k\) bits. The random bits could be utilized to gain better properties, such as threshold mechanism, and improving the visual quality. In step 2, the k bits are utilized in parallel to gain threshold mechanism, i.e., when less than k shadow images are collected, the secret will not be revealed. While in Step 3, first we set the next \(N_k \times k - k + 2\) bits to be distinct one of the first k bits to improve the probability of covering\(~b_1,b_2, \cdots b_k~\)so as to improve the visual quality of recovered secret image. Then the last \(n-N_k \times k- 1\) are set to be 0, aiming to decrease the darkness of the reconstructed secret image, in the proposed scheme. As a result, progressive visual quality of the revealed secret image will be gained. In step 4, in order to make all the shadow images be equal to each other, the generated n bits are randomly rearranged to corresponding n shadow images bits.

We note that, for pages limitation, we omit theoretical analysis about security and contrast.

4 Experimental Results and Analyses

In this section, we conduct experiments and analyses to evaluate the effectiveness of the proposed scheme. In the experiments, two secret images are used: original binary secret image1 as shown in Fig. 2(a), and original binary secret image2 as shown in Fig. 3(a) are used as the binary secret images, with size of 512\(~\times ~\)512, to test the efficiency of the proposed scheme.

4.1 Image Illustration

To test (3, 4) (i.e. \(k =3, n =4\)) threshold of our scheme with secret image1, Fig. 2 (b–e) show the 4 shadow images SC\(_{1}\), SC\( _{2}\), SC\(_{3}\) and SC\(_{4}\), which are noise-like. Figure 2 (f–j) show the recovered secret images with any 3 or 4 shadow images with stacking recovery, from which the secret image recovered from\(~k=3~\)or more shadow images could be recognized based on superposition. Figure 2 (k–p) show the recovered secret image with any less than\(~k=3~\)shadow images based on stacking recovery, from which there is no information could be recognized.

The next experiments, we only give the results by the first t th shadow images for saving pages.

Secret image2 is used to do the test for case (2,5). Figure 3 (b) shows one of the 5 shadow images, which is noise-like. Figure 3 (c–f) show the recovered binary secret image with any\(~t\left( {2 \le t \le 5} \right) ~\)(taking the first  t shadow images as an example) with stacking recovery, from which better visual of the recovered secret will be gained by superposing more shadow images.

Fig. 2.
figure 2

Experimental example of the proposed (3, 4) scheme

Full size image

Based on the above results we can conclude that:

  1. 1.

    The shadow images are noise-like, every single shadow image can not disclose the secret image.

  2. 2.

    When\(~t < k~\)shadow images are collected, there is no information of the secret image could be recognized, which shows the security of the proposed scheme.

  3. 3.

    When\(~t(k \le t \le n)~\)shadow images are recovered by stacking, the secret image could be recognized by HVS, which indicates our scheme is visually recognizable.

  4. 4.

    The progressive visual quality of the recovered secret can be achieved when more shares are superposing.

Table 1. Average contrast of the proposed scheme
Full size table

4.2 Visual Quality of the Recovered Secret Images

The visual quality of the recovered secret images is evaluated by contrast in Definition 1. The same original binary secret image as shown in Fig. 3(a) is used to do the experiments of contrast.

Average contrast for different shadow images combinations of the proposed \((k,n)(2 \le k \le n)\) scheme is shown in Table 1, where t denotes the number of recovered shadow images.

From Table 1, we can find that, in the proposed scheme, \(~\alpha > 0~\)when\(~t \ge k\) and contrast increases as t increases for a certain (k, n) by superposing when \(2 \le n \le 5\). Thus, for case (k, n), our scheme is progressive on t in interval [k, n] or \([k,n-1]\). The experimental results of the contrast further verify the validity of our scheme.

Fig. 3.
figure 3

Experimental example of the proposed (2, 5) scheme

Full size image
Fig. 4.
figure 4

Experimental example of Chen and Tsao’s (2, 5) scheme

Full size image
Fig. 5.
figure 5

Experimental example of Guo et al.’s (2, 5) scheme

Full size image

4.3 Comparisons with Related Schemes

Herein, we compare the proposed scheme with other related schemes especially Chen and Tsao’s scheme [22] and Guo et al.’s scheme  [23] in terms of image illustration and contrast. since both the proposed scheme and [23] are a continuous and extension work of the scheme in [22]. In addition, schemes in [22, 23] have good features in VSS, such as no codebook design, no pixel expansion and so on.

Image Illustration Comparison. Here, (2, 5) threshold with\(~k \le t \le n~\)is also applied for comparison. The simulation results of Chen and Tsao’s scheme and Guo et al.’s scheme are illustrated in Figs. 4 and 5, respectively. We can see that Guo et al.’s scheme improves the visual quality of Chen and Tsao’s scheme. From Figs. 3, 4 and 5, Guo et al.’s scheme and Chen and Tsao’s scheme are darker, while the darkness of the proposed scheme is acceptable, since\(~sc_1 \otimes sc_2 \otimes \cdots \otimes sc_k \cdots \otimes sc_{n - 1} \otimes sc_n = sc_1 \otimes sc_2 \otimes \cdots \otimes sc_k~\)in the proposed scheme. Hence, the proposed scheme overall outperforms the other two in terms of darkness and progressive property for the case.

Contrast Comparison. Table 2 shows contrast of Chen and Tsao’s scheme and Guo et al.’s scheme with all \(( k, n )( 2 \le n \le 5,2 \le k \le n,k \le t \le n )\). Remark: The theoretical contrast of the proposed scheme is not given directly by k, t and n, hence the contrast comparisons are given by experiments. In addition, Definition 1 is a statistical result. Thus, the experimental results are close to the theoretical contrast.

Based on Tables 1 and 2, we have the following conclusions:

Table 2. Contrast of Chen and Tsao’s scheme and Guo et al.’s scheme
Full size table
  1. 1.

    The contrast of the proposed scheme is overall similar as or greater than others except case (2, 3) with \(t=2\).

  2. 2.

    In our scheme for case (2, 3), two bits of \(b_1,b_2,b_3\) are 0, thus \(P_1\) will be increased. As a result, from Definition 1 contrast will be decreased.

  3. 3.

    If\(~t=n~\)for case (n, n), the contrast of the proposed scheme is nearly the same as that of the others, since they reduce to the same algorithm.

  4. 4.

    The proposed scheme is overall greater than others for the other (k, n) cases when\(~n - k \ge 0\). Especially for cases (2, 4) and (2, 5), the contrast of the proposed scheme achieves 0.5. Tacking case (2, 5) as an example, our \(\alpha \left( {2,5} \right) = \frac{{\sum \limits _{t = 2}^5 {\alpha \left( {k,n,t} \right) } }}{{4}}=0.38136\) according to Definition 6, while that of Chen and Tsao’s scheme and Guo et al.’s scheme are 0.0625 and 0.1257, respectively, Thus, our contrast expectation is greater than theirs. Furthermore, by Definition 5, our \( r(2,5,2) = \alpha (2,5,3)-\alpha (2,5,2)=0.2101\), while that of Chen and Tsao’s scheme and Guo et al.’s scheme are 0.02761 and 0.05921, respectively. Hence, our Progressive rate is better than theirs. Because the probability of correctly collecting the first k bits of the proposed scheme is larger than that of the others.

  5. 5.

    The contrast of stacking\(~t=n-1~\)is the same as that of stacking\(~t=n~\)for cases (2, 4) and (2, 5), since\(~sc_1 \otimes sc_2 \otimes \cdots \otimes sc_k \cdots \otimes sc_{n - 1} \otimes sc_n = sc_1 \otimes sc_2 \otimes \cdots \otimes sc_k~\)in the proposed scheme.

  6. 6.

    The idea of our scheme may be applied in Guo et al.’s scheme and other schemes to improve their visual quality.

5 Conclusion

This paper proposed a new RG-based progressive VSS with improved visual quality as well as less darkness by in parallel utilizing the last\(~n - k~\) bits are set to be equal to the first k bits or white (0), which outperformed relative schemes in terms of image illustration and contrast. The probability of correctly reconstructing the secret pixels is improved, whose successful points lie in: (1) (k, n) threshold by parallel, (2) requiring no codebook design, (3) avoiding the pixel expansion problem, (4) setting the random bits to be equal to the previous bits or white to achieve larger visual quality and less darkness than the previous related schemes. However, the contrast of the proposed scheme is not given directly by k, t and n, which is left as an open problem for further studies. The idea of our scheme in the future may be extended to other schemes to improve the visual quality.