Title: Constructions and Properties of General (<i>k, n</i>) Block-Based Progressive Visual Cryptography
Abstract: ETRI JournalVolume 37, Issue 5 p. 979-989 ArticleFree Access Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography Ching-Nung Yang, Ching-Nung Yang [email protected] Search for more papers by this authorChih-Cheng Wu, Chih-Cheng Wu [email protected] Search for more papers by this authorYi-Chin Lin, Yi-Chin Lin [email protected] Search for more papers by this authorCheonshik Kim, Corresponding Author Cheonshik Kim [email protected] Corresponding Author[email protected]Search for more papers by this author Ching-Nung Yang, Ching-Nung Yang [email protected] Search for more papers by this authorChih-Cheng Wu, Chih-Cheng Wu [email protected] Search for more papers by this authorYi-Chin Lin, Yi-Chin Lin [email protected] Search for more papers by this authorCheonshik Kim, Corresponding Author Cheonshik Kim [email protected] Corresponding Author[email protected]Search for more papers by this author First published: 01 October 2015 https://doi.org/10.4218/etrij.15.0114.0327Citations: 7 Ching-Nung Yang ([email protected]), Chih-Cheng Wu ([email protected]), and Yi-Chin Lin ([email protected]) are with the Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien, Taiwan. Cheonshik Kim (corresponding author, [email protected]) is with the Department of Digital Media Engineering, Anyang University, Rep. of Korea. 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). AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract 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 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 , Construction 1 is reduced to Hou and others’ (2, n)-BPVCS.] I. Introduction A (k, n) visual cryptographic scheme (VCS), where , 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 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 — known as probabilistic VCS (PVCS). Hence, a conventional VCS with fixed m 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, . The progressive recovery operates under the assumption that if any shadows are stacked and participant is involved, then the image block Pi 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 participants. Two constructions — “Construction 1” and “Construction 2” — using and image blocks, respectively, are proposed. For , 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 “”B“h”W (that is, () black subpixels and h white subpixels) and “”B“l”W, where , to represent white and black secret pixels, respectively. The collection of the corresponding m subpixels in n shadows can be represented by an Boolean matrix , where the element Si,j represents the jth subpixel in the ith shadow. If Si,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 , where i1, i2, …, it 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 Boolean matrices, B1 and B0. 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 B1 (respectively B0) 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) In B1, the OR-ed vector v1 of any k out of n rows satisfies . 2) In B0, the OR-ed vector v0 of any k out of n rows satisfies 3) For any subset with , the two collections of matrices obtained by restricting each matrix to rows i1, i2, …, it are indistinguishable in the sense that they contain the same matrices with the same frequencies. The first two conditions are called contrast conditions, and the third condition is the security condition. Let OR(B1|t) and OR(B0|t) denote the “OR”-ed of any t rows in B1 and B0, 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): and for for . 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, 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 (that is, no pixel expansion). A (k, n)-PVCS can be constructed by a black set and a white set (C1 and C0) consisting of column matrices, respectively. When sharing a black (respectively white) pixel, the dealer first randomly chooses one column matrix in C1 (respectively C0), 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 B0 and B1 in a DVCS as the column matrices of sets C0 and C1 in a PVCS. Let OR(C1 | t) and OR(C0 | t) denote OR-ed t rows in all column matrices in C1 and C0, 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: and for , where . for . 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 p0 and p1, respectively, the average contrast of a PVCS is defined to be [4]. Since all matrices in C0 and C1 are 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 and It is observed that , and ; thus, they satisfy (D-1) and (D-2). Suppose that xByW represents and its permutations. In a reconstructed image, the black color is 2B0W and the white color is 1B1W; the contrast is . 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 B0 and B1 as the column matrices in sets and respectively. Since OR and , we have and . This satisfies condition (P-1); and the average contrast . In addition, 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 S1 and S2 be two shadows of a (2, 2)-EVCS, and ci is the cover pixel on Si, where . Suppose that is a matrix for a black (white) secret pixel in a (2, 2)-EVCS. Then, the associated cover pixel is black or white , where c1 and c2 denote the colors in S1 and S2, respectively. The following example shows Naor and Shamir's (2, 2)-EVCS [2]. Example 2. Construct a (2, 2)-EVCS with . All eight basis matrices, are given as follows: (1) The contrast of the recovered image is given by . Since the Hamming weight of the ith row , is 2 and 3 for and , respectively, the contrast of shadow αs is also . If two shadows in this (2, 2)-EVCS have the same cover image, then the colors of c1 and c2 are the same (that is, ). Thus, we only require 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 for (2, 2)-DVCS, while 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 column matrices — Therefore, the sets of a (2, 2)-PEVCS with two different cover images on shadows are shown as follows: (2) Since and , we have and . So, . For a (2, 2)-PEVCS with shadows that have an identical cover image, there are only four sets — 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 {P1, P2, …, Pn} that satisfy the following two properties: (a) any two image blocks do not have the same overlapping area; that is, for (disjoint property) and (b) their union is the original secret image P; that is, (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 is involved in reconstruction, then the image block Pi can be recovered. When any 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 — P1, P2, and P3. When two participants, p1 and p2, cooperate together, they can recover image blocks P1 and P2, and the other area is noise-like. However, when stacking shadows, or , the image blocks P1 and P3, and P2 and P3 are recovered, respectively. All three stacked shadows can recover all image blocks, P1, P2, and P3. 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 Pi, , to get noise-like sub-shadows Si,1 and Si,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 Oi, , according to the position of image block Pi. Then, for each Pi and Oi, , we apply (2, 2)-PEVCS with the same cover image to obtain sub-shadows Si,1 and Si,2. The method of composition of shadows for these two (2, n)-BPVCSs is the same. The dealer delivers Si,1 to participant i and Si,2 to the other participants. Afterwards, every participant offers up all of their received sub-shadows according to the position of Pi to construct n shadows as follows: (3) 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. Figure 1Open in figure viewerPowerPoint Composition of shadows for Hou and others’ (2, 4)-BPVCS: (a) four image blocks, (b) four subcover images, and (c) four shadows. (4) Consider the stacked result of . We have two image blocks, P1 and P2, and two noise-like blocks, S3,2 and S4,2, as shown in (5). By stacking another shadow S3 on , we obtain three image blocks, P1, P2, and P3, and one noise-like block, S4,2, in (6). When stacking all four shadows, we can recover all image blocks (see (7)). (5) (6) (7) 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 P1, P2, P3, and P4 are the printed-texts , , , and , respectively; that is, P is . By applying a (2, 2)-PVCS with and to P1, P2, P3, and P4, 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 S1 and S3, we have (see Fig. 2(b-2)). By adding another shadow, S4, we have (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. Figure 2Open in figure viewerPowerPoint 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 satisfying both the aforementioned disjoint property and union property. For each , we use (k, k)-PVCS to generate k sub-shadows, . In this paper, we will show how to construct n shadows from these sub-shadows. Moreover, both constructions use different image blocks (Construction 1: and Construction 2: 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. Table 1. Notations used in proposed (k, n)-BPVCS. Notation Description D(·) Function dividing an image into image blocks in Construction 1 and image blocks in Construction 2 satisfies disjoint property and union property. Pj Divide a secret image into N image blocks Pj, , where . Oj Divide a cover image into N subcover images Oj, , where . PVCSk,k(·) Encoding function of (k, k)-PVCS. PEVCSk,k(·,·) Encoding function of (k, k)-PEVCS. Sj,1, …, Sj,k k sub-shadows of an image block Pj by using PVCSk,k(·) or PEVCSk,k(·,·). binary matrix used in Construction 1, where , and , and every column vector has Hamming weight . binary matrix used in Construction 2, where , and , and every column vector has Hamming weight k. Si n shadows, , in the proposed (k, n)-BPVCS The design concept of Construction 1 is described as follows. We use a matrix having columns with 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 shadows for 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 . (Step 1–1) Obtain image blocks , by D(P), where . (Step 1–2) Obtain subcover images , where . /* (Step 1–2) is only required for the proposed (k, n)-BPVCS with meaningful shadows */ (Step 2–1) For every image block Pj, create k sub-shadows by PVCSk,k(Pj). (Step 2–2) For every image block Pj and sub cover image Oj, create k sub-shadows (Sj,1, …, Sj.k) by PEVCSk,k(Pj,Oj). /* (Step 2–2) is only required for the proposed (k, n)-BPVCS with meaningful shadows */ (Step 3) Set . (Step 4) Choose a matrix . (Step 5) for to N do ; for to n do then and ; else ;} }; (Step 6) . /* each participant puts up received according to the position of Pj to construct Si*/ 1. Construction 1: (k, n)-BPVCS Using Image Blocks The encoding procedure of the proposed (k, n)-BPVCS with noise-like and meaningful shadows by 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 shadows cannot recover any image block. Any rows in do not have 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 1s and 0s. So, any rows in have t-tuples with 1s and 0s, and have enough k sub-shadows for reconstructing image blocks. For , the number of image blocks is . 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 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 image blocks, . Each image block is divided into three sub-shadows by (3, 3)-PVCS (or (3, 3)-PEVCS). The matrices and of a (3, 4)-BPVCS are given as follows: (8) (9) Four shadows, S1, S2, S3, and S4, are then generated by (10) (11) (12) Figures 3(a) and 3(b) are partitions of the secret image and cover image. Figure 3(c) shows the composition of shadows for the proposed (3, 4)-BPVCS by Construction 1. Figure 3Open in figure viewerPowerPoint Composition of shadows for proposed (3, 4)-BPVCS: (a) six image blocks, (b) six sub-cover images, and (c) four shadows. (13) 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 S1 and S2, we have six noise-like image blocks (see (11)). As shown in (12), by stacking S1, S3, and S4, we can recover three image blocks, P2, P3, and P6, and three noise-like blocks. All four stacked shadows can recover all image blocks (see (13)). 2. Construction 2: (k, n)-BPVCS Using Image Blocks The design concept of Construction 2 is described as follows. We use a matrix having 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 instead of , and instead of . Also, (Step 5) in Construction 1 is modified as (Step 5′) in Construction 2 (see Fig. 4). Figure 4Open in figure viewerPowerPoint Modified (Step 5′) in Construction 2. Random sub-shadows Sj,0 in Construction 2, , are randomly generated in the (k, n)-BPVCS with noise-like shadows. For the (k, n)-BPVCS with meaningful shadows, meaningful sub-shadows Sj,0 , are generated according to Pj and Oj, where the subpixels for black and white pixels are the same as those in (k, k)-PEVCS. For the case 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, Sj,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 Sj,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 Sj,0 is not related to other sub-shadows, Sj,1, Sj,2, …, Sj,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 Pj at the element of “1” in the jth column. Since rows in 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 Sj,0 in position “0” has no contribution for reconstruction. Every column vector has k 1s and 0s. So, any rows in have tCk t-tuples with k 1s, and have enough sub-shadows for reconstructing image blocks. ■ Example 6. Generate four shadows of the proposed (3, 4)-BPVCS by Construction 2. A secret image P is first partitioned into image blocs, P1, P2, P3, and P4. 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, S1,0, S2,0, S3,0, and S4,0, for the (3, 4)-BPVCS with noise-like and meaningful shadows, respectively. The matrices and of a (3, 4)-BPVCS are shown as follows: (14) (15) Four shadows, S1, S2, S3, S4, are then generated by (16) 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. Figure 5Open in figure viewerPowerPoint Composition of shadows for proposed (3, 4)-BPVCS. Let us consider a reconstruction. When stacking two shadows, S1 and S2, we have four noise-like image blocks (see (17)). As shown in (18), when stacking S1, S3, and S4, we will have one image block, P3, and three noise-like blocks since S1,0, S2,0, and S4,0 are unrelated in the reconstruction; thus, we have nothing when stacking . (17) (18) Obviously, we can recover all image blocks when stacking all shadows (see (19)). (19) 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 p1, p2, …, pt) can stack their shadows to recover the image blocks (P1, P2, …, Pt). So, every participant has his own image block. We have n participants; thus, there are n image blocks. In Construction 1, there are image blocks. There are image blocks for our (3, 4)-BPVCS. Here, we rename these six image blocks p1, p2, …, P6, as P1,2, P1,3, P1,4, P2,3, P2,4, and P3,4, respectively. As shown in (20), for P1,4 (see the third column), there are two 1s elements — one in the first row and the other in the fourth row. (20) In Construction 1, we use the same sub-shadow Sj,1 for “0.” Therefore, the shadows S1 and S4 for each of the “1” elements are necessary in reconstructing the image block P1,4. This implies that the involved three participants need p1 and p4 to recover P1,4. Therefore, p1 and p4 have their own decryption key for the particular image block P1,4. In Construction 1, we have image blocks , where and . When t participants (say p1, p2, …, pt) are involved in reconstruction, then image blocks, , where and , associated with these t participants can be recovered. For example, in a (3, 4)-BPVCS by Construction 1, S1, S3, and S4 can be stacked to recover P1,3, P1,4, and P3,4. On the other hand, in a (3, 4)-BPVCS by Construction 2, there are image blocks. Here, we rename the four image bocks, P1, P2, P3, and P4, as P1,2,3, P1,2,4, P1,3,4, and P2,3,4, respectively. Let us consider the first column in (21), we use sub-shadows S1,1, S1,2, and S1,3 for the element “1”; thus, the participants p1, p2, and p3 are necessary in reconstructing the image block P1,2,3. Thus, we can say they have their own decryption key for the particular image block P1,2,3. From the above description, t participants in both constructions have their own decryption keys for (Construction 1) or (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 . (21) 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 and . Suppose that the secret image is , and that this is divided into six image blocks , , , , , and . 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 S1 and S2, the area of P6 only has one sub-shadow, S6,1 (see (11)); however, the other five areas have two stacked sub-shadows. Therefore, the area of P6 is lighter than the other areas. When stacking any three shadows, we can recover image blocks. For example, when stacking S1, S3, and S4 (see (12)), we will have three image blocks, P2, P3, and P6, and three noise-like blocks. The stacked result of with the contrast is illustrated in Fig. 6(c-3). As shown in Fig. 6(d), the complete secret is recovered for stacking all four shadows, and the contrast is still 1/4. Figure 6Open in figure viewerPowerPoint 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 , and that this is divided into four image blocks , , , and . 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 image block. For example, when stacking S1, S3, and S4 (see (18)), we have one image block, P3, and three noise-like blocks. The stacked result of is illustrated in Fig. 7(c-3). The contrast for this image block is . The complete secret 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, Sj,0. Figure 7Open in figure viewerPowerPoint 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 and image blocks, respectively. Although the three schemes have different numbers of image blocks, any participants in all these three schemes have their own decryption keys for the particular image blocks. In fact, image blocks in Construction 1 is reduced to 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 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, Sj,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 Sj,0 in Construction 2. A. Non-uniform Stacked Results Form our experimental results, it is observed that Construction 1 has the non-uniform stacked results when stacking t shadows, where . Since Construction 1 is based on the matrix , where every column has 1s, the stacked result has t-tuples with r 0s. We use the same sub-shadow Sj,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 . A (3, 4)-BPVCS by Construction 1 has 2-tuples with zero 0s, 2-tuples with one 0, and with two 0s, respectively. As shown in Fig. 6(b), there are five darker image blocks ( and 1) and one lighter image block when stacking shadows. Construction 2 also has a similar characteristic, because we use the same sub-shadow Sj,0 at the element “0” in the jth column. Since every column of has k 1s, so the stacked result has t-tuples with r 0s. Therefore, when stacking two shadows, a (3, 4)-BPVCS by Construction 2 has 2-tuples with zero 0s and 2-tuples with one 0, respectively. So, there are four darker image blocks ( and 1) but no lighter image block (see Fig. 7(b)). Our scheme extends Hou and others’ (2, n)-BPVCS to the BPVCS with by using the same sub-shadow for each “0” element in matrices and . 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 Blocks In Construction 1, we have image blocks and n participants. Every participant has privilege to recover the particular image blocks when they are involved in reconstruction. On the other hand, Construction 2 has image blocks, and every participant has privilege to recover the particular image blocks. For Construction 1 with (that is, Hou and others’ (2, n)-BPVCS), the number of image blocks, , happens to equal the number of participants. For this case, each participant pi can be assigned for recovering image block Pi, 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 P1, P2, P3, and P4. Two participants, pi and pj, can recover two image blocks, Pi and Pj. In this reconstruction, the participant pi is necessary for recovering the image block Pi. Each participant is required for their image block. For another (2, 4)-BPVCS by Construction 2, suppose that six image blocks are P1,2, P1,3, P1,4, P2,3, P2,4, and P3,4. When participant p1 cooperates with another participant, p2, p3, or p4, respectively, they can recover P1,2, P1,3, or P1,4. So, every participant has privilege to recover particular image blocks. Thus, each participant in Construction 2 also has his own decryption key for particular image blocks. C. Progressive Recovery Ratio Here, 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 . The progressive recovery ratios of Hou and others’ (2, n)-BPVCS, Construction 1, and Construction 2 are , and , respectively. It can be easily verified that the difference of RH, R1, and R2 between stacking t and shadows is , and . Hou and others’ scheme is fixed, so its progressive recovery ratio is linear and smooth. For the case , the variation of is greater than , so R1 is more uniform than R2. Figure 8 reveals the progressive recovery ratios for (2, 30)-BPVCS and (3, 30)-BPVCS. Figure 8Open in figure viewerPowerPoint Progressive recovery ratios, , of proposed (k, n)-BPVCS by Construction 1 and Construction 2: (a) (2, 30)-BPVCS and (b) (3, 30)-BPVCS. D. Requirement of Sj,0 in Construction 2 In Construction 2, we use a random Sj,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 , 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, S1,0, S2,0, S3,0 and S4,0, then (15) will be modified as (22). (22) Four shadows, S1, S2, S3, and S4, are then generated in (23), and each shadow only has three sub-shadows. For example, ; there is no sub-shadow at the position of image block P4. (23) In Fig. 9, four shadows generated from (23) look so odd without using the sub-shadow Sj,0. This is why we use Sj,0 in Construction 2. Figure 9Open in figure viewerPowerPoint 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 , Construction 1 is reduced to Hou and others’ (2, n)-BPVCS. Both constructions using different image blocks have different progressive recovery ratios. Biographies Ching 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. Chih 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. Yi-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. Cheonshik 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. References 1S. Cimato and C.-N. Yang, “Visual Cryptography and Secret Image Sharing,” New York, USA: CRC Press, Aug. 2011, pp. 5– 16. 2M. Naor and A. Shamir, “Visual Cryptography,” Workshop Theory Appl. Cryptographic Techn., Perugia, Italy, May 9–12, 1994, pp. 1– 12. 3R. Ito, H. Kuwakado, and H. Tanaka, “Image Size Invariant Visual Cryptography,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci., vol. E82-A, Oct. 1999, pp. 2172– 2177. 4C.-N. Yang, “New Visual Secret Sharing Schemes Using Probabilistic Method,” Pattern Recogn. Lett., vol. 25, no. 4, Mar. 2004, pp. 481– 494. 5S. Cimato, R. de Prisco, and A. de Santis, “Probabilistic Visual Cryptography Schemes,” Comput. J., vol. 49, no. 1, Jan. 2006, pp. 97– 107. 6D. Wang, F. Yi, and X. Li, “Probabilistic Visual Secret Sharing Schemes for Grey-Scale Images and Color Images,” Inf. Sci., vol. 181, no. 11, June 2011, pp. 2189– 2208. 7Y.C Hou et al., “Block-Based Progressive Visual Secret Sharing,” Inf. Sci., vol. 233, June 2013, pp. 290– 304. 8E.R Verheul and H.C.A. van Tilborg, “Constructions and Properties of k out of n Visual Secret Sharing Schemes,” Des., Codes Cryptography, vol. 11, no. 2, May 1997, pp. 179– 196. 9M. Bose and R. Mukerjee, “Optimal (k, n) Visual Cryptographic Schemes for General k,” Des., Codes, Cryptography, vol. 55, no. 1, Apr. 2010, pp. 19– 35. 10S.J Shyu and M.C. Chen, “Optimum Pixel Expansions for Threshold Visual Secret Sharing Schemes,” IEEE Trans. Inf. Forensics Security, vol. 6, no. 3, May 2011, pp. 960– 969. 11G. Ateniese et al., “Extended Capabilities for Visual Cryptography,” Theoretical Comput. Sci., vol. 250, no. 1–2, Jan. 2001, pp. 143– 161. 12F. Liu, C.K. Wu, and X.J. Lin, “Some Extensions on Threshold Visual Cryptography Schemes,” Comput. J., vol. 53, no. 1, Jan. 2010, pp. 107– 119. Citing Literature Volume37, Issue5October 2015Pages 979-989 FiguresReferencesRelatedInformation