Cheating Immune Visual Cryptographic Scheme with Reduced Pixel Expansion

Abstract

One of the drawbacks in visual cryptography is cheating attacks, where the malicious adversaries can cheat the honest participant by submitting fake shares during reconstruction phase. Cheating immune visual cryptographic schemes are used for mitigating cheating attacks in visual cryptography. There are two types of cheating immune schemes: One is share authentication-based schemes, and the other is blind authentication-based schemes. For the existing blind authentication-based schemes, the pixel expansion value will increase in the order of O(n). In this paper, a blind authentication-based cheating immune visual cryptographic scheme is proposed by modifying the existing scheme based on uniform codes where the pixel expansion value will increase in the order of O(log n).

1 Introduction

Visual cryptography is an unconditionally secure secret splitting technique used to generate n shares from a secret image (SI). During the distribution phase, these shares are given to each of the n participants, and the secret image will be visible only during the reconstruction phase when sufficient participants combine their shares. In visual cryptographic scheme (VCS) for reconstruction, the Boolean operators OR, AND, NOT, XOR are used instead of complicated computation as in conventional cryptography. The quality of a VCS is quantified using pixel expansion m and contrast α.m. A pixel in SI is converted to m sub pixels in all shares. In the reconstructed image, gray levels of black and white pixel differ by α.m. The participants in the qualified (resp. forbidden) set can (resp. cannot) reconstruct the secret image. VCS are of different types namely (2, n), (k, n), and general access structure.VCS can also be classified into deterministic and probabilistic scheme depending upon the reconstruction of the secret. In 1994, Naor and Adi Shamir [1] developed deterministic VCS’s, where OR (stacking) operation is used for reconstruction of secret image. The constructions of conventional VCS cannot resist against cheating attacks. So attacks (deterministic white to black (DWtB), deterministic black to white (DBtW) and region based) are possible against honest participants or victims by the malicious adversaries (collusive cheaters, malicious participant, and malicious outsider), by submitting fake shares during reconstruction process. There are two types of cheating immune visual cryptographic scheme (CIVCS): One is share authentication (SA)-based CIVCS, and the other is blind authentication (BA)-based CIVCS. In SA, apart from the shares of participants, extra information generated by the dealer or the participant is needed to verify cheating but in BA the shares are constructed in such a manner that the cheaters are not able to identify the structure of other participant’s share. Two SA-based CIVCS are proposed by Yang and Laih [3] in 1999. The verification of shares is done with (resp. without) the help of an online trusted third party in the first (resp. second) CIVCS. The collusive cheating attack in (k, n)—VCS and its two mitigation techniques was developed by Horng et al. [4] in 2006. The first one is a SA technique, where each participant needed to carry extra verification transparencies, while the second technique is a (2, n) scheme based on BA, where (n + l) shares are generated in the sharing phase but only randomly selected n shares are used for distribution which makes cheaters hard to accomplish a successful attack. But, second technique protects only black pixels from cheating while white pixels are vulnerable to attack. Tsai et al. [5] in 2007 proposed a BA-based CIVCS using genetic algorithm by creating multiple homogeneous secret images. Here, the probability of successful cheating is highly decreased compared to [4] second scheme. Hu and Tzeg [6] in 2007 identified that cheating attack is possible by malicious participant or a malicious outsider if the VCS is not following perfect black criteria. The authors showed attacks on [3] first cheating method and on [4] scheme. The paper [6] also proposes SA-based CIVCS with reduced pixel expansion than [3] second method. De Prisco et al. [7] in 2010 proposed an (n, n) BA-based CIVCS and two (2, n) BA-based CIVCS. The first (2, n) scheme is a simple scheme but with a weakness that white pixels are not protected. The second scheme protects both white and black pixels by making use of larger m. Tsai et al. [8] in 2010 showed that the genetic algorithm-based CIVCS given in Tsai et al. [5] decodes the secret share incorrectly. Liu et al. [9] in 2011 proposed a SA-based CIVCS by disclosing t secret pixels to participants during the share distribution phase. The scheme is applicable to every VCS by verifying that the positions of randomly choosing t pixels in the secret are following the same color or not in the reconstructed image. Wang et al. [10] in 2011 proposed a SA-based tagged VCS for cheating prevention. Chen et al. [11] in 2011 showed a new variant of attack called Region cheating attack (RCA) which cheat human visual system (HVS), when for a region in the secret image if there is a white pixel surrounded by lot of black pixels or a black pixel surrounded by lot of white pixels. The paper also shows that DWtB attack and RCA are possible in the second construction of [7] scheme even though the pixel expansion is high. Chen et al. [12] in 2011 also proposed a BA-based (2, n) scheme which is immune to RCA attack but still vulnerable to DWtB attack. Both Chen et al. [12] and Liu et al. [9] showed that scheme proposed by Hu and Tzeg [6] is not a CIVCS. Chen et al. [13] in 2012 suggested an improvement to [6] CIVCS. Chen et al. in 2012 [13] (resp. 2013 [14]) proposed SA-based (2, n) CIVCS, with (resp. without) extra verification transparency for each participant.

Here, this paper proposes a novel (2, n) CIVCS. The preliminaries for VCS are given in Sect. 2. In Sect. 3, the background for BA-based CIVCS and collusive cheating attacks on VCS is discussed. In Sect. 4, the novel construction of (2, n) CIVCS based on OR operation is explained.

2 Preliminaries

Let PA = {pa ₁, pa ₂, pa ₃,…., pa _n } be the participant set and 2^PA is the cardinality of power set of PA. Then, the share S _i , 1 ≤ i ≤ n of SI is distributed to each pa _i . Let us denote Γ _Qual as a collection of qualified sets and Γ _Forb as a collection of forbidden sets, where Γ _Qual $\cup$ Γ _Forb = 2^PA and Γ _Qual $\cap$ Γ _Forb = $\varphi$, then Γ = (PA, Γ _Qual, Γ _Forb) is called the access structure of VCS. Any set C $\in$ Γ _Qual can recover SI whereas any set C $\in$ Γ _Forb is not able to recover SI. Let Γ ₀ = {C $\in$ Γ _Qual:$C^{\prime}$ $\notin$ Γ _Qual for all $C^{\prime}$ $\subseteq$ C, $C^{\prime}$ ≠ C} be the collection of minimal qualified subset of PA. Let B ₁ and B ₀ are two collections which consist of $n \times m$ Boolean matrices used for constructing n shares of SI. The row of each matrix in both B ₁ and B ₀ corresponds to m sub pixels. For sharing a 1 (resp. 0) pixel in SI, randomly choose a matrix T from B ₁ (resp. B ₀) and assign row i of T to the corresponding positions of share S _i , 1 ≤ i ≤ n. The matrices in the two collections B ₁ (resp. B ₀) consist of all column permutations of T ₁ (resp. T ₀). The vector obtained by bitwise OR operation to the rows of T corresponding to the elements in PA is represented as T _PA . Let w(T _PA ) denotes the Hamming weight of the vector T _PA . The stacking corresponds to the bitwise operation between sub pixels in the shares (S _i ).

Definition 1

[2]: Let Γ = (PA, Γ _Qual, Γ _Forb) be an access structure. Two collections B ₁ and B ₀ constitute a (Γ, m)—VCS if there exists a value $\alpha (m) > 0$ and a set $\left\{ {(PA,t_{PA} )} \right\}$ _{PA ∈ ΓQual} which satisfies the following conditions.

• 1. Any set {pai ₁, pai ₂, pai ₃,…, pai _q } ∈ Γ _Qual can recover SI by stacking their shares. Formally, for any T ∈ B ₀, w (T _PA ) ≤ t _PA – α.m, whereas for any T ∈ B ₁, w (T _PA ) ≥ t _PA .

• 2. Any set {pai ₁, pai ₂, pai ₃,…, pai _q } ∈ Γ _Forb has no information on SI. Formally, the collections B _t , t ∈ {0, 1} of $q \times m$ matrices obtained by restricting each $n \times m$ matrix in T ∈ B _t to rows i ₁, i ₂, i ₃,…, i _q are indistinguishable in the sense that they contain the same matrices with the same frequencies.

The property 1 (resp. 2) ensures contrast (resp. security) of the scheme. The following is an example of (2, 3)—VCS with contrast α = $\frac{1}{3}$ and m = 3, for PA = {pa ₁, pa ₂, pa ₃}, where Γ _Qual  = {{pa ₁, pa ₂}, {pa ₃, pa ₂}, {pa ₁, pa ₃}, {pa ₁, pa ₂, pa ₃}} and Γ _Forb  = {{pa ₁}, {pa ₂}, {pa ₃}}.

Example 1

Let the basis matrices be T ₀ = $\left[ {\begin{array}{*{20}c} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{array} } \right]$ and T ₁ = $\left[ {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} } \right]$. Then, when stacking the value of w(T _PA ) = 2 is obtained for black pixel, and the value of w(T _PA ) = 1 is obtained for white pixel.

3 A Review of Collusive Cheating Attacks and CIVCS’s

3.1 DWtB and DBtW Attack—Horng et al. (2006) [4]

Let S ₁, S ₂, and S ₃ are three distinct shares of SI, and they are distributed to each participant pa ₁, pa ₂, and pa ₃, respectively. Let pa ₁ and pa ₂ are the adversaries, and pa ₃ is the honest participant. During attack, pa ₁ and pa ₂ will create fake block F by predicting the share structure of pa ₃. Let us explain a DWtB and DBtW attack using the basis matrices given in the example of Sect. 2. For 0 pixel, the block in the shares of pa ₁, pa ₂, and pa ₃ is [1 0 0]. If the cheaters pa ₁ and pa ₂ collusively identify the structure of pa ₃, they can create F using the blocks [0 1 0] and [0 0 1], respectively. The stacking of F and corresponding block in S ₃ will result in a 1 pixel. This is DWtB attack. For the secret pixel 1, the blocks in the shares of pa ₁, pa ₂, and pa ₃ are [1 0 0], [0 1 0], [0 0 1], respectively. If pa ₁ and pa ₂ collusively identify the structure of pa ₃ to generate F as [0 0 1], the stacking of F with corresponding block in S ₃ will results in a white pixel. This is DBtW attack.

3.2 CIVCS—Horng et al. (HCT) (2006) [4]

In this method instead of creating n shares and distribute it to each participants, (n + l) shares are generated from SI, and randomly picked n shares are distributed to each participant. This scheme will protect pixel 1 but not pixel 0. The probability that adversaries can correctly guess the 1 pixel’s in the honest participants share is $\frac{1}{l + 1}$. This scheme can protect only DBtW attack, but not DWtB attack. Section 2.3 of paper [4] explains how complementary images can be used to make this scheme immune against DWtB attack.

3.3 Simple CIVCS—de Prisco et al. (DD1) (2010) [7]

Let T ₁ (resp. T ₀) be the basis matrices shown in example of Sect. 2, then the basis matrices for CIVCS are given by A ₁ (resp. A ₀) for 1 (resp. 0) pixel are

$$ A_{0} = \left[ {\begin{array}{*{20}c} {\left| {\begin{array}{*{20}c} 0 \\ . \\ 0 \\ \end{array} } \right|} & {T_{0} } \\ \end{array} } \right]\;{\text{and}}\,A_{1} = \left[ {\begin{array}{*{20}c} {\left| {\begin{array}{*{20}c} 0 \\ . \\ 0 \\ \end{array} } \right|} & {T_{1} } \\ \end{array} } \right] $$

respectively. This scheme also can protect only DBtW attack, but not DWtB attack.

3.4 Better CIVCS—de Prisco et al. (DD2), 2010

Let A ₁ (resp. A ₀) be the basis matrices of DD1 scheme given above. Let D be a matrix which contain all possible 2ⁿ column vectors, then the basis matrices B ₁ (resp. B ₀) for 1 (resp. 0) pixel for better scheme are $\left[ {\begin{array}{*{20}c} D & {A_{0} } \\ \end{array} } \right]$ (resp.$\left[ {\begin{array}{*{20}c} D & {A_{1} } \\ \end{array} } \right]$). But it is shown in Sect. 4 of paper [11] that, this scheme is also vulnerable to collusive cheating.

4 Proposed (2, N)—CIVCS’s

4.1 MS CIVCS—Modified (Sreekumar and Babusundar 2008) [15]

A uniform code of length t consists of precisely $\left\lceil {\frac{t}{2}} \right\rceil$ 1’s and $\left\lfloor {\frac{t}{2}} \right\rfloor$ 0’s. Let $N_{t}$ denote the number of uniform codes of length t, where $N_{t} = \left( {\begin{array}{*{20}c} t \\ {\left\lfloor {\frac{t}{2}} \right\rfloor } \\ \end{array} } \right)$. In the construction of (2, n)—VCS based on OR operation by Sreekumar and Babusundar [15], the n ≤ $N_{t}$ shares are generated using uniform codes. The scheme [15] is vulnerable to DWtB in the case of more than two collusive adversaries for any value of n and vulnerable to DBtW attack in the case of n – 1 collusive adversaries only when n == $N_{t}$. But, in the case of 2 to n – 2 collusive adversaries, the scheme [15] is immune to DBtW attack when n == $N_{t}$. The following shows an example of vulnerability of the scheme [15].

Example 2

For constructing a (2, 6)-VCS using uniform codes [15], let us select the value of t = 4, which satisfies the condition n ≤ $N_{t}$. The ($N_{t}$ = 6) distinct uniform codes for the value of t = 4 are given in UC = {1100, 0110, 0011, 1001, 1010, 0101}. Let M = $\left[ {\begin{array}{*{20}c} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} } \right]$ be a matrix constructed using UC. For sharing a pixel 1, a randomly selected row from M is distributed to all the six participants. For sharing a pixel 0, each row of M is distributed to six corresponding participants. Here, DWtB attack is possible because when any $n - 1$ cheaters (here 5) collude, they can predict the block of the victim as [1 0 0 1], if the matrix used for sharing a pixel 0 is

$\left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ \end{array} } \right]$.The five cheaters can conduct a DWtB attack by generating the fake matrix $\left[ {\begin{array}{*{20}c} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} } \right]$. Here, DBtW attack is possible because when any $n - 1$ cheaters (here 5) collude, they can predict the block of the victim as [1 0 0 1], if the matrix used for sharing a pixel 1 is $\left[ {\begin{array}{*{20}c} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} } \right]$.The five cheaters can conduct a DBtW attack by generating the fake matrix $\left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ \end{array} } \right]$. Here, in this example, the value of n = 6 and the value of $N_{t}$ = 6. So when n == $N_{t}$, DBtW attack is possible by $n - 1$ (here 5) cheaters.

Proposed construction: The following are the steps done by the dealer.

• Step1: If the value of n == $N_{t}$, then M be the basis matrix of order $N_{t + 1} \times (t + 1)$ and each element in the matrices is different vectors of length (t + 1).

  Else M be the basis matrix of order $N_{t} \times t$, and each row in the matrices is different vectors of length t.

• Step2: Construct a set G which is a collection of different row permuted matrix of M.

• Step3: This step is applicable to all pixels in SI. The dealer randomly selects a matrix from G and constructs another matrix K of order $n \times (t + 1)$ or $n \times t$ based on the value of n. For sharing 1, the dealer uses any row permuted matrix K, and for sharing 0 the dealer selects any one row of matrix K and distribute to all n participants.

Theorem 1:

The MS—(2, n) CIVCS is vulnerable to DWtB attack but immune to DBtW attack.

Proof Let TS be the share of honest participant, and let B be the block corresponding to 1 of SI, and W is a block corresponding to 0 of SI. The dealer selects a matrix M of order $N_{m} \times m$, where $m = \left\{ {\begin{array}{*{20}c} {t + 1} & {\begin{array}{*{20}c} {if} & {n = = N_{t} } \\ \end{array} } \\ t & {Otherwise} \\ \end{array} } \right\}$, n ≥ 2 and t ≥ 2. Here, when any d collusive participants (cheaters) combine, the probability for correctly guessing B in TS is $\frac{1}{{N_{m} - d}}$, and the probability for correctly guessing W in TS is 1.

This scheme is used as a BA-based CIVCS which can resist both DWtB and DBtW attack, if the shares of complementary secret image are also distributed to participants analogous to (2, n + l)—CIVCS constructed by Horng et al. [4]. Assume that SI = [1 0] be the secret image to be shared using (2, 3)—CIVCS. For constructing a CIVCS, we need to generate a complementary matrix of SI, say $SI^{\prime}$ = [0 1]. Both SI and $SI^{\prime}$ are shared among the three participants.

Example 3

For constructing a (2, 6)—CIVCS, let us select a matrix $K = \left[ {\begin{array}{*{20}c} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ \end{array} } \right]$

which satisfies the following criteria n ≤ $N_{t}$. Here, if any five collusive adversaries combine, they cannot predict the block corresponding to pixel 1. So the scheme is immune to DBtW attack. If complementary secret is also shared with the original secret, the scheme resists DWtB attack also.

4.2 Comparison of CIVCS’s

Below Tables 1 and 2 show the comparison of proposed MS CIVCS with related works which are reported as secure in the paper [14] (CTH).

Table 1 Comparison of secure (2, n)—CIVCS’s

Table 2 Pixel expansion of secure (2, n)—CIVCS’s

5 Conclusion

The order of pixel expansion for the existing secure blind authentication based (2, n)—CIVCS’s is O(n). Here, we proposed a (2, n)—CIVCS which can prevent n – 1 cheaters by modifying Sreekumar and Babusundar [15] uniform code scheme in which the order of pixel expansion is O(log n).