Advanced
Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography
Constructions and Properties of General (k, n) Block-Based Progressive Visual Cryptography
ETRI Journal. 2015. Oct, 37(5): 979-989
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : March 16, 2014
  • Accepted : July 14, 2015
  • Published : October 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Ching-Nung Yang
Chih-Cheng Wu
Yi-Chin Lin
Cheonshik Kim

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 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.]
Keywords
I. Introduction
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, Pi (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 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 k (≥ 2) participants. Two constructions — “Construction 1” and “Construction 2” — using nC k−1 and nCk 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 = [ Si,j ], where the element Si,j represents the j th subpixel in the i th 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 v = OR( i 1 , i 2 , ... , it ), where i 1 , i 2 , ... , 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 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,
α= H( V 1 )H( V 0 ) m = (ml)(mh) m = hl 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 x B y W 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 ci is the cover pixel on Si , 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 ( ci = 1) or white ( ci = 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:
B 0 00 =[ 1 0 0 1 1 0 1 0 ] B 0 01 =[ 1 0 0 1 1 0 1 1 ], B 0 10 =[ 1 0 1 1 1 0 1 0 ] B 0 11 =[ 1 0 1 1 1 0 1 1 ], B 1 00 =[ 1 0 0 1 0 1 1 0 ] B 1 01 =[ 1 0 0 1 1 1 1 0 ], B 1 10 =[ 1 0 1 1 1 1 0 0 ] B 1 11 =[ 1 0 1 1 1 1 1 0 ].
The contrast of the recovered image is given by α = ( h − l)/ m [= (1 − 0)/4 = 1/4]. Since the Hamming weight of the i th row ( i =1, 2), is 2 and 3 for ci = 0 and ci = 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:
C 0 00 ={ [ 1 1 ][ 0 0 ][ 0 1 ][ 1 0 ] } C 0 01 ={ [ 1 1 ][ 0 0 ][ 0 1 ][ 1 1 ] }, C 0 10 ={ [ 1 1 ][ 0 0 ][ 1 1 ][ 1 0 ] } C 0 11 ={ [ 1 1 ][ 0 0 ][ 1 1 ][ 1 1 ] }, C 1 00 ={ [ 1 0 ][ 0 1 ][ 0 1 ][ 1 0 ] } C 1 01 ={ [ 1 1 ][ 0 1 ][ 0 1 ][ 1 0 ] }, C 1 10 ={ [ 1 1 ][ 0 1 ][ 1 0 ][ 1 0 ] } C 1 11 ={ [ 1 1 ][ 0 1 ][ 1 1 ][ 1 0 ] }.
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 , ... , Pn } that satisfy the following two properties: (a) any two image blocks do not have the same overlapping area; that is, Pi Pj = ϕ for i j (disjoint property) and (b) their union is the original secret image P ; that is, O = P 1 P 2 ∪ ⋯ ∪ Pn (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 Pi 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 Pi , 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 Oi , 1 ≤ i n , according to the position of image block Pi . Then, for each Pi and Oi , 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 Pi to construct n shadows as follows:
S j = S j,1 ( i{1,...,n},ij S i,2 )   (1jn). 
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.
PPT Slide
Lager Image
Composition of shadows for Hou and others’ (2, 4)-BPVCS: (a) four image blocks, (b) four subcover images, and (c) four shadows.
{ S 1 = S 1,1 S 2,2 S 3,2 S 4,2 , S 2 = S 1,2 S 2,1 S 3,2 S 4,2 , S 3 = S 1,2 S 2,2 S 3,1 S 4,2 , S 4 = S 1,2 S 2,2 S 3,2 S 4,1 .
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)).
{ S 1 + S 2 =( S 1,1 + S 1,2 )( S 2,1 + S 2,2 )( S 3,2 + S 3,2 )( S 4,2 + S 4,2 ) = P 1 P 2 2 image blocks S 3,2 S 4,2 2 noise-like blocks .
{ S 1 + S 2 + S 3 =( S 1,1 + S 1,2 + S 1,2 )( S 2,2 + S 2,1 + S 2,2 )  ( S 3,2 + S 3,2 + S 3,1 )( S 4,2 + S 4,2 + S 4,2 ) = P 1 P 2 P 3 3 image blocks S 4,2 1 noise-like block .
{ S 1 + S 2 + S 3 + S 4 =( S 1,1 + S 1,2 + S 1,2 + S 1,2 )( S 2,2 + S 2,1 + S 2,2 + S 2,2 )  ( S 3,2 + S 3,2 + S 3,1 + S 3,2 )( S 4,2 + S 4,2 + S 4,2 + S 4,1 ) = P 1 P 2 P 3 P 4 4 image blocks .
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.
PPT Slide
Lager Image
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 , ... , PN } satisfying both the aforementioned disjoint property and union property. For each Pj , 1 ≤ j N , we use ( k , k )-PVCS to generate k sub-shadows, S i,1 , S i,2 , ... , Si,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 = nC k−1 and Construction 2: N = nCk ) 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 .
Notations used in proposed (k,n)-BPVCS.
Notation Description
D(·) Function dividing an image into N = nCk−1 image blocks in Construction 1 and N = nCk image blocks in Construction 2 satisfies disjoint property and union property.
Pj Divide a secret image into N image blocks Pj, 1 ≤ jN, where D(P) = {P1, P2, ... , PN}.
Oj Divide a cover image into N subcover images Oj, 1 ≤ jN, where D(O) = {O1, O2, ... , ON}.
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(·,·).
Bn,k−1 n × nCk−1 binary matrix Bn,k−1= [bij] used in Construction 1, where bij∈[0, 1], 1 ≤ in and 1 ≤ jnCk−1, and every column vector has Hamming weight (k − 1).
B n,k n × nCk binary matrix B n,k =[ b ij ] used in Construction 2, where bij∈[0, 1], 1 ≤ in and 1 ≤ jnCk, and every column vector has Hamming weight k.
Si n shadows, 1 ≤ in, in the proposed (k, n)-BPVCS
The design concept of Construction 1 is described as follows. We use a matrix having nC 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 Si, i∈[1, n]. (Step 1-1) Obtain image blocks Pj, j∈[1, N], by D(P), where N = nCk−1. (Step 1-2) Obtain subcover images Oj, j∈[1, N], where N = nCk−1. /* (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 (Sj,1, ... , Sj.k) 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 S1 = S2 = ⋯ Sn = ϕ. (Step 4) Choose a matrix Bn,k−1 = [bij]. (Step 5) for j = 1 to N do   {Set x = 2;    for i = 1 to n do{If bij = 1 then S ^ i,j = S j,x and x = x + 1; else S ^ i,j = S j,1 ;}   }; (Step 6) S i = j=1 N S ^ i,j ,i[1,n] . /* each participant puts up received S ^ i,j according to the position of Pj to construct Si*/
- 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 nC 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 tC k−1 t -tuples with ( k − 1) 1s and ( t k + 1) 0s, and have enough k sub-shadows for reconstructing tC k−1 image blocks. For k = 2, the number of image blocks is N = nC k−1 = nC 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
[ S ^ i,j ]
of a (3, 4)-BPVCS are given as follows:
B 4,2 =[ b 11 b 12 b 13 b 14 b 15 b 16 b 21 b 22 b 23 b 24 b 25 b 26 b 31 b 32 b 33 b 34 b 35 b 36 b 41 b 42 b 43 b 54 b 45 b 46 ]=[ 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 ].
[ S ^ i,j ]=       [ S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 S ^ 1,5 S ^ 1,6 S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 S ^ 2,5 S ^ 2,6 S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 S ^ 3,5 S ^ 3,6 S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 S ^ 4,5 S ^ 4,6 ]=[ S 1,2 S 2,2 S 3,2 S 4,1 S 5,1 S 6,1 S 1,3 S 2,1 S 3,1 S 4,2 S 5,2 S 6,1 S 1,1 S 2,3 S 3,1 S 4,3 S 5,1 S 6,2 S 1,1 S 2,1 S 3,3 S 4,1 S 5,3 S 6,3 ]  .
Four shadows, S 1 , S 2 , S 3 , and S 4 , are then generated by
S i = ∪ j=1  6   S ^ i,j , i∈[1, 4].
{ S 1 = S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 S ^ 1,5 S ^ 1,6 = S 1,2 S 2,2 S 3,2 S 4,1 S 5,1 S 6,1 , S 2 = S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 S ^ 2,5 S ^ 2,6 = S 1,3 S 2,1 S 3,1 S 4,2 S 5,2 S 6,1 , S 3 = S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 S ^ 3,5 S ^ 3,6 = S 1,1 S 2,3 S 3,1 S 4,3 S 5,1 S 6,2 , S 4 = S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 S ^ 4,5 S ^ 4,6 = S 1,1 S 2,1 S 3,3 S 4,1 S 5,3 S 6,3 .
{ S 1 + S 2 =( S 1,2 S 2,2 S 3,2 S 4,1 S 5,1 S 6,1 )+( S 1,3 S 2,1 S 3,1 S 4,2 S 5,2 S 6,1 ) = ( S 1,2 + S 1,3 )( S 2,2 + S 2,1 )( S 3,2 + S 3,1 )( S 4,1 + S 4,2 )( S 5,1 + S 5,2 )( S 6,1 ) 6 noise-like blocks .
{ S 1 + S 3 + S 4 =( S 1,2 S 2,2 S 3,2 S 4,1 S 5,1 S 6,1 ) +( S 1,1 S 2,3 S 3,1 S 4,3 S 5,1 S 6,2 )+( S 1,1 S 2,1 S 3,3 S 4,1 S 5,3 S 6,3 ) =( S 1,2 + S 1,1 )( S 2,2 + S 2,3 + S 2,1 ) ( S 3,2 + S 3,1 + S 3,3 )( S 4,1 + S 4,3 )( S 5,1 + S 5,3 )( S 6,1 + S 6,2 + S 6,3 ) = P 2 P 3 P 6 3 image blocks ( S 1,2 + S 1,1 )( S 4,1 + S 4,3 )( S 5,1 + S 5,3 ) 3 noise-like blocks .
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.
PPT Slide
Lager Image
Composition of shadows for proposed (3, 4)-BPVCS: (a) six image blocks, (b) six sub-cover images, and (c) four shadows.
{ S 1 + S 2 + S 3 + S 4 =( S 1,2 S 2,2 S 3,2 S 4,1 S 5,1 S 6,1 ) +( S 1,3 S 2,1 S 3,1 S 4,2 S 5,2 S 6,1 )+( S 1,1 S 2,3 S 3,1 S 4,3 S 5,1 S 6,2 ) +( S 1,1 S 2,1 S 3,3 S 4,1 S 5,3 S 6,3 ) =( S 1,2 + S 1,3 + S 1,1 + S 1,1 )( S 2,2 + S 2,1 + S 2,3 + S 2,1 )( S 3,2 + S 3,1 + S 3,1 + S 3,3 ) ( S 4,1 + S 4,2 + S 4,3 + S 4,1 )( S 5,1 + S 5,2 + S 5,1 + S 5,3 )( S 6,1 + S 6,1 + S 6,2 + S 6,3 ) = P 1 P 2 P 3 P 4 P 5 P 6 6 image blocks .
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 nCk 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 = nCk instead of N = nC 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 ).
PPT Slide
Lager Image
Modified (Step 5′) in Construction 2.
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 Pj and Oj , 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 Pj at the element of “1” in the j th 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 tCk t -tuples with k 1s, and have enough sub-shadows for reconstructing tCk 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
[ S ^ i,j ]
of a (3, 4)-BPVCS are shown as follows:
B 4,3 =[ b 11 b 12 b 13 b 14 b 21 b 22 b 23 b 24 b 31 b 32 b 33 b 34 b 41 b 42 b 43 b 54 ]=[ 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 ],
[ S ^ i,j ]=[ S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 ]=[ S 1,1 S 2,1 S 3,1 S 4,0 S 1,2 S 2,2 S 3,0 S 4,1 S 1,3 S 2,0 S 3,2 S 4,2 S 1,0 S 2,3 S 3,3 S 4,3 ].
Four shadows, S 1 , S 2 , S 3 , S 4 , are then generated by
S i = ∪ j=1  4   S ^ i,j , i∈[1, 4].
{ S 1 = S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 = S 1,1 S 2,1 S 3,1 S 4,0 , S 2 = S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 = S 1,2 S 2,2 S 3,0 S 4,1 , S 3 = S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 = S 1,3 S 2,0 S 3,2 S 4,2 , S 4 = S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 = S 1,0 S 2,3 S 3,3 S 4,3 .
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 .
PPT Slide
Lager Image
Composition of shadows for proposed (3, 4)-BPVCS.
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 ).
{ S 1 + S 2 =( S 1,1 S 2,1 S 3,1 S 4,0 )+( S 1,2 S 2,2 S 3,0 S 4,1 ) = ( S 1,1 + S 1,2 )( S 2,1 + S 2,2 )( S 3,1 + S 3,0 )( S 4,0 + S 4,1 ) 4 noise-like blocks ,
{ S 1 + S 3 + S 4 =( S 1,1 S 2,1 S 3,1 S 4,0 )+( S 1,3 S 2,0 S 3,2 S 4,2 )                                 +( S 1,0 S 2,3 S 3,3 S 4,3 ) =( 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 ) ( S 4,0 + S 4,2 + S 4,3 )​​​​​​​​​​​ = P 3 1 image block ( S 1,1 + S 1,3 + S 1,0 )( S 2,1 + S 2,0 + S 2,3 )( S 4,0 + S 4,2 + S 4,3 ) 3 noise-like blocks .
Obviously, we can recover all image blocks when stacking all shadows (see (19)).
{ S 1 + S 2 + S 3 + S 4 =( S 1,1 S 2,1 S 3,1 S 4,0 )+( S 1,2 S 2,2 S 3,0 S 4,1 ) +( S 1,3 S 2,0 S 3,2 S 4,2 )+( S 1,0 S 2,3 S 3,3 S 4,3 ) =( S 1,1 + S 1,2 + S 1,3 + S 1,0 )( S 2,1 + S 2,2 + S 2,0 + S 2,3 ) ( S 3,1 + S 3,0 + S 3,2 + S 3,3 )( S 4,0 + S 4,1 + S 4,2 + S 4,3 ) = P 1 P 2 P 3 P 4 4 image blocks .
- 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 , ... , pt ) can stack their shadows to recover the image blocks ( P 1 , P 2 , ... , Pt ). So, every participant has his own image block. We have n participants; thus, there are n image blocks. In Construction 1, there are nC 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 = p 1 p 2 p 3 p 4 [ 1 P 1,2 1 P 1,3 1 P 1,4 0 P 2,3 0 P 2,4 0 P 3,4  1  0  0  1  1  0  0  1  0  1  0  1  0  0  1  0  1  1 ].
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 nC k−1 image blocks P j1,j2,...,jk−1 , where ji ∈{1, 2, ... , n } and i = 1, 2, ... , k − 1. When t participants (say p 1 , p 2 , ... , pt ) are involved in reconstruction, then tC k−1 image blocks, P j1,j2,...,jk−1 , where ji ∈ {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 tC k−1 (Construction 1) or tCk (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 = p 1 p 2 p 3 p 4 [ 1 P 1,2,3 1 P 1,2,4 1 P 1,3,4 0 P 2,3,4   1   1   0   1   1   0   1   1   0   1   1   1 ].
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.
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
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 nC k−1 and nCk 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, nC k−1 image blocks in Construction 1 is reduced to nC 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 Results
Form 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 tCr × n−tC k−1−t+r t -tuples with r 0s. We use the same sub-shadow S j,1 at the element “0” in the j th 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 j th column. Since every column of B n,k has k 1s, so the stacked result has tCr × n−tC kt+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 Blocks
In Construction 1, we have nC 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 nCk 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, nC 2−1 = n , happens to equal the number of participants. For this case, each participant pi can be assigned for recovering n−1 C 2−2 = 1 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 P 1 , P 2 , P 3 , and P 4 . 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 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 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 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 = tC k−1 / nC k−1 , and R 2 = tCk / nCk , 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 ) × nC k−1 ], and R 2 = [ k × t−1 Ck ]/[( t k ) × nCk ]. 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 Ck 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.
PPT Slide
Lager Image
Progressive recovery ratios, ktn, 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 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).
[ S ^ i,j ]=[ S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 ]=[ S 1,1 S 2,1 S 3,1 ϕ S 1,2 S 2,2 ϕ S 4,1 S 1,3 ϕ S 3,2 S 4,2 ϕ S 2,3 S 3,3 S 4,3 ].
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 .
{ S 1 = S ^ 1,1 S ^ 1,2 S ^ 1,3 S ^ 1,4 = S 1,1 S 2,1 S 3,1 , S 2 = S ^ 2,1 S ^ 2,2 S ^ 2,3 S ^ 2,4 = S 1,2 S 2,2 S 4,1 , S 3 = S ^ 3,1 S ^ 3,2 S ^ 3,3 S ^ 3,4 = S 1,3 S 3,2 S 4,2 , S 4 = S ^ 4,1 S ^ 4,2 S ^ 4,3 S ^ 4,4 = S 2,3 S 3,3 S 4,3 .
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.
PPT Slide
Lager Image
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.tw
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.
d9721004@ems.ndhu.edu.tw
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.
u9721020@ems.ndhu.edu.tw
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.
Corresponding Author mipsan@paran.com
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
Cimato S. , Yang C.-N. 2011 “Visual Cryptography and Secret Image Sharing,” CRC Press New York, USA 5 - 16
Naor M. , Shamir A. “Visual Cryptography,” Workshop Theory Appl. Cryptographic Techn. Perugia, Italy May 9–12,1994 1 - 12
Ito R. , Kuwakado H. , Tanaka H. 1999 “Image Size Invariant Visual Cryptography,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci. E82-A 2172 - 2177
Yang C.-N. 2004 “New Visual Secret Sharing Schemes Using Probabilistic Method,” Pattern Recogn. Lett. 25 (4) 481 - 494    DOI : 10.1016/j.patrec.2003.12.011
Cimato S. , de Prisco R. , de Santis A. 2006 “Probabilistic Visual Cryptography Schemes,” Comput. J. 49 (1) 97 - 107
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
Hou Y.C. 2013 “Block-Based Progressive Visual Secret Sharing,” Inf. Sci. 233 290 - 304    DOI : 10.1016/j.ins.2013.01.006
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
Bose M. , Mukerjee R. 2010 “Optimal (k, n) Visual Cryptographic Schemes for General k,” Des., Codes, Cryptography 55 (1) 19 - 35    DOI : 10.1007/s10623-009-9327-6
Shyu S.J. , Chen M.C. 2011 “Optimum Pixel Expansions for Threshold Visual Secret Sharing Schemes,” IEEE Trans. Inf. Forensics Security 6 (3) 960 - 969    DOI : 10.1109/TIFS.2011.2158096
Ateniese G. 2001 “Extended Capabilities for Visual Cryptography,” Theoretical Comput. Sci. 250 (1–2) 143 - 161    DOI : 10.1016/S0304-3975(99)00127-9
Liu F. , Wu C.K. , Lin X.J. 2010 “Some Extensions on Threshold Visual Cryptography Schemes,” Comput. J. 53 (1) 107 - 119    DOI : 10.1093/comjnl/bxn072