On the security of threshold random grid-based visual secret sharing

Abstract

Visual secret sharing (VSS) technology encodes a secret image into some share images for sharing some classified information. Only when the participants gather and stack their share pictures the secret image would be reconstructed and recognizable by the human visual system. Two well-known encoding ways of VSS, visual cryptography (VC) and random grid (RG), have been developed in recent years. As both VC and RG have been considered as a secure way for communicating with high security, they have been pointed out with cheating problems. In this paper, we propose two RG-based VSS schemes with fraud prevention for the cases of (2,n) and (k,n). The experimental results and the analysis of security and contrast show that the proposed method is efficient and practical.

1 Introduction

For secure communication, visual secret sharing (VSS) turns a secret image into some meaningless share images in visual, only if stacking enough number of share images the secret image would be revealed in visual. Except for secure communication, VSS can also be applied in visual authentication [17, 18], image hiding [2, 8] or digital watermarking [11, 24, 25] and so on.

In VSS scheme, the encoding way is mainly classified into visual-cryptography-based (VC-based) and random-grid-based (RG-based). The features of VC-based VSS scheme can be summarized in two. 1) For each case of k-out-of-n (noted by (k,n)), it needs a tailor-made codebook for encoding. 2) The size of generated share images and the reconstructed secret image is larger than the original secret image, that is, pixel expansion. The first threshold VC-based VSS was defined and proposed by Naor and Shamir [19] in 1995. After that, more improved threshold VC-based VSS schemes with different thresholds and codebook designs have been proposed [1, 6, 12].

Comparing with VC-based VSS, the feature of RG-based VSS is also considered in two. 1) It only needs to design an encoding algorithm, and the algorithm can be applied in each (k,n). 2) The size of share images and the reconstructed secret image keeps the same as the original secret image, that is, no pixel expansion. The first threshold RG-based VSS was proposed by Kafri and Keren [13]. Although RG-based VSS is still in its infancy, many schemes have also been proposed [3,4,5, 7, 15, 16, 21] in the past decade.

Taking the security of VC-based VSS into account, Horng et al. [9] pioneered in claiming the (k,n) VC-based VSS suffering from the cheating of malicious participants intending to mislead honest participants by generating a share to cheat honest members to accept the wrongly revealed secret information. Furthermore, the first scheme [9] is presented to prevent VSS from cheating by the designed that every participant has one extra share image to authenticate the validity of the generic share of the other participants. The second scheme adopted a (2,n + l) VC-based VSS scheme in which n + l shares are generated but only deliver n share images to n participants while l shares are discarded. Since the fraud problem was found, a series of cheating prevention schemes [10, 20, 22, 23] have been designed. Tsai et al. [22] proposed another cheating-prevention scheme using the computation-expensive. Hu and Tzeng [10] proposed three kinds of cheating and a preventive scheme.

Nevertheless, unfortunately, threshold RG-based VSS has also pointed out that it suffers from cheating problem [14, 26]. In the case of (2,n) (or (k,n)) RG-based VSS [4], at least 2 (or k) malicious participants can reconstruct secret information before the rest associates know the secret information. The malicious participants then can generate artificial share images with a cheating message and send to the rest participants. After stacking with the artificial share images, the rest participants will reconstruct the cheating message without awareness.

Lee and Chen [14] pointed out that the collusion attack did work in (2,n) and (k,n) RG-based VSS [4]. In (2,n) RG-based VSS, the area in the reconstructed secret image corresponding to the white secret pixels can be maliciously operated by cheaters turning white to black; furthermore, in (k,n) RG-based VSS, cheaters can choose a cheating image freely.

Hence, in this paper, we propose two threshold RG-based VSS schemes with cheating prevention for cases (2,n) and (k,n). We add an authentication image into the algorithm and let each two share images be able to perform the authentication process. The fake share images will be detected by the authentication process.

The rest of this paper is organized as follows. The next section briefly reviews the cheating problem in threshold RG-based VSS [14]. The proposed (2,n) scheme, its experimental results, and performance analysis are illustrated in Section 3, and the proposed (k,n) scheme is described in Section 4. Finally, the further discussion and the conclusion are shown in Section 5 and 6.

2 The cheating problem

Lee and Chen [14] pointed out that the cheating attacks in threshold RG-based VSS were possible and demonstrated how to work in (2,n) and (k,n) cases. The reviewing is as follows.

2.1 The cheating problem in (2,n) RG-based VSS

In the cheating process, supposing that two malicious participants (cheaters) intend to cheat the other participants, they stack the random-grids which they have to confirm the secret information previously. With the known secret information, the cheaters can modify the secret information and make a cheating image. Forwardly, the cheaters generate a fake random-grid with their grids and the cheating image by the cheating process.

In the encoding algorithm of (2,n) scheme, when secret pixel is white, the same positions in each random grid have the same pixel values no matter white or black. When the secret pixel is black, the same positions of each random grid are randomly determined separately. Therefore, based on their own random grid, the cheater let a part of the pixel values which are known as a white area of the secret image be random, that is, the cheater is able to modify the secret information. The modified random grid is regarded as the fake grid. When stacking with the fake grid, the rest participants will see the modified information. The concept of cheating attacks in (2,n) scheme is shown in Fig. 1.

Fig. 1

The concept of cheating attacks in (2,n) scheme

2.2 The cheating problem in (k,n) RG-based VSS

At least k malicious participants reconstruct the secret image previously and try to generate an evaluated grid. The pixels in the evaluated grid have a high probability that similar with the rest members. Then, the malicious participants perform (k,n) VSS scheme with a picked cheating image and the evaluated grid to generated k-1 fake grids. When the rest participants stack with the k-1 fake grids, they will reconstruct the cheating image in visual. The concept of cheating attacks in (k,n) scheme is shown in Fig. 2.

Fig. 2

The concept of cheating attacks in (k,n) scheme

3 The proposed (2,n) VSS scheme with cheating prevention

In this section, the proposed (2,n) RG-based VSS scheme with cheating prevention is described as follows, and the experimental results and performance analysis are shown after it.

3.1 The proposed scheme

The main design aims at that two generated share images can be superimposed to disclose the secret image and simultaneously one share and the other rotated share can be superimposed to appear the authentication message. In such a way, the cheating-prevention VSS scheme does work. The proposed scheme is mainly disported to two phases: (2,2) generation and (2,n) generation.

In the first phase, input a secret image S = {S[i, j]| S[i, j] ∈ {0, 1}, 0 ≤ i ≤ (w − 1), 0 ≤ j ≤ (h − 1)} (“0” presents the white pixel, and “1” the black one.) and an authentication image A = {A[i, j]| A[i, j] ∈ {0, 1}, 0 ≤ i ≤ (w − 1), 0 ≤ j ≤ (h − 1)} with RG-based VSS scheme to generate two random-grids P₁ and P₂ (P_1(or 2) = {P_1(or 2)[i, j]| P_1(or 2)[i, j] ∈ {0, 1}, 0 ≤ i ≤ (w − 1), 0 ≤ j ≤ (h − 1)}).When stacking P₁ and P₂, the secret image S will be reconstructed. When stacking P₁ and RP₂ (90 degrees rotated P₂), the authentication image A will be reconstructed.

In the second phase, distribute the pixels of P₁ and P₂ into n random-grids, G_m = {G_m[i, j]| G_m[i, j] ∈ {0, 1}, 0 ≤ i ≤ (w − 1), 0 ≤ j ≤ (h − 1)}, where m = 1, 2, …, n. Then, the n random-grids are the final output. Stacking each two of these random-grids can reconstruct the secret image S. Furthermore, rotating one of them by 90 degrees and stacking can reconstruct the authentication image A.

3.1.1 Phase 1: Generate (2,2) random-grids P ₁ and P ₂

(From Step 1.1 to 1.8, see Fig. 3.)

• Step 1.1: Randomly choose P₁[i, j] ∈ {0, 1}. (“0” presents the white pixel, and “1” the black one.)

• Step 1.2: Determine P₂[h − j, i] by referring P₁[i, j] and A[i, j] as ${P}_2\left[h-j,i\right]=\left\{\begin{array}{l}{P}_1\left[i,j\right]\kern0.5em \mathrm{if}\ A\left[i,j\right]=0\\ {}\left({P}_1\left[i,j\right]+1\right)\operatorname{mod}2\kern0.75em \mathrm{if}\ A\left[i,j\right]=1\end{array}\right.$.

• Step 1.3: Determine P₁[h − j, i] by referring P₂[h − j, i] and S[h − j, i] as ${P}_1\left[h-j,i\right]=\left\{\begin{array}{l}{P}_2\left[h-j,i\right]\kern0.5em \mathrm{if}\ S\left[h-j,i\right]=0\\ {}\left({P}_2\left[h-j,i\right]+1\right)\operatorname{mod}2\kern0.5em \mathrm{if}\ S\left[h-j,i\right]=1\end{array}\right.$.

• Step 1.4: Determine P₂[w − i, h − j] by referring P₁[h − j, i] and A[h − j, i] as ${P}_2\left[w-i,h-j\right]=\left\{\begin{array}{l}{P}_1\left[h-j,i\right]\kern0.5em \mathrm{if}\ A\left[h-j,i\right]=0\\ {}\left({P}_1\left[h-j,i\right]+1\right)\operatorname{mod}2\kern0.5em \mathrm{if}\ A\left[h-j,i\right]=1\end{array}\right.$.

• Step 1.5: Randomly choose P₁[w − i, h − j] ∈ {0, 1}.

• Step 1.6: Determine P₂[j, h − i] by referring P₁[w − i, h − j] and A[w − i, h − j] as ${P}_2\left[j,h-i\right]=\left\{\begin{array}{l}{P}_1\left[w-i,h-j\right]\kern0.5em \mathrm{if}\ A\left[w-i,h-j\right]=0\\ {}\left({P}_1\left[w-i,h-j\right]+1\right)\operatorname{mod}2\kern0.75em \mathrm{if}\ A\left[w-i,h-j\right]=1\end{array}\right.$.

• Step 1.7: Determine P₁[j, h − i] by referring P₂[j, h − i] and S[j, h − i] as ${P}_1\left[j,h-i\right]=\left\{\begin{array}{l}{P}_2\left[j,h-i\right]\kern0.5em \mathrm{if}\ S\left[j,h-i\right]=0\\ {}\left({P}_2\left[j,h-i\right]+1\right)\operatorname{mod}2\kern0.5em \mathrm{if}\ S\left[j,h-i\right]=1\end{array}\right.$.

• Step 1.8: Determine P₂[i, j] by referring P₁[j, h − i] and A[j, h − i] as ${P}_2\left[i,j\right]=\left\{\begin{array}{l}{P}_1\left[j,h-i\right]\kern0.5em \mathrm{if}\ A\left[j,h-i\right]=0\\ {}\left({P}_1\left[j,h-i\right]+1\right)\operatorname{mod}2\kern0.5em \mathrm{if}\ A\left[j,h-i\right]=1\end{array}\right.$.

• Step 1.9: Repeat Step 1.1 to 1.8 until all pixels of P₁ and P₂ are determined, but notice that each circle from Step 1.1to 1.8 determines 4 pixel values in P₁ (and in P₂). Hence, P₁ can be derived into 4 blocks with same size.

Fig. 3

Concept of Step 1.1 to 1.8

When each circle starts from Step 1.1, the beginning position P₁[i, j] can be randomly located in one of blocks I~VI, except the pixels which have been determined already.

3.1.2 Phase 2: Gererate (2,n) random-grids by distributing P ₁ and P ₂ into G _m, where m = 1,2,…,n

• Step 2.1: For G_m[i, j], randomly choose P₁ or P₂ and distribute its four pixel values at one time with positions (i, j), (h − j, i), (w − i, h − j) and (j, h − i) into corresponding G_m[i, j], G_m[h − j, i], G_m[w − i, h − j] and G_m[j, h − i].

• Step 2.2: For a grid G_m, where 0 ≤ i ≤ (w/2 − 1), 0 ≤ j ≤ (h/2 − 1), repeat Step 2.1 until all pixel values of G_m are determined.

• Step 2.3: Repeat Step 2.1 and 2.2 until all random-grids G_m are generated, where m = 1, 2, …, n.

The concept of Phase 2 is shown in Fig. 4.

Fig. 4

Concept of Phase 2

The algorithm of the proposed encoding process is briefly illustrated as follows.

The decoding process directly stacks two or more random-grids to reconstruct the secret image detectable by the human visual system. Rotating one of them by 90 degrees and stacking will rebuild the authentication image.

3.2 Experimental results

To demonstrate that the proposed scheme achieves the collusion attack prevention and its feasibility, the experimental results are given in this section.

First, we choose images Fig. 5a as the secret image and Fig. 5b as the authentication image with both size 1024 × 1024. After performing the proposed encoding process with n = 3, we have three random-grids Fig. 5c, d and e.

Fig. 5

The experimental results of the proposed scheme with n = 3

3.2.1 Stacking results of (2,3) case

Then, the results of stacking each two random-grids are Fig. 5f, g and h. The authentication results are as Fig. 5i, j and k. Notice that RG₁, RG₂ and RG₃ stand for the 90 degrees rotated random-grids. Finally, Fig. 5l is the result of stacking all random-grids.

3.2.2 Stacking results of (2,3) case with cheating attacks

Next, we implement the collusion attacks of (2,n) introduced in Ref. [14] on the proposed scheme. Supposing that the two participants, u₁ and u₂, have random-grids, G₁ and G₂, perform the collusion attacks to cheat the rest participant, u₃. Because, by stacking G₁ and G₂, u₁ and u₂ have already known the secret information, they modify the secret information as Fig. 6a and generate a fake image, FG, Fig. 6b, to cheat u₃. When u₃ receives FG and stacks with G₃, Fig. 6c, u₃ will recover the cheating information. However, if u₃ performs the authentication Fig. 6d, (s)he will see that the authenticating result is different from the authentication image Fig. 5b. Hence, u₃ can tell that FG is a fake grid.

Fig. 6

The collusion attacks [14] in the proposed scheme

3.3 Security analysis

To show the security and performance of the proposed schemes, the values of average light transmission and contrast are popularly used in VSS scheme. Hence, the definitions are given as follows.

• Definition 1. (Average light transmission)

For a binary image I with size w × h, the light transmission of some pixel I[i, j] is defined as $t\left[I\left[i,j\right]\right]=\left\{\begin{array}{l}0\kern0.5em \mathrm{if}\ I\left[i,j\right]=1\\ {}1\kern0.5em \mathrm{if}\ I\left[i,j\right]=0\end{array}\right.$ (I[i, j] = 0 stands for the white pixels of I, and the other is black). Furthermore, the average light transmission of I is defined as $T\left[B\right]=\frac{1}{w\times h}\sum \limits_{i=0}^{w-1}\sum \limits_{j=0}^{h-1}t\left[B\left[i,j\right]\right]$, that is, the ratio of white pixels in I.

• Definition 2. (Contrast)

The contrast of a binary image I on the secret image S is defined as $\alpha =\frac{T\left[I\left[S(0)\right]\right]-T\left[I\left[S(1)\right]\right]}{1+T\left[I\left[S(1)\right]\right]}$ from [30]. T[I[S(0)]] means the average light transmission of the area in I which is according to the white area of S, and T[I[S(1)]] is according to the black area. The range of α is −1 ≤ α ≤ 1, but the secret information in I is visually recognizable when α ≠ 0, and the visual quality is better when α is larger in positive or smaller in negative.

3.3.1 Proposition 1 (Security of each random-grid)

Without stacking, each random-grid reveals neither secret information nor authentication information.

Proof

In the proposed scheme, the first step randomly determines P₁[i, j] ∈ {0, 1}, so its probability of white pixel is $\frac{1}{2}$. Then, determine pixel values by referencing the authentication image A or the secret image S. According to the rule of reference, the probability of white pixel keeps $\frac{1}{2}$ no matter referencing A or S. Therefore, the white pixel’s probability of each pixel in P₁ or P₂ is always $\frac{1}{2}$, even distributing the pixel into G₁, G₂, …, G_n. Hence, for some G_m, where m = 1, 2, …, n, the average light transmission according to white area in S is $T\left[{G}_m\left[S(0)\right]\right]=\frac{1}{\mid S(0)\mid}\sum \limits_1^{\mid S(0)\mid}\frac{1}{2}=\frac{1}{2}$, and $T\left[{G}_m\left[S(1)\right]\right]=\frac{1}{\mid S(1)\mid}\sum \limits_1^{\mid S(1)\mid}\frac{1}{2}=\frac{1}{2}$ is for black area (∣ ⋅ ∣ is the number of pixels). Then, the contrast is $\alpha =\frac{T\left[{G}_m\left[S(0)\right]\right]-T\left[{G}_m\left[S(1)\right]\right]}{1+T\left[{G}_m\left[S(1)\right]\right]}=\frac{1/2-1/2}{1+1/2}=0$, that is, the random-grid G_m reveals no secret information in visual. On the other hand, the average light transmission according to white area in A is $T\left[{G}_m\left[A(0)\right]\right]=\frac{1}{\mid A(0)\mid}\sum \limits_1^{\mid A(0)\mid}\frac{1}{2}=\frac{1}{2}$ is for black area. Then, the contrast is $\alpha =\frac{T\left[{G}_m\left[A(0)\right]\right]-T\left[{G}_m\left[A(1)\right]\right]}{1+T\left[{G}_m\left[A(1)\right]\right]}=\frac{1/2-1/2}{1+1/2}=0$, that is, the random-grid G_m also reveals no authentication information in visual.

3.3.2 Proposition 2 (Cheating prevention)

Analyzing with two or more random-grids cannot infer another random-grid.

Proof

When two or more malicious participants intend to cheat another participant, for generating fake grids, they must analyze the grids they have and guess the pixel values of another random-grid. A success cheating attacks based on the high similarity between estimating random-grid and aim random-grid. In other words, if the attackers fail in inferring pixel values, the cheating attacks cannot be performed. In Phase 2 of the proposed scheme, the pixel values of P₁ and P₂ are randomly distributed into G₁, G₂, …, G_n, that is, each random-grid can be viewed as a random combination of P₁ and P₂ alone. Therefore, even gathering two or more random-grids, the probability of guessing each pixel in another random-grid is always $\frac{1}{2}$. Forwardly, generate the estimating random-grid based on the $\frac{1}{2}$ fail guessing and make a fake random-grid. Then, in the authentication process, the fake information or doctoring trail will appear on the authenticating result. Hence, the proposed (2,n) scheme can prevent cheating attacks.

3.4 Contrast analysis

In the proposed (2,n) scheme, G₁, G₂, …, G_n are generated by randomly distributing the pixels of P₁ and P₂. Hence, before giving the analysis of stacking results of G₁, G₂, …, G_n, we should analyze the stacking result of P₁ and P₂ first.

3.4.1 Proposition 1 (Contrast of stacking result with P ₁ and P ₂)

When stacking P₁ and P₂, the contrast of the reconstructed secret image is $\alpha =\frac{2}{9}$ (The average light transmission appears $T\left[{P}_1\oplus {P}_2\left[S(0)\right]\right]=\frac{3}{8}$ and $T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]=\frac{1}{8}$.). When authenticating with P₁ and P₂, the contrast of the revealed authentication image is $\alpha =\frac{1}{2}$ (The average light transmission appears $T\left[{P}_1\oplus {RP}_2\left[A(0)\right]\right]=\frac{1}{2}$ and T[P₁ ⊕ RP₂[A(1)]] = 0, where RP₂ means rotating P₂ with 90 degrees.).

Proof

In the process of generating P₁ and P₂, for each four relating positions, the secret image, S, is referenced only two times, while the authentication image, A, is four times. This implies that half pixels of the secret image won’t be correctly reconstructed, and the authentication image can be fully reconstructed. The definition of successfully reconstructing is that the stacking result is same with (2,2) scheme; that is, considering the normally reconstructed secret image in (2,2) scheme, the average light transmission of stacking result corresponding to white (or black) area of the secret image is $\frac{1}{2}$ (or 0). Therefore, when reconstructing the secret image with P₁ and P₂, for the pixels which are corresponding to the white (or black) area in S, there are half pixels that the probability of white pixels is $\frac{1}{2}\times \frac{1}{2}$ (failing reconstruction), and the other’s probability is $\frac{1}{2}$ (or 0) (successful reconstruction). Hence, the average light transmission appears $T\left[{P}_1\oplus {P}_2\left[S(0)\right]\right]=\frac{1}{\mid S(0)\mid}\left[\left(\sum \limits_1^{\mid S(0)\mid /2}\frac{1}{2}\times \frac{1}{2}\right)+\left(\sum \limits_1^{\mid S(0)\mid /2}\frac{1}{2}\right)\right]=\frac{1}{8}+\frac{1}{4}=\frac{3}{8}$ and $T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]=\frac{1}{\mid S(1)\mid}\left[\left(\sum \limits_1^{\mid S(1)\mid /2}\frac{1}{2}\times \frac{1}{2}\right)+\left(\sum \limits_1^{\mid S(1)\mid /2}0\right)\right]=\frac{1}{8}$. Forwardly, the contrast of the revealed secret image with P₁ and P₂ is $\alpha =\frac{T\left[{P}_1\oplus {P}_2\left[S(0)\right]\right]-T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]}{1+T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]}=\frac{3/8-1/8}{1+1/8}=\frac{2}{9}$. On the other hand, when authenticating with P₁ and P₂, all pixels are reconstructed successfully, so the result is same with (2,2) scheme. Hence, the average light transmission appears $T\left[{P}_1\oplus {RP}_2\left[A(0)\right]\right]=\frac{1}{\mid A(0)\mid}\sum \limits_1^{\mid A(0)\mid}\frac{1}{2}=\frac{1}{2}$ and $T\left[{P}_1\oplus {RP}_2\left[A(1)\right]\right]=\frac{1}{\mid A(1)\mid}\sum \limits_1^{\mid A(1)\mid }0=0$. Forwardly, the contrast of the revealed authentication image with P₁ and P₂ is $\alpha =\frac{T\left[{P}_1\oplus {RP}_2\left[A(0)\right]\right]-T\left[{P}_1\oplus {RP}_2\left[A(1)\right]\right]}{1+T\left[{P}_1\oplus {RP}_2\left[A(1)\right]\right]}=\frac{1/2-0}{1+0}=\frac{1}{2}$.

3.4.2 Proposition 2 (Contrast of reconstructed secret image)

The contrast of the reconstructed secret image in the proposed (2,n) scheme is $\alpha =\frac{2^n-{2}^{n-r+1}}{9\times {2}^{n-1}+3\times {2}^{n-r}-12}$, where r = 2, 3, …, n is the number of stacked grids.

Proof

According to the proposed (2,n) scheme, the pixels of P₁ and P₂ are randomly distributed into n random-grids. Therefore, when stacking r random-grids for reconstructing the secret image, for each pixel, there exists a probability, $\frac{2^{n-r}-1}{2^{n-1}-1}$, of fail reconstructing. Here, the definition of fail reconstructing is that the stacked r pixels are all from P₁ (or P₂), and the probability of white pixel of stacked result is $\frac{1}{2}$. On the other hand, if the stacked r pixels including pixels of both P₁ and P₂, this is considered as successful reconstructing, and the probabilities of white pixel are same with the average light transmission of stacking results of P₁ and P₂, that is, $T\left[{P}_1\oplus {P}_2\left[S(0)\right]\right]=\frac{3}{8}$ and $T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]=\frac{1}{8}$ (Proposition 1). Hence, the average light transmission appears ${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(0)\right]\right]=\frac{2^{n-r}-1}{2^{n-1}-1}\times \frac{1}{2}+\left(1-\frac{2^{n-r}-1}{2^{n-1}-1}\right)\times T\left[{P}_1\oplus {P}_2\left[S(0)\right]\right]\\ {}=\frac{1}{8}\times \frac{2^{n-r}-1}{2^{n-1}-1}+\frac{3}{8}\\ {}=\frac{2^{n-r}+{2}^n+{2}^{n-1}-4}{2^{n+2}-8}\end{array}}$ and ${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]=\frac{2^{n-r}-1}{2^{n-1}-1}\times \frac{1}{2}+\left(1-\frac{2^{n-r}-1}{2^{n-1}-1}\right)\times T\left[{P}_1\oplus {P}_2\left[S(1)\right]\right]\\ {}=\frac{3}{8}\times \frac{2^{n-r}-1}{2^{n-1}-1}+\frac{1}{8}\\ {}=\frac{3\times {2}^{n-r}+{2}^{n-1}-4}{2^{n+2}-8}\end{array}}$ where ${G}_{u_1},{G}_{u_2},\dots {G}_{u_r}$ mean any different r random-grids chosen from G₁, G₂, …G_n. Forwardly, the contrast is $\alpha =\frac{T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(0)\right]\right]-T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]}{1+T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]}=\frac{2^n-{2}^{n-r+1}}{9\times {2}^{n-1}+3\times {2}^{n-r}-12}$.

To show that the theoretical contrast is close to the experimental result, we give the comparison table, see Table 1.

Table 1 Contrast values of reconstructed secret image and theoretical values

3.4.3 Proposition 3 (Contrast of authentication result)

The contrast of authentication result in the proposed (2,n) scheme is $\alpha =\frac{\left(n-1\right)\times {2}^{n-1}}{\left(9\times n+1\right)\times {2}^{n-2}-5\times n}$.

Proof

When performing authentication, it is similar to Proposition 2 that there exists $\frac{2^{n-2}-1}{2^{n-1}-1}$ (r = 2, the authentication process only uses two random-grids each time.) pixels fail in reconstructing, but because of rotating in authentication, the probability of white pixel is $\frac{1}{2}\times \frac{1}{2}$. However, in the rest $1-\frac{2^{n-2}-1}{2^{n-1}-1}$ pixels, there also exists a probability, $\frac{1}{n}$, of fail reconstructing because of the wrong way of rotating. (From Proposition 1, $T\left[{P}_1\oplus {RP}_2\left[A(0)\right]\right]=\frac{1}{2}$ and T[P₁ ⊕ RP₂[A(1)]] = 0) Hence, the average light transmission appears ${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {RG}_{u_2}\left[A(0)\right]\right]\\ {}=\frac{2^{n-2}-1}{2^{n-1}-1}\times \frac{1}{4}+\frac{1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times \frac{1}{4}+\frac{n-1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times T\left[{P}_1\oplus {RP}_2\left[A(0)\right]\right]\\ {}=\frac{2^{n-2}-1}{2^{n-1}-1}\times \frac{1}{4}+\frac{1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times \frac{1}{4}+\frac{n-1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times \frac{1}{2}\\ {}=\frac{2\times n-1}{4\times n}-\frac{n-1}{4\times n}\times \frac{2^{n-2}-1}{2^{n-1}-1}\\ {}=\frac{\left(3\times n-1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\end{array}}$ and ${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {RG}_{u_2}\left[A(1)\right]\right]\\ {}=\frac{2^{n-2}-1}{2^{n-1}-1}\times \frac{1}{4}+\frac{1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times \frac{1}{4}+\frac{n-1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times T\left[{P}_1\oplus {RP}_2\left[A(1)\right]\right]\\ {}=\frac{2^{n-2}-1}{2^{n-1}-1}\times \frac{1}{4}+\frac{1}{n}\times \left(1-\frac{2^{n-2}-1}{2^{n-1}-1}\right)\times \frac{1}{4}\\ {}=\frac{1}{4\times n}+\frac{n-1}{4\times n}\times \frac{2^{n-2}-1}{2^{n-1}-1}\\ {}=\frac{\left(n+1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\end{array}}$.

Forwardly, the contrast is $\alpha =\frac{T\left[{G}_{u_1}\oplus {RG}_{u_2}\left[A(0)\right]\right]-T\left[{G}_{u_1}\oplus {RG}_{u_2}\left[A(1)\right]\right]}{1+T\left[{G}_{u_1}\oplus {RG}_{u_2}\left[A(1)\right]\right]}=\frac{\left(n-1\right)\times {2}^{n-1}}{\left(9\times n+1\right)\times {2}^{n-2}-5\times n}$.

To show that the theoretical contrast is close to the experimental result, we give the comparison table, see Table 2, with different cases.

Table 2 Contrast values of reconstructed authentication image and theoretical values

4 The proposed (k,n) VSS scheme with cheating prevention

In this section, the proposed (k,n) RG-based VSS scheme with cheating prevention is described as follows. The experimental results and performance analysis are shown after it.

4.1 The proposed scheme

Because, in the proposed (2,n) scheme in Section 3, the generated random-grids have a property that authentication can be performed between each two random-grids, we expect that the property will also work on our (k,n) scheme. The proposed scheme is mainly disported to three phases: (2,n) generation for the authentication image and a random image, encoding the secret image by a (k,n) scheme, and cheating-prevention (k,n) generation.

• Phase 1: Gererate (2,n) random-grids

Input a random image and an authentication image, A, to perform the proposed (2,n) prevention scheme in Section 3, and denote the n grids by P₁, P₂, …, P_n.

• Phase 2: Gererate (k,n) random-grids

Input the secret image, S, to perform the (k,n) scheme in Ref. [5], and denote the n grids by Q₁, Q₂, …, Q_n.

• Phase 3: Gererate (k,n) final random-grids by distributing P₁ and P₂ into G_m, where m = 1,2,…,n

Randomly insert some pixels of P₁, P₂, …, P_n into Q₁, Q₂, …, Q_n, and the renewed n grids of Q₁, Q₂, …, Q_n are regarded as final output random-grids, denoted by G₁, G₂, …, G_n.

The concept of the proposed scheme is shown in Fig. 7.

Fig. 7

The concept of the proposed (k,n) scheme

The algorithm of the proposed encoding process is briefly illustrated as follows.

The decoding process directly stacks k or more random-grids to reconstruct the secret image detectable by the human visual system. For each two random-grids, rotating one of them by 90 degrees and stacking will reconstruct the authentication image.

4.2 Experimental results

To demonstrate that the proposed scheme can prevent the collusion attacks and its feasibility, the experimental results are given in this section.

We choose images Fig. 8a as the secret image and Fig. 8b as the authentication image with both size 1024 × 1024. Then, perform the proposed scheme with (3,4) to generate four random-grids Fig. 8c, d, e and f.

Fig. 8

The experimental results of the proposed scheme with (3,4)

4.2.1 Stacking results of (3,4) case

The results of stacking each three random-grids are Fig. 8g, h, i, j and k for stacking all. The authentication results are as Fig. 9a, b, c, d, e and f. Notice that RG₁, RG₂, RG₃ and RG₄ stand for the 90 degree rotated random-grids.

Fig. 9

The authentication of the proposed scheme with (3,4)

4.2.2 Stacking results of (3,4) case with cheating attacks

Next, we implement the collusion attacks of (k,n) introduced in Ref. [14] on the proposed scheme. Suppose that three members, u₁, u₂ and u₃, who have random-grids, G₁, G₂ and G₃, perform the collusion attacks to cheat the rest participant, u₄. According to the analysis of the grid pixels in G₁, G₂ and G₃, the three cheaters can generate an evaluated grid which is similar to G₄ with high probability. Then, input the evaluated image and a determined cheating image, Fig. 10a, and perform the (n,n) scheme, where n = 3, to generate two fake grids, FG₁ and FG₂, as shown in Fig. 10b and c. When u₄ uses G₄ to stack with FG₁ and FG₂, Fig. 10d, u₄ will recover the cheating information. Nevertheless, if u₄ performs the authentication Fig. 10e and f, (s)he will see the authenticating results being different from the authentication image Fig. 8b. Hence, u₄ can tell that FG₁ and FG₂ are fake grids.

Fig. 10

The collusion attacks [14] in the proposed scheme

4.3 Security analysis

4.3.1 Proposition 1 (Security of each random-grid)

Without stacking, each random-grid reveals neither secret information nor authentication information.

Proof

In the proposed (k,n) scheme, for each generated G_m, where m = 1, 2, …, n, it is the random combination of random-grids generated from the proposed (2,n) scheme and Chen and Tsao’s (k,n) scheme [5]. The security of the proposed (2,n) scheme has been proven in Section 3.3, and the security of Chen and Tsao’s scheme is also proved in their thesis. Hence, the security of the combination with the two scheme’s random-grids is also guaranteed.

4.3.2 Proposition 2 (Cheating prevention)

Analyzing with two or more random-grids cannot infer another random-grid.

Proof

Although Chen and Tsao’s (k,n) scheme [5] has been pointed out the insecurity in cheating attacks [14], the proposed scheme randomly combines the random-grids of the proposed (2,n) scheme and Chen and Tsao’s (k,n) scheme. If the attackers do not separate the pixels generated by the proposed (2,n) scheme, the generated fake grid will appear nothing in the authentication process, that is, the cheating attack is not a success. On the other hand, if the attackers intend to guess out the pixels which are generated by Chen and Tsao’s scheme and perform the cheating attacks, the probability of correctness is $\frac{1}{2}$. With the $\frac{1}{2}$ fail guessing, after the authentication process, the fake information or doctoring trail will appear on the authenticating result. Hence, the proposed (k,n) scheme can prevent cheating attacks.

4.4 Contrast analysis

4.4.1 Proposition 1(Contrast of reconstructed secret image)

The contrast of authentication result in the proposed (k,n) scheme is $\alpha =\frac{2^{n-k+1}-\left(n-r+2\right)\times \left(n-r-1\right)}{\left({2}^{n-2}+{2}^{k-2}\right)\times \left(\frac{2^{n+2}+{2}^{n-1}-{2}^{n-r}}{2^{n-1}-1}\right)+{2}^{k-2}\times \left(n-r+1\right)\times \left(n-r\right)}$, where r = 2, 3, …, n is the number of stacked grids.

Proof. Because G₁, G₂, …, G_n are generated by combining the proposed (2,n) scheme and Chen and Tsao’s (k,n) scheme, there is a half stacking result which is same with the proposed (2,n) scheme (or Chen and Tsao’s (k,n) scheme). About the stacking result of the proposed (2,n) scheme, a random grid is used as the secret image. Hence, from the proof of Proposition 2 in Section 3.4, the stacking result’s average light transmission of the proposed (2,n) scheme is $\frac{T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(0)\right]\right]+T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]}{2}=\frac{2^{n-r}+{2}^{n-1}-2}{2^{n+1}-4}$. On the other hand, the stacking result’s average light transmission of Chen and Tsao’s (k,n) scheme is $\frac{1}{2^{k-1}}$ according to white area in the secret image (or 0 to black area). Furthermore, considering the fail stacking in Chen and Tsao’s (k,n) scheme, that is, the stacked pixels being same, the average light transmission is $\frac{1}{2}$, and its probability is $\frac{\left(\begin{array}{c}n-r+1\\ {}2\end{array}\right)}{2^{n-k}+1}$. Therefore, the average light transmission appear ${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(0)\right]\right]\\ {}=\frac{1}{2}\times \left(\frac{2^{n-r}+{2}^{n-1}-2}{2^{n+1}-4}\right)+\frac{1}{2}\times \frac{\left(\begin{array}{c}n-r+1\\ {}2\end{array}\right)}{2^{n-k}+1}\times \frac{1}{2}+\frac{1}{2}\times \left(1-\frac{\left(\begin{array}{c}n-r+1\\ {}2\end{array}\right)}{2^{n-k}+1}\right)\times \frac{1}{2^{k-1}}\\ {}=\frac{1}{2}\times \left(\frac{2^{n-r}+{2}^{n-1}-2}{2^{n+1}-4}\right)+\frac{1}{4}\times \frac{\left(n-r+1\right)\times \left(n-r\right)}{2^{n-k+1}+2}+\frac{1}{2^k}\times \left(1-\frac{\left(n-r+1\right)\times \left(n-r\right)}{2^{n-k+1}+2}\right)\end{array}}$

and

${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]\\ {}=\frac{1}{2}\times \left(\frac{2^{n-r}+{2}^{n-1}-2}{2^{n+1}-4}\right)+\frac{1}{2}\times \frac{\left(\begin{array}{c}n-r+1\\ {}2\end{array}\right)}{2^{n-k}+1}\times \frac{1}{2}+\frac{1}{2}\times \left(1-\frac{\left(\begin{array}{c}n-r+1\\ {}2\end{array}\right)}{2^{n-k}+1}\right)\times 0\\ {}=\frac{1}{2}\times \left(\frac{2^{n-r}+{2}^{n-1}-2}{2^{n+1}-4}\right)+\frac{1}{4}\times \frac{\left(n-r+1\right)\times \left(n-r\right)}{2^{n-k+1}+2}\end{array}}$

Forwardly, the contrast is

${\displaystyle \begin{array}{l}\alpha =\frac{T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(0)\right]\right]-T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]}{1+T\left[{G}_{u_1}\oplus {G}_{u_2}\oplus \cdots \oplus {G}_{u_r}\left[S(1)\right]\right]}\\ {}=\frac{2^{n-k+1}-\left(n-r+2\right)\times \left(n-r-1\right)}{\left({2}^{n-2}+{2}^{k-2}\right)\times \left(\frac{2^{n+2}+{2}^{n-1}-{2}^{n-r}}{2^{n-1}-1}\right)+{2}^{k-2}\times \left(n-r+1\right)\times \left(n-r\right)}\end{array}}$

To show that the theoretical contrast is close to the experimental result, we give the comparison table, Table 3, with different cases.

Table 3 Contrast values of reconstructed secret image and theoretical values

4.4.2 Proposition 2 (Contrast of authentication result)

The contrast of authentication result in the proposed (k,n) scheme is $\alpha =\frac{\left(n-k+1\right)\times \left(n-1\right)\times {2}^{n-1}}{\left(n-k+1\right)\times \left(39\times n+1\right)\times {2}^{n-2}-10\times n\times \left(2\times n-2\times k+1+{2}^{n-1}\right)}$.

Proof. Because G₁, G₂, …, G_n are generated by combining the proposed (2,n) scheme and Chen and Tsao’s (k,n) scheme, there exist half pixels belonging to Q₁, Q₂, …, Q_n generated by Chen and Tsao’s (k,n) scheme. Q₁, Q₂, …, Q_n have no authentication information. Therefore, after rotating and stacking for authenticating with each two random-grids, the half part’s average light transmission is $\frac{1}{2}\times \frac{1}{2}$. And the authentication result of the other half pixels is related to the authentication result of the proposed (2,n) scheme. In this half part, there exist some pixels which fail to reconstruct the authentication image (wrong rotating way) with probability $\frac{n-k}{2\times n-2\times k+1}$, and its average light transmission is $\frac{1}{2}\times \frac{1}{2}$. Then, the authenticating result of the rest part is same with the proposed (2,n) scheme, and the average light transmission is equal to $T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(0)\right]\right]$ and $T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(1)\right]\right]$ (see the proof of Proposition 3 in Section 3.4). Hence, the average light transmission appears${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(0)\right]\right]\\ {}=\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \frac{n-k}{2\times n-2\times k+1}\times \frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \left(1-\frac{n-k}{2\times n-2\times k+1}\right)\times \frac{\left(3\times n-1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\\ {}=\frac{1}{8}+\frac{1}{8}\times \frac{n-k}{2\times n-2\times k+1}+\frac{1}{2}\times \frac{n-k+1}{2\times n-2\times k+1}\times \frac{\left(3\times n-1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\end{array}}$

and

${\displaystyle \begin{array}{l}T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(1)\right]\right]\\ {}=\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \frac{n-k}{2\times n-2\times k+1}\times \frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \left(1-\frac{n-k}{2\times n-2\times k+1}\right)\times \frac{\left(n+1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\\ {}=\frac{1}{8}+\frac{1}{8}\times \frac{n-k}{2\times n-2\times k+1}+\frac{1}{2}\times \frac{n-k+1}{2\times n-2\times k+1}\times \frac{\left(n+1\right)\times {2}^{n-2}-n}{n\times {2}^{n+1}-4\times n}\end{array}}$Forwardly, the contrast is

$$ {\displaystyle \begin{array}{l}\alpha =\frac{T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(0)\right]\right]-T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(1)\right]\right]}{1+T\left[{G}_{u_1}\oplus R{G}_{u_2}\left[A(1)\right]\right]}\\ {}=\frac{\left(n-k+1\right)\times \left(n-1\right)\times {2}^{n-1}}{\left(n-k+1\right)\times \left(39\times n+1\right)\times {2}^{n-2}-10\times n\times \left(2\times n-2\times k+1+{2}^{n-1}\right)}\end{array}} $$

To show that the theoretical contrast is close to the experimental result, we give the comparison table, Table 4, with different cases.

Table 4 Contrast values of reconstructed authentication image and theoretical values

5 Further discussion

Carry on the demonstration of contract and security analyses in Sections 3 and 4, it’s worthwhile to highlight the difference and advantages of the proposed schemes compared with the related work.

Firstly, the proposed scheme does not maintain any extra share like Ref. [9, 10]. Secondly, the pixel expansion is avoided compared to the tradition VSS scheme. Thirdly, the computation cost in the encoding phase is very low compared to Ref. [22] while the decoding phase involves no computation cost. The comparison between the proposed schemes and the related cheating prevention schemes in Ref. [9, 10, 22] is shown in Table 5.

Table 5 Comparison between the related cheating prevention schemes and the proposed schemes

6 Conclusion

In this paper, we propose two threshold RG-based VSS schemes with cheating prevention for cases (2,n) and (k,n). To prevent cheating attacks, each two random grids can perform the authentication process in both proposed schemes, and the fake grids will be detected. The experimental results and the analysis of security and contrast show that the proposed method is efficient and practical.