Deterministic extended visual cryptographic schemes for general access structures with OR-AND and XOR-AND operations

Abstract

In Visual Cryptographic Scheme (VCS) shares of the secret image look like random, whereas in Extended Visual Cryptographic Scheme (EVCS) the shares look like meaningful images. In the case of ideal contrast deterministic constructions for VCS, depending upon the access structure, each participant needs to hold one/multiple image shares with same size of the binary secret image and the secret image will be reconstructed without any change in resolution. In this paper, two deterministic constructions for EVCS with a relative contrast of 0.333 are proposed by utilizing the ideal contrast deterministic constructions for VCS as a building block. The proposed schemes are applicable to share secret binary images only. Theoretical analysis and comparison with other related works are given in this paper.

1 Introduction

Today, every business, medical and research units of government/private sectors transfer digital images over the Internet and store it in public cloud servers. In order to mitigate any event of disclosure of secret images to unauthorized persons, there exist various techniques like steganography [23,24,25] and secret sharing. Secret image sharing is a practice of encoding the secret image into shares and steganography is the practice of hiding a secret information within another file, image or video. Secret images can be encoded into shares either by complex computations like Lagrange interpolations or using Visual cryptography. In this paper, we focus on the development of Visual cryptographic scheme.

Visual cryptography, pioneered by Naor and Shamir [34], is a method in which the dealer generates random-looking shares from a secret image (SI Figs. 1, 7 and 11), then distributes these shares to a set of participants and when sufficient shares combine, the reconstructed image (RI) will be generated. The quality of a VCS is measured using two parameters: pixel expansion and contrast. The pixel expansion is the number of sub pixels used for encoding a pixel while, contrast is the difference in gray level between black and white pixels of SI. One can distinguish the black (1) and white (0) pixel in the RI because every m sub pixel in black area will have more black sub pixels than in white area. The Boolean operations used in VCS for reconstruction are: XOR, OR, AND and NOT. In deterministic VCS all the black and white areas of SI will be reconstructed in RI. Deterministic VCS were introduced in [3, 6, 34]. The perfect black VCS constructions were discussed in [6, 7]. In ideal contrast VCS, the secret SI is reconstructed using combined Boolean operations (either OR and NOT [10] or OR and XOR [45] or OR and AND [37]) without loss of resolution. For XOR based ideal contrast step construction [28], participants hold less number of multiple shares when compared with the constructions given in [10, 37, 45]. Deterministic EVCS [5, 20, 27, 31, 32, 44, 46, 48,49,50, 53, 56, 58, 59, 62, 63] and probabilistic EVCS [8, 9, 12, 15, 16, 18, 22, 35, 36, 39,40,41, 47, 54, 55] are other types of VCS where the shares of SI look like meaningful. The halftone EVCS constructions are discussed in [48,49,50, 56, 63]. EVCS for (2, 2) [32], (k, k) [18], (k, n) [46] are some of the existing threshold access structure constructions. Progressive EVCS constructions are given in [8, 16]. Apart from some of these schemes [1, 51, 52] as a solution for authentication, Naor and Pinkas [33] proposed a solution based on visual cryptography. Some other applications of visual cryptography are discussed in papers [2, 11, 21, 30, 38, 43, 60, 61].

Fig. 1

Reconstructed images for (2, 3) EVCS

In ideal contrast VCS constructions [10, 28, 37, 45], each participant needs to carry multiple shares which are of same size of SI. For EVCS in general each participant carries a single pixel expanded meaningful image as share. In this paper, we propose constructions (PC1 and PC2) for EVCS having the relative contrast value of RI as 0.333, where each participant carries multiple meaningful images as shares. Since each participant holds multiple shares, we consider the average pixel expansion (APE) instead of pixel expansion, where the APE [28] is defined as the average value of the total pixel expansions of the share images that each participant holds. For a good EVCS the APE value needs to be low and relative contrast value of the reconstructed image needs to be high. Our construction shows better results for relative contrast (Fig. 1) and APE values compared with the existing EVCS. The proposed algorithm works when the secret and cover are binary images.

The rest of the paper is organized as follows. Section 2 shows the background and Section 3 shows the proposed EVCS constructions respectively. Conclusions are given in Section 4.

2 Preliminaries

Let P = {p₁,p₂,p₃,......,p_t,......,p_n} be the set of participants, and 2^P denote the power set of P. Let us define a subset E = {p₁,......,p_t} of P. Denote Γ_Qual as qualified set and Γ_Forb as forbidden set where, Γ_Qual ∩Γ_Forb = ∅. Any set A∈Γ_Qual can recover SI whereas any set A ∈Γ_Forb cannot recover SI. Let Γ_QM = {A $\in {\Gamma }_{\textit {Qual}}: \textit {A}^{\prime } \notin {\Gamma }_{\textit {Qual}}$ for all $\textit {A}^{\prime } \subset \textit {A}$} be the set of minimal qualified subsets of P. Let Γ_FM = {B∈Γ_Forb : B ∪{i}∈Γ_Qual for all i ∈P ∖B} be the set of maximal forbidden subsets of P. The pair Γ = (Γ_Qual,Γ_Forb) is the access structure of the scheme. A VCS with Γ_QM = {A ∈Γ_Qual: A $\subseteq$ P and |A| = k} is called (k, n) - VCS. A VCS with Γ_QM = {A ∈Γ_Qual: A $\subseteq$ P, p₁ ∈A and |A| = k} is called (1, k, n) - VCS. A VCS with Γ_QM = {A ∈Γ_Qual: A $\subseteq$ P, E $\subseteq$ A and |A| = k} is called (t, k, n) - VCS. Let us denote the set Γ_EM = {A₁,A₂,A₃,......,A_r} which contains r minimal qualified subsets such that A₁ ∩A₂ ∩A₃,......,A_r− 1 ∩A_r = E≠∅. Let S be an n× m Boolean matrix and A $\subseteq$ P, then the vector obtained by applying the Boolean operations to the rows of S corresponding to the elements of A is denoted by S^A and number of ones in the vector S^A is denoted as W(S^A).

Let us define the notations used in this paper.

• 1) $\overline {\textit {x}} =\left \{ \begin {array}{ll} 1 & \textit {if}~~\textit {x} == 0\\ 0 & \textit {if}~~\textit {x} == 1 \end {array} \text { as NOT operation } \right .$

• 2) $\bigotimes$ as OR operation

• 3) $\bigoplus$ as XOR operation

• 4) $\bigodot$ as AND operation

• 5) $\left [\begin {array}{ccc}\textit {x}_{1} & \textit {x}_{2} & \textit {x}_{3} \end {array}\right ]\bigotimes \left [\begin {array}{ccc}\textit {y}_{1} & \textit {y}_{2} & \textit {y}_{3} \end {array}\right ] = \left [\begin {array}{ccc}\textit {x}_{1}\bigotimes \textit {y}_{1}& \textit {x}_{2}\bigotimes \textit {y}_{2}&\textit {x}_{3}\bigotimes \textit {y}_{3} \end {array}\right ]$

• 6) $\left [\begin {array}{ccc}\textit {x}_{1} & \textit {x}_{2} & \textit {x}_{3} \end {array}\right ]\bigoplus \left [\begin {array}{ccc}\textit {y}_{1} & \textit {y}_{2} & \textit {y}_{3} \end {array}\right ] = \left [\begin {array}{ccc}\textit {x}_{1}\bigoplus \textit {y}_{1}& \textit {x}_{2}\bigoplus \textit {y}_{2}&\textit {x}_{3}\bigoplus \textit {y}_{3} \end {array}\right ]$

• 7) $\left [\begin {array}{ccc}\textit {x}_{1} & \textit {x}_{2} & \textit {x}_{3} \end {array}\right ]\bigodot \left [\begin {array}{ccc}\textit {y}_{1} & \textit {y}_{2} & \textit {y}_{3} \end {array}\right ] = \left [\begin {array}{ccc}\textit {x}_{1}\bigodot \textit {y}_{1}& \textit {x}_{2}\bigodot \textit {y}_{2}&\textit {x}_{3}\bigodot \textit {y}_{3} \end {array}\right ]$

• 8) N_i as the number of shares held by participant p_i

• 9) Size_i as the share size of a single pixel of SI

• 10) # as the number of Boolean operations done during reconstruction.

• 11) SPP as Shares hold by each participant.

• 12) RI as the reconstructed image.

• 13) OI as the intermediate image generated for reconstructing RI in PC2.

• 14) D_(u,j): The j^th share of the u^th participant, Sh_(u,j) of size p × 3q is generated using all the p ×q row vectors D_(u,j) of size 1 × 3.

Definition 1 (OR operation based)

[6]: Let Γ = (Γ_Qual,Γ_Forb) be an access structure on a set of n participants. Two collections of n × m Boolean matrices C₀ and C₁ constitute a (Γ_Qual,Γ_Forb)-VCS if there exists a positive real number α and the set of thresholds $\left \{\textit {t}_{\textit {A}} \mid \textit {A} \in {\Gamma }_{\textit {Qual}} \right \}$ satisfying the following two properties

• 1. Any qualified set A = $\left \{\textit {i}_{1},\textit {i}_{2}, ......,\textit {i}_{\textit {p}}\right \} \in {\Gamma }_{\textit {Qual}}$ can recover SI by stacking their transparencies. Formally for any S₀ in $\textit {C}_{0}, \textit {W}(\,\textit {S}_{0}^{\textit {A}}) \, \leq \textit {t}_{\textit {A}} - \alpha \times \textit {m}$ and for any S₁ in $\textit {C}_{1}, \textit {W}(\,\textit {S}_{1}^{\textit {A}})\, \geq \textit {t}_{\textit {A}}$.

• 2. Any forbidden set A = $\left \{\textit {i}_{1},\textit {i}_{2}, ......,\textit {i}_{\textit {p}}\right \} \in {\Gamma }_{\textit {Forb}}$ has no information on SI.

Two collections of matrices $\textit {C}_{\textit {v}}, \textit {v} \in \left \{ 0,1 \right \}$ in Definition 1 are obtained by generating all permutations of the basis matrices $\textit {S}_{\textit {v}}, \textit {v} \in \left \{ 0,1 \right \}$. In such a case, |C₀| = |C₁| = m! and r = $\log _{2}{\textit {m}!}$ is called the randomness of the VCS [13, 17]. Formally the two collections of p ×m matrices are obtained by restricting each n ×m matrix in S_v to the rows i₁,i₂,......,i_p are indistinguishable. The first property is related to contrast α ×m of RI. The number α is called the relative contrast. The second is for the security of the scheme.

2.1 EVCS - Ateniese et al. [5]

In the case of EVCS, the share of the participants belonging to set P is meaningful, and is not random-looking in nature as in conventional VCS. Let $\textit {C}_{\textit {sc}}^{\textit {c}_{1}, ......,\textit {c}_{\textit {n}} }$ where, {c₁, ......, c_n} ∈ {0, 1}, be the collection of matrices from which the dealer chooses a matrix to encode a c_i pixel, where i = 1 to n in the image COV_i (cover images or meaningful images) associated to participants in set P in order to obtain a sc pixel when the transparencies associated to the participants in the set A ∈Γ_Qual are stacked together. Hence there will be a collection of 2ⁿ pairs ($\textit {C}_{0}^{ \textit {c}_{1}, ......,\textit {c}_{\textit {n}}}, \textit {C}_{1}^{\textit {c}_{1}, ......,\textit {c}_{\textit {n}}}$) for all possible combinations of white and black pixels in the n original images. Let $\textit {T}_{0}^ {\textit {c}_{1}, ......,\textit {c}_{\textit {n}}} = \left [\begin {array}{l}\textit {S}_{0} \ || \ \textit {D} \end {array}\right ] \in \textit {C}_{0}^{ \textit {c}_{1}, ......,\textit {c}_{\textit {n}}}$ and $\textit {T}_{1}^{ \textit {c}_{1}, ......,\textit {c}_{\textit {n}}} = \left [\begin {array}{l}\textit {S}_{1} \ || \ \textit {D} \end {array}\right ] \in \textit {C}_{1}^{ \textit {c}_{1}, ......,\textit {c}_{\textit {n}}}$ where, S₀ (resp. S₁) are the basis matrices of perfect black VCS [6, 7] and when stacking the rows of D matrix corresponding to the participants in the qualified set, an all one row vector will obtain. This implies that T₀ (resp. T₁) are basis matrices of a perfect black EVCS for sharing 0 (resp. 1) pixel in SI.

Example 1

Let P = {p₁,p₂,p₃} be the set of participants, Γ_QM ={{p₁,p₂},{p₁,p₃},{p₂,p₃}} and Γ_FM = {{p₁},{p₂},{p₃}}. Let SI = $\left [\begin {array}{cc} 1 & 0 \end {array}\right ]$. Let the three cover images used in this construction be $\textit {COV}_{1} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {COV}_{2} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ]$ and $\textit {COV}_{3} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ]$. Let $\textit {S}_{0} = \left [ \begin {array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end {array}\right ]$ and $\textit {S}_{1} = \left [ \begin {array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end {array}\right ]$. Then the Boolean matrices constructed for sharing a 0 pixel is $\textit {T}_{0}^{011} = \left [ \begin {array}{cccc||ccc} 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \end {array}\right ]$ and for sharing a 1 pixel is $\textit {T}_{1}^{001} = \left [ \begin {array}{cccc||ccc} 0 & 1 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 \end {array}\right ]$. So for the access structure (Γ_QM,Γ_FM) the pixel expansion and relative contrast of Ateniese et al. [5] scheme is 7 and 1/7 respectively.

2.2 Ideal contrast constructions for VCS

Let S₀ (resp. S₁) be the basis matrices of perfect black general access structure scheme ([6] and [7]) for sharing a 0 (resp. 1).

The share generation phase:

In Cimato et al. [10] scheme the m shares for each participant is generated as follows.H_(u,j)(g, h) = $\left \{ \begin {array}{ll} \textit {S}_{0}(\textit {u}, \textit {j}) & \textit {if} \textit {SI}(\textit {g}, \textit {h}) == 0 \\ \textit {S}_{1}(\textit {u}, \textit {j}) & \textit {if} \textit {SI}(\textit {g}, \textit {h}) == 1 \end {array}; \text { where } j = 1 \text { to } m, 1\leq u \leq n, \right .$0 ≤g ≤p − 1,0 ≤h ≤q − 1.

The secret reconstruction phase:

Generate ${\Delta }_{1}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {H}_{(\textit {u}, 1)}(\textit {g}, \textit {h}), {\Delta }_{2}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {H}_{(\textit {u}, 2)}(\textit {g}, \textit {h})$, ...,${\Delta }_{\textit {m}-1}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {H}_{(\textit {u}, \textit {m}-1)}(\textit {g}, \textit {h}), {\Delta }_{\textit {m}}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {H}_{(\textit {u}, \textit {m})}(\textit {g}, \textit {h})$. Then RI is obtained in any of the following three ways when the gray levels of SI is 2. Based on Cimato et al. [10] OR-NOT scheme, RI(g, h)=$\overline {\bigotimes \limits _{j = 1}^{m}\overline {{\Delta }_{\textit {j}}(\,\textit {g}, \textit {h})}}$. Based on Wang et al. [45] OR-XOR scheme, RI(g, h) = $\bigoplus \limits _{j = 1}^{m} {\Delta }_{\textit {j}}(\,\textit {g}, \textit {h})$. Based on Praveen et al. [37] OR-AND scheme, RI(g, h) = $\bigodot \limits _{j = 1}^{m} {\Delta }_{\textit {j}}(\,\textit {g}, \textit {h})$. The Wang et al. [45] scheme is also applicable to non perfect black general access structure schemes.

2.3 Ideal contrast Step construction for VCS [28]

In the case of XOR based (2, 2) - VCS, two collections of 2 × 1 Boolean matrices for sharing a 0 (resp .1) pixel in SI are $\textit {C}_{0} = \left \{\left [\begin {array}{l} 1\\ 1 \end {array}\right ], \left [\begin {array}{l} 0\\ 0 \end {array}\right ] \right \}$ and $\textit {C}_{1} = \left \{ \left [\begin {array}{l} 1\\ 0 \end {array}\right ], \left [\begin {array}{l} 0\\ 1 \end {array}\right ] \right \}$ respectively. Here RI is identical to SI which implies that the contrast is ideal (α ×m = 1) and pixel expansion m = 1. By recursively calling XOR based (2, 2)-VCS, Liu et al. [28] in 2010 developed the ideal contrast XOR step construction, where the amount of shares each participant holds is different. The APE and relative contrast of step construction is better when compared to other results and is given in TABLE I of paper [28].

2.3.1 Step construction for (n, n) - VCS (Construction1)

Here initially two shares $\textit {Sh}_{1}^{L}$ and $\textit {Sh}_{1}^{R}$ are generated from SI using XOR based (2, 2)-VCS. Then for constructing an (n, n)-VCS select any one of the shares say $\textit {Sh}_{1}^{R}$ as secret image and again generate two shares $\textit {Sh}_{2}^{L}$ and $\textit {Sh}_{2}^{R}$ using XOR based (2, 2)-VCS. This procedure is continued till the shares $\textit {Sh}_{\textit {n}-1}^{L}$ and $\textit {Sh}_{\textit {n}-1}^{R}$ are generated from the share $\textit {Sh}_{\textit {n}-2}^{R}$ using XOR based (2, 2)-VCS. During the share distribution phase, distribute $\textit {Sh}_{1}^{L}, \textit {Sh}_{2}^{L}$, ......, $\textit {Sh}_{\textit {n}-1}^{L}, \textit {Sh}_{\textit {n}-1}^{R}$ to the n participants in the set P respectively. During the share reconstruction phase, when all the n participants combine their shares, the following procedure will recover the RI = SI = $\textit {Sh}_{1}^{L}\oplus \textit {Sh}_{2}^{L}$, ......, $\textit {Sh}_{\textit {n}-1}^{L}\oplus \textit {Sh}_{\textit {n}-1}^{R}$. Hence the XOR step construction for (n, n) access structure generates a VCS with ideal contrast (α ×m = 1) and pixel expansion m = 1.

Access structures can be simplified using equivalent participants for effective construction (for achieving small APE). Participants who have the same right can be considered as equivalent participants.

2.3.2 Generation of the simplified qualified set $\widetilde {{\Gamma }_{\textit {QM}}}$

Without affecting the security, identical shares are distributed to equivalent participants for simplifying the access structure of VCS. Formally, equivalent participants are defined as follows:

Definition 2 (Equivalent participants)

[28]: Let Γ_QM be the access structure on P. If participant p_i and p_j satisfy that, for all A ∈Γ_FM,p_i ∈A hold iff p_j ∈A hold, then participant p_i and p_j are considered to be equivalent participants on Γ_QM, denoted by $\textit {p}_{\textit {i}}\sim \textit {p}_{\textit {j}}$.

Here $\sim$ is an equivalence relation on P. A quotient set is a set derived from another by an equivalence relation. Let $\widetilde {\textit {P}}$ be the quotient set derived from P based on $\sim$. Following definition shows how to simplify the access structure based on equivalent participants.

Definition 3 (Simplifying access structure)

: The simplified access structure based on the equivalent participants is $\widetilde {{\Gamma }_{\textit {QM}}}$ = {$\widetilde {\textit {A}}: \textit {A}\in {\Gamma }_{\textit {QM}}$ }, where the set $\widetilde {\textit {A}}$ = {$\tilde {\textit {p}_{\textit {i}}}\in \widetilde {\textit {P}}: \textit {p}_{\textit {i}}\in \textit {A}\}$ is called the corresponding set of A and $\widetilde {\textit {p}_{\textit {i}}}$ is called the equivalence class or corresponding participant of p_i.Γ_QM is called the most simplified access structure when $\widetilde {{\Gamma }_{\textit {QM}}} = {\Gamma }_{\textit {QM}}$.

Theorem 1

[28]: Let $\widetilde {{\Gamma }_{\textit {QM}}}$ ={$\widetilde {\textit {A}}: \textit {A}\in {\Gamma }_{\textit {QM}}$ }. By distributing the share images of corresponding participants to the equivalent participants, a construction of VCS for the $\widetilde {{\Gamma }_{\textit {QM}}}$ is also a construction of VCS for the Γ_QM.

Using Definition 3 and Theorem 1, the ideal contrast XOR based step constructions for VCS are given below.

2.3.3 Step construction for Γ_EM (Construction2)

Let us denote the set Γ_EM = {A₁,A₂,A₃,......,A_r} which contains r minimal qualified subsets such that A₁ ∩A₂ ∩A₃,......,A_r− 1 ∩A_r = E≠∅ where E = {p₁,......,p_t}. Let ${\Gamma }^{\prime }$ = {A ∖E: A∈Γ_EM}. Method 1 and Method 2 for constructing Γ_EM are represented as construction trees of Figs. 2 and 3, respectively. It is given in Theorem 6 of paper [28] that the APE and contrast for both the methods are the same.

Method 1: :

The shares $\textit {Sh}_{1}^{L}, \textit {Sh}_{2}^{L}$, ......, $\textit {Sh}_{\textit {t}}^{L}$ shown in Fig. 2 are distributed to the participants p₁,p₂, ......, p_t respectively. For all $\textit {L} \in {\Gamma }^{\prime }$, if |L| = 1, distribute $\textit {Sh}_{\textit {t}}^{\textit {R}}$ to the participant in L, else for all L when |L| = d and g = t + d-1, take $\textit {Sh}_{\textit {t}}^{\textit {R}}$ as secret image and generate share images for participants in L based on the construction shown in the Fig. 2. Then distribute the shares $\textit {Sh}_{\textit {t}+ 1}^{\textit {L}}$, ......, $\textit {Sh}_{\textit {g}}^{\textit {L}}, \textit {Sh}_{\textit {g}}^{\textit {R}}$ to the participants in L.

Method 2: :

For all $\textit {L} \in {\Gamma }^{\prime }$, if |L| = 1, the dealer distributes $\textit {Sh}_{1}^{\textit {R}}$ to the participant in the set L, else for all L when |L| = d, take $\textit {Sh}_{1}^{R}$ as secret image and generate share images $\textit {Sh}_{2}^{RL}$, ......, $\textit {Sh}_{\textit {d}}^{RL}, \textit {Sh}_{\textit {d}}^{RR}$ and distribute it to the participants in the set L respectively as shown in Fig. 3. When t = 1, distribute $\textit {Sh}_{1}^{L}$ to p₁, else generate share images $\textit {Sh}_{2}^{LR}$, ......, $\textit {Sh}_{\textit {t}-1}^{LL}$ and $\textit {Sh}_{\textit {t}-1}^{LR}$ from $\textit {Sh}_{1}^{L}$ and distribute it to the participants p₁,p₂, ......, p_t respectively.

For both methods 1 and 2, the step construction for the sets $\textit {L} \in {\Gamma }^{\prime }$ are processed independently. Let w=|L ∪E|, then the step construction of the set L ∪E forms a step construction of (w, w)-VCS. In the case of Γ_QM = {A₁} and A₁ = {p₁,......,p_t}, apply step construction of (t, t)-VCS for the participant set A₁.

Fig. 2

Step construction Method 1

Fig. 3

Step construction Method 2

2.3.4 Step construction of VCS for general access structure(Construction 3)

Following are the steps performed by the dealer for generating shares for Γ = (Γ_QM,Γ_FM).

Step 1) :

Simplify Γ_QM to $\widetilde {{\Gamma }_{\textit {QM}}}$ according to Theorem 1.

Step 2) :

Then divide $\widetilde {{\Gamma }_{\textit {QM}}}$ into several parts, say Γ_i = {A₁,A₂,A₃,......,A_ri} such that A₁ ∩A₂ ∩A₃,......,A_ri = E_i≠∅.

Step 3) :

For each part Γ_i, let ${\Gamma }_{\textit {i}}^{\prime }$ = {A ∖E_i: A ∈Γ_i} and ${\Gamma }_{\textit {i}}^{\prime \prime }$ = {$\textit {L}\in {\Gamma }_{\textit {i}}^{\prime } : |\textit {L}| \neq 1$}. If ${\Gamma }_{\textit {i}}^{\prime \prime } = \emptyset$ then apply Construction 2 directly on ${\Gamma }_{\textit {i}}^{\prime }$. Else treat ${\Gamma }_{\textit {i}}^{\prime \prime }$ as virtual participant $\textit {E}_{\textit {i}}^{\prime }$ in ${\Gamma }_{\textit {i}}=\{\textit {E}_{\textit {i}}, \textit {E}_{\textit {i}}^{\prime }\}$. Then apply Construction 2 (Method 1 or Method 2) on Γ_i i.e., apply the (2, 2)-VCS and denote the share image distributed to $\textit {E}_{\textit {i}}^{\prime }$ as $\textit {Sh}_{\textit {i}}^{\prime }$. Then go to Step 1 and apply a new step construction of VCS, which takes $\textit {Sh}_{\textit {i}}^{\prime }$ as the secret image for the access structure ${\Gamma }_{\textit {i}}^{\prime \prime }$.

Step 4) :

Repeat Step 1, 2 and 3 until all the participants receive their share images for all the qualified sets in Γ_QM.

Theorem 1 simplifies the access structure Γ_QM. Step 1 reduces the number of qualified sets in Γ_QM. There always exist partitions for a general access structure where each part satisfies the condition of Construction 2 [28]. A simple example for partitioning $\widetilde {{\Gamma }_{\textit {QM}}}$ is explained as follows. Assume $\widetilde {{\Gamma }_{\textit {QM}}}$ = {A₁,A₂,A₃,......,A_r}, then let Γ₁ = {A₁,A₂,A₃,......,A_f} be the set of qualified sets which contain p₁, i.e., A₁ ∩A₂ ∩A₃,......,A_f− 1 ∩A_f = {p₁}. Let Γ₂ be generated from ${\Gamma }_{1}^{\prime } = \widetilde {{\Gamma }_{\textit {QM}}}\setminus {\Gamma }_{1}$. Similarly Γ_i is generated from ${\Gamma }_{\textit {i}-1}^{\prime } = {\Gamma }_{\textit {i}-2}^{\prime }\setminus {\Gamma }_{\textit {i}-1}$, where all the minimal qualified sets in Γ_i contain participant p_i. Suppose when there are n partitions in total, $\widetilde {{\Gamma }_{\textit {QM}}} = {\Gamma }_{1}\cup {\Gamma }_{2}\cup ...\cup {\Gamma }_{\textit {n}}$ and each Γ_i satisfies the condition of Construction 2. APE of VCS will vary based on the partition methods and it is quite complicated to find a general partition method to obtain minimal APE [28]. Suppose for example when $\widetilde {{\Gamma }_{\textit {QM}}} = \{ \{\textit {p}_{1},\textit {p}_{2},\textit {p}_{3}\}, \{\textit {p}_{1},\textit {p}_{2},\textit {p}_{4}\}, \{\textit {p}_{1},\textit {p}_{3},\textit {p}_{4}\}, \{\textit {p}_{2},\textit {p}_{3},\textit {p}_{4}\}\}$. Then we can generate two partitions from $\widetilde {{\Gamma }_{\textit {QM}}}$ as Γ₁ = {{p₁,p₂,p₃},{p₁,p₂,p₄}} where {p₁,p₂,p₃}∩{p₁,p₂,p₄} = {p₁,p₂} and Γ₂ ={{p₁,p₃,p₄},{p₂,p₃,p₄}} where {p₁,p₃,p₄}∩{p₂,p₃,p₄} = {p₃,p₄}. Even though in Step 2, when each part of $\widetilde {{\Gamma }_{\textit {QM}}}$ satisfies the condition of Construction 2, in order to obtain a smaller APE, the dealer needs to further divide ${\Gamma }_{\textit {i}}^{\prime \prime }$ by recursively applying Construction 3. Example 2 shows a (t = 1, k = 3, n = 4) access structure where, participant p₁ is an essential participant and is present in all the qualified sets.

Based on some access structures mentioned in Table 1 it is evident that APE for XOR based step construction by Liu et al. [28] VCS is less when compared with VCS by Ateniese et al. [6], Adhikari et al. [3], Shyu et al. [42], Cimato et al. [10], Wang et al. [45] and Praveen et al.[37]. Also constructions [10, 28, 37, 45] will provide ideal contrast, but we cannot obtain ideal contrast for constructions [3, 6, 42]. The disadvantage of constructions [10, 28, 37, 45] is each participant needs to carry multiple shares which is of the same size of secret image, but in the case of constructions [3, 6, 42] each participant needs to carry a single pixel expanded share.

Table 1 APE of VCS for some access structures

Example 2

Let P = {p₁,p₂,p₃,p₄} be the set of participants, the secret image is denoted as SI and shares generated using XOR step construction are of same size of SI. Let Γ_EM = {{p₁,p₂,p₃},{p₁,p₂,p₄},{p₁,p₃,p₄}} and Γ_FM = {{p₂,p₃},{p₂,p₄},{p₃,p₄},{p₁,p₂},{p₁,p₃},{p₁,p₄}}.

As per the scheme, Γ_EM is already in the most simplified form and also satisfies the condition of Construction 2, so $\widetilde {{\Gamma }_{\textit {QM}}} = {\Gamma }_{\textit {QM}}$. Let Γ₁ be the partition obtained from $\widetilde {{\Gamma }_{\textit {QM}}}$. Then apply Construction 2 on Γ₁ to generate ${\Gamma }_{1}^{\prime } = {\Gamma }_{1}^{\prime \prime }$ = {{p₂,p₃},{p₂,p₄},{p₃,p₄}}.

Let the virtual participant be $\textit {E}_{1}^{\prime } = {\Gamma }_{1}^{\prime \prime }$ then ${\Gamma }_{1} = \{\textit {p}_{1} ,\textit {E}_{1}^{\prime }\}$. Apply (2, 2)-VCS on the set Γ₁ which generate shares $\textit {Sh}_{1}^{L}$ and $\textit {Sh}_{1}^{\prime }$ from SI. Distribute $\textit {Sh}_{1}^{L}$ to p₁ and $\textit {Sh}_{1}^{\prime }$ to virtual participant $\textit {E}_{1}^{\prime }$. Take $\textit {Sh}_{1}^{\prime }$ as the secret image and apply step construction on ${\Gamma }_{1}^{\prime \prime }$. As per the scheme it is possible to divide ${\Gamma }_{1}^{\prime \prime }$ into two parts say, {{p₂,p₃},{p₂,p₄}} and {{p₃,p₄}}.In the case of set {{p₂,p₃},{p₂,p₄}},{p₃,p₄}∈Γ_FM. So $\textit {p}_{3}\sim \textit {p}_{4}$. Apply (2, 2)-VCS on $\textit {Sh}_{1}^{\prime }$ to generate shares $\textit {Sh}_{2}^{L1}$ and $\textit {Sh}_{2}^{R1}$. Based on Definition 2, 3 and Theorem 1, distribute $\textit {Sh}_{2}^{L1}$ to p₂ and $\textit {Sh}_{2}^{R1}$ to p₃ and p₄.In the case of set {{p₃,p₄}}, apply (2, 2)-VCS on $\textit {Sh}_{1}^{\prime }$ to generate shares $\textit {Sh}_{2}^{L2}$ and $\textit {Sh}_{2}^{R2}$. Distribute $\textit {Sh}_{2}^{L2}$ to p₃ and $\textit {Sh}_{2}^{R2}$ to p₄.

So p₁ holds share $\textit {H}_{(1, 1)} = \textit {Sh}_{1}^{L}$ which implies N₁ = 1. p₂ holds share $\textit {H}_{(2, 1)} = \textit {Sh}_{2}^{L1}$ which implies N₂ = 1. p₃ holds shares $\textit {H}_{(3, 1)} = \textit {Sh}_{2}^{R1}$ and $\textit {H}_{(3, 2)} = \textit {Sh}_{2}^{L2}$ which implies N₃ = 2. p₄ holds shares $\textit {H}_{(4, 1)} = \textit {Sh}_{2}^{R1}$ and $\textit {H}_{(4, 2)} = \textit {Sh}_{2}^{R2}$ which implies N₄ = 2. So APE = (1 + 1 + 2 + 2)/4.

3 Main results

3.1 Proposed Construction (PC1)

Initially generate H_(u,j)(g,h) for SI as given in share generation phase of Section 2.2. As given in Definition 1, in order to provide randomness [13, 17] while encoding each pixel in SI, S₀ or S₁ are updated with a column permutation operation. The algorithm to generate n ×m meaningful shares Sh_(u,j)(g,h) from the n × (m − 2) distinct cover images COV_(u,j)(g,h) and a pair of complementary cover images (CV, IV ) for the secret image SI is given below.

3.1.1 Share generation and distribution phase

3.1.2 Secret reconstruction phase

Using Praveen et al. [37] reconstruction algorithm generate the secret RI(g, h) = $\bigodot \limits _{j = 1}^{m} \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in \textit {A}}\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h})$.

3.1.3 Analysis on the APE, contrast and security

This construction is based on the proper arrangement of first, second and third bit in the blocks D_(u,j) which is of size 1 × 3. In the construction, same column permutation is applied for all D matrices corresponding to a secret pixel s in SI. Let us assume r₁,r₂,r₃ as random bits either 0 or 1 and COV_(u,j),CV (g,h),IV (g,h) (inverted CV (g,h)) as meaningful cover images. Assign the second bit of all D_(u,j) as H_(u,j), the first and third bit are same as that of corresponding meaningful image. If m is the pixel expansion of a VCS, according to the algorithm m - 2 shares of u^th participant are generated using COV_(u,j). During reconstruction phase corresponding to s, all the j^th (D_(u,j)) block of the qualified participants stacked(OR) together to generate j^th ($\left [\begin {array}{ccc}\textit {r}_{1} & \textit {r}_{2} & \textit {r}_{3} \end {array}\right ]$) block and when AND-ing all the j blocks, $\left [\begin {array}{ccc} 0 & \textit {s} & 0 \end {array}\right ]$ is obtained corresponding to s in RI. The design rationale is (m − 1)^th meaningful share and m^th meaningful share of u^th participant are constructed using CV (g,h) and IV (g,h) respectively. In this construction all the n participants hold m shares and the pixel expansion in each share is 3. So APE for this EVCS is $\frac {3\times \textit {n}\times \textit {m}}{\textit {n}}$, where m is the pixel expansion of a perfect black general access structure VCS. It is possible to construct a (t, k, n) - EVCS based on our PC1, when the inputs S₀ (resp. S₁) are basis matrices of size $\textit {n}\times 2^{t}\textit {m}_{1}$ constructed from a perfect black Guo et al. [19] - VCS, where m₁ is the pixel expansion of a perfect black (k - t, n - t) VCS. It is also possible to construct a (1, k, n) - EVCS, when the inputs S₀ (resp. S₁) are basis matrices of size n × 2m₂ constructed from a perfect black scheme of Arumugam et al. [4] - VCS, where m₂ is the pixel expansion of a perfect black (k - 1, n - 1) VCS. Arumugam et al. [4] - VCS is a special case of Guo et al. [19] - VCS. The APE for our (t, k, n) - EVCS constructed by using Guo et al. [19] - VCS is $\frac {3\times \textit {n}\times (2^{t}\times \textit {m}_{1})}{\textit {n}}$. The APE for our (1, k, n) - EVCS constructed by using Arumugam et al. [4] - VCS is $\frac {3\times \textit {n}\times (2\times \textit {m}_{2})}{\textit {n}}$. Step construction based (t = 1, k = 3, n = 4) - VCS using XOR operation is shown in Example 2. In the construction same permutation is applied for all D matrices corresponding to a secret pixel in SI. For proving contrast and security we have not considered permutation of D matrices.

Proof of Contrast :

Let ${\Omega }_{1}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {Sh}_{(\textit {u}, 1)}(\textit {g}, \textit {h}), {\Omega }_{2}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {Sh}_{(\textit {u}, 2)}(\textit {g}, \textit {h})$, ......, ${\Omega }_{\textit {m}-1}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {Sh}_{(\textit {u}, \textit {m}-1)}(\textit {g}, \textit {h}), {\Omega }_{\textit {m}}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {Sh}_{(\textit {u}, \textit {m})}(\textit {g}, \textit {h})$.

Let RI(g, h) = $\bigodot \limits _{j = 1}^{z} {\Omega }_{\textit {j}}(\,\textit {g}, \textit {h})\bigodot {\Omega }_{\textit {m} - 1}(\,\textit {g}, \textit {h})\bigodot {\Omega }_{\textit {m}}(\,\textit {g}, \textit {h})$, where z = m - 2= $\bigodot \limits _{j = 1}^{z} {\Omega }_{\textit {j}}(\,\textit {g}, \textit {h}) \bigodot \left [\begin {array}{ccc}{\Omega }_{\textit {m}-1}(\,\textit {g}, \textit {h})\bigodot {\Omega }_{\textit {m}}(\,\textit {g}, \textit {h}) \end {array}\right ] = \bigodot \limits _{j = 1}^{z} {\Omega }_{\textit {j}}(\,\textit {g}, \textit {h})\bigodot \left [\begin {array}{ccc}0 & ({\Delta }_{\textit {m} - 1}(\,\textit {g}, \textit {h})\bigodot {\Delta }_{\textit {m}}(\,\textit {g}, \textit {h})) & 0 \end {array}\right ]$= $\left [\begin {array}{ccc}0 & \bigodot \limits _{j = 1}^{m} {\Delta }_{\textit {j}}(\,\textit {g}, \textit {h}) & 0 \end {array}\right ] = \left [\begin {array}{ccc}0 & \textit {SI}(\,\textit {g}, \textit {h}) & 0 \end {array}\right ]$. When SI = $\left [\begin {array}{cc} 1 & 0 \end {array}\right ]$, for SI(0, 0) the reconstructed RI(0, 0) = $\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$ and for SI(0, 1) the reconstructed RI(0, 1) = $\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$. Then relative contrast of reconstructed image RI is calculated as $\frac {\left (\textit {W}\left (\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]\right )-\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )\right )}{3}$ = 0.333. This implies that when the participants in the qualified set join, the 0 and 1 pixel are distinguishable so that secret is revealed.

Proof of Security :

Generate ${\Omega }_{1}(\textit {g}, \textit {h}) = \bigotimes _{\textit {p}_{\textit {u}\in {\Gamma }_{\textit {FM}}}}\textit {Sh}_{(\textit {u}, 1)}(\textit {g}, \textit {h}), {\Omega }_{2}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {FM}}}\textit {Sh}_{(\textit {u}, 2)}(\textit {g}, \textit {h})$, ......, ${\Omega }_{\textit {m}-1}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {FM}}}\textit {Sh}_{(\textit {u}, \textit {m} - 1)}(\textit {g}, \textit {h}), {\Omega }_{\textit {m}}(\textit {g}, \textit {h}) = \bigotimes \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {FM}}}\textit {Sh}_{(\textit {u}, \textit {m})}(\textit {g}, \textit {h})$. Here, when SI =$\left [\begin {array}{cc} 1 & 0 \end {array}\right ]$, for SI(0, 0) the reconstructed RI(0, 0) = $\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$ and for SI(0, 1) the reconstructed RI(0, 1) = $\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$. Then relative contrast of reconstructed image RI is calculated as $\frac {\left (\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )-\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )\right )}{3}$ = 0 and this implies that when the participants in the forbidden set join, the 0 and 1 pixel are indistinguishable so that secret cannot be revealed.

Proof of Contrast for meaningful shares :

According to the construction when H_(u,j)(g,h) = 0 and COV_(u,j)(g,h) = 0, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$, when H_(u,j)(g,h) = 0 and COV_(u,j)(g,h) = 1, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}1 & 0 & 1 \end {array}\right ]$, when H_(u,j)(g,h) = 1 and COV_(u,j)(g,h) = 0, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$, when H_(u,j)(g,h) = 1 and COV_(u,j)(g,h) = 1, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}1 & 1 & 1 \end {array}\right ]$. So $\textit {W}(\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}1 & 0 & 1 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}1 & 1 & 1 \end {array}\right ])$ which implies that the contrast of the cover images is preserved in the meaningful shares. The contrast value will range from 1 to 3. So the ratio of cover pixel (resp. secret information pixel) preserved in a block of size 1 × 3 of the meaningful share is 0.666 (resp. 0.333).

Example 3

Let P = {p₁,p₂,p₃} be the set of participants, Γ_QM ={{p₁,p₂},{p₁,p₃},{p₂,p₃}} and Γ_FM = {{p₁},{p₂},{p₃}}. Let SI = $\left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {S}_{0} = \left [ \begin {array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end {array}\right ]$ and $\textit {S}_{1} = \left [ \begin {array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end {array}\right ]$. The cover images used for creating meaningful shares are $\textit {COV}_{(1, 1)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {COV}_{(1, 2)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {COV}_{(1, 3)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {COV}_{(1, 4)} = \overline {\textit {COV}_{(1,3)}}, \textit {COV}_{(2, 1)} = \left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {COV}_{(2, 2)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {COV}_{(2, 3)} = \textit {COV}_{(1, 3)}, \textit {COV}_{(2, 4)} = \overline {\textit {COV}_{(1, 3)}}, \textit {COV}_{(3, 1)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {COV}_{(3, 2)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {COV}_{(3, 3)} = \textit {COV}_{(1, 3)}, \textit {COV}_{(3, 4)} = \overline {\textit {COV}_{(1, 3)}}$. The constructed H matrices are $\textit {H}_{(1, 1)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {H}_{(1, 2)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(1, 3)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(1, 4)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(2, 1)} = \left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {H}_{(2, 2)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {H}_{(2, 3)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(2, 4)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(3, 1)} = \left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {H}_{(3, 2)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(3, 3)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {H}_{(3, 4)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ]$. Then the constructed meaningful shares are $\textit {Sh}_{(1, 1)} = \left [\begin {array}{cc} 000 & 000 \end {array}\right ], \textit {Sh}_{(1, 2)} = \left [\begin {array}{cc} 010 & 111 \end {array}\right ], \textit {Sh}_{(1, 3)} = \left [\begin {array}{cc} 111 & 111 \end {array}\right ], \textit {Sh}_{(1, 4)} = \left [\begin {array}{cc} 010 & 010 \end {array}\right ], \textit {Sh}_{(2, 1)} = \left [\begin {array}{cc} 111 & 000 \end {array}\right ], \textit {Sh}_{(2, 2)} = \left [\begin {array}{cc} 101 & 111 \end {array}\right ], \textit {Sh}_{(2, 3)} = \left [\begin {array}{cc} 111 & 111 \end {array}\right ], \textit {Sh}_{(2 ,4)} = \left [\begin {array}{cc} 010 & 010 \end {array}\right ], \textit {Sh}_{(3, 1)} = \left [\begin {array}{cc} 010 & 101 \end {array}\right ], \textit {Sh}_{(3, 2)} = \left [\begin {array}{cc} 010 & 010 \end {array}\right ], \textit {Sh}_{(3, 3)} = \left [\begin {array}{cc} 101 & 111 \end {array}\right ], \textit {Sh}_{(3, 4)} = \left [\begin {array}{cc} 010 & 010 \end {array}\right ]$. Same column permutations are applied to all Sh matrices corresponding to a single pixel in SI. According to this construction $\textit {RI} = \left [\begin {array}{cc} 010 & 000 \end {array}\right ]$. Thus relative contrast of reconstructed image is 0.333 and APE = 12. Figs. 4 , 5 , 6 and 7 shows the experimental results for this Example.

Fig. 4

Meaningful share images of participant p₁ for (2, 3) PC1-EVCS

Fig. 5

Meaningful share images of participant p₂ for (2, 3) PC1-EVCS

Fig. 6

Meaningful share images of participant p₃ for (2, 3) PC1-EVCS

Fig. 7

Secret image and Reconstructed image in the case of (2, 3) PC1-EVCS

3.2 Proposed Construction (PC2)

Initially, generate {H_(u,j) : 1 ≤u ≤n,1 ≤j ≤N_u} by XOR step construction [28] for VCS given in share generation phase of Section 2.3. The algorithm to generate (N_u + 1) meaningful shares from {H_(u,j) : 1 ≤u ≤n,1 ≤j ≤N_u} for each u^th participant is given below.

3.2.1 Share generation and distribution phase

3.2.2 Secret reconstruction phase [28]

Let A = $\left \{\textit {i}_{1},\textit {i}_{2}, ......,\textit {i}_{\textit {p}}\right \} \in {\Gamma }_{\textit {QM}}$. Assume the shares carried by the participant i_p are $\textit {Sh}_{(\textit {i}_{\textit {p}}, \textit {j})}$, where 1 ≤j ≤Ni_p. Here Ni_p denotes the number of shares carried by the participant i_p.For j₁ = 1 to Ni₁For j₂ = 1 to Ni₂..For j_p = 1 to Ni_p$\textit {O}_{(\textit {j}_1, \textit {j}_2 , ......,\textit {j}_{\textit {p}})}(\textit {g}, \textit {h}) = \textit {Sh}_{(\textit {i}_1, \textit {j}_1)} \bigoplus \textit {Sh}_{(\textit {i}_2, \textit {j}_2)} \bigoplus$......$\bigoplus \textit {Sh}_{(\textit {i}_{\textit {p}-1}, \textit {j}_{\textit {p}-1})} \bigoplus \textit {Sh}_{(\textit {i}_{\textit {p}}, \textit {j}_{\textit {p}})}$.End..EndEnd Here only one OI(g,h) from the set of all $\textit {O}_{(\textit {j}_1, \textit {j}_2 , ......,\textit {j}_{\textit {p}})}(\textit {g}, \textit {h})$ will be used to generate RI(g, h). So, each u^th participant in Γ_QM generates the secret, RI(g, h) = $\textit {OI}(\textit {g}, \textit {h}) \bigodot (\textit {Sh}_{(\textit {u}, (\textit {N}_{u} + 1))}\bigoplus \textit {Sh}_{(\textit {u}, \textit {R}_{u})})$.

3.2.3 Analysis on the APE, contrast and security

This construction is based on the proper arrangement of first, second and third bit in the blocks D_(u,j) which is of size 1 × 3. In the construction same column permutation is applied for all D matrices corresponding to a secret pixel s in SI. Let us assume r₁,r₂,r₃ as random bits either 0 or 1 and {COV_(u,j) : 1 ≤u ≤n,1 ≤j ≤N_u} be the set of distinct cover images. Assign the second bit of all D_(u,j) as H_(u,j), the first and third bit are same as that of corresponding {COV_(u,j)}. During reconstruction phase, when XOR-ing D_(u,j) blocks of the qualified participants $\left [\begin {array}{ccc}\textit {r}_1 & \textit {s} & \textit {r}_3 \end {array}\right ]$ block is generated. Then $\left [\begin {array}{ccc} 0 & \textit {s} & 0 \end {array}\right ]$ block corresponding to s in RI is generated when AND-ing $\left [\begin {array}{ccc}\textit {r}_1 & \textit {s} & \textit {r}_3 \end {array}\right ]$ with $\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$. Each u^th participant can generate $\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$ block by XOR-ing $\textit {D}_{(\textit {u}, (\textit {N}_{u} + 1))}$ with $\textit {D}_{(\textit {u}, \textit {R}_{u})}$ because the first and the third bit of blocks $\textit {D}_{(\textit {u}, (\textit {N}_{u} + 1))}$ and $\textit {D}_{(\textit {u}, \textit {R}_{u})}$ are generated using same cover image $\textit {COV}_{(\textit {u}, \textit {R}_{u})}$. Here each i^th participant in P holds (N_i + 1) shares, so APE for this step construction based EVCS is $\frac {3\times \left (\sum \limits _{i = 1}^n \textit {N}_{\textit {i}} + \textit {n}\right )}{\textit {n}}$.

Proof of Contrast :

Consider the case of (n, n) access structure, where OI(g, h) = $\textit {Sh}_{(\textit {i}_1,1)} \bigoplus \textit {Sh}_{(\textit {i}_2,1)}\bigoplus$...... $\bigoplus \textit {Sh}_{(\textit {i}_{\textit {p}-1},1)}\bigoplus \textit {Sh}_{(\textit {i}_{\textit {p}},1)}, \big \{\textit {i}_1,\textit {i}_2, ......,\textit {i}_{\textit {p}}\big \} \in {\Gamma }_{\textit {QM}}$. Let us denote the following $\textit {b}_1 = \bigoplus \nolimits _{\textit {p}_{\textit {u}}\in {\Gamma }_{\textit {QM}}}\textit {COV}_{(\textit {u}, 1)}(\textit {g}, \textit {h})$ $\textit {Sh}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}\textit {COV}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h})&\textit {H}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h})&\textit {COV}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h}) \end {array}\right ]$

$\textit {Sh}_{(\textit {u}, (\textit {N}_{u} + 1))}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}\textit {COV}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h})&\overline {\textit {H}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h})}&\textit {COV}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h}) \end {array}\right ]$RI(g, h) $= \textit {OI}(\textit {g}, \textit {h}) \bigodot (\textit {Sh}_{(\textit {u}, (\textit {N}_{u} + 1))}(\textit {g}, \textit {h})\bigoplus \textit {Sh}_{(\textit {u}, \textit {R}_{u})}(\textit {g}, \textit {h}))$

$= \left [\begin {array}{ccc}\textit {b}_{1}&\textit {SI}(\,\textit {g}, \textit {h})&\textit {b}_{1} \end {array}\right ]\bigodot \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$

= $\left [\begin {array}{ccc}0 & \textit {SI}(\,\textit {g}, \textit {h}) & 0 \end {array}\right ]$.

When SI = $\left [\begin {array}{cc} 1 & 0 \end {array}\right ]$, for SI(0, 0) reconstructed pixel RI(0, 0) = $\left [\begin {array}{ccc}\textit {b}_{1} & 1 & \textit {b}_{1} \end {array}\right ]\bigodot \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ] = \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$ and for SI (0, 1) reconstructed RI(0, 1) = $\left [\begin {array}{ccc}\textit {b}_{1} & 0 & \textit {b}_{1} \end {array}\right ]\bigodot \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ] = \left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$. So the relative contrast of the reconstructed image RI is calculated as $\frac {\left (\textit {W}\left (\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]\right )-\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )\right )}{3}$ = 0.333. This implies that when the participants in the qualified set join, the 0 and 1 pixel are distinguishable so that secret is revealed.

In Figs. 8, 9 and 10 (Sh_(1,1),Sh_(1,2)), (Sh_(2,1),Sh_(2,3)) and (Sh_(3,1),Sh_(3,3)) are the similar cover shares held by participants p₁,p₂ and p₃ respectively for (2, 3) - EVCS.

Fig. 8

Meaningful share images of participant p₁ for (2, 3) PC2-EVCS

Fig. 9

Meaningful share images of participant p₂ for (2, 3) PC2-EVCS

Fig. 10

Meaningful share images of participant p₃ for (2, 3) PC2-EVCS

Proof of Security:

Here, for SI = $\left [\begin {array}{cc} 1 & 0 \end {array}\right ]$, when $\left \{\textit {i}_{1},\textit {i}_{2}, ......,\textit {i}_{\textit {p}}\right \} \in {\Gamma }_{\textit {FM}}$, for SI(0, 0) (resp. SI(0, 1)) the intermediate pixels OI(0, 0) (resp. OI(0, 1)) is $\left [\begin {array}{ccc}\textit {b}_{1} & 0 & \textit {b}_{1} \end {array}\right ]$, the reconstructed pixels RI(0, 0) (resp. RI(0, 1)) is $\left [\begin {array}{ccc}\textit {b}_{1} & 0 & \textit {b}_{1} \end {array}\right ]\bigodot \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ] = \left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$. So the relative contrast is calculated as $\frac {\left (\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )-\textit {W}\left (\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]\right )\right )}{3}$ = 0. This provides a 0 contrast and implies that when the participants in the forbidden set join, the 0 and 1 pixel are indistinguishable so that secret cannot be revealed.

Proof of Contrast for meaningful shares:

According to the construction when H_(u,j)(g,h) = 0 and COV_(u,j)(g,h) = 0, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]$, when H_(u,j)(g,h) = 0 and COV_(u,j)(g,h) = 1, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}1 & 0 & 1 \end {array}\right ]$, when H_(u,j)(g,h) = 1 and COV_(u,j)(g,h) = 0, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]$, when H_(u,j)(g,h) = 1 and COV_(u,j)(g,h) = 1, then $\textit {Sh}_{(\textit {u}, \textit {j})}(\textit {g}, \textit {h}) = \left [\begin {array}{ccc}1 & 1 & 1 \end {array}\right ]$. So $\textit {W}(\left [\begin {array}{ccc}0 & 0 & 0 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}0 & 1 & 0 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}1 & 0 & 1 \end {array}\right ]) < \textit {W}(\left [\begin {array}{ccc}1 & 1 & 1 \end {array}\right ])$ which implies that the contrast of the cover images is preserved in the meaningful shares. The contrast value will range from 1 to 3. So the ratio of cover pixel (resp. secret information pixel) preserved in a block of size 1 × 3 of the meaningful share is 0.666 (resp. 0.333).

Example 4

Consider same P, Γ_QM,Γ_FM, SI as given in Example 1. Let R_u = {1,2,1}. The cover images used are $\textit {COV}_{(1, 1)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {COV}_{(1, 2)} = \textit {COV}_{(1, 1)}$, $\textit {COV}_{(2, 1)} = \left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {COV}_{(2, 2)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {COV}_{(2, 3)} = \textit {COV}_{(2, 2)}, \textit {COV}_{(3, 1)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {COV}_{(3, 2)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ], \textit {COV}_{(3, 3)} = \textit {COV}_{(3,1)}$. The constructed H matrices are $\textit {H}_{(1, 1)} = \left [\begin {array}{cc} 0 & 1 \end {array}\right ], \textit {H}_{(2, 1)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(2, 2)} = \left [\begin {array}{cc} 1 & 0 \end {array}\right ], \textit {H}_{(3, 1)} = \left [\begin {array}{cc} 1 & 1 \end {array}\right ], \textit {H}_{(3, 2)} = \left [\begin {array}{cc} 0 & 0 \end {array}\right ]$. Then the constructed meaningful shares with APE = $\frac {(3 + 3)+(3 + 3 + 3)+ (3 + 3 + 3)}{3}$ = 8 are $\textit {Sh}_{(1, 1)} = \left [\begin {array}{cc} 000 & 010 \end {array}\right ], \textit {Sh}_{(1, 2)} = \left [\begin {array}{cc} 010 & 000 \end {array}\right ], \textit {Sh}_{(2, 1)} = \left [\begin {array}{cc} 111 & 010 \end {array}\right ], \textit {Sh}_{(2, 2)} = \left [\begin {array}{cc} 111 & 101 \end {array}\right ], \textit {Sh}_{(2, 3)} = \left [\begin {array}{cc} 101 & 111 \end {array}\right ], \textit {Sh}_{(3, 1)} = \left [\begin {array}{cc} 010 & 111 \end {array}\right ], \textit {Sh}_{(3, 2)} = \left [\begin {array}{cc} 000 & 000 \end {array}\right ], \textit {Sh}_{(3, 3)} = \left [\begin {array}{cc} 000 & 101 \end {array}\right ]$. Same column permutations are applied to all Sh matrices corresponding to a single pixel in SI. After reconstruction $\textit {RI} = \left [\begin {array}{cc} 010 & 000 \end {array}\right ]$ with α = 0.330. Figs. 8 , 9 , 10 and 11 shows the experimental results for this example.

Fig. 11

Secret image and Reconstructed image in the case of (2, 3) PC2-EVCS

3.3 Comparison with related works

There are plenty of deterministic and probabilistic schemes applicable for Binary/Gray/Color images available in the literature. The reconstruction operations for these schemes are Stacking(OR) and XOR operation. Each participant may hold Single/Multiple meaningful shares based on the construction. In Halftone VCS [27, 63], a single secret pixel is encoded with a halftone cell size which is selected based on the access structure and the number of participants. In order to avoid image distortion (maintain the aspect ratio) during halftoning process, halftone cell size is selected as square number like 4, 9, 16, 25, 32 etc. According to EVCS by Wang et al. [48] and Yan et al. [56] for maintaining good quality meaningful shares, if m is the pixel expansion of a VCS then the halftone cell size needs to be ≥ 2 ×m based on the access structure. According to EVCS by Wang et al. [46] if m is the pixel expansion of a (k, n) - VCS the pixel expansion of (k, n) - EVCS will be ≥m + $\lceil \frac {\textit {n}}{\textit {k}-1}\rceil$. Guo et al. [19] derived that, the pixel expansion for a (t, k, n) - VCS by Ateniese et al. [6] is $2^{{{\textit {n} - \textit {t}}\choose {\textit {k} - \textit {t} - 1}}+\textit {t} - 1}$. So, the pixel expansion for a (t, k, n) - EVCS by Ateniese et al. [5] is obtained as $2^{{{\textit {n} - \textit {t}}\choose {\textit {k} - \textit {t} - 1}}+\textit {t}}$. Based on these observations comparison of our schemes with related works is shown below.

• 1) Table 2 shows that our PC1 (resp. PC2) are deterministic general access structure schemes applicable to Binary images which use OR-AND (resp. XOR-AND) operations for reconstruction. Based on our constructions each participant need to hold multiple shares similar to the EVCS constructed by Zhou et al. [63]. The advantages of our PC1 (resp. PC2) with a computing model of OR-AND (resp. XOR-AND) compared to other approaches are the following a)Less APE b)High relative contrast for the reconstructed image(α) c) High relative contrast for the meaningful share images(ρ).

• 2) Table 2 shows a review on various EVCS constructions. In Table 3, 4 and 5, deterministic schemes which are applicable to Binary images are selected from Table 2 for comparison. In Table 3, for (2, 3)-Halftone VCS [63], participant p₁ holds one share each and participant p₂ and p₃ hold two shares each. The APE and relative contrast are $\frac {(16 + (2\times 16) + (2\times 16))}{3}$ = 26.63 and 0.062 respectively. In Table 4 , for (1, 3, 4)-Halftone VCS [63], participants p₁ and p₂ hold one share each and participants p₃ and p₄ hold two shares each. The APE and relative contrast are $\frac {(16 + 16 + (2\times 16) + (2\times 16))}{4}$ = 24 and 0.062 respectively. In Table 5, for (2, 4, 5)-Halftone VCS [63], participants p₁,p₂ and p₃ hold one share each and participants p₄ and p₅ hold two shares each. The APE and relative contrast are $\frac {(16 + 16 + 16 + (2\times 16) + (2\times 16))}{5}$ = 22.4 and 0.062 respectively. Our PC1(resp. PC2) have better results compared to Halftone VCS [63] and other related works because our computing model is OR-AND (resp. XOR-AND) instead of only OR or XOR reconstruction. The reconstruction operation count for different EVCS constructions for (2, 3) access structure is also given in Table 3. In case of EVCS given in paper [63] the minimum (resp. maximum) number of OR operations is 16(resp. 32). For PC2 the secret image will be reconstructed by minimum 6 XOR + 3 AND operations or by maximum 12 XOR + 6 AND operations. If more shares of a participant are involved in reconstruction the Boolean operations will also increase.

• 3) For (2, 2) and (3, 3) EVCS by Liu et al. [27], the APE is 9 and 16 respectively, but for our PC2 it is 6. Some probabilistic EVCS [18, 22] have better relative contrast of reconstructed secret image than 0.333 for some access structure. But the relative contrast calculations of deterministic and probabilistic schemes are different. Like our construction, schemes given in paper [5, 27] also use perfect black VCS as building blocks.

• 4) The (APE, α) values for the EVCS constructions [5, 27, 46, 48, 56, 62, 63] given in Tables 3, 4 and 5 are calculated under the assumption that the VCS used is Ateniese et al. [6] construction. But Blundo et al. [7] constructed a perfect black (k, n) - VCS with less pixel expansion in 2001. So the (APE, α) values for the EVCS constructions [5, 46, 48, 56] given in Table 6 (resp. 7) are calculated under the assumption that the (k, n) - VCS used is Blundo et al. [7] construction and (t, k, n) - VCS used is Guo et al. [19] construction. In Tables 8 and 9, the (APE, α) values for our PC2 - EVCS are calculated under the assumption that the VCS used is XOR based step construction by Liu et al. [28]. The APE values of our PC2 - EVCS are directly derived from the APE values of XOR based VCS given in Table 1 of paper [28].

• 5) In Halftoning EVCS, the halftone block size vary depends on the pixel expansion of VCS used, peak signal to noise ratio (PSNR) and universal quality index(UQI) measurements are used to calculate the distortion of cover share image compared to original halftoned share images. Let us define em (resp. m) as the pixel expansion of an EVCS (resp. VCS). Then em = m (represents: secret information pixels) + q (represents: cover image information pixels + auxiliary black pixels). So the visual quality (relative contrast) of the cover share images is calculated as $\rho =\frac {\textit {em} - \textit {m}}{\textit {em}}>0$ [48, 56]. Table 10 shows that the visual quality of our EVCS constructions maintain the quality of existing deterministic EVCS in the literature. The user can select the values for em and m based on the applications.

• 6) The reconstructed image quality of our EVCS (Fig. 1) is better than Ateniese et al. [5] - EVCS and the probabilistic scheme of Yang [57] for (2, 3) access structure.

Table 2 Review of different EVCS construction

Table 3 Comparison for (2, 3) - EVCS

Table 4 Comparison for (1, 3, 4) - deterministic schemes

Table 5 Comparison for (2, 4, 5) - deterministic schemes

Table 6 Comparison for (k, n) access structure

Table 7 Comparison for (t, k, n) access structure

Table 8 Comparison for some access structure using step construction

Table 9 Comparison for (k, n) access structure using step construction

Table 10 Comparison of visual quality of cover share images ρ for (3, 3) - EVCS

4 Conclusions

Our deterministic EVCS constructions have a relative contrast of 0.333 for both the reconstructed image and cover share images for all access structures. It is evident that our EVCS construction PC2 has less APE and high relative contrast for reconstructed image compared to all other deterministic EVCS constructions for any access structure. It is true that, our proposed deterministic EVCS constructions are complex due to a) Combined use of Boolean operations OR and AND (resp. XOR and AND) instead of only OR or XOR operation for reconstruction b) Each participant holds multiple shares instead of single share c) Selection of cover images (Complementary cover images in PC1, Similar cover images in PC2). But in our schemes there are no complex calculations involved in finding q (represents: cover image information pixels + auxiliary black pixels) needed for maintaining the visual quality of cover share images, as in halftoning EVCS constructions. In our schemes, for all the cover image shares the value of q = 2 for any access structure, but in halftoning EVCS constructions q will vary according to the access structure. Moreover our proposed schemes can be used effectively for applications [2, 11, 21, 30, 38, 43, 60, 61] which need less storage space (less APE) and high reconstructed image quality (high relative contrast). At the same time in deterministic EVCS, a thin line in the secret is converted to a thick line and due to pixel expansion problem it may lead to graying effect but in probabilistic EVCS, a thin line may not be visible in the reconstructed secret. Our deterministic EVCS constructions solves this problem of thin line discussed in papers [26, 29].