Visual Cryptography and Random Grids Schemes

Abstract

Visual Cryptography (VC) and Random Grids (RG) are both visual secret sharing (VSS) techniques, which decode the secret by stacking some authorized shares. It is claimed that RG scheme benefits more than VC scheme in terms of removing the problems of pixel expansion, tailor-made codebook design, and aspect ratio change. However, we find that the encryption rules of RGS are actually the matrices sets of probabilistic VCS. The transformation from RGS to PVCS is proved and shown by means of giving theoretical analysis and conducting some specific schemes. The relationship between codebook and computational complexity are analyzed for PVCS and RGS. Furthermore, the contrast of PVCS is no less than the one of RGS under the same access structure, which is shown by experimental results.

1 Introduction

Visual secret sharing (VSS) techniques encrypt a secret image into several meaningless share images, and decrypt the secret by overlapping the some authorized shares. Due to the ease of decoding, VSS provides some new and secure imaging applications, e.g., visual authentication, steganography, and image encryption.

Visual cryptography scheme (VCS) was introduced by Naor and Shamir in Euro-crypt’94 [1]. The difference between visual cryptography and the traditional secret sharing schemes [2, 3] is the decryption process. Most secret sharing schemes are mainly realized by the computer, while visual cryptography schemes can decrypt secrets only with human eyes. In recent years, the studies of VCS focus on the general access structure [4], the optimization of the pixel expansion and the relative difference [5–8], and the grey and color images [9–12], etc.

In order to design the unexpanded shares, Ito et al. [13] firstly introduced a scheme without pixel expansion. Yang et al. [14, 15] provided a new model of visual cryptography scheme, in which the reconstruction of the secret image was probabilistic. In probabilistic model, the secret pixel is correctly reconstructed with probability. Thus, the quality of the reconstructed images depends on how big the probability is. The probabilistic scheme differs from the traditional VCS, which is now called deterministic scheme. The deterministic means that a white (black) original pixel can be represented in the reconstructed image by a set of subpixels with certain whiteness (blackness). Cimato et al. [16] introduced how to trade pixel expansion for the probability of a good reconstruction, which can be seen as a generalization of both the classical deterministic model and the probabilistic model.

Another VSS scheme is realized by Random Grids, which was proposed by Kafri and Keren in 1987 [17]. A binary secret image is encoded into two meaningless grids, which have the same size as the secret image. RG scheme (RGS) is mainly realized by using three different functions (f _ran , f _equ , f _com ) recursively, and has no requirement of codebook which is the basis of VCS. Inspired of Kafri and Keren [17], Shyu [18] presented the other two RGSs to encrypt gray-level and color images in 2007. Later, Shyu [19] and Chen et al. [20, 21] proposed (2, n), (n, n) and (k, n) RGSs, which made further research.

In this paper, we mainly analyze the relationship between VCS and RGS, which is considered for the first time. It is found that the encryption rules of RGS are actually the set of distribution matrices in PVCS. In other words, there always exists a PVCS corresponding to every RGS. On the other hand, the corresponding RGS for every PVCS can not been guaranteed. Furthermore, the cost and contrast comparisons between RGS and PVCS are discussed in detail.

The rest of this paper is organized as follows. Section 2 briefly reviews RGS and PVCS. As the main part of this paper, Sect. 3 analyzes how to transform RGS into PVCS. Section 4 shows experimental results and discussions about the parameters of RGS and PVCS. Section 5 concludes the paper.

2 Related Studies

Prior to describing the proposed scheme, the reviews of RGS and PVCS are briefly introduced.

2.1 Random Grids Scheme

RGS mainly consists of three operations: (1) randomization, (2) complement, and (3) equivalence. The detailed definitions are given below.

Definition 1

(randomization) [20]. A random bit generation function

$$ f_{ran} (.) = \left\{ {\begin{array}{*{20}l} 0 & {with\;the\;probability\;0.5} \\ 1 & {with\;the\;probability\;0.5} \\ \end{array} } \right. $$

is used to create the pixel of cipher-grid. Precisely, a certain pixel r of a grid R is assigned the value 0 or 1 to represent the color white or black with the same probability 1/2. In other words, r = f _ran (.) means P(r = 1) = P(r = 0) = 1/2.

Definition 2

(complement) [20]. According to a pixel r ₁ of grid, say R ₁, the complement function

$$ f_{com} (x) = \left\{ {\begin{array}{*{20}l} 0 & {if\;x = 1} \\ 1 & {if\;x = 0} \\ \end{array} } \right. $$

turns r ₁ inversely and assigns the inversed pixel value to a pixel r ₂ of the other grid, say R ₂. For instance, if r ₁ is 0, the pixel value r ₂ = 1 is obtained, i.e., r ₂ = f _com (r ₁ = 0) = 1.

Definition 3

(equivalence) [20]. The equivalence function

$$ f_{equ} (x) = \left\{ {\begin{array}{*{20}l} 0 & {if\;x = 0} \\ 1 & {if\;x = 1} \\ \end{array} } \right. $$

referring to a pixel r ₁ of grid R ₁ assigns the same pixel value to a pixel r ₂ of the other grid R ₂. For instance, if r ₁ is 0, the pixel value r ₂ = 0 is obtained. In other words, r ₂ = f _equ (r ₁ = 0) = 0.

Definition 4

(Representation of corresponding area) [20]. Assume that A(0) (resp. A(1)) is the corresponding area of all the white (resp. black) pixels in the secret image A, where A = A(0) ∪ A(1) and A(0) ∩ A(1) = ∅. Hence, B[A(0)] (resp. B[A(1)]) is the corresponding area of all the white (resp. black) pixels in the binary image B, which is reconstructed by the VSS scheme based on RG, with respect to the secret image A.

Definition 5

(Average light transmission) [20]. For a certain pixel r in a binary image B, the light transmission of a white (resp. black) pixel is defined as t(r) = 1 (resp. 0). In addition, for B with the size of h × w, the average light transmission of B is defined as

$$ T(B) = \frac{1}{h \times w} \cdot \sum\limits_{i = 1}^{h} {\sum\limits_{j = 1}^{w} {t(r[i,j])} } . $$

Definition 6

(Contrast) [20]. The contrast of the superimposed binary image B with respect to the original secret image A is,

$$ \alpha = \frac{T(B[A(0)]) - T(B[A(1)])}{1 + T(B[A(1)])}. $$

$\alpha$ would be as large as possible. In other words, the larger the value of $\alpha$, the more recognizable the superimposed secret will be.

Since the recovery of the secret images depends on the human visual system, the contrast of superimposed secret images plays a critical role in guaranteeing that the superimposed image can be visually recognized as the exact secret message. Consequently, the following definition is given.

Definition 7

(Visually recognizable) [20]. The reconstructed binary image B with respect to the original secret A by superimposing two RG is visually recognizable in the sense, at least, that its contrast is greater than or equal to a threshold value which is greater than zero. In principle, if the reconstructed binary image can be recognizable, $\alpha$ must be greater than zero. The numerator of $\alpha$ is T(B[A(0)]) − T(B[A(1)]) that causes $\alpha$ to be a non-zero value. Therefore, if T(B[A(0)]) is greater than T(B[A(1)]), B is visual recognizable. On the contrary, if T(B[A(0)]) is equal to or less than T(B[A(1)]), B is meaningless.

2.2 Probabilistic Visual Cryptography Scheme

In a probabilistic scheme, the recovery property cannot be guaranteed. Each pixel can be correctly reconstructed only with a probability given as a parameter of the scheme. Given a qualified set of participants Q, let p _i|j denote the probability of having a reconstructed pixel i, and the corresponding pixel in the secret image is j, where i, j ∈ {0, 1}. Then p _0|0 (Q) denotes the probability of correctly reconstructing a white pixel when stacking the shares of Q, and p _1|0 (Q) is the probability of incorrectly reconstructing a white pixel. In a similar way p _1|1 (Q) and p _0|1 (Q) can be defined. The formal definition of a β-probabilistic visual cryptography scheme is as follow.

Definition 8

(Probabilistic VCS) [15]. A (Γ _Qual, Γ _Forb, m, β) -PVCS consists of two collections of n × m binary matrices, C ₀ and C ₁, satisfying the following properties:

1. (Contrast property) For any set Q =  {i ₁, i ₂, …, i _q } ∈ Γ _Qual , there exists β > 0 such that p _1|1 (Q) − p _1|0 (Q) ≥ β and p _0|0 (Q) − p _0|1 (Q) ≥β

2. (Security property) For any set F =  {i ₁, i ₂, …, i _f } ∈ Γ _Forb , the two collections of f × m matrices D _t, with t ∈ {0, 1}, obtained by restricting each n × m matrix in C _t to rows i ₁, i ₂, …, i _p are indistinguishable in the sense that they contain the same matrices with the same frequencies.

In this paper, we mainly use PVCS scheme with no pixel expansion, that is having m = 1. Suppose $C_{0} = \{ M_{0}^{1} ,M_{0}^{2} , \cdots ,M_{0}^{c0} \}$, $C_{1} = \{ M_{1}^{1} ,M_{1}^{2} , \cdots ,M_{1}^{c1} \}$, S[i, j] is the i-th row and j-th column pixel in secret image S, n shares denoted as {R ₁, R ₂, …, R _n }. The secret sharing algorithm of PVCS only needs two steps: select and distribute.

Select::

if S[i, j] = 0, generate a random number k ∈ [1, …, c ₀], $M = M_{0}^{k}$.

else S[i, j] = 1, generate a random number k ∈ [1, …, c ₁], $M = M_{1}^{k}$.

Distribute: (R ₁[i, j], R ₂[i, j], …, R _n [i, j])^T = M.

Example 1.

(2, 2) -PVCS

$C_{0} = \left\{ {\left[ {\begin{array}{*{20}c} 1 \\ 1 \\ \end{array} } \right],\left[ {\begin{array}{*{20}c} 0 \\ 0 \\ \end{array} } \right]} \right\}$,$C_{1} = \left\{ {\left[ {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array} } \right],\left[ {\begin{array}{*{20}c} 0 \\ 1 \\ \end{array} } \right]} \right\}$. For this scheme, m = 1, p _1|1 = 1, p _1|0 = 1/2, p _0|0 = 1/2, p _0|1 = 0, and β = p _1|1 − p _1|0 = p _0|0 − p _0|1 = 1/2.

3 A Transformation from RGS to PVCS

In RGS, the random grids are with the same size of the original secret image. The sharing algorithm of RGS relies on iterations and loops, which has no requirement of designing a codebook. Although RGS is called removing the problems of pixel expansion, tailor-made codebook design, and aspect ratio change in VCS [20], we find that the encryption rules of RGS are actually the matrices sets of PVCS. In this section we will show how to transform a RGS into a PVCS with the same contrast and security.

Definition 9

(sets of encryption rules). Let E ₀ = {f ₁, f ₂, …, f _e0} and E ₁ = {g ₁, g ₂, …, g _e1} be two sets, where f _i and g _j are both n × 1 Boolean vector (i ∈ [1, …, e ₀], j ∈ [1, …, e ₁]). f _i denotes the i-th encryption rule by which a white pixel is encrypted, while g _j denotes the j-th encryption rule by which a black pixel is encrypted. We call E ₀ and E ₁ the sets of encryption rules, which represent all of the encryption rules of a RGS.

Definition 10.

r denotes a random Boolean number, where r = 0 or 1 with the same probability 1/2. Let [r] denote two 1 × 1 matrices [1] and [0]. Suppose x is a Boolean number, let $\left[ \begin{gathered} r \\ x \\ \end{gathered} \right]$ denote two 2 × 1 matrices $\left[ \begin{gathered} 0 \\ x \\ \end{gathered} \right]$ and $\left[ \begin{gathered} 1 \\ x \\ \end{gathered} \right]$. Suppose r ₁ is another random Boolean number which is independent with r, let $\left[ \begin{gathered} r \\ r_{1} \\ \end{gathered} \right]$ denote four 2 × 1 matrices $\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]$, $\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right]$, $\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right]$ and $\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right]$. Suppose M = {M ₁, M ₂, …, M _m } is a set of n × 1 matrices, let $\left[ \begin{gathered} r \\ M \\ \end{gathered} \right]$ denote 2m (n + 1) × 1 matrices $\left[ \begin{gathered} 0 \\ M_{1} \\ \end{gathered} \right]$, $\left[ \begin{gathered} 1 \\ M_{1} \\ \end{gathered} \right]$, $\left[ \begin{gathered} 0 \\ M_{2} \\ \end{gathered} \right]$, $\left[ \begin{gathered} 1 \\ M_{2} \\ \end{gathered} \right]$,…, $\left[ \begin{gathered} 0 \\ M_{m} \\ \end{gathered} \right]$, $\left[ \begin{gathered} 1 \\ M_{m} \\ \end{gathered} \right]$.

3.1 (2, 2)-RGS

Chen et al. proposed three different kinds of (2, 2)-RGSs, which were the basic model of RGS. In this section, we firstly analyze the sets of encryption rules of (2, 2)-RGS, and then prove that E ₀ and E ₁ are also the sets of distribution functions.

Algorithm 1.

(2, 2) ₁ -RGS [20]

Input: A binary secret image S = {S[i, j]| S[i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]}

Output: Two cipher-grids R ₁ = {R ₁[i, j]| R ₁[i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]} and R ₂ = {R ₂[i, j]| R ₂[i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]}

Step 1. R ₁[i, j] = f _ran (.), for all i and j. // Create R ₁ as a cipher-grid

Step 2. R ₂[S(0)] = f _equ (R ₁[S(0)]). // Create the white area of R ₂ corresponding to S by R ₁

Step 3. R ₂[S(1)] = f _com (R ₁[S(1)]). //Create the black area of R ₂ corresponding to S by R ₁

The construction of encryption rules of Algorithm 1 will be described in detail, which is in accordance with the steps in Algorithm 1. The construction is as follows.

Step 1. $E_{0} = \left\{ {[r]} \right\},E_{1} = \left\{ {[r]} \right\}R_{1}$, where r is a random Boolean number.

Step 2. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$.

Step 3. $E_{1} = \left\{ {\left[ \begin{gathered} r \\ {\bar{r}} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$, where $\bar{r}$ is the complement of r.

Since r ∈ {0,1}, we have $E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$ finally.

Theorem 1.

E ₀ and E ₁ of (2, 2)₁-RGS are the sets of distribution functions of (2, 2)-PVCS.

Proof.

(1) Contrast property. For two participants, p _1|1 = 1, p _1|0 = 1/2, p _0|0 = 1/2 and p _0|1 = 0. There exist β = 1/2 satisfying p _1|1 − p _1|0 ≥ β and p _0|0 (Q) − p _0|1 (Q) ≥ β. Therefore, E ₀ and E ₁ satisfy the contrast property of Definition 2.

(2) Security property. For single participant, let D _t (t ∈ {0, 1}) denote the set of matrices, obtained by restricting each n × 1 matrix in E _t to the single row. Since D ₀ = D ₁ = {[0], [1]}, E ₀ and E ₁ satisfy the security property of Definition 2.

To sum up, E ₀ and E ₁ are the sets of distribution functions of (2, 2)-PVCS. ∎

Algorithm 2.

(2, 2) ₂ -RGS [20]

Input and Output are as same as Algorithm 1.

Step 1. R ₁[i, j] = f _ran (.), for all i and j. // Create R ₁ as a cipher-grid

Step 2. R ₂[S(0)] = f _equ (R ₁[S(0)]). // Create the white area of R ₂ corresponding to S by R ₁

Step 3. R ₂[S(1)] = f _ran (.), for all i and j. // Create the black area of R ₂ corresponding to S

The construction of encryption rules of Algorithm 2 is as follows.

Step 1. $E_{0} = \left\{ {[r]} \right\},E_{1} = \left\{ {[r]} \right\}R_{1}$, where r is a random Boolean number.

Step 2. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$.

Step 3. $E_{1} = \left\{ {\left[ \begin{gathered} r \\ r_{1} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$, and r ₁ is another random number, which is independent with r.

Since r ∈ {0,1} and r ₁ ∈ {0,1}, $E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$ can be gotten.

Theorem 2.

E ₀ and E ₁ of (2, 2)₂-RGS are the sets of distribution functions of (2, 2)-PVCS.

Proof.

(1) Contrast property. For two participants, p1|1 = 3/4, p1|0 = 1/2, p0|0 = 1/2 and p0|1 = 1/4. There exist β = 1/4 satisfying p1|1 − p1|0 ≥ β and p0|0 (Q) − p0|1 (Q) ≥ β. Therefore, E0 and E1 satisfy the contrast property of Definition 2.

(2) Security property. For single participant, let D _t (t ∈ {0, 1}) denote the set of matrices, obtained by restricting each n × 1 matrix in E _t to the single row. Since D ₀ = {[0], [1]} and D ₁ = {[0], [0], [1], [1]}, D ₀ and D ₁ contain the same matrices ([0], [1]) with the same frequencies (1/2). Therefore, E ₀ and E ₁ satisfy the security property of Definition 2.

To sum up, E ₀ and E ₁ are the sets of distribution functions of (2, 2)-PVCS. ■

Algorithm 3.

(2, 2) ₃ -RGS [20]

Input and Output are as same as Algorithm 1.

Step 1. R ₁[i, j] = f _ran (.), for all i and j. // Create R ₁ as a cipher-grid

Step 2. R ₂[S(0)] = f _ran (R ₁[S(0)]). // Create the white area of R ₂ corresponding to S by R ₁

Step 3. R ₂[S(1)] = f _com (.), for all i and j. // Create the black area of R ₂ corresponding to S

The construction of encryption rules of Algorithm 3 is as follows.

Step 1. $E_{0} = \left\{ {[r]} \right\},E_{1} = \left\{ {[r]} \right\}R_{1}$, where r is a random Boolean number.

Step 2. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r_{1} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$, and r ₁ is another random number, which is independent with r.

Step 3. $E_{1} = \left\{ {\left[ \begin{gathered} r \\ {\bar{r}} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$, where $\bar{r}$ is the complement of r.

Since r ∈ {0,1} and r ₁ ∈ {0,1}, $E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$ can be gotten.

Theorem 3.

E ₀ and E ₁ of (2, 2)₃-RGS are the sets of distribution functions of (2, 2)-PVCS.

The proof is like as the proof of Theorem 2.

3.2 (n, n)-RGS

In this section, the n-out-of-n RGS is discussed. It is extended from the (2, 2)-RGS to form a general model. When encrypting the secret image into n cipher-grids, the (n, n)-RGS will recall the (2, 2)₁-RGS (n − 1) times.

Algorithm 4.

( n, n )-RGS [20]

Input: A binary secret image: S = {S[i, j]| S[i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]} and a number of cipher-grids: n.

Output: n cipher-grids: R _k  = {R _k [i, j]| R _k [i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]}, where k = 1, 2,…, n

Step 1. R ₁||ℜ₂ = (2, 2)₁-RGS(S). // Create R ₁, ℜ₂ as two cipher-grids

Step 2. If (n > 2) { for k = 2 to n − 1 R _k || ℜ _k+1 = (2, 2)₁-RGS(ℜ _k )} // Create R ₂ ~ R _n − 1 as cipher-grids recursively

Step 3. R _n  = ℜ _n . // Create R _n as the last cipher-grid

The construction of encryption rules of Algorithm 4 is as follows.

Step1. $E_{0}^{2} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1}^{2} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {\Re_{2} } \\ \end{array}$.

Step2. $E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ E_{1}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ E_{0}^{2} \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ E_{0}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ E_{1}^{2} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {\Re_{2} } \\ \end{array} .$

$$ \Rightarrow E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ {\Re_{3} } \\ \end{array} . $$

Step2’. $E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ E_{0}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ E_{1}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ E_{1}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ E_{0}^{2} \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ E_{1}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ E_{0}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ E_{0}^{2} \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ E_{1}^{2} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ {\Re_{3} } \\ \end{array}$

$$ \Rightarrow E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ 0 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ {R_{3} } \\ {\Re_{4} } \\ \end{array} , $$

$$ E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ R_{2} \\ R_{3} \\ {\Re_{4} } \\ \end{array} . $$

……

Step 3. E ₀ is the set of all Boolean vectors of length n with an even number of ones, and E ₁ is the set of all Boolean vectors of length n with an odd number of ones. Hence, | E ₀| = | E ₁|= 2^n − 1.

Theorem 4.

E ₀ and E ₁ of (n, n)-RGS are the sets of distribution functions of (n, n)-PVCS.

Proof.

(1) Contrast property. For n participants, p _1|1 = 1, p _1|0 = 1 – 2^1 − n, p _0|0 = 2^1 − n and p _0|1 = 0. There exist β = 2^1 − n satisfying p _1|1 − p _1|0 ≥ β and p _0|0 (Q) − p _0|1 (Q) ≥ β. Therefore, E ₀ and E ₁ satisfy the contrast property of Definition 2.

(2) Security property. Let B ₀ (resp. B ₁) be a n × 2^n − 1 matrix, which is constructed by connecting all vectors of E ₀ (resp. E ₁). It is interesting that B ₀ and B ₁ are the basis matrices of (n, n)-VCS proposed by Naor and Shamir [1]. Therefore, E ₀ and E ₁ satisfy the security property of Definition 2.

To sum up, E ₀ and E ₁ are the sets of distribution functions of (n, n)-PVCS. ∎

3.3 (2, n)-RGS

In this section, the 2-out-of-n RGS is analyzed. Assume a secret image S will be encrypted into n cipher-grids R ₁, R ₂, …, R _n . The decryption process is superimposing directly any pair of cipher-grids and the original secret can be disclosed.

Algorithm 5.

(2, n )-RGS [20]

Input: A binary secret image: S = {S[i, j]| S[i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]} and a number of cipher-grids: n.

Output: n cipher-grids: R _k  = {R _k [i, j]| R _k [i, j] ∈ {0, 1}, i ∈ [1, 2,…, h], j ∈ [1, 2, …, w]}, where k = 1, 2,…, n

Step 1. R ₁[i, j] = f _ran (.), for all i and j. // Create R ₁ as a cipher-grids

Step 2. For k = 2 to n // Create R ₂ ~ R _n as cipher-grids repeatedly

$$ \begin{gathered} R_{k} [S\left( 0 \right)] = f_{equ} (R_{k\,-\,1} [S\left( 0 \right)])\;//{\text{Create}}\;{\text{the}}\;{\text{white}}\;{\text{area}}\;{\text{of}}\;R_{k} \\ R_{k} [S\left( 1 \right)] = f_{ran} \left( . \right)\;{\text{for}}\;{\text{all}}\;i\;{\text{and}}\;j\;//{\text{Create}}\;{\text{the}}\;{\text{black}}\;{\text{area}}\;{\text{of}}\;R_{k} \\ \end{gathered} $$

The construction of encryption rules of Algorithm 5 is as follows.

Step1. $E_{0} = \left\{ {\left[ r \right]} \right\},E_{1} = \left\{ {\left[ r \right]} \right\}R_{1}$

Step2. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} r \\ r_{1} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array}$

$$ \Rightarrow E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ {R_{2} } \\ \end{array} $$

Step3. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r \\ r \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} r \\ r_{1} \\ r_{2} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ R_{2} \\ R_{3} \\ \end{array}$ $\Rightarrow E_{0} = \left\{ {\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ \end{gathered} \right]} \right\},$

$$ E_{1} = \left\{ {\left[ \begin{gathered} 1 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 0 \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ R_{2} \\ R_{3} \\ \end{array} $$

……

Step n. $E_{0} = \left\{ {\left[ \begin{gathered} r \\ r \\ \ldots \\ r \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} r \\ r_{1} \\ \ldots \\ r_{n - 1} \\ \end{gathered} \right]} \right\}\begin{array}{*{20}c} {R_{1} } \\ R_{2} \\ \ldots \\ R_{n} \\ \end{array}$. r, r ₁, …, r _n − 1 are random Boolean numbers, where any one of them is independent with others. Hence, | E ₁| = 2 and | E ₁| = 2ⁿ.

Theorem 5.

E ₀ and E ₁ of (2, n)-RGS are the sets of distribution functions of (2, n)-PVCS.

Proof.

(1) Contrast property. For two participants, p1|1 = 3/4, p1|0 = 1/2, p0|0 = 1/2 and p0|1 = 1/4. There exist β=1/4 satisfying p1|1 − p1|0 ≥ β and p0|0 (Q) − p0|1 (Q) ≥ . Therefore, E0 and E1 satisfy the contrast property of Definition 2.

(2) Security property. For single participant, let D _t (t ∈ {0, 1}) denote the set of matrices, obtained by restricting each n × 1 matrix in E _t to the single row. Since D _0 = {[0], [1]} and D ₁ consists of 2ⁿ⁻¹ [0] and 2ⁿ⁻¹ [1], D ₀ and D ₁ contain the same matrices ([0], [1]) with the same frequencies (1/2). Therefore, E ₀ and E ₁ satisfy the security property of Definition 2.

To sum up, E ₀ and E ₁ are the sets of distribution functions of (2, n)-PVCS. ∎

3.4 (k, n)-RGS

In this section, (k, n)-RGS can encode a binary secret image S with the size of h × w into n random grids, denoted as {R ₁, R ₂, …, R _n }, which are so noise-like that no one can recognize the original secret information by any set of less than k random grids. In the decoding process, if participants collect and superimpose k or more random grids, denoted as {R _i1, R _i2, …, R _ik } where {i ₁, i ₂,…, i _k } ⊆ {1, 2,…, n}, the secret information can be disclosed by human visual system without extra computation cost.

Algorithm 6.

( k, n )-RGS [21]

Step 1. Exploit traditional RGS to encode a pixel S[i, j] ∈ S so that two bits R ₁ and ℜ₂ are obtained, [i, j] being the pixel position in the secret image (i ∈ [1, … , h] and j ∈ [1, … , w]). Encode ℜ₂ in the same way to generate two bits R ₂ and ℜ₃. Repeat this operation until R ₁, R ₂, …, ℜ _k are generated (the final bit ℜ _k represented as R _k ).

Step 2. The generated k bits are dispatched into k randomly selected random grid pixels { R _i1[i, j], R _i2[i, j], … , R _ik [i, j]}, a subset of { R ₁[i, j], R ₂[i, j], … , R _n [i, j]}; these k bits are arranged at the same spatial location, say [i, j], in the individual random grids R _i1, R _i2 , …, and R _ik .

Step 3. Lastly, the (n − k) bits located in the same location [i, j] of the remaining (n−k) random grids { R ₁, R ₂, … , R _n} − { R _i1, R _i2 , …, R _ik } are generated by the function f _ran (.) used to randomly select “0” or “1”, representing a transparent or opaque pixel, respectively.

Step 4. Repeat Steps 1~3 until all pixels S[i, j] of secret image S are done.

The construction of encryption rules of Algorithm 6 is as follows.

$$ E_{0} = \left\{ {\left[ \begin{gathered} E_{0}^{k} \\ r_{1,1} \\ r_{1,2} \\ \ldots \\ r_{1,n - k} \\ \end{gathered} \right],\left[ \begin{gathered} r_{2,1} \\ E_{0}^{k} \\ r_{2,2} \\ \ldots \\ r_{2,n - k} \\ \end{gathered} \right], \ldots ,\left[ \begin{gathered} r_{C(n,k),1} \\ r_{C(n,k),2} \\ \ldots \\ r_{C(n,k),n - k} \\ E_{0}^{k} \\ \end{gathered} \right]} \right\},E_{1} = \left\{ {\left[ \begin{gathered} E_{1}^{k} \\ r_{1,1} \\ r_{1,2} \\ \ldots \\ r_{1,n - k} \\ \end{gathered} \right],\left[ \begin{gathered} r_{2,1} \\ E_{1}^{k} \\ r_{2,2} \\ \ldots \\ r_{2,n - k} \\ \end{gathered} \right], \ldots ,\left[ \begin{gathered} r_{C(n,k),1} \\ r_{C(n,k),2} \\ \ldots \\ r_{C(n,k),n - k} \\ E_{1}^{k} \\ \end{gathered} \right]} \right\}. $$

$E_{0}^{k}$ and $E_{1}^{k}$ are the encryption rules of (n, n)-RGS in Algorithm 4.

| E ₀| = | E ₁| = C(n, k) × 2^k − 1 × 2^n − k = C(n, k) × 2^n− 1.

Theorem 6.

E ₀ and E ₁ of (k, n)-RGS are the sets of distribution functions of (k, n)-PVCS.

Proof.

(1) Contrast property. For k participants, p _1|1 − p _1|0 = $\frac{1}{{C(n,k) \times 2^{n - 1} }}$. Since p _0|1 = 1 − p _1|1 and p _0|0 = 1 − p _1|0, we have β = p _0|0 −  p _0|1 =  p _1|1 − p _1|0 = $\frac{1}{{C(n,k) \times 2^{n - 1} }}$. Therefore, E ₀ and E ₁ satisfy the contrast property of Definition 2.

(2) Security property. For k − 1 participant, let D _t (t ∈ {0, 1}) denote the set of matrices, obtained by restricting each n × 1 matrix in E _t to the k − 1 rows. Every matrix of D ₀ (resp. D ₁) has the character that i (i ∈ [0,…, k − 1]) rows are from $E_{0}^{k}$(resp. $E_{1}^{k}$) and the other k – 1 − i rows are random Boolean numbers. According to the security of $E_{0}^{k}$ and $E_{1}^{k}$, we have $D_{0}^{i} = D_{1}^{i}$ for any i (i ∈ [0,…, k–1]) participants. Therefore, D ₀ =  D ₁, which means that E ₀ and E ₁ satisfy the security property of Definition 2.

To sum up, E ₀ and E ₁ are the sets of distribution functions of (k, n)-PVCS. ∎

4 Experimental Results and Discussions

4.1 Codebook and Computational Complexity

The encryption of PVCS relies on codebook C ₀ and C ₁, which is easy to generate shares but needs more storage space costs than RGS. The encryption of RGS is realized by several recursive computing steps, which does not need codebook but requires more computing resources than PVCS.

Generally speaking, the complexity evaluation of an algorithm contains two aspects: space and time. PVCS and RGS are just good at one point, respectively. In some sense, PVCS and RGS are complementation for each other.

4.2 Contrasts of PVCS and RGS

The evaluation of contrast property in PVCS is $\beta$ = p _0|0 − p _0|1. In RGS, the recovery image is evaluated by $\alpha = \frac{T(B[A(0)]) - T(B[A(1)])}{1 + T(B[A(1)])}$. α is used for measuring decrypted image as a whole. Since each pixel in original image is encrypted independently, we have $T(B[A(0)]) = p_{0|0}$ and $T(B[A(1)]) = p_{0|1}$. Therefore,

$$ \alpha = \frac{{p_{0|0} - p_{0|1} }}{{1 + p_{0|1} }} = \frac{\beta }{{1 + p_{0|1} }}. $$

The recovery effects of PVCS and RGS can be compared under the same parameter α or β. For each RGS, there always exists a PVCS corresponding to it. However, transforming any PVCS to RGS can not be guaranteed, since some PVCSs can not be expressed by just f _equ , f _ran and f _com . Therefore, for (k, n) scheme, we have the following equations:

$$ \alpha_{RGS} \le \alpha_{PVCS} \; or \; \beta_{RGS} \le \beta_{PVCS} . $$

Taking (3, 4) scheme for example, a secret image S of size 512 × 512 pixels is encrypted. RGS is realized according to Algorithm 6. For PVCS, we construct C ₀ and C ₁ as follows.

$$ C_{0} = \left\{ {\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ 0 \\ \end{gathered} \right]} \right\},C_{1} = \left\{ {\left[ \begin{gathered} 0 \\ 0 \\ 0 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 0 \\ 1 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 0 \\ 1 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 0 \\ 0 \\ 0 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ 1 \\ \end{gathered} \right],\left[ \begin{gathered} 1 \\ 1 \\ 1 \\ 1 \\ \end{gathered} \right]} \right\}. $$

Figure 1 shows the results of (3, 4)-RGS and (3, 4)-PVCS, which encrypt secret S (Fig. 1(a)) into four random grids and shares, respectively. Nobody can recognize the original secret from single grid (Fig. 1(b)) or single share (Fig. 1(c)). Figure 1(d)–(e) show the noise-like decoding effects of two grids and two shares, respectively. The secret information can be recognized by stacking three grids or three shares, shown in Fig. 1(f)–(g) with contrast $\alpha_{RGS} = {2 \mathord{\left/ {\vphantom {2 {35}}} \right. \kern-0pt} {35}}$ < $\alpha_{PVCS} = {1 \mathord{\left/ {\vphantom {1 7}} \right. \kern-0pt} 7}$. All grids or shares stacked, the reconstructed secrets are shown in Fig. 1(h) and Fig. 1(i) with contrast $\alpha_{RGS} = {1 \mathord{\left/ {\vphantom {1 8}} \right. \kern-0pt} 8}$ < $\alpha_{PVCS} = {1 \mathord{\left/ {\vphantom {1 3}} \right. \kern-0pt} 3}$.

Fig. 1.

The experimental results of the (3, 4)-RGS and (3, 4)-PVCS: (a) secret image S, (b) single grid of RGS with $\alpha_{RGS} = 0$, (c) single share of PVCS with $\alpha_{PVCS} = 0$, (d) two overlapped grids of RGS with $\alpha_{RGS} = 0$, (e) two overlapped shares of PVCS with $\alpha_{PVCS} = 0$, (f) three overlapped grids of RGS with $\alpha_{RGS} = {2 \mathord{\left/ {\vphantom {2 {35}}} \right. \kern-0pt} {35}}$, (g) three overlapped shares of PVCS with $\alpha_{PVCS} = {1 \mathord{\left/ {\vphantom {1 7}} \right. \kern-0pt} 7}$, (h) four overlapped grids of RGS with $\alpha_{RGS} = {1 \mathord{\left/ {\vphantom {1 8}} \right. \kern-0pt} 8}$, (i) four overlapped shares of PVCS with $\alpha_{PVCS} = {1 \mathord{\left/ {\vphantom {1 3}} \right. \kern-0pt} 3}$.

5 Conclusion

The relationship between VCS and RGS is analyzed for the first time. It is interesting that the encryption rules of RGS are actually the set of distribution matrices in PVCS. Considering the costs of algorithms, PVCS is good at the computational complexity while RGS has advantage in no codebook needed. Generally speaking, the contrast of PVCS is better than RGS under the same access structure. Our future work is how to improve the contrast of RGS.