(t, k, n)-Deterministic Extended Visual Secret Sharing Scheme Using Combined Boolean Operations

Abstract

In Visual Cryptographic Scheme (VCS), the shares of the secret image are viewed as random whereas in Extended Visual Cryptographic Scheme (EVCS), the shares are viewed as meaningful images. When the number of participants increases the graying effect problem in deterministic VCS is caused due to high pixel expansion. This graying effect was resolved using ideal contrast constructions in VCS, but not in EVCS. In ideal contrast VCS; combinations of Boolean operations are used during reconstruction. Here in this paper, we designed a deterministic construction for $(t,k,n)$ access structure using the existing VCS constructions with contrast one as building block. In existing EVCS constructions the relative contrast will vary depending on the access structure, but in the proposed EVCS construction it is 0.25, which is better than existing schemes.

1 Introduction

In Visual cryptographic scheme, dealer constructs random shares from a secret image (SI) and then distributes shares to participants. During sufficient participants join their shares, the reconstructed image (RI) will be produced. Based on the pixel expansion and the contrast value [1], the quality of a VCS is measured. XOR, OR, AND and NOT are the Boolean operations used for reconstruction in VCS. In deterministic VCS all the black and white pixels of SI will be reconstructed in RI, but in probabilistic VCS [11] the correct reconstruction cannot be assured. VCS was pioneered by Naor et al. [1] in 1994. The deterministic VCS for general access structures are introduced in papers [2, 3, 12]. The constructions given in papers [3, 4] reconstruct the black pixel without distortion. For VCS constructions with contrast value one, the secret SI is generated without loss of resolution using combined Boolean operations [5,6,7, 27]. EVCS is a type of VCS developed by Ateniese et al. [13] where the encoded shares of SI are viewed as meaningful image. Schemes given in papers [13,14,15,16,17,18,19,20] are EVCS with pixel expansion and constructions given in papers [21,22,23,24,25,26] are EVCS without pixel expansion.

Table 1. Notations and its description

Let $P = \left\{ {p_1 ,p_2 ,p_3 , \ldots ,p_t ,p_{t + 1} ,p_{t + 2} , \ldots ,p_n } \right\}$ be the set of participants, and 2^P denotes the power set of P. Let us denote $\Gamma_{Qual}$ as qualified set and $\Gamma_{Forb}$ as forbidden set where $\Gamma_{Qual} \cap \Gamma_{Forb} = {\text{\O }}$. Any set $A \in \Gamma_{Qual}$ can recover SI whereas any set $A \in \Gamma_{Forb}$ cannot recover SI. Let Γ_QM = {A ∈ Γ_Qual:$A^{\prime}$ $\notin$ Γ_Qual for all $A^{\prime}$ $\subseteq$ A, $A^{\prime}$ ≠ A} be the set of minimal qualified subset of P. Let Γ_FM be denoted as the maximum forbidden set of P. Then the pair $\Gamma = (\Gamma_{Qual} ,\Gamma_{Forb} )$ is denoted as the access structure of the scheme. Let S be a $n \times m$ Boolean matrix and $A \subseteq P$. The vector obtained by applying the Boolean operation (e.g.: OR) using rows of S corresponding to the elements of A is denoted by S_A. Then $w(S_A )$ is denoted as the Hamming weight of vector S_A. The definition for contrast and security of the VCS are given in [3].

Define two sets $L = \left\{ {p_1 ,p_2 ,p_3 , \ldots ,p_t } \right\}$ and $R = \left\{ {p_{t + 1} ,p_{t + 2} , \ldots ,p_n } \right\}$ which contains t respectively $(n - t)$ participants. For a $(t,k,n)$-EVCS the minimal qualified set is represented as Γ_QM = {A: A $\subseteq$ P, L ∈ A and $\left| A \right|$= k}. It is mandatory that all the participants in the set L and any k participants from set R need to involve in the reconstruction phase of a $(t,k,n)$-EVCS [8,9,10].

In this paper, we propose a deterministic EVCS for $(t,k,n)$ access structure with a related contrast of 0.25. Our scheme is applicable only for sharing binary images. In the deterministic EVCS given in papers [13, 14, 16,17,18,19,20], each of the participants carry single meaningful image as share. Our proposed constructions are similar to the deterministic EVCS given in paper [15], where each of the participants carries multiple meaningful images as shares. Our EVCS has better reconstruction image quality than the deterministic EVCS constructions given in papers [13,14,15,16,17,18,19,20]. Table 1 describes the notations used in our algorithm.

2 A (t, k, n)-EVCS with Reduced Pixel Expansion

Let us define a set $L = \left\{ {p_1 ,p_2 ,p_3 , \ldots ,p_t } \right\}$ which contains t essential participants and $R = \left\{ {p_{t + 1} ,p_{t + 2} , \ldots ,p_n } \right\}$ which contains $(n - t)$ remaining participants. For a $(t,k,n)$-EVCS the minimal qualified set is represented as Γ_QM = {A: A $\subseteq$ P, L ∈ A and $\left| A \right|$ = k}. It is mandatory that all the participants in the set L and any k participants from set R need to involve in the reconstruction phase of $(t,k,n)$-EVCS.

In today’s world, there is a need for storing user’s valuable private data like texts, images, passwords, or keys, on his/her computer or on any other electronic device. But in the current computing world all devices can fall prey to viruses, spyware, Trojan horses and other types of malware, exposing user data and breaching his/her privacy. Under such circumstances, it becomes paramount for a user or company to ensure the confidentiality of his/her data. One of the applications of essential access structure (1, k, n)-VCS in this scenario is that, user can store copies of the essential share in each of his/her own devices (home computer, mobile phones etc.) and outsource the remaining $n - 1$ shares to $n - 1$ trusted servers. So, an event of corruption or loss of his/her own single device will not result in the loss of data. Even on compromise of $k - 1$ servers, it will not expose the private information of user to public. A (1, k, n) scheme is a (t, k, n) scheme where the value of t is 1. Figure 1 shows the experimental results and implies that our scheme has better contrast than Ateniese et al. [13] scheme. The following section shows our proposed algorithm for share generation and secret reconstruction for (t, k, n)-EVCS.

Fig. 1.

Reconstructed image for (2, 3) scheme

2.1 Share Generation and Distribution Phase

Input:

• 1. SI and a random image K of size $p \times q$.

• 2. The t cover images $COV_{(p_r ,1)}$ of size $p \times q$, where $p_r \in L$, $1 \le r \le t$.

  ($COV_{(p_r ,1)}$, used for generating meaningful shares for t mandatory participants in L).

• 3. The $(n - t) \times m$ cover images $COV_{(p_u ,j)}$ of size $p \times q$, where $p_u \in R$, $(t + 1) \le u \le n$.

  ($COV_{(p_u ,j)}$, used for generating meaningful shares for remaining $(n - t)$ participants where $1 \le j \le m$, pixel expansion of a perfect black $(k - t,n - t)$ scheme is m).

• 4. S⁰ and S¹ are basis matrices of a perfect black $(k - t,n - t)$-VCS of size $(n - t) \times m$.

• 5. Let Odd (resp. Even) be column vectors of size $(t \times 1)$ which contain odd (resp. even) number of ones.

• 6. Set Mp (Mp contains any one essential participant, $\left| {Mp} \right| = 1$).

Output:

• 1. Shares {$Sh_{(p_r ,1)}$:$1 \le r \le t$}. The t meaningful shares of size $p \times 4q$ are distributed to t mandatory participants in set L.

• 2. Shares {$Sh_{(p_u ,j)}$:$(t + 1) \le u \le n$,$1 \le j \le m$}. The $(n - t) \times m$ meaningful shares of size $p \times 4q$ are distributed to remaining participants in set R.

• 3. Share MS of size $p \times 4q$ is distributed to participants in the set Mp.

2.2 Secret Reconstruction Phase

• Step 1. $\lambda_j$’s are generated by OR-ing shares $Sh_{(p_u ,j)}$ of any $(k - t)$ out of $(n - t)$ participants in $R = \left\{ {p_{t + 1} ,p_{t + 2} ,\begin{array}{*{20}c} {} \\ \end{array} ....,p_n } \right\}$, where $1 \le j \le m$.

• Step 2.

• The construction of K can be done using any one of the following schemes

• a) Cimato et al. [5] (OR and NOT operation) b) Wang et al. [6] (OR and XOR operation) and c) Praveen et al. [7] (OR and AND operation).

• Step 3. XOR-ing the shares of all the participants in the set L along with K will generate RI. Then AND-ing RI with MS will reconstruct the secret OI.

Tables 2, 3 and 4 shows the comparison results.

Table 2. Reconstruction operations count for (t, k, n)

Table 3. Comparison of deterministic (1, 3, 4) scheme

Table 4. Comparison of deterministic (2, 4, 5) scheme

2.3 Analysis on the Pixel Expansion, Contrast and Security

The matrices S⁰ (resp. S¹) are constructed based on the Definition 1. The proposed (t, k, n)-perfect black EVCS is valid only when the following three conditions meet.

Condition 1:

It should not be possible for any (k − t) participant in the set R out of (n − t) participants to identify SI in the absence of participants in the set L.

Condition 2:

It should not be possible for any participant less than (k − t) in the set R out of (n − t) participants to identify SI with participants in the set L.

Condition 3:

It should be possible for any (k − t) in the set R out of (n − t) participants to identify SI in the presence of all participants in the set L. The first two conditions are for the security of the scheme and the third is for the correctness of reconstruction. Assume that variables q, b, b₁, b₂, z take the values either 0 or 1. Let $Pbr(q = b)$ denote the probability of occurrence of q equal to b. Let b₁ and b₂ be the two independent bits and $q = b_1 \oplus b_2$. Let $Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = z} \right)}}} \right)$ be the probability of $q = b_2$ given bit b₁ equal to z.

Lemma 1:

Let b₁ (resp. b₂) be known (resp. unknown) bit and $q = b_1 \oplus b_2$ then

$$ Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 0} \right)}}} \right) = Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 1} \right)}}} \right) = \frac{1}{2}. $$

Proof:

Here the given information is b₁ and $q = b_1 \oplus b_2$. But b₂ is unknown then,

$Pbr\left( {{{\left( {q = 0} \right)} / {\left( {b_1 = 0} \right)}}} \right) = Pbr\left( {{{\left( {q = 1} \right)} / {\left( {b_1 = 0} \right)}}} \right) = \frac{1}{2}$ and $Pbr\left( {{{\left( {q = 0} \right)} / {\left( {b_1 = 1} \right)}}} \right) = Pbr\left( {{{\left( {q = 1} \right)} / {\left( {b_1 = 1} \right)}}} \right) = \frac{1}{2}$ accordingly,$Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 0} \right)}}} \right) = Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 1} \right)}}} \right) = \frac{1}{2}$.

Lemma 2:

Given two bits b₁, b₂ and $q = b_1 \oplus b_2$ then $Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 0} \right)}}} \right) = 1$ and $Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 1} \right)}}} \right) = 0$.

Proof:

Here the given information is b₁, b₂ and $q = b_1 \oplus b_2$ then, $Pbr\left( {{{\left( {q = 0} \right)} / {\left( {b_1 = 0} \right)}}} \right) = Pbr\left( {{{\left( {q = 1} \right)} / {\left( {b_1 = 0} \right)}}} \right) = 1$ and

$Pbr\left( {{{\left( {q = 0} \right)} / {\left( {b_1 = 1} \right)}}} \right) = Pbr\left( {{{\left( {q = 1} \right)} / {\left( {b_1 = 1} \right)}}} \right) = 0$ accordingly, $Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 0} \right)}}} \right) = 1$ and $Pbr\left( {{{\left( {q = f(b_2 )} \right)} / {\left( {b_1 = 1} \right)}}} \right) = 1$.

which implies that $Pbr\left( {{{\left( {q = b_2 } \right)} / {\left( {b_1 = 1} \right)}}} \right) = 0$.

Fig. 2.

Experimental results for our (2, 3) EVCS

Let x be a bit obtained by combining the shares (MS is not taken) of any $(k - t)$ out of $(n - t)$ participants from the set R. Let y be a bit obtained by combining all the shares of participants in the set Land s is the secret bit in RI. Then $s = x \oplus y$.The security for Condition 1 and 2 can be proved using Lemma 1.

Fig. 3.

Experimental results for (2,3) EVCS by Ateniese et al. [13]

Condition 1:

Here $b_1 = y$ (is given), $b_2 = x$ (is unknown bit either 0 or 1) and $q = s$ (either 0 or 1). $Pbr\left( {{{\left( {s = x} \right)} / {\left( {y = 0} \right)}}} \right) = Pbr\left( {{{\left( {s = x} \right)} / {\left( {y = 1} \right)}}} \right) = \frac{1}{2}$ (Lemma 1).

Condition 2:

Here $b_1 = x$ (is given), $b_2 = y$ (is unknown bit either 0 or 1) and q = s (either 0 or 1). $Pbr\left( {{{\left( {s = y} \right)} / {\left( {x = 0} \right)}}} \right) = Pbr\left( {{{\left( {s = y} \right)} / {\left( {x = 1} \right)}}} \right) = \frac{1}{2}$ (Lemma 1).

Condition 3:

Here $b_1 = y$, $b_2 = x$ (is given) and $q = s$. $Pbr\left( {{{\left( {s = x} \right)} / {\left( {y = 0} \right)}}} \right) = 1$, $Pbr\left( {{{\left( {s = x} \right)} / {\left( {y = 1} \right)}}} \right) = 0$ (Lemma 2).

Figure 2 shows the experimental results of our scheme with meaningful shares (Sh) and reconstructed images (RI and OI). Figure 3 shows the experimental results of Ateniese et al. [13] scheme with meaningful shares (Sh) and reconstructed images (AI). It is clear that the contrast of AI is less than OI.

3 Conclusion

Even though deterministic schemes need huge amount of data, it guarantees reconstruction of all the secret data correctly. In the case of probabilistic scheme there is no such guarantee. So constructions of deterministic schemes with high relative contrast and less pixel expansion are of great demand. In this paper a deterministic EVCS for (t, k, n) access structure is proposed. It is true that in our constructions OR, XOR and AND Boolean operations are used for reconstruction instead of only OR operation as in existing EVCS constructions. But the experimental results show that, the quality of reconstructed image for our EVCS is better when compared to other related EVCS.