Recently, Hou and others introduced a (2,
n
) block-based progressive visual cryptographic scheme (BPVCS) in which image blocks can be gradually recovered step by step. In Hou and others’ (2,
n
)-BPVCS, a secret image is subdivided into
n
non-overlapping image blocks. When
t
(2 ≤
t
≤
n
) participants stack their shadow images, all the image blocks associated with these
t
participants will be recovered. However, Hou and others’ scheme is only a simple 2-out-of-
n
case. In this paper, we discuss a general (
k
,
n
)-BPVCS for any
k
and
n
. Our main contribution is to give two constructions (Construction 1 and Construction 2) of this general (
k
,
n
)-BPVCS. Also, we theoretically prove that both constructions satisfy a threshold property and progressive recovery of the proposed (
k
,
n
)-BPVCS. For
k
= 2, Construction 1 is reduced to Hou and others’ (2,
n
)-BPVCS.]
A (k, n) visual cryptographic scheme (VCS), where k ≤ n, encodes a secret image into n shadow images (referred to as shadows) distributed to n participants. The secret can be visually reconstructed when k or more shadows are stacked. No information will be revealed with any (k − 1) or fewer shadows. The reconstruction can be done by the human visual system directly without any cryptographic knowledge or the need for a computer. Applications of VCS can be found in [1]. The first VCS was proposed by [2], which used whiteness to distinguish black color from white color. In the VCS of [2], a secret pixel is subdivided into m (the pixel expansion) subpixels in each of n shadows. Most studies tried to reduce the pixel expansion. Some of them, [3]–[6], even have no pixel expansion (m = 1) — known as probabilistic VCS (PVCS). Hence, a conventional VCS with fixed m (m > 1) is referred to as a deterministic VCS (DVCS). Recently, Hou and others [7] proposed a (2, n) block-based progressive VCS (BPVCS) with a progressive recovery scheme, whereby image blocks can be gradually recovered step by step. In Hou and others’ (2, n)-BPVCS, a secret image, P, is subdivided into n non-overlapping image blocks; namely, P_{i} (1 ≤ i ≤ n). The progressive recovery operates under the assumption that if any t (2 ≤ t ≤ n) shadows are stacked and participant i (1 ≤ i ≤ n) is involved, then the image block P_{i} can be restored. All the image blocks can be recovered when all n participants are involved in the reconstruction. In other words, each participant has their own decryption key for one particular image block. However, Hou and others’ (2, n)-BPVCS is only a simple 2-out-of-n case. In this paper, we discuss a general (k, n)-BPVCS where a qualified set of participants consists of any k (≥ 2) participants. Two constructions — “Construction 1” and “Construction 2” — using _{n}C_{k−1} and _{n}C_{k} image blocks, respectively, are proposed. For k = 2, Construction 1 is reduced to Hou and others’ (2, n)-BPVCS.The rest of this paper is organized as follows. In Section II, we describe the notions of DVCS, PVCS, extended VCS (EVCS) with meaningful shadow, and probabilistic EVCS (PEVCS), which are the basic elements in our new (k, n)-BPVCS. Also, Hou and others’ (2, n)-BPVCS is introduced. Two constructions of the general (k, n)-BPVCS are proposed in Section III. Furthermore, we theoretically prove that they hold progressive recovery and security. Our experiments are explained along with some discussions in Section IV. Finally, conclusions are given in Section V.
II. Related Works
- 1. DVCS and PVCS
In DVCS, a black-and-white secret pixel is subdivided into m black-and-white subpixels in each of n shadows. We use “m − h”B“h”W (that is, (m − h) black subpixels and h white subpixels) and “m − l”B“l”W, where 0 ≤ l < h ≤ m, to represent white and black secret pixels, respectively. The collection of the corresponding m subpixels in n shadows can be represented by an n × m Boolean matrix S = [S_{i,j}], where the element S_{i,j} represents the jth subpixel in the ith shadow. If S_{i,j} is a black subpixel, then this is represented by “1”; similarly, if it is a white subpixel, then it is represented by “0.” Stacking t shadows together, the grey-level of each secret pixel (m subpixels) in the stacked image is proportional to Hamming weight H(v). The vector v is OR-ed m-tuple v = OR(i_{1}, i_{2}, ... , i_{t}), where i_{1}, i_{2}, ... , i_{t} are t rows of S associated with the shadows we stack. The formal definition for a binary DVCS is given as follows [8].Definition 1. A (k, n)-DVCS consists of two n × m Boolean matrices, B_{1} and B_{0}. To share a black (respectively white) secret pixel, the dealer arbitrarily chooses one row of a matrix in the set that includes all matrices obtained by permuting the columns in B_{1} (respectively B_{0}) to a relative shadow. The chosen matrix defines the color of this m subpixel block in each one of n shadows. The (k, n)-DVCS is valid if the following three conditions are met:
1) InB1, the OR-ed vectorv1of anykout ofnrows satisfies
H(v1) ≥ (m−l).
2) InB0, the OR-ed vectorv0of anykout ofnrows satisfies
H(v0) ≤ (m−h).
3) For any subset {i1,i2, ... ,it} ⊂ {1, 2, ... ,n} witht
The first two conditions are called contrast conditions, and the third condition is the security condition. Let OR(B_{1}|t) and OR(B_{0}|t) denote the “OR”-ed of any t rows in B_{1} and B_{0}, respectively. The authors in [9]–[10] rewrite the conditions in Definition 1 as the contrast condition (D-1) and the security condition (D-2) as follows; in addition, they theoretically prove the equivalence of the condition of (3) in Definition 1 and condition (D-2): (D-1) H(OR(B_{1}|t)) ≥ (m − l) and H(OR(B_{0}|t)) ≤ (m − h) for t = k. (D-2) H(OR(B_{1}|t)) = H(OR(B_{0}|t)) for t ≤ (k − 1).In [2], the contrast of a DVCS is defined as the difference in weight between a black pixel and a white pixel in the reconstructed image; that is,$$\alpha =\frac{H({V}_{1})-H({V}_{0})}{m}=\frac{(m-l)-(m-h)}{m}=\frac{h-l}{m}.$$To address the pixel expansion problem, a PVCS adopts the frequency of white pixels in an area to distinguish between the black area and white area in a reconstructed image. In a white area of a reconstructed image, this frequency is higher than that in the black area. In [4], Yang proposed a PVCS with m = 1 (that is, no pixel expansion). A (k, n)-PVCS can be constructed by a black set and a white set (C_{1} and C_{0}) consisting of n × 1 column matrices, respectively. When sharing a black (respectively white) pixel, the dealer first randomly chooses one n × 1 column matrix in C_{1} (respectively C_{0}), and then randomly selects one row in this column matrix to a relative shadow. The chosen set defines the color level of the pixel in shadows. The author in [4] showed that we can use all the columns of the basis matrices B_{0} and B_{1} in a DVCS as the n × 1 column matrices of sets C_{0} and C_{1} in a PVCS. Let OR(C_{1} | t) and OR(C_{0} | t) denote OR-ed t rows in all column matrices in C_{1} and C_{0}, respectively, and P(·) be the appearance probability of the “0” (whiteness) in a set. The contrast condition and the security condition of (k, n)-PVCS are shown as follows: (P-1) P(OR(C_{1}|t)) ≤ p_{1} and P(OR(C_{0}|t)) ≥ p_{0} for t = k, where p_{1} < p_{0}. (P-2) P(OR(C_{1}|t)) = P(OR(C_{0}|t)) for t ≤ (k − 1).Conditions (P-1) and (P-2) are similar to (D-1) and (D-2), but they are in a probabilistic manner. In (P-1), the different probability of “whiteness” is used to distinguish between black color and white color. Condition (P-2) ensures a (k, n)-PVCS scheme that is of the unconditional security type. A secret image can be successfully recognized through the different probabilities of “whiteness” in the reconstructed image. Since the frequency of white subpixels in the white and black areas is p_{0} and p_{1}, respectively, the average contrast of a PVCS is defined to be α = p_{0} − p_{1}[4]. Since all matrices in C_{0} and C_{1} are n × 1 matrices, it can be said that a PVCS has no pixel expansion. However, shadows of a DVCS are m times those of a PVCS. We give one example to illustrate the shadows and stacked results of both a DVCS and a PVCS.Example 1. Construct a (2, 2)-DVCS and (2, 2)-PVCS by
B 0 =[ 10 10 ]
and
B 1 =[ 10 01 ].
It is observed that H(OR(B_{1}|2)) = 2, H(OR(B_{0}|2)) = 1, and H(OR(B_{1}|1)) = H(OR(B_{0}|1)) = 1; thus, they satisfy (D-1) and (D-2). Suppose that xByW represents
( 1 ⋯ 1 ︷ x , 0 ⋯ 0 ︷ y )
and its permutations. In a reconstructed image, the black color is 2B0W and the white color is 1B1W; the contrast is α = (h − l)/m = 1/2. Because all 2-subpixel blocks in two shadows are all 1B1W, they are noise-like. On the other hand, we can use all two columns of B_{0} and B_{1} as the 2 × 1 column matrices in sets
C 0 = { [ 1 1 ],[ 0 0 ] }
and
C 1 = { [ 1 0 ],[ 0 1 ] },
respectively. Since OR(C_{0}|2) = {1,0} and OR(C_{1}|2) = {1,1}, we have P(OR(C_{0}|t)) ≥ p_{0} = 1/2 and P(OR(C_{1}|t)) ≤ p_{1} = 0. This satisfies condition (P-1); and the average contrast α = p_{0} − p_{1} = 1/2. In addition, P(OR(C_{1}|1)) = P(OR(C_{0}|1)) = 1/2 satisfies condition (P-2). Shadows of (2, 2)-PVCS are not expanded. However, the visual quality of a recovered image will be degraded.
- 2. EVCS and PEVCS
Noise-like shadows in DVCS (or PVCS) are unusual and susceptible to censors. In addition, the identification and management of noise-like shadows is difficult. Therefore, an EVCS (with its extended ability — “the meaningful shadow”) is accordingly proposed. This extended capability was first introduced by Naor and Shamir [2]. They used 3B1W (2B2W) to represent black (white) pixels in shadows, but used 4B0W (3B1W) in reconstructed images to represent black and white colors. With regards to the formal definition of EVCS, one should refer to [11].Let S_{1} and S_{2} be two shadows of a (2, 2)-EVCS, and c_{i} is the cover pixel on S_{i}, where i = 1, 2. Suppose that
B 1 c 1 c 2 ( B 0 c 1 c 2 )
is a matrix for a black (white) secret pixel in a (2, 2)-EVCS. Then, the associated cover pixel is black (c_{i} = 1) or white (c_{i} = 0), where c_{1} and c_{2} denote the colors in S_{1} and S_{2}, respectively. The following example shows Naor and Shamir’s (2, 2)-EVCS [2].Example 2. Construct a (2, 2)-EVCS with m = 4. All eight basis matrices,
B 0 00 , B 0 01 , B 0 10 , B 0 11 , B 1 00 , B 1 01 , B 1 10 , and B 1 11 ,
are given as follows:$$\begin{array}{l}{B}_{0}^{00}=\left[\begin{array}{cccc}1& 0& 0& 1\\ 1& 0& 1& 0\end{array}\right]\text{,}{B}_{0}^{01}=\left[\begin{array}{cccc}1& 0& 0& 1\\ 1& 0& 1& 1\end{array}\right],{B}_{0}^{10}=\left[\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 1& 0\end{array}\right]\text{,}{B}_{0}^{11}=\left[\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 1& 1\end{array}\right],\\ \\ {B}_{1}^{00}=\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 1& 0\end{array}\right]\text{,}{B}_{1}^{01}=\left[\begin{array}{cccc}1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right],{B}_{1}^{10}=\left[\begin{array}{cccc}1& 0& 1& 1\\ 1& 1& 0& 0\end{array}\right]\text{,}{B}_{1}^{11}=\left[\begin{array}{cccc}1& 0& 1& 1\\ 1& 1& 1& 0\end{array}\right].\end{array}$$The contrast of the recovered image is given by α = (h − l)/m [= (1 − 0)/4 = 1/4]. Since the Hamming weight of the ith row (i =1, 2), is 2 and 3 for c_{i} = 0 and c_{i} = 1, respectively, the contrast of shadow α_{s} is also (2−1)/4 = 1/4.If two shadows in this (2, 2)-EVCS have the same cover image, then the colors of c_{1} and c_{2} are the same (that is, c_{1} = c_{2}). Thus, we only require
B 0 00 , B 1 00 , B 0 11 , and B 1 11
from (1) for the (2, 2)-EVCS containing two shadows having the same cover image.Generally, EVCS has a larger pixel expansion than VCS. For example, let us assume that we have m = 2 for (2, 2)-DVCS, while m = 4 for (2, 2)-EVCS. As in the case of a DVCS, we can also apply a probabilistic approach (that is, choosing every column randomly each time) to EVCS to implement a PEVCS.Example 3. Continuation of Example 2.We use all four columns of the basis matrices featured in (1) to construct sets of 2 × 1 column matrices —
C 0 00 , C 0 01 , C 0 10 , C 0 11 , C 1 00 , C 1 01 , C 1 10 and C 1 11 .
Therefore, the sets of a (2, 2)-PEVCS with two different cover images on shadows are shown as follows:$$\begin{array}{l}{C}_{0}^{00}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 0\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\}\text{,}{C}_{0}^{01}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 0\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\right\},{C}_{0}^{10}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 0\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\}\text{,}{C}_{0}^{11}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 0\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\right\},\\ \\ {C}_{1}^{00}=\left\{\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\}\text{,}{C}_{1}^{01}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\},{C}_{1}^{10}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\}\text{,}{C}_{1}^{11}=\left\{\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right\}.\end{array}$$Since OR(
C 0 c 1 c 2
| 2) = {1,0,1,1} and OR(
C 1 c 1 c 2
| 2) = {1,1,1,1}, we have P(OR(
C 0 c 1 c 2
| 2)) ≥ p_{0} = 1/4 and P(OR(
C 1 c 1 c 2
| 2)) ≤ p_{1} (= 0). So, α = p_{0} − p_{1} = 1/4. For a (2, 2)-PEVCS with shadows that have an identical cover image, there are only four sets —
C 0 00 , C 0 11 , C 1 00 , and C 1 11 .
- 3. Hou and Others’ (2,n)-BPVCS
In [7], Hou and others propose a (2, n)-BPVCS with non-expanded shadow size. In Hou and others’ (2, n)-BPVCS, a secret image P is subdivided into n image blocks {P_{1}, P_{2}, ... , P_{n}} that satisfy the following two properties: (a) any two image blocks do not have the same overlapping area; that is, P_{i} ∩ P_{j} = ϕ for i ≠ j (disjoint property) and (b) their union is the original secret image P; that is, O = P_{1} ∪ P_{2} ∪ ⋯ ∪ P_{n} (union property). The disjoint property provides the progressive recovery, and the union property ensures that all participants can work together to reconstruct the whole secret image. If participant i, 1 ≤ i ≤ n, is involved in reconstruction, then the image block P_{i} can be recovered. When any t (2 ≤ t ≤ n) shadows are stacked, all the image blocks corresponding to these t participants will be recovered, but other areas are still noise-like. Therefore, each participant has his own decryption key for one particular image block. Considering the example (2, 3)-BPVCS, the secret image is first subdivided into three image blocks — P_{1}, P_{2}, and P_{3}. When two participants, p_{1} and p_{2}, cooperate together, they can recover image blocks P_{1} and P_{2}, and the other area is noise-like. However, when stacking shadows, (S_{1} + S_{3}) or (S_{2} + S_{3}), the image blocks P_{1} and P_{3}, and P_{2} and P_{3} are recovered, respectively. All three stacked shadows can recover all image blocks, P_{1}, P_{2}, and P_{3}. There are two types of Hou and others’ (2, n)-BPVCS — a (2, n)-BPVCS with noise-like shadows and a (2, n)-BPVCS with meaningful shadows. In fact, Hou and others’ (2, n)-BPVCS with noise-like shadows and (2, n)-BPVCS with meaningful shadows are constructed by (2, 2)-PVCS (see Example 1) and (2, 2)-PEVCS with the same cover image (see Example 3), respectively. In Hou and others’ (2, n)-BPVCS with noise-like shadows, the dealer applies (2, 2)-PVCS on P_{i}, 1 ≤ i ≤ n, to get noise-like sub-shadows S_{i,1} and S_{i,2}. On the other hand, when constructing Hou and others’ (2, n)-BPVCS with meaningful shadows, we should additionally consider the cover image O. The cover image is partitioned into n subcover images to give O_{i}, 1 ≤ i ≤ n, according to the position of image block P_{i}. Then, for each P_{i} and O_{i}, 1 ≤ i ≤ n, we apply (2, 2)-PEVCS with the same cover image to obtain sub-shadows S_{i,1} and S_{i,2}. The method of composition of shadows for these two (2, n)-BPVCSs is the same. The dealer delivers S_{i,1} to participant i and S_{i,2} to the other (n − 1) participants. Afterwards, every participant offers up all of their received sub-shadows according to the position of P_{i} to construct n shadows as follows:$${S}_{j}={S}_{j,1}\cup \left({\displaystyle \underset{i\in \{1,\mathrm{...},n\},i\ne j}{\cup}{S}_{i,2}}\right)\text{(}1\le j\le n).$$Since both a (2, 2)-PVCS and a (2, 2)-PEVCS have a non-expanded shadow size, the shadow size of Hou and others’ (2, n)-BPVCS is also not expanded. As an example, Hou and others’ (2, 4)-BPVCS is constructed below. By (3), we have four shadows as given below in (4). Figures 1(a) and 1(b) are partitions of a secret image and partitions of a cover image, respectively. Figure 1(c) illustrates four shadows.
Composition of shadows for Hou and others’ (2, 4)-BPVCS: (a) four image blocks, (b) four subcover images, and (c) four shadows.
$$\{\begin{array}{l}{S}_{1}={S}_{1,1}\cup {S}_{2,2}\cup {S}_{3,2}\cup {S}_{4,2},\\ {S}_{2}={S}_{1,2}\cup {S}_{2,1}\cup {S}_{3,2}\cup {S}_{4,2},\\ {S}_{3}={S}_{1,2}\cup {S}_{2,2}\cup {S}_{3,1}\cup {S}_{4,2},\\ {S}_{4}={S}_{1,2}\cup {S}_{2,2}\cup {S}_{3,2}\cup {S}_{4,1}.\end{array}$$Consider the stacked result of (S_{1} + S_{2}). We have two image blocks, P_{1} and P_{2}, and two noise-like blocks, S_{3,2} and S_{4,2}, as shown in (5). By stacking another shadow S_{3} on (S_{1} + S_{2}), we obtain three image blocks, P_{1}, P_{2}, and P_{3}, and one noise-like block, S_{4,2}, in (6). When stacking all four shadows, we can recover all image blocks (see (7)).$$\{\begin{array}{cc}{S}_{1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2}\text{\hspace{0.05em}}\hfill & =({S}_{1,1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{1,2})\cup ({S}_{2,1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2,2})\cup ({S}_{3,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3,2})\cup ({S}_{4,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4,2})\hfill \\ \hfill & =\text{\hspace{0.17em}}\stackrel{\text{2imageblocks}}{\overbrace{{P}_{1}\cup {P}_{2}}}\cup \stackrel{\text{2noise-likeblocks}}{\overbrace{{S}_{3,2}\cup {S}_{4,2}}}.\text{\hspace{0.17em}}\hfill \end{array}$$$$\{\begin{array}{cc}{S}_{1}+{S}_{2}+{S}_{3}\hfill & =({S}_{1,1}+{S}_{1,2}+{S}_{1,2})\cup ({S}_{2,2}+{S}_{2,1}+{S}_{2,2})\hfill \\ \hfill & \text{}\cup \text{\hspace{0.17em}}({S}_{3,2}+{S}_{3,2}+{S}_{3,1})\cup ({S}_{4,2}+{S}_{4,2}+{S}_{4,2})\hfill \\ \hfill & =\stackrel{\text{3imageblocks}}{\overbrace{{P}_{1}\cup {P}_{2}\cup {P}_{3}}}\cup \stackrel{\text{1noise-likeblock}}{\overbrace{{S}_{4,2}}}.\hfill \end{array}$$$$\{\begin{array}{cc}{S}_{1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4}\text{\hspace{0.05em}}& =({S}_{1,1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{1,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{1,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{1,2})\cup ({S}_{2,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2,1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2,2}\text{\hspace{0.05em}}+{S}_{2,2})\hfill \\ \hfill & \text{}\cup \text{\hspace{0.17em}}({S}_{3,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3,1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3,2})\cup ({S}_{4,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4,2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4,1})\hfill \\ \hfill & =\stackrel{\text{4imageblocks}}{\overbrace{{P}_{1}\cup {P}_{2}\cup {P}_{3}\cup {P}_{4}}}.\text{\hspace{0.17em}}\hfill \end{array}$$Example 4. Construct Hou and others’ (2, 4)-BPVCS with noise-like shadows.Suppose that a secret image is divided into four image blocks, as in Fig. 1(a). Then, the contents of P_{1}, P_{2}, P_{3}, and P_{4} are the printed-texts
A
,
B
,
C
, and
D
, respectively; that is, P is
A B C D
. By applying a (2, 2)-PVCS with
C 1 = { [ 1 0 ],[ 0 1 ] }
and
C 0 = { [ 1 1 ],[ 0 0 ] }
to P_{1}, P_{2}, P_{3}, and P_{4}, we obtain sub-shadows on which Hou and others’ (2, 4)-BPVCS can be implemented. Four noise-like shadows and the progressive recovery results of stacking two, three, and four shadows are given in Fig. 2. For example, when stacking S_{1} and S_{3}, we have
S 1 + S 3 = A C
(see Fig. 2(b-2)). By adding another shadow, S_{4}, we have
S 1 + S 3 + S 4 = A C D
(see Fig. 2(c-3)). Obviously, we can implement Hou and others’ (2, 4)-BPVCS with the same cover image by using a (2, 2)-PEVCS.
Progressive recovery of Hou and others’ (2, 4)-BPVCS with noise-like shadows: (a) four shadows, (b) stacking any two shadows, (c) stacking any three shadows, and (d) stacking all four shadows.
III. Proposed (k,n)-BPVCS
A secret image P is first divided into N image blocks {P_{1}, P_{2}, ... , P_{N}} satisfying both the aforementioned disjoint property and union property. For each P_{j}, 1 ≤ j ≤ N, we use (k, k)-PVCS to generate k sub-shadows, S_{i,1}, S_{i,2}, ... , S_{i,k}. In this paper, we will show how to construct n shadows from these (N × k) sub-shadows. Moreover, both constructions use different image blocks (Construction 1: N = _{n}C_{k−1} and Construction 2: N = _{n}C_{k}) and have different progressive recovery ratios. One can choose a construction method according to his application need. Two construction methods are introduced in sequence. Some notations are defined in Table 1.
Function dividing an image into N = _{n}C_{k−1} image blocks in Construction 1 and N = _{n}C_{k} image blocks in Construction 2 satisfies disjoint property and union property.
P_{j}
Divide a secret image into N image blocks P_{j}, 1 ≤ j ≤ N, where D(P) = {P_{1}, P_{2}, ... , P_{N}}.
O_{j}
Divide a cover image into N subcover images O_{j}, 1 ≤ j ≤ N, where D(O) = {O_{1}, O_{2}, ... , O_{N}}.
PVCS_{k,k}(·)
Encoding function of (k, k)-PVCS.
PEVCS_{k,k}(·,·)
Encoding function of (k, k)-PEVCS.
S_{j,1, ... , Sj,k}
k sub-shadows of an image block P_{j} by using PVCS_{k,k}(·) or PEVCS_{k,k}(·,·).
B_{n,k−1}
n × _{n}C_{k−1} binary matrix B_{n,k−1}= [b_{ij}] used in Construction 1, where b_{ij}∈[0, 1], 1 ≤ i ≤ n and 1 ≤ j ≤ _{n}C_{k−1}, and every column vector has Hamming weight (k − 1).
${B}_{n,k}^{\prime}$
n × _{n}C_{k} binary matrix ${B}_{n,k}^{\prime}=\left[{b}_{ij}\right]$ used in Construction 2, where b_{ij}∈[0, 1], 1 ≤ i ≤ n and 1 ≤ j ≤ _{n}C_{k}, and every column vector has Hamming weight k.
S_{i}
n shadows, 1 ≤ i ≤ n, in the proposed (k, n)-BPVCS
The design concept of Construction 1 is described as follows. We use a matrix having _{n}C_{k−1} columns with (k − 1) 1s in every column. Meantime, we generate k shadows from (k, k)-PVCS. From these k shadows, for every single column, we choose one shadow for all 0s and (k − 1) shadows for (k − 1) 1s. Therefore, when stacking t shadows, some corresponding image blocks can be revealed. The formal construction is shown in Construction 1. Construction 1. Encoding of the proposed (k, n)-BPVCS. Input: a secret image P. Output:n shadows S_{i}, i∈[1, n]. (Step 1-1) Obtain image blocks P_{j}, j∈[1, N], by D(P), where N = _{n}C_{k−1}. (Step 1-2) Obtain subcover images O_{j}, j∈[1, N], where N = _{n}C_{k−1}. /* (Step 1-2) is only required for the proposed (k, n)-BPVCS with meaningful shadows */ (Step 2-1) For every image block P_{j}, create k sub-shadows (S_{j,1}, ... , S_{j.k}) by PVCS_{k,k}(P_{j}). (Step 2-2) For every image block P_{j} and sub cover image O_{j}, create k sub-shadows (S_{j,1}, ... , S_{j.k}) by PEVCS_{k,k}(P_{j},O_{j}). /* (Step 2-2) is only required for the proposed (k, n)-BPVCS with meaningful shadows */ (Step 3) Set S_{1} = S_{2} = ⋯ S_{n} = ϕ. (Step 4) Choose a matrix B_{n,k−1} = [b_{ij}]. (Step 5) forj = 1 to Ndo {Set x = 2; for i = 1 to n do{If b_{ij} = 1 then ${\widehat{S}}_{i,j}={S}_{j,x}$ and x = x + 1; else ${\widehat{S}}_{i,j}={S}_{j,1}$;} }; (Step 6) ${S}_{i}={\cup}_{j=1}^{N}{\widehat{S}}_{i,j},i\in [1,n]$. /* each participant puts up received ${\widehat{S}}_{i,j}$ according to the position of P_{j} to construct S_{i}*/
- 1. Construction 1: (k,n)-BPVCS UsingnCk−1Image Blocks
The encoding procedure of the proposed (k, n)-BPVCS with noise-like and meaningful shadows by _{n}C_{k−1} image is shown below. (Step 1-1) and (Step 2-1) (respectively, (Step 1-2) and (Step 2-2)) are used for noise-like (respectively, meaningful) shadows.Theorem 1. The scheme from Construction 1 is a (k, n)-BPVCS having both the progressive recovery and threshold property.Proof. We first prove the security condition (that is, the threshold property), in which t (t ≤ k − 1) shadows cannot recover any image block. Any t (t ≤ k − 1) rows in B_{n,k−1} do not have (k − 1) 1s and at least one 0 in a column; so, there are not enough k sub-shadows in a (k, k)-PVCS (or (k, k)-PEVCS) to reconstruct any image block. With regards to progressive recovery, every column vector has (k − 1) 1s and (n − k + 1) 0s. So, any t (t ≥ k) rows in B_{n,k−1} have _{t}C_{k−1}t-tuples with (k − 1) 1s and (t − k + 1) 0s, and have enough k sub-shadows for reconstructing _{t}C_{k−1} image blocks. For k = 2, the number of image blocks is N = _{n}C_{k−1} = _{n}C_{1} = n. Shadows obtained from Construction 1 are exactly the same as those in (3), and Construction 1 will be reduced to Hou and others’ (2, n)-BPVCS. The following example shows a (3, 4)-BPVCS where k > 2 by using Construction 1. ■Example 5. Generate four shadows of the proposed (3, 4)-BPVCS by Construction 1.A secret image P is first partitioned into 6 = _{4}C_{2} image blocks, P_{1}, P_{2}, ... , P_{6}. Each image block is divided into three sub-shadows by (3, 3)-PVCS (or (3, 3)-PEVCS). The matrices B_{n,k−1} = B_{4,2} and
Composition of shadows for proposed (3, 4)-BPVCS: (a) six image blocks, (b) six sub-cover images, and (c) four shadows.
$$\{\begin{array}{l}{S}_{1}+{S}_{2}+{S}_{3}+{S}_{4}=({S}_{1,2}\cup {S}_{2,2}\cup {S}_{3,2}\cup {S}_{4,1}\cup {S}_{5,1}\cup {S}_{6,1})\\ +({S}_{1,3}\text{\hspace{0.17em}}\cup {S}_{2,1}\text{\hspace{0.17em}}\cup {S}_{3,1}\cup {S}_{4,2}\cup {S}_{5,2}\cup {S}_{6,1})+({S}_{1,1}\text{\hspace{0.17em}}\cup {S}_{2,3}\text{\hspace{0.17em}}\cup {S}_{3,1}\cup {S}_{4,3}\text{\hspace{0.17em}}\cup {S}_{5,1}\text{\hspace{0.17em}}\cup {S}_{6,2})\\ +({S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,3}\cup {S}_{4,1}\cup {S}_{5,3}\cup {S}_{6,3})\\ =({S}_{1,2}\text{\hspace{0.05em}}+{S}_{1,3}\text{\hspace{0.17em}}+{S}_{1,1}\text{\hspace{0.17em}}+{S}_{1,1})\cup ({S}_{2,2}\text{\hspace{0.17em}}+{S}_{2,1}\text{\hspace{0.17em}}+{S}_{2,3}\text{\hspace{0.17em}}+{S}_{2,1})\cup ({S}_{3,2}\text{\hspace{0.17em}}+{S}_{3,1}\text{\hspace{0.17em}}+{S}_{3,1}\text{\hspace{0.17em}}+{S}_{3,3})\\ \cup \text{\hspace{0.17em}}({S}_{4,1}\text{\hspace{0.17em}}+{S}_{4,2}\text{\hspace{0.17em}}+{S}_{4,3}\text{\hspace{0.17em}}+{S}_{4,1})\cup ({S}_{5,1}\text{\hspace{0.17em}}+{S}_{5,2}\text{\hspace{0.17em}}+{S}_{5,1}\text{\hspace{0.17em}}+{S}_{5,3})\cup ({S}_{6,1}\text{\hspace{0.17em}}+{S}_{6,1}\text{\hspace{0.17em}}+{S}_{6,2}\text{\hspace{0.17em}}+{S}_{6,3})\\ =\stackrel{\text{6imageblocks}}{\overbrace{{P}_{1}\cup {P}_{2}\cup {P}_{3}\cup {P}_{4}\cup {P}_{5}\cup {P}_{6}}}.\text{\hspace{0.17em}}\end{array}$$Let us consider a reconstruction. It can be easily verified that any two shadows do not have enough sub-shadows for reconstructing an image block. For example, when stacking S_{1} and S_{2}, we have six noise-like image blocks (see (11)). As shown in (12), by stacking S_{1}, S_{3}, and S_{4}, we can recover three image blocks, P_{2}, P_{3}, and P_{6}, and three noise-like blocks. All four stacked shadows can recover all image blocks (see (13)).
- 2. Construction 2: (k,n)-BPVCS UsingnCkImage Blocks
The design concept of Construction 2 is described as follows. We use a matrix having _{n}C_{k} columns with k 1s in every column. Meantime, we generate k shadows from (k, k)-PVCS. For every single column, we assign these k shadows to k 1s, and generate one random shadow for “0.” Therefore, when stacking t shadows, some corresponding image blocks can be revealed. The formal construction is shown in Construction 2.The encoding procedure of Construction 2 is similar to Construction 1, except using N = _{n}C_{k} instead of N = _{n}C_{k−1}, and B′_{n,k} instead of B_{n,k−1}. Also, (Step 5) in Construction 1 is modified as (Step 5′) in Construction 2 (see Fig. 4).
Random sub-shadows S_{j,0} in Construction 2, 1 ≤ j ≤ N, are randomly generated in the (k, n)-BPVCS with noise-like shadows. For the (k, n)-BPVCS with meaningful shadows, meaningful sub-shadows S_{j,0} 1 ≤ j ≤ N, are generated according to P_{j} and O_{j}, where the subpixels for black and white pixels are the same as those in (k, k)-PEVCS. For the case k = 3 in the proposed (k, n)-BPVCS, we need (3, 3)-PVCS and (3, 3)-PEVCS. Suppose that we use Naor and Shamir’s (3, 3)-PVCS [2] and Liu and others’ (3, 3)-PEVCS [12] to implement our (3, 4)-BPVCS with noise-like and meaningful shadows, respectively. Since Naor and Shamir’s (3, 3)-PVCS uses shadows that contain an equal number of black and white pixels, S_{j,0} in the (3, n)-BPVCS with noise-like shadows is randomly generated. On the other hand, Liu and others’ (3, 3)-PEVCS adopts probabilities 5/9 and 4/9 of blackness to represent black and white secret pixels. Therefore, the black and white pixels of S_{j,0} for (3, n)-BPVCS with meaningful shadows are generated according to the above probabilities; so, we can visually view the cover image on shadow. However, the sub-shadow S_{j,0} is not related to other sub-shadows, S_{j,1}, S_{j,2}, ... , S_{j,k}; thus, it does not have any contribution for reconstruction.Theorem 2. The scheme from Construction 2 is a (k, n)-BPVCS having both the progressive recovery and threshold property.Proof. We put k sub-shadows of P_{j} at the element of “1” in the jth column. Since t (t ≤ k − 1) rows in B′_{n,k} do not have k 1s, there are not enough k sub-shadows in a (k, k)-PVCS (or (k, k)-PEVCS) to reconstruct any image block. For the progressive recovery, we only consider the sub-shadows in position “1” because the sub-shadow S_{j,0} in position “0” has no contribution for reconstruction. Every column vector has k 1s and (n − k) 0s. So, any t (t ≥ k) rows in B′_{n,k} have _{t}C_{k}t-tuples with k 1s, and have enough sub-shadows for reconstructing _{t}C_{k} image blocks. ■Example 6. Generate four shadows of the proposed (3, 4)-BPVCS by Construction 2.A secret image P is first partitioned into 4 = _{4}C_{3} image blocs, P_{1}, P_{2}, P_{3}, and P_{4}. Each image block is shared into three sub-shadows by (3, 3)-PVCS (or (3, 3)-PEVCS). Also, we generate four random and meaningful sub-shadows, S_{1,0}, S_{2,0}, S_{3,0}, and S_{4,0}, for the (3, 4)-BPVCS with noise-like and meaningful shadows, respectively. The matrices B′_{n,k} = B′_{4,3} and
$$\{\begin{array}{l}{S}_{1}={\widehat{S}}_{1,1}\cup {\widehat{S}}_{1,2}\cup {\widehat{S}}_{1,3}\cup {\widehat{S}}_{1,4}={S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,1}\cup {S}_{4,0},\\ {S}_{2}={\widehat{S}}_{2,1}\cup {\widehat{S}}_{2,2}\cup {\widehat{S}}_{2,3}\cup {\widehat{S}}_{2,4}={S}_{1,2}\cup {S}_{2,2}\cup {S}_{3,0}\cup {S}_{4,1},\\ {S}_{3}={\widehat{S}}_{3,1}\cup {\widehat{S}}_{3,2}\cup {\widehat{S}}_{3,3}\cup {\widehat{S}}_{3,4}={S}_{1,3}\cup {S}_{2,0}\cup {S}_{3,2}\cup {S}_{4,2},\\ {S}_{4}={\widehat{S}}_{4,1}\cup {\widehat{S}}_{4,2}\cup {\widehat{S}}_{4,3}\cup {\widehat{S}}_{4,4}={S}_{1,0}\cup {S}_{2,3}\cup {S}_{3,3}\cup {S}_{4,3}.\end{array}$$By using partitions of both the secret and cover images in Figs. 3(a) and 3(b), the composition of shadows for the proposed (3, 4)-BPVCS by Construction 2 is shown in Fig. 5.
Let us consider a reconstruction. When stacking two shadows, S_{1} and S_{2}, we have four noise-like image blocks (see (17)). As shown in (18), when stacking S_{1}, S_{3}, and S_{4}, we will have one image block, P_{3}, and three noise-like blocks since S_{1,0}, S_{2,0}, and S_{4,0} are unrelated in the reconstruction; thus, we have nothing when stacking (S_{1,1} + S_{1,3} + S_{1,0}), (S_{2,1} + S_{2,0} +S_{2,3}), (S_{3,1} + S_{3,2} + S_{3,3}), and (S_{4,0} + S_{4,2} + S_{4,3}).$$\{\begin{array}{l}{S}_{1}+{S}_{2}=({S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,1}\cup {S}_{4,0})+({S}_{1,2}\cup {S}_{2,2}\cup {S}_{3,0}\cup {S}_{4,1})\\ =\stackrel{\text{4noise-likeblocks}}{\overbrace{({S}_{1,1}+{S}_{1,2})\cup ({S}_{2,1}+{S}_{2,2})\cup ({S}_{3,1}+{S}_{3,0})\cup ({S}_{4,0}+{S}_{4,1})}}\end{array},$$$$\{\begin{array}{l}{S}_{1}+{S}_{3}+{S}_{4}=({S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,1}\cup {S}_{4,0})+({S}_{1,3}\cup {S}_{2,0}\cup {S}_{3,2}\cup {S}_{4,2})\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}+({S}_{1,0}\cup {S}_{2,3}\cup {S}_{3,3}\cup {S}_{4,3})\\ =({S}_{1,1}+{S}_{1,3}+{S}_{1,0})\cup ({S}_{2,1}+{S}_{2,0}+{S}_{2,3})\cup ({S}_{3,1}+{S}_{3,2}+{S}_{3,3})\\ \cup \text{\hspace{0.17em}}({S}_{4,0}+{S}_{4,2}+{S}_{4,3})\text{}\\ =\stackrel{\text{1imageblock}}{\overbrace{{P}_{3}}}\text{}\cup \stackrel{\text{3noise-likeblocks}}{\overbrace{({S}_{1,1}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{S}_{1,3}\text{\hspace{0.17em}}+{S}_{1,0})\cup ({S}_{2,1}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{S}_{2,0}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{S}_{2,3})\cup ({S}_{4,0}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{S}_{4,2}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{S}_{4,3})}}.\end{array}$$Obviously, we can recover all image blocks when stacking all shadows (see (19)).$$\{\begin{array}{l}{S}_{1}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{2}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{3}\text{\hspace{0.05em}}+\text{\hspace{0.05em}}{S}_{4}\text{\hspace{0.05em}}=({S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,1}\cup {S}_{4,0})\text{\hspace{0.17em}}+\text{\hspace{0.17em}}({S}_{1,2}\text{\hspace{0.17em}}\cup {S}_{2,2}\text{\hspace{0.17em}}\cup {S}_{3,0}\text{\hspace{0.17em}}\cup {S}_{4,1})\\ +({S}_{1,3}\cup {S}_{2,0}\cup {S}_{3,2}\cup {S}_{4,2})+({S}_{1,0}\cup {S}_{2,3}\cup {S}_{3,3}\cup {S}_{4,3})\\ =({S}_{1,1}+{S}_{1,2}+{S}_{1,3}+{S}_{1,0})\cup ({S}_{2,1}+{S}_{2,2}+{S}_{2,0}+{S}_{2,3})\\ \cup \text{\hspace{0.17em}}({S}_{3,1}+{S}_{3,0}+{S}_{3,2}+{S}_{3,3})\cup ({S}_{4,0}+{S}_{4,1}+{S}_{4,2}+{S}_{4,3})\\ =\stackrel{\text{4imageblocks}}{\overbrace{{P}_{1}\cup {P}_{2}\cup {P}_{3}\cup {P}_{4}}}.\end{array}$$
- 3. Image Blocks in (k,n)-BPVCS
With regards to the recovered image blocks, in Hou and others’ (2, n)-BPVCS, each participant has his own decryption key for one particular image block; for example, t participants (say p_{1}, p_{2}, ... , p_{t}) can stack their shadows to recover the image blocks (P_{1}, P_{2}, ... , P_{t}). So, every participant has his own image block. We have n participants; thus, there are n image blocks. In Construction 1, there are _{n}C_{k−1} image blocks. There are _{4}C_{2} = 6 image blocks for our (3, 4)-BPVCS. Here, we rename these six image blocks p_{1}, p_{2}, ... , P_{6}, as P_{1,2}, P_{1,3}, P_{1,4}, P_{2,3}, P_{2,4}, and P_{3,4}, respectively. As shown in (20), for P_{1,4} (see the third column), there are two 1s elements — one in the first row and the other in the fourth row.$${B}_{4,2}=\begin{array}{c}\begin{array}{l}\\ {p}_{1}\to \end{array}\\ {p}_{2}\to \\ {p}_{3}\to \\ {p}_{4}\to \end{array}\left[\begin{array}{llllll}\stackrel{{P}_{1,2}}{\overbrace{1}}\hfill & \stackrel{{P}_{1,3}}{\overbrace{1}}\hfill & \stackrel{{P}_{1,4}}{\overbrace{1}}\hfill & \stackrel{{P}_{2,3}}{\overbrace{0}}\hfill & \stackrel{{P}_{2,4}}{\overbrace{0}}\hfill & \stackrel{{P}_{3,4}}{\overbrace{0}}\hfill \\ \text{}1\hfill & \text{}0\hfill & \text{}0\hfill & \text{}1\hfill & \text{}1\hfill & \text{}0\hfill \\ \text{}0\hfill & \text{}1\hfill & \text{}0\hfill & \text{}1\hfill & \text{}0\hfill & \text{}1\hfill \\ \text{}0\hfill & \text{}0\hfill & \text{}1\hfill & \text{}0\hfill & \text{}1\hfill & \text{}1\hfill \end{array}\right].$$In Construction 1, we use the same sub-shadow S_{j,1} for “0.” Therefore, the shadows S_{1} and S_{4} for each of the “1” elements are necessary in reconstructing the image block P_{1,4}. This implies that the involved three participants need p_{1} and p_{4} to recover P_{1,4}. Therefore, p_{1} and p_{4} have their own decryption key for the particular image block P_{1,4}. In Construction 1, we have _{n}C_{k−1} image blocks P_{j1,j2,...,jk−1}, where j_{i}∈{1, 2, ... , n} and i = 1, 2, ... , k − 1. When t participants (say p_{1}, p_{2}, ... , p_{t}) are involved in reconstruction, then _{t}C_{k−1} image blocks, P_{j1,j2,...,jk−1}, where j_{i} ∈ {1, 2, ... , t} and i = 1, 2, ... , k − 1, associated with these t participants can be recovered. For example, in a (3, 4)-BPVCS by Construction 1, S_{1}, S_{3}, and S_{4} can be stacked to recover P_{1,3}, P_{1,4}, and P_{3,4}. On the other hand, in a (3, 4)-BPVCS by Construction 2, there are _{4}C_{3} = 4 image blocks. Here, we rename the four image bocks, P_{1}, P_{2}, P_{3}, and P_{4}, as P_{1,2,3}, P_{1,2,4}, P_{1,3,4}, and P_{2,3,4}, respectively.Let us consider the first column in (21), we use sub-shadows S_{1,1}, S_{1,2}, and S_{1,3} for the element “1”; thus, the participants p_{1}, p_{2}, and p_{3} are necessary in reconstructing the image block P_{1,2,3}. Thus, we can say they have their own decryption key for the particular image block P_{1,2,3}.From the above description, t participants in both constructions have their own decryption keys for _{t}C_{k−1} (Construction 1) or _{t}C_{k} (Construction 2) particular image blocks. The proposed (k, n)-BPVCS has a similar progressive recovery to that of Hou and others’ (2, n)-BPVCS. In fact, Construction 1 is reduced to Hou and others’ (2, n)-BPVCS for k = 2.$${B}_{4,3}^{\prime}=\begin{array}{c}\begin{array}{l}\\ {p}_{1}\to \end{array}\\ {p}_{2}\to \\ {p}_{3}\to \\ {p}_{4}\to \end{array}\left[\begin{array}{llll}\stackrel{{P}_{1,2,3}}{\overbrace{1}}\hfill & \stackrel{{P}_{1,2,4}}{\overbrace{1}}\hfill & \stackrel{{P}_{1,3,4}}{\overbrace{1}}\hfill & \stackrel{{P}_{2,3,4}}{\overbrace{0}}\hfill \\ \text{}1\hfill & \text{1}\hfill & \text{}0\hfill & \text{}1\hfill \\ \text{1}\hfill & \text{0}\hfill & \text{1}\hfill & \text{}1\hfill \\ \text{}0\hfill & \text{1}\hfill & \text{}1\hfill & \text{1}\hfill \end{array}\right].$$
IV. Experiment and Discussion
- 1. Experimental Results
There are two types of Hou and others’ (2, n)-BPVCS — one containing noise-like shadows and one containing meaningful shadows. Construction 1 and Construction 2 can also be implemented with noise-like and meaningful shadows. The difference is that one uses (k, k)-PVCS and the other uses (k, k)-PEVCS with the same cover image. Here, we conduct two experiments to evaluate the performance of the proposed (k, n)-BPVCS with noise-like shadows by Construction 1 and Construction 2.Experiment A. Construct the proposed (3, 4)-BPVCS with noise-like shadows by Construction 1.Here, we use (3, 3)-PVCS with
C 1 ={ [ 1 0 0 ],[ 0 1 0 ],[ 0 0 1 ],[ 1 1 1 ] }
and
C 0 ={ [ 0 0 0 ],[ 0 1 1 ],[ 1 0 1 ],[ 1 1 0 ] }
. Suppose that the secret image is
P = A B C D E F
, and that this is divided into six image blocks
P 1 = A
,
P 2 = B
,
P 3 = C
,
P 4 = D
,
P 5 = E
, and
P 6 = F
.Figure 6 reveals four noise-like shadows and the results of stacking two, three, and four shadows. Obviously, we have six noise-like image blocks, and we do not have any secret information for stacking any two shadows. However, in Fig. 6(b), it is observed that there is one noise-like image block lighter than the other five noise-like image blocks when stacking two shadows. When stacking S_{1} and S_{2}, the area of P_{6} only has one sub-shadow, S_{6,1} (see (11)); however, the other five areas have two stacked sub-shadows. Therefore, the area of P_{6} is lighter than the other areas. When stacking any three shadows, we can recover _{3}C_{2} = 3 image blocks. For example, when stacking S_{1}, S_{3}, and S_{4} (see (12)), we will have three image blocks, P_{2}, P_{3}, and P_{6}, and three noise-like blocks. The stacked result of (S_{1} + S_{3} + S_{4}) with the contrast α = 1 / 4 is illustrated in Fig. 6(c-3). As shown in Fig. 6(d), the complete secret
A B C D E F
is recovered for stacking all four shadows, and the contrast is still 1/4.
Progressive recovery of (3, 4)-BPVCS with noise-like shadows by Construction 1: (a) four shadows, (b) stacking any two shadows, (c) stacking any three shadows, and (d) stacking all four shadows.
Experiment B. Construct the proposed (3, 4)-BPVCS with noise-like shadows by Construction 2.We use the (3, 3)-PVCS in Experiment A. Construction 2 only needs four image blocks. Suppose that the secret image is
P=M A B C D
, and that this is divided into four image blocks
P 1 = A
,
P 2 = B
,
P 3 = C
, and
P 4 = D
.Figure 7 reveals four noise-like shadows and the stacked results of stacking two, three, and four shadows. Any two stacked shadows have two stacked sub-shadows in each image-block area; thus, we have nothing. When stacking any three shadows, we can recover _{3}C_{3} = 1 image block. For example, when stacking S_{1}, S_{3}, and S_{4} (see (18)), we have one image block, P_{3}, and three noise-like blocks. The stacked result of (S_{1} + S_{3} + S_{4}) is illustrated in Fig. 7(c-3). The contrast for this image block is α = (1 − 0)/4 = 1/4. The complete secret
A B C D
is recovered for four stacked shadows (see Fig. 7(d)), and the contrast is reduced to 1/8 due to stacking an extra random sub-shadow, S_{j,0}.
Progressive recovery of (3, 4)-BPVCS with noise-like shadows by Construction 2: (a) four shadows, (b) stacking any two shadows, (c) stacking any three shadows, and (d) stacking all four shadows.
- 2. Comparison and Discussion
Hou and others’ scheme is a simple 2-out-of-n BPVCS. Both our constructions can be applied to any k and n. Hou and others’ scheme uses n image blocks, but Construction 1 and Construction 2 use _{n}C_{k−1} and _{n}C_{k} image blocks, respectively.Although the three schemes have different numbers of image blocks, any t (≥ k) participants in all these three schemes have their own decryption keys for the particular image blocks. In fact, _{n}C_{k−1} image blocks in Construction 1 is reduced to _{n}C_{2−1} = n in Hou and others’ (2, n)-BPVCS. When stacking k shadows, all three schemes have the same contrast to that of (k, k)-PVCS (note: k is 2 in Hou and others’ scheme).When stacking (k + 1) or more shadows, the contrasts of Hou and others’ scheme and Construction 1 are invariant. However, the contrast of Construction 2 is compromised due to an extra sub-shadow, S_{j,0}. Next, we discuss the following issues of the proposed (k, n)-BPVCS in detail: (a) non-uniform stacked results, (b) reconstruction of image blocks, (c) progressive recovery ratio, and (d) requirement of S_{j,0} in Construction 2.A. Non-uniform Stacked ResultsForm our experimental results, it is observed that Construction 1 has the non-uniform stacked results when stacking t shadows, where 2 ≤ t ≤ k − 1. Since Construction 1 is based on the matrix B_{n,k−1}, where every column has (k − 1) 1s, the stacked result has _{t}C_{r} × _{n−t}C_{k−1−t+r}t-tuples with r 0s. We use the same sub-shadow S_{j,1} at the element “0” in the jth column; thus, the color in the stacked result is lighter if this image block has r 0s, where r ≥ 2. A (3, 4)-BPVCS by Construction 1 has _{2}C_{0} × _{4−2}C_{3−1−2+0} = 1 2-tuples with zero 0s, _{2}C_{1}× _{4−2}C_{3−1−2+1} = 4 2-tuples with one 0, and _{2}C_{2} × _{4−2}C_{3−1–2+2} = 1 with two 0s, respectively. As shown in Fig. 6(b), there are five darker image blocks (r = 0 and 1) and one lighter image block (r = 2) when stacking t = 2 shadows. Construction 2 also has a similar characteristic, because we use the same sub-shadow S_{j,0} at the element “0” in the jth column. Since every column of B′_{n,k} has k 1s, so the stacked result has _{t}C_{r} × _{n−t}C_{k−t+r}t-tuples with r 0s. Therefore, when stacking two shadows, a (3, 4)-BPVCS by Construction 2 has _{2}C_{0} ×_{4−2}C_{3–2+0} = 2 2-tuples with zero 0s and _{2}C_{1}×_{4−2}C_{3−2+1} = 2 2-tuples with one 0, respectively. So, there are four darker image blocks (r = 0 and 1) but no lighter image block (see Fig. 7(b)). Our scheme extends Hou and others’ (2, n)-BPVCS to the BPVCS with k > 2 by using the same sub-shadow for each “0” element in matrices B_{n,k−1} and B′_{n,k}. This approach causes color darkening in some areas when stacking less than k shadows. Although our (k, n)-BPVCS may have non-uniform stacked results, it does not compromise the security.B. Reconstruction of Image BlocksIn Construction 1, we have _{n}C_{k−1} image blocks and n participants. Every participant has privilege to recover the particular _{n−1}C_{k−2} image blocks when they are involved in reconstruction. On the other hand, Construction 2 has _{n}C_{k} image blocks, and every participant has privilege to recover the particular _{n−1}C_{k−1} image blocks. For Construction 1 with k = 2 (that is, Hou and others’ (2, n)-BPVCS), the number of image blocks, _{n}C_{2−1} = n, happens to equal the number of participants. For this case, each participant p_{i} can be assigned for recovering _{n−1}C_{2−2} = 1 image block P_{i}, and it is easy to understand the statement [14] about Hou and others’ (2, n)-BPVCS, “Each participant has his/her own decryption key for one particular image block.” Suppose that four image blocks of (2, 4)-BPVCS using Construction 1 (that is, Hou and others’ (2, 4)-BPVCS) are P_{1}, P_{2}, P_{3}, and P_{4}. Two participants, p_{i} and p_{j}, can recover two image blocks, P_{i} and P_{j}. In this reconstruction, the participant p_{i} is necessary for recovering the image block P_{i}. Each participant is required for their image block. For another (2, 4)-BPVCS by Construction 2, suppose that six image blocks are P_{1,2}, P_{1,3}, P_{1,4}, P_{2,3}, P_{2,4}, and P_{3,4}. When participant p_{1} cooperates with another participant, p_{2}, p_{3}, or p_{4}, respectively, they can recover P_{1,2}, P_{1,3}, or P_{1,4}. So, every participant has privilege to recover _{4−1}C_{2−1} = 3 particular image blocks. Thus, each participant in Construction 2 also has his own decryption key for particular image blocks.C. Progressive Recovery RatioHere, we define the progressive recovery ratio as the number of recovered image blocks over the number of whole image blocks when stacking t shadows, where k ≤ t ≤ n. The progressive recovery ratios of Hou and others’ (2, n)-BPVCS, Construction 1, and Construction 2 are R_{H} = t/n, R_{1} = _{t}C_{k−1}/_{n}C_{k−1}, and R_{2} = _{t}C_{k}/_{n}C_{k}, respectively. It can be easily verified that the difference of R_{H}, R_{1}, and R_{2} between stacking t and (t − 1) shadows is R_{H} = 1/n, R_{1} = [(k − 1) × _{t−1}C_{k−1}]/[(t + 1 − k) × _{n}C_{k−1}], and R_{2} = [k × _{t−1}C_{k}]/[(t − k) × _{n}C_{k}]. Hou and others’ scheme R_{H} = 1/n is fixed, so its progressive recovery ratio is linear and smooth. For the case k << n, the variation of _{t−1}C_{k} is greater than _{t−1}C_{k−1}, so R_{1} is more uniform than R_{2}. Figure 8 reveals the progressive recovery ratios for (2, 30)-BPVCS and (3, 30)-BPVCS.
Progressive recovery ratios, k ≤ t ≤ n, of proposed (k, n)-BPVCS by Construction 1 and Construction 2: (a) (2, 30)-BPVCS and (b) (3, 30)-BPVCS.
D. Requirement of S_{j,0} in Construction 2In Construction 2, we use a random S_{j,0} for each element “0” in B′_{n,k}. This sub-shadow is completely unrelated to other sub-shadows. It has no contribution for recovering the secret but only degrades the contrast. However, it has k 1s in every column in B′_{n,k}, where we use k sub-shadows from (k, k)-PVCS (or (k, k)-PEVCS). Actually, we do not need a sub-shadow for the “0” elements. Consider (3, 4)-BPVCS by Construction 2. If we do not use a random sub-shadow, S_{1,0}, S_{2,0}, S_{3,0} and S_{4,0}, then (15) will be modified as (22).$$\left[{\widehat{S}}_{i,j}\right]=\left[\begin{array}{cccc}{\widehat{S}}_{1,1}& {\widehat{S}}_{1,2}& {\widehat{S}}_{1,3}& {\widehat{S}}_{1,4}\\ {\widehat{S}}_{2,1}& {\widehat{S}}_{2,2}& {\widehat{S}}_{2,3}& {\widehat{S}}_{2,4}\\ {\widehat{S}}_{3,1}& {\widehat{S}}_{3,2}& {\widehat{S}}_{3,3}& {\widehat{S}}_{3,4}\\ {\widehat{S}}_{4,1}& {\widehat{S}}_{4,2}& {\widehat{S}}_{4,3}& {\widehat{S}}_{4,4}\end{array}\right]=\left[\begin{array}{cccc}{S}_{1,1}& {S}_{2,1}& {S}_{3,1}& \varphi \\ {S}_{1,2}& {S}_{2,2}& \varphi & {S}_{4,1}\\ {S}_{1,3}& \varphi & {S}_{3,2}& {S}_{4,2}\\ \varphi & {S}_{2,3}& {S}_{3,3}& {S}_{4,3}\end{array}\right].$$Four shadows, S_{1}, S_{2}, S_{3}, and S_{4}, are then generated in (23), and each shadow only has three sub-shadows. For example, S_{1} = S_{1,1} ∪ S_{2,1} ∪ S_{3,1}; there is no sub-shadow at the position of image block P_{4}.$$\{\begin{array}{l}{S}_{1}={\widehat{S}}_{1,1}\cup {\widehat{S}}_{1,2}\cup {\widehat{S}}_{1,3}\cup {\widehat{S}}_{1,4}={S}_{1,1}\cup {S}_{2,1}\cup {S}_{3,1},\\ {S}_{2}={\widehat{S}}_{2,1}\cup {\widehat{S}}_{2,2}\cup {\widehat{S}}_{2,3}\cup {\widehat{S}}_{2,4}={S}_{1,2}\cup {S}_{2,2}\cup {S}_{4,1},\\ {S}_{3}={\widehat{S}}_{3,1}\cup {\widehat{S}}_{3,2}\cup {\widehat{S}}_{3,3}\cup {\widehat{S}}_{3,4}={S}_{1,3}\cup {S}_{3,2}\cup {S}_{4,2},\\ {S}_{4}={\widehat{S}}_{4,1}\cup {\widehat{S}}_{4,2}\cup {\widehat{S}}_{4,3}\cup {\widehat{S}}_{4,4}={S}_{2,3}\cup {S}_{3,3}\cup {S}_{4,3}.\end{array}$$In Fig. 9, four shadows generated from (23) look so odd without using the sub-shadow S_{j,0}. This is why we use S_{j,0} in Construction 2.
Four shadows of (3, 4)-BPVCS by Construction 2 with noise-like shadows.
V. Conclusion
In this paper we provided two constructions for a general (k, n)-BPVCS. Also, we theoretically proved that the proposed (k, n)-BPVCS satisfies the threshold property and progressive recovery. For the special case k = 2, Construction 1 is reduced to Hou and others’ (2, n)-BPVCS. Both constructions using different image blocks have different progressive recovery ratios.
The research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) by the Ministry of Education, Science & Technology (20120192).
BIO
cnyang@mail.ndhu.edu.twChing Nung Yang received his BS and MS degrees in telecommunication engineering from National Chiao Tung University, Hsinchu, Taiwan. He received his PhD degree in electrical engineering from National Cheng Kung University, Tainan, Taiwan. Since 2009, he has been working as a professor with the Computer Science and Information Engineering Department, National Dong Hwa University, Hualien, Taiwan. He is also an IEEE senior member. He has published a number of journal and conference papers in the areas of information security, multimedia security, and coding theory. He is the guest editor of a special issue on “Visual Cryptography Schemes” for Communication of CCISA, and a coauthor of a series of articles on “Image Secret Sharing” for the Encyclopedia of Multimedia. He is the coeditor of two books, “Visual Cryptography and Secret Image Sharing” published by CRC Press/Taylor & Francis, and “Steganography and Watermarking” published by Nova Science Publishers, Inc. He serves as a technical reviewer for over 30 major scientific journals in the areas of his expertise, and serves on the editorial boards of selected journals. He is the recipient of the 2000, 2006, 2010, 2012, and 2014 Fine Advising Award in the Thesis of Master/PhD of Science awarded by the Institute of Information & Computer Machinery of Dong Wha University. His current research interests include coding theory, information security, and cryptography.
d9721004@ems.ndhu.edu.twChih Cheng Wu is a graduate student in computer science and information engineering at National Dong Hwa University, Hualien, Taiwan. His research interests are visual cryptography, secret image sharing, and digital signatures.
u9721020@ems.ndhu.edu.twYi-Chin Lin is a graduate student in computer science and information engineering at National Dong Hwa University, Hualien, Taiwan. His current research interests include visual cryptography and secret image sharing.
Corresponding Authormipsan@paran.comCheonshik Kim received his PhD degree in computer engineering from Hankuk Univesity of Foreign Studies, Seoul, Rep. of Korea, in 2003. From March 2013, he worked for Digital System Engineering, Anyang University, Rep. of Korea. His researches were supported by NRF (2012–2015). He was a subject of biographical record in Marquis Who’s Who in the World 2013–2015.
Wang D.
,
Yi F.
,
Li X.
2011
“Probabilistic Visual Secret Sharing Schemes for Grey-Scale Images and Color Images,”
Inf. Sci.
181
(11)
2189 -
2208
DOI : 10.1016/j.ins.2011.01.019
Verheul E.R.
,
van Tilborg H.C.A.
1997
“Constructions and Properties of k out of n Visual Secret Sharing Schemes,”
Des., Codes Cryptography
11
(2)
179 -
196
DOI : 10.1023/A:1008280705142
@article{ HJTODO_2015_v37n5_979}
,title={Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography}
,volume={5}
, url={http://dx.doi.org/10.4218/etrij.15.0114.0327}, DOI={10.4218/etrij.15.0114.0327}
, number= {5}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Yang, Ching-Nung
and
Wu, Chih-Cheng
and
Lin, Yi-Chin
and
Kim, Cheonshik}
, year={2015}
, month={Oct}
TY - JOUR
T2 - ETRI Journal
AU - Yang, Ching-Nung
AU - Wu, Chih-Cheng
AU - Lin, Yi-Chin
AU - Kim, Cheonshik
SN - 1225-6463
TI - Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography
VL - 37
PB - Electronics and Telecommunications Research Institute
DO - 10.4218/etrij.15.0114.0327
PY - 2015
UR - http://dx.doi.org/10.4218/etrij.15.0114.0327
ER -
Yang, C. N.
,
Wu, C. C.
,
Lin, Y. C.
,
&
Kim, C.
( 2015).
Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography.
ETRI Journal,
37
(5)
Electronics and Telecommunications Research Institute.
doi:10.4218/etrij.15.0114.0327
Yang, CN
,
Wu, CC
,
Lin, YC
,
&
Kim, C
2015,
Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography,
ETRI Journal,
vol. 5,
no. 5,
Retrieved from http://dx.doi.org/10.4218/etrij.15.0114.0327
[1]
CN Yang
,
CC Wu
,
YC Lin
,
and
C Kim
,
“Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography”,
ETRI Journal,
vol. 5,
no. 5,
Oct
2015.
Yang, Ching-Nung
Wu, Chih-Cheng
Lin, Yi-Chin
et al.
“Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography”
ETRI Journal,
5.
5
2015:
Yang, CN
,
Wu, CC
,
Lin, YC
,
Kim, C
Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography.
ETRI Journal
[Internet].
2015.
Oct ;
5
(5)
Available from http://dx.doi.org/10.4218/etrij.15.0114.0327
Yang, Ching-Nung
,
Wu, Chih-Cheng
,
Lin, Yi-Chin
,
and
Kim, Cheonshik
,
“Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography.”
ETRI Journal
5
no.5
()
Oct,
2015):
http://dx.doi.org/10.4218/etrij.15.0114.0327