Visual Cryptograms of Random Grids for General Access Structures

414 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 Visual Cryptograms of Random Grids for General Access Structures Shyong Jian Shyu Abstract—This paper re-examines the problem of visual secret sharing for general access structures by using visual cryptograms of random grids (VCRG). Given a binary or color secret image shared by a set of n participants with a strong access structure, we devise two effective algorithms to produce a set of VCRG so that the members in each qualified set can reconstruct the secret image by superimposing their shares, while those in any forbidden set cannot. Our algorithms do not require any extra pixel expansion, which is indispensable and grows exponentially as n increases in conventional visual cryptographic schemes. The feasibility, light contrasts, flexibility, and limitations of our algorithms are explored from both theoretical and empirical points of view. Index Terms—General access structures, pixel expansion, random grids, visual cryptography, visual secret sharing. I. Introduction THE STUDY of visual cryptography, which deals withthe visual version of secret sharing, was first proposed by Naor and Shamir in Eurocrypt’94 [15]. They defined and designed threshold k-out-of-n visual cryptographic schemes ((k, n)-VCSs) to share a binary secret image P among a set P of n participants. Specifically, P is encoded into n transparencies, called shares, which are distributed to the n participants one by one, such that k (or more) participants can recognize P from the superimposed result of their shares, while less than k participants obtain no information (in an information-theoretic sense) about P. A visual cryptography scheme for general access structures (VCS-GAS) defined by Ateniese et al. [1] is an extension to the threshold (k, n)-VCS [3], [6], [9], [13]–[16], [19], [21]. It encodes P into n transparencies for the n participants in such a way that only the participants in qualified subsets of P can visually recover P by superimposing their shares, but those in forbidden subsets of P cannot acquire any information about P. A VCS-GAS is more general than a (k, n)-VCS and may be applied to different applications. The design of a VCS (with a threshold or general ac- cess structure) aims at constructing two n × m 0/1 basis Manuscript received December 20, 2011; revised May 22, 2012; accepted May 23, 2012. Date of publication June 14, 2012; date of current version March 7, 2013. This work was supported in part by the National Science Foundation, Taiwan, under Grant NSC 100-2221-E-130-006. This paper was recommended by Associate Editor M. Barni. The author is with the Department of Computer Science and Informa- tion Engineering, Ming Chuan University, Taoyuan 33348, Taiwan (e-mail: [email protected], [email protected]). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TCSVT.2012.2204940 matrices B0 and B1 to encode each white and black pixel, respectively, in P into m subpixels for each of the n shares [1]–[4], [9], [13]–[16], [19], [21]. The binary color of the jth subpixels in the ith share for pixel p is determined by Mp[i, j] for 1 ≤ j ≤ m, 1 ≤ i ≤ n, and p ∈ {0, 1} where Mp is the matrix obtained by permuting all columns in Bp randomly. For those participants who are able to recon- struct the secret, the number of white subpixels (namely h) in each reconstructed white pixel is more than that (l) in a black one (i.e., h > l), which causes the white pixels look relatively brighter than the black ones in the superimposed result by our visual ability so that P can be recognized. On the contrary, for those who cannot, they are the same (i.e., h = l), which prevents our visual perception from telling the white and black pixels apart so that P is safeguarded. Owing to the fact that there is a loss of contrast between the white and black pixels in the reconstructed result, a larger relative contrast, defined as α = (h− l)/m in [15], is preferred to ease the visual perception. Further, the number of subpixels (m) for encoding each secret pixel, referred to as the pixel expansion, is the smaller the better to reduce the share size. In brief, the pixel expansion and relative contrast are the most critical measurements to evaluate the effectiveness of a VCS [1]–[6], [8]–[11], [13]–[16], [19], [21]. The encryption process in visual cryptography does not demand sophisticated knowledge of cryptography and the decryption process relies on human visual ability without any computation. Such features not only differentiate the study of visual cryptography from that of traditional cryptography, but also attract much attention from researchers. Please refer to [1], [2], [5], [9], [13]–[15], [19], [21] and [23] to acquire a smaller or minimum pixel expansion for a VCS, [3], [4], [6], [9] and [10] for delivering a better or maximum contrast, and [6], [11], [16] and [21] for sharing a color image, just to name a few. More research subjects on visual cryptography can be found in [8] and [22]. To relieve the concern of pixel expansion, some models different from Naor and Shamir’s have been proposed recently, including probabilistic VCS [7], [24], multipixel encoding [12], or random grids [17], [18], [20]. Most of them address the design of threshold schemes for sharing binary images. Our interest in this paper is to resolve the problem of visual secret sharing for general access structures using the concept of visual cryptograms of random grids (VCRG) proposed in [17], [18], and [20]. The proposed VCRG-GAS algorithms require no extra pixel expansion and can be extended to cope 1051-8215/$31.00 c© 2012 IEEE SHYU: VISUAL CRYPTOGRAMS OF RANDOM GRIDS FOR GENERAL ACCESS STRUCTURES 415 with color images. Concerning the (n, n) case, m(n,n)VCRG = 1 [18], while m(n,n)VCS = 2n−1, which has been proved to be the minimum [15] and would be even larger when dealing with the sharing of a color image [6], [11], [16], [21]. The contribution of VCRG on reducing the pixel expansion is significant from either theoretical or practical perspectives. The remainder of this paper is organized as follows. Sec- tion II discusses some valuable previous works inspiring our research. Section III presents our algorithms for generating VCRG-GASs and formally demonstrates their correctness. The experimental results of our algorithms for binary and color images are illustrated and discussed in Section IV to validate the feasibility in a visual sense. Section V gives conclusions. II. Previous Studies Section II-A briefly introduces the definitions and termi- nologies for VCS-GAS. Section II-B makes a comparison between the conventional VCS in [15] and VCRG in [17], [18], and [20]. Section II-C examines the (n, n)-VCRG algorithms proposed in [18], based on which our VCRG-GAS algorithms can be established. A. Visual Cryptographic Scheme for General Access Structures Consider a secret image P shared by a set of n participants P = {1, 2, . . . , n}. We collect all subsets of P that are able to reveal P into a set �Qual and those that are not into �Forb where �Qual, �Forb⊆ 2P. We refer to each member of �Qual as a qualified set and that of �Forb as a forbidden set. The pair (�Qual, �Forb) is called the access structure of P with regard to P, in which �Qual ∩�Forb = φ since it makes no sense that some subset A of P exists such that A∈ �Qual and A∈ �Forb [1]. Let w(V ) denote the Hamming weight of a 1×m vector V . The following definition, slightly modified from the original version in [1], specifies the necessary conditions for B0 and B1 to be the basis matrices of a VCS-GAS. Definition 1: Let (�Qual, �Forb) be an access structure on a set of n participants. A VCS-GAS for (�Qual, �Forb) with relative difference α and set of thresholds {(X, tX)}X∈�Qual is realized using the two n × m basis matrices B0 and B1 if the following two conditions hold. 1) If X = {i1, i2, . . . , ip} ∈ �Qual (i.e., if X is a qualified set), then the or V of rows i1, i2, . . . , ip of B0 satisfies w(V ) ≤ tX−α×m, whereas for B1 it results that w(V ) ≥ tX. 2) If X = {i1, i2, . . . , ip} ∈ �Forb (i.e., if X is a forbidden set), then the two p×m matrices obtained by restricting B0 and B1 to rows i1, i2, . . . , ip are equal up to a column permutation. Ateniese et al. [1] also explored informative properties for (�Qual, �Forb) as follows. �0, consisting of all the minimal qualified sets, is defined as follows: �0 = {A ∈ �Qual|A′ /∈ �Qual for all A′ ⊆ A}. (1) TABLE I Basic Encoding Idea in Naor and Shamir’s Scheme A participant a ∈ P is essential if there exists a set X ⊆P such that X ∪ {a} ∈ �Qual but X /∈ �Qual. If any participant is not essential, we simply ignore his or her existence and remove him or her from P. On the other hand, ZM , consisting of the maximal forbidden sets of �Forb, is defined as follows: ZM = {B ⊆ �Forb|B ∪ {i} ⊆ �Qual for all i ∈ P\B}. (2) For A ⊆ 2P, we say that A is monotone increasing if for any B ∈ A and any C ⊆ P such that B ∩ C = φ, we have B ∪ C ∈ A. We say that A is monotone decreasing if for any B ∈ A and any C ⊆ B we have that B\C ∈ A. It is easy to see that any subset of a forbidden set is forbidden so that �Forb is monotone decreasing. In addition, any superset of a qualified set would be qualified. Thus, �Qual is monotone increasing. In the case where �Qual is monotone increasing, �Forb is monotone decreasing, and �Qual∪�Forb = 2P, we say that the access structure is strong. It is assumed that throughout this paper all participants are essential and all access structures discussed are strong. For instance, consider (�0′, Z′M) = ({{2, 3}, {2, 4}, {3, 4}, {1, 2, 3, 4}}, {{1, 2}, {1, 3}, {1, 4}}) with respect to P′ = {1, 2, 3, 4}. It should be rephrased as (�0, ZM) = ({{2, 3}, {2, 4}, {3, 4}}, {{2}, {3}, {4}}) with respect to P = {2, 3, 4}, because participant 1 is no more essential (where no set X ⊆ P′ exists such that X∪ {1} ∈ �Qual but X /∈ �Qual) so that he or she can be removed from P′ (�′0 and Z′M , too), and the qualification of {2, 3, 4} (after deleting 1 from {1, 2, 3, 4}) has been guaranteed by {2, 3} (or {2, 4}, {3, 4}) owing to the strong property so that it is deleted from �′0. B. Basic Models of Visual Cryptographic Scheme and Visual Cryptograms of Random Grids The encoding idea of Naor and Shamir’s (2, 2)-VCS [15] for each p∈P into corresponding s1∈S1 and s2∈S2 can be illustrated by Table I, where both s1 and s2 are blocks of two pixels. When all pixels in P are encoded in this way, S1 and S2 become two seemingly random pictures, whereas S = S1⊗S2 reveals P to our eyes where ⊗ is the superimposition operation. The pixel expansion is m(2, 2)VCS = 2. Let s = s1⊗s2 and s[p(0)] (s[p(1)]) be such block s whose corresponding p is � (�). The contrast of s, the relative difference between the reconstructed white (s[p(0)]) and black (s[p(1)]) blocks, is measured by α(2, 2)VCS = (h−l)/m(2, 2)VCS = (1−0)/2 = 1/2, where h (l) is the number of transparent pixels in s[p(0)] (s[p(1)]). In spite of a 50% loss of contrast in S, our visual perception is still able to recognize P. Regarding VCRG, we refer to a random grid R as a 2-D transparency consisting of all pixels with the same probability 416 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 TABLE II Encoding Pixel p ∈ P Into Random Pixels r1 ∈ R1 and r2 ∈ R2 of being transparent (0) [17], [18], [20]. Let each pixel r∈R be a random pixel with Prob(r = 1) = Prob(r = 0) = 1/2. The light transmission of r, i.e., the probability of r = 0, is 1/2 and consequently that of R is also 1/2, denoted as t(r) = Prob(r = 0) = 1/2 (or t(R) = 1/2). (3) Table II illustrates one of the three (2, 2)-VCRG encoding processes of p∈P into corresponding r1∈R1 and r2∈R2 in [17]. We see that there is no way to judge p = � or � from a single r1 or r2 individually. Let r = r1⊗r2 and r[p(0)] (r[p(1)]) denote such pixel r whose corresponding p is � (�). We obtain t(r[p(0)]) = 1/2, while t(r[p(1)]) = 0, as shown in Table II. Owing to such a difference, our visual system can distinguish r[p(0)] from r[p(1)]. As a result, both R1 and R2 are random grids with T (R1) = T (R2) = 1/2, whereas R = R1⊗R2 reveals P to our eyes due to T (R[P(0)]) = 1/2 and T (R[P(1)]) = 0 where R[P(0)] (R[P(1)]) denotes the area in R corresponding to the white (black) pixels in P. Note that there is no extra pixel expansion, i.e., m(2, 2)VCRG= 1. The light contrast, which measures the relative difference between the light transmissions of the transparent and opaque areas in the superimposed result R, was defined in [17] and [18] as follows: L(R) = T (R[P(0)]) − T (R[P(1)]) 1 + T (R[P(1)]) or l (r) = t(r[p(0)]) − t(r[p(1)]) 1 + t(r[p(1)]) (4) where r∈R. In this (2, 2)-VCRG, L(R1⊗R2) = ((1/2)−0)/(1+0) = 1/2. Note that when two light contrasts are with the same T (R[P(0)])−T (R[P(1)]), the one with a larger T (R[P (1)]) results in a smaller L(R) since more light in T (R[(1)]) degrades our visual perception relatively. Let us observe s = s1 ⊗ s2 and r = r1 ⊗ r2 in Tables I and II, respectively. From s[p(0)] (�� or ��) and s[p(1)] (��) in VCS, we can exactly recognize the corresponding p = � or �. However, from r[p(0)] (� or �) and s[p(1)] (�) in VCRG, we cannot do so accurately (since all r[p(1)]s are �s, but about half r[p(0)]s become �s, too). We say that the reconstruction ability of VCS is flawless in each single pixel level, but that of VCRG is not. More specifically, VCS maintains the recognition of both p = � and � from s[p(0)] and s[p(1)], respectively, at the expense of pixel expansion, whereas VCRG prevents any pixel from expanding at the cost of losing about 50% the reconstruction of p = � from r[p(0)]. To elaborate further, small false black regions are likely to appear in regions that should be white in VCRG. Fig. 1. Reconstruction abilities of VCS and VCRG. (a) P. (b) S1⊗S2. (c) R1⊗R2. Fig. 1 deliberately elucidates the reconstruction abilities of VCS and VCRG for dealing with small white regions. Fig. 1(a) is the secret image P consisting of eight kinds (10×10, 8×8, 6×6, 5×5, 4×4, 3×3, 2×2, 1×1 pixels) of ten white regions. Fig. 1(b) shows S1⊗S2 by (2, 2)-VCS, which reconstructs all white and black pixels in P flawlessly with mVCS = 2. Fig. 1(c) gives R1⊗R2 by (2, 2)-VCRG with mVCRG = 1, in which about 50%1 × 1 white regions are mis-reconstructed as black [see the bottom of Fig. 1(c)]. Nevertheless, VCRG works well as long as the white regions are not too small (say, no less than 3 × 3 pixels in this case) in P. Regarding the study on the lower bound of the size of a recognizable white region in the reconstructed result for VCRG, please refer to [20] and [24]. This paper thus excludes the consideration of those secret images whose critical information is characterized by very small white regions. C. (n, n)-Visual Cryptograms of Random Grids We refine the definition to a set of visual cryptograms of n random grids in [18] with respect to secret image P as follows. Definition 2: Given a binary image P, E = {R1, R2, . . . , Rn} is a set of n-out-of-n visual cryptograms of random grids, referred to as (n, n)-VCRG, with respect to P, if the following conditions are met. 1) Ri is a random grid with T (Ri[P(0)]) = T (Ri[P(1)]) for 1≤i≤n. 2) T (SD[P(0)]) = T (SD[P(1)]) where SD = Ri1 ⊗ Ri2 ⊗ . . .⊗Rid , which is the superimposed result of some set D = {Ri1 , Ri2 , . . . , Rid} of d distinct random grids in E , i.e., D ⊂ E , for 2 ≤ d ≤ n− 1 and 1 ≤ i1 < i2 < . . . < id ≤ n. 3) T (SE [P(0)]) > T (SE [P(1)]) where SE = R1⊗R2⊗. . .⊗ Rn. Note that the first two conditions are the security conditions and the third is the contrast condition. Given a random pixel r1 with t(r1) = 1/2 and another r2 produced by r2 = r1, r2 = random pixel() (returning 0 or 1 randomly), and r2 = r¯1, the light transmission of r1⊗r2 is t(r1⊗ r2)= ⎧⎨ ⎩ 1/2, if r2 = r1 1/4, if r2 and r1 are independent random pixels 0, if r2 = r¯1. (5) Based on the three simple operations, Shyu developed three algorithms [18] to generate a set of (n, n)-VCRG for P. We encapsulate them into Algorithm 1. There are three approaches (using the three operations in (5)) to fulfill determine−last(p, an−1) in Algorithm 1. We call the resultant ones Algorithms 1-a, 1-b, and 1-c, accordingly. SHYU: VISUAL CRYPTOGRAMS OF RANDOM GRIDS FOR GENERAL ACCESS STRUCTURES 417 Algorithm 1 Generating (n, n)-VCRG Input: a binary image P where each pixel p in P is either white (0) or black (1) and a set P of n participants sharing P Output: E = {R1, R2, . . . , Rn}, which comprises a set of (n, n)-VCRG of P where each pixel rk in Rk is either transparent (0) or opaque (1), for 1 ≤ k ≤ n VCRG(n, P, P) 1. for (each share k, 1≤k≤n−1) do 1.1 { for (each pixel rk∈Rk) do rk = random pixel() } // Generate Rk as a random grid with T (Rk) // = 1/ 2 for 1 ≤ k ≤ n − 1 2. for (each pixel p∈P) do 2.1 { let r1, r2, . . ., rn−1 be the corresponding pixels of p where rk ∈ Rk for 1 ≤ k ≤ n − 1 2.2 a1 = r1 2.3 for (each share k, 2 ≤ k ≤ n − 1) do { if (rk = 0) then ak = ak−1 else ak = a¯k−1 } 2.4 rn = determine−last(p, an−1) } 3. output(R1, R2, . . ., Rn) Table III lists their operations, light transmissions, and con- trasts where r = r1 ⊗ r2 ⊗ . . . ⊗ rn. To simply the following discussion, whenever Algorithm 1 is mentioned we address on Algorithm 1-a if not explicitly specified, because it possesses the highest light contrast among the three. The subsequent inferences obtained from analyzing Algorithm 1-a can also be applied to Algorithms 1-b and 1-c. The following theorem was proved in [18] where the contrast and security conditions were formally discussed. More discussion and security analysis on random grids can be found in [20]. Theorem 1: E = {R1, R2, . . . , Rn} produced by Algorithm 1-a is a set of (n, n)-VCRG for secret image P shared by a set P of n participants such that: 1) (T (SE [P(0)]), T (SE [P(1)])) = (1/2n−1, 0) where SE = R1⊗R2⊗ ... ⊗Rn; 2) (T (SD[P(0)]), T (SD[P(1)])) = (1/2d, 1/2d) where D = {Ri1 , Ri2 , . . . , Rid } ⊂ E , 1 ≤ d(= |D|) < n and SD = Ri1 ⊗ Ri2 ⊗ . . . ⊗ Rid . We compare the pixel expansions and contrasts of (3, 3)- VCS and (3, 3)-VCRG as follows. Example 1: Fig. 2 shows the results of implementations to Naor and Shamir’s (3, 3)-VCS using basis matrices B0 = ⎡ ⎣ 0 1 1 00 1 0 1 0 0 1 1 ⎤ ⎦ and B0 = ⎡ ⎣ 1 1 0 01 0 1 0 1 0 0 1 ⎤ ⎦ and Shyu’s (3, 3)-VCRG, in which (a) is secret image P, (b) and (c) show S1 and S1⊗S2, (d) presents S1⊗S2⊗S3 by Fig. 2. Implementation results of (3, 3)-VCS and (3, 3)-VCRG. (a) P. (b) S1. (c) S1⊗S2. (d) S1⊗S2⊗S3. (e) R1. (f) R1⊗R2. (g) R1⊗R2⊗R3. VCS, (e) and (f) depict R1 and R1⊗R2, respectively, and (g) exhibits R1⊗R2⊗R3 by VCRG. It is easily seen that (b), (c), (e) and (f) are seemingly random pictures, whereas both (d) and (g) reveal P to our eyes. The (3, 3) access structure is fulfilled by these two approaches. Note that S2, S3, S1⊗S3, and S2⊗S3 (R2, R3, R1⊗R3, and R2⊗R3) look seemingly random pictures just like Fig. 2(b) or (c) ((e) or (f)) so that we omitted them here. The pixel expansion in (3, 3)-VCS is m(3, 3)VCS = 4 (the minimum among all), while that in (3, 3)-VCRG is merely m (3, 3) VCRG= 1. Thus, the width and height of the shares in VCS are twice those in VCRG. In terms of the measurement of contrast (i.e., α = (h−l)/m), α(S1⊗S2⊗S3) = (1−0)/4 = 1/4, and α(R1⊗R2⊗R3) = (1/4−0)/1 = 1/4 (in which h = 1/4 (l = 0) because the average number of white pixels corresponding to p(0) (p(1)) is 1/4 (0) in r1⊗r2⊗r3). Meanwhile, in terms of light contrast, L(S1⊗S2⊗S3) = (1/4 − 0)/(1 + 0) = (1 − 0)/4 = 1/4 (where the light transmission corresponding to p(0) (p(1)) is 1/4 (0) in s1⊗s2⊗s3), and L(R1⊗R2⊗R3) = (1/23−1 − 0)/(1 + 0) = 1/4. That is, the relative contrasts between the reconstructed white and black pixels of (3, 3)- VCS and (3, 3)-VCRG are the same under these two measure- ments. In short, an (n, n)-VCRG takes m(n,n)VCRG = 1 (much less than the optimal m(n,n)VCS = 2n−1, which expands the resolution or size of the shares exponentially as n increases) and still achieves the same contrast as the optimal (n, n)-VCS as long as there does not exist a very small white region in the secret image. III. Proposed VCRGs for General Access Structures Consider a secret image P shared by a set P of n participants with a strong access structure (�Qual, �Forb). We denote the encoded shares as R1, R2,..., Rn. Let P(0) and P(1) be the areas of white and black pixels, respectively, in P where P(0)∪P(1) = P and P(0)∩P(1) = φ. Suppose that X = {i1, i2, . . . , ik} ⊆P. Let SX = Ri1 ⊗ Ri2 ⊗ . . . ⊗ Rik , i.e., the superimposed result of all shares held by the members in X, and let SX[P(p)] be the area in SX corresponding to P(p) where p∈{0, 1}. Based on Definitions 1 and 2, we give a formal definition to a set of visual cryptograms of random grids for general access structures (VCRG-GAS). Definition 3: R = {R1, R2, . . . , Rn} constitutes a set of VCRG-GAS of the shared secret image P for P with access 418 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 TABLE III determine−last(p, an−1), Light Transmissions and Contrast in Algorithms 1-a , 1-b, and 1-c determine−last(p, an−1) Light Transmission Light Algorithm Contrast p = 0 p = 1 t(r[p(0)]) t(r[p(1)]) l (r) 1-a an−1 a¯n−1 1/2n−1 0 1/2n−1 1-b an−1 random−pixel() 1/2n−1 1/2n 1/(2n+1) 1-c random−pixel() a¯n−1 1/2n 0 1/2n structure (�Qual, �Forb), if the following conditions are met. 1) Any qualified set Q∈ �Qual can recover P by stack- ing their transparencies. Formally, T (SQ[P(0)]) − T (SQ[P(1)]) = σQ, where 0 < σQ < 1. 2) Any forbidden set F∈ �Forb has no information about P in an information-theoretic sense. Formally, T (SF [P(0)]) = T (SF [P(1)]). The first is called the contrast condition to ensure the revealing ability of P for the participants in each qualified set, while the second is the security condition to safeguard P from those in any forbidden set. Both conditions measured by the light contrasts σQ (>0) or σF (=0) are conceptually equivalent to those of VCS-GAS (see Definition 1) measured by the contrasts αQ (>0) or αF (=0) where Q∈ �Qual and F∈ �Forb. Notice that we associate a specific σQ to each Q∈ �Qual since every Q may have its own light contrast (while all σF s are 0s). By exploiting a set of (n, n)-VCRG, we devise two algo- rithms based on �0 and ZM , respectively, to construct sets of VCRG-GASs in the following subsections. A. Constructing VCRG-GAS Based on �0 Consider �0 = {Q1,Q2, . . . ,Qγ} with regard to P, P, and (�Qual, �Forb) without any non-essential participant. Because all participants are essential, we have P = Q1 ∪ Q2 ∪ . . .∪Qγ (or denoted as P =∪1≤j≤γ Qj). (6) Our first construction of VCRG-GAS, which simply relies on �0, consists of three phrases. 1) For each Qj∈ �0, produce ρj (= |Qj|) constituent shares of P using (ρj, ρj)-VCRG where 1≤j≤γ . 2) Distribute these ρj constituent shares to the ρj partici- pants in Qj one by one for 1 ≤ j ≤ γ . 3) Merge all constituent shares belonging to each individual participant by superimposing those shares distributed to him or her altogether. In particular, for each Qj={ij1, ij2, . . . , ijρj } or {i1, i2, . . . , iρj } by omitting superscripts js to simplify the notations) ∈ �0 where 1 ≤ j ≤ γ , we call VCRG (ρj , P , Qj) to obtain ρj constituent shares, namely Ai1,j , Ai2,j, . . ., Aiρj ,j , (i.e., (Ai1,j , Ai2,j, . . ., Aiρj,j) = VCRG(ρj, P,Qj)), which are distributed to participants i1, i2, . . ., iρj , respectively. After that, partici- pant i superimposes all his or her constituent shares into share Ri for 1 ≤ i ≤ n, denoted by Ri = ⊗i∈Qj,1≤j≤γAi,j (7) where i ∈ Qj for 1 ≤ j ≤ γ . Algorithm 2 formally depicts the whole idea. Algorithm 2 Generating VCRG-GAS based on �0 Input: a set of n participants P = {1, 2, . . . , n}, a secret image P and a strong access structure (�Qual, �Forb) with �0 = {Q1,Q2, . . . ,Qγ} Output: a set of VCRG-GAS R = {R1, R2, . . . , Rn} with regard to P , P and (�Qual, �Forb) 1. for (each participant i, 1 ≤ i ≤ n) do Ri = 0 // 0 denotes a transparent transparency 2. for (each Qj = {i1, i2, . . . , iρj} ∈ �0, 1 ≤ j ≤ γ) do 2.1 { (Ai1,j , Ai2,j , . . ., Aiρj ,j) = VCRG(ρj , P, Qj) // ρj = |Qj| 2.2 for (each share k, 1 ≤ k ≤ ρj) do 2.2.1 { distribute Aik,j to participant ik 2.2.2 Rik = Rik ⊗ Aik,j } }// distribute Ri to participant i for 1 ≤ i ≤ n 3. output(R1, R2, . . ., Rn) A simple example is given to explain how Algorithm 2 works. Example 2: Consider the strong access structure (�Qual, �Forb) with �0 = {Q1, Q2, Q3, Q4} = {{1, 2}, {1, 4}, {2, 3}, {3, 4}} with regard to P and P = {1, 2, 3, 4}. We simply perform (A1,1, A2,1) = VCRG(2, P, {1, 2}), (A1,2, A4,2) = VCRG(2, P, {1, 4}), (A2,3, A3,3) = VCRG(2, P, {2, 3}), and (A3,4, A4,4) = VCRG(2, P, {3, 4}) for Q1, Q2, Q3 and Q4, respectively. In this case, each participant receives two constituent shares, i.e., (R1, R2, R3, R4) = (A1,1 ⊗A1,2, A2,1 ⊗ A2,3, A3,3 ⊗ A3,4, A4,2 ⊗ A4,4). To ease the understanding on the relationship between the participants and their constituent shares received, we introduce the Boolean inclusion matrix X, in which entry xi,j represents whether participant i belongs to Qj (or Qj includes participant i), that is xi,j = { 1, if i ∈ Qj 0, otherwise (8) for 1 ≤ i ≤ n and 1 ≤ j ≤ γ . Following the above example, its inclusion matrix X is as follows: Q1 Q2 Q3 Q4 {1, 2} {1, 4} {2, 3} {3, 4} 1 2 3 4 ⎡ ⎢⎢⎣ 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 ⎤ ⎥⎥⎦ . Hence, each xi,j = 1 corresponds to one constituent share Ai,j SHYU: VISUAL CRYPTOGRAMS OF RANDOM GRIDS FOR GENERAL ACCESS STRUCTURES 419 and Ri(= ⊗i∈Qj,1≤j≤γ Ai,j) is actually the superimposed result of those constituent shares whose xi,js = 1 in row i. To demonstrate the correctness of Algorithm 2, we begin with exploring the light transmissions of Ri[P(0)] and Ri[P(1)] for 1≤i≤n. If participant i∈Qj (i.e., xi,j = 1), he or she would receive a constituent share Ai,j produced by VCRG(ρj , P, Qj), which is a random grid with (T (Ai,j[P(0)]), T (Ai,j[P(1)])) = (1/2, 1/2) by Theorem 1. Since each call to VCRG(ρj , P, Qj) focuses on one particular Qj , all constituent shares Ai,js for 1 ≤ j ≤ γ held by participant i are independently generated. It is not hard to see that T (R1 ⊗ R2) = T (R1) × T (R2) if R1 and R2 are independently generated random grids [see also (5)]. Thus, Ri is also a random grid for 1 ≤ i ≤ n with (T (Ri[P(0)]), T (Ri[P(1)])) = (T (⊗i∈Qj,1≤j≤γAi,j[P(0)]), T (⊗i∈Qj,1≤j≤γAi,j[P(1)])) = ⎛ ⎝ ∏ i∈Qj,1≤j≤γ 1 2 , ∏ i∈Qj,1≤j≤γ 1 2 ⎞ ⎠ = (( 1 2 )∑γ j=1 xi,j , ( 1 2 )∑γ j=1 xi,j ) . (9) Consider a certain qualified subset Q ∈ �Qual. Let SQ = ⊗i∈Q,1≤i≤nRi (10) which denotes the superimposition of Ris owned by all participants in Q for 1 ≤ i ≤ n. We now show that SQ reveals P owing to T (SQ[P(0)]) > T (SQ[P(1)]). From (7) and (10), we obtain SQ = ⊗i∈Q,1≤i≤nRi = ⊗i∈Q,1≤i≤n(⊗i∈Qj,1≤i≤γAi,j) = ⊗i∈Q∩Qj,1≤i≤n,1≤j≤γAi,j (11) which indicates that SQ can be represented as the superim- position of all constituent shares Ai,js with i ∈ Q ∩ Qj for 1 ≤ i ≤ n and 1 ≤ j ≤ γ (or simply with xi,js = 1 for all rows is ∈ Q∩Qj and all columns js by observing X columnwise; in fact, if i ∈ Q but i /∈ Qj , then xi,j = 0) . We first focus on a given j (or column j in X). Let CQ∩Qjj be the superimposed result of the constituent shares Ai,js where i ∈ Q ∩ Qj (or xi,js = 1 for rows is∈Q∩Qj in one single column j of X). According to Theorem 1, we realize that if Q ∩ Qj = Qj , CQ∩Qjj reveals P; otherwise (Q ∩ Qj ⊂ Qj where |Q ∩ Qj| < |Qj|), it is merely a random grid with (T (CQ∩Qlj [P(0)]), T (CQ∩Qlj [P(1)])) = ⎧⎪⎪⎪⎨ ⎪⎪⎪⎩ ( 1 2ρj−1 , 0 ) , if Q ∩ Qj = Qj ( 1 2|Q∩Qj | , 1 2|Q∩Qj | ) , otherwise (12) in which ρj = |Qj|. When all js for 1 ≤ j ≤ γ (all columns in X) are considered, we have SQ = ⊗1≤j≤γCQ∩Qij (13) with (T (SQ[P(0)]), T (SQ[P(1)])) = (�1≤j≤γT (CQ∩Qjj [P(0)]), �1≤j≤γT (CQ∩Qjj [P(1)]))(14) for the reason that all CQ∩Qjj s are independent random grids. Since there is at least one Qk∈ �0 such that Qk ⊆ Q, thus Q∩Qk = Qk must exist and consequently T (CQ∩Qkk [P(0)])> T (CQ∩Qkk [P(1)])(= 0) holds. Other Qhs ∈ �0 may cause Q ∩ Qh �= Qh and T (CQ∩Qhh [P(0)])=T (CQ∩Qhh [P(1)]) [see (12)]. When we put all Qjs∈ �0 for 1 ≤ j ≤ γ together, �1≤j≤γT (CQ∩Qjj [P(0)])> �1≤j≤γT (CQ∩Qjj [P(1)])(=0) or sim- ply T (SQ[P(0)]) > T (SQ[P(0)]), which implies that SQ reveals P to our eyes for each Q ∈ �Qual. Following Example 2, we explain why SQ reveals P using Q = {1, 2, 3}(∈ �Qual). It is easy to see that SQ = S{1,2,3} = R1 ⊗ R2 ⊗ R3 = (A1,1 ⊗ A1,2) ⊗ (A2,1 ⊗ A2,3) ⊗ (A3,3 ⊗ A3,4) [the superimposition of Ai,js with xi,js = 1 for rows 1, 2, and 3 in X, see also (7)] = (A1,1 ⊗ A2,1) ⊗ (A1,2) ⊗ (A2,3 ⊗ A3,3) ⊗ A3,4 [reordering them columnwise, see (11)] = C Q∩Q1 1 ⊗CQ∩Q22 ⊗CQ∩Q33 ⊗CQ∩Q44 [see (13)] = C{1,2}1 ⊗C{1}2 ⊗ C {2,3} 3 ⊗ C{3}4 . Due to (T (CQ∩Qjj [P(0)]), T (CQ∩Qjj [P(1)]) = (1/2, 0), ((1/2, 1/2), (1/2, 0), (1/2, 1/2)) for j = 1(2, 3, 4, re- spectively) by (12), we have (T (SQ[P(0)]), T (SQ[P(1)]) = ((1/2) × (1/2) × (1/2) × (1/2), 0) = (1/16, 0), which indicates that SQ reveals P . The aforementioned reasoning with regard to each qualified set Q ∈ �Qual can be carried out to find the light transmissions of SF [P(0)] and SF [P(1)] for each forbidden set F ∈ �Forb. In fact SF = ⊗i∈F,1≤i≤nRi = ⊗i∈F,1≤i≤n(⊗i∈Qj,1≤j≤γAi,j) = ⊗i∈F∩Qj,1≤i≤n,1≤j≤γAi,j = ⊗1≤j≤γCFj (15) in which CFj = ⊗i∈F∩Qj,1≤i≤nAi,j (16) for a certain j (i.e., the superimposition of Ai,js with xi,js = 1 for rows is ∈ F ∩Qj in column j of X). Since it is impossible for F to cover all members in any Qj ∈ �0 (i.e., F ⊂ Qj where |F|< |Qj|) for 1 ≤ j ≤ γ , CFj is a random grid with (T (CFj [P(0)]), T (CFj [P(1)])) = ( 1 2|F∩Qj | , 1 2|F∩Qj | ) . (17) All CFj s for 1 ≤ j ≤ γ are independent random grids so that T (SF [P(0)]) and T (SF [P(1)]) are (T (SF [P(0)]), T (SF [P(1)])) = ( ∏ i∈F∩Qj , 1≤j≤γ T (CFj [P(0)]), ∏ i∈F∩Qj, 1≤j≤γ T (CFj [P(1)]) ) = ( ∏ i∈F∩Qj , 1≤j≤γ 1 2|F∩Qj | , ∏ i∈F∩Qj , 1≤j≤γ 1 2|F∩Qj | ) . (18) We use F = {2}(∈ �Forb) in Example 2 as an illustrative case. SF = S{2} = A2,1⊗A2,3 [the superimposition of Ai,js with xi,js = 1 for row 2 and columns 1, 3 in X, see also (15)] with 420 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 (T (A2,1[P(0)]), T (A2,1[P(1)])) = (1/2, 1/2) = (T (A2,3[P(0)]), T (A2,3[P(1)])) by (17). Hence, (T (SF [P(0)]), T (SF [P(1)])) = (1/4, 1/4) by (18), which implies that SF is only a random grid without any information of P. Theorem 2 summarizes the above discussions. Theorem 2: R = {R1, R2, . . . , Rn} produced by Algorithm 2 is a set of VCRG-GAS with regard to P , P and (�Qual, �Forb) with basis �0 = {Q1,Q2, . . . ,Qγ} such that: 1) (T (SQ[P(0)]), T (SQ[P(1)])) = (�1≤j≤γT (CQ∩Qjj [P(0)]), 0) for each Q∈�Qual where T (CQ∩Qjj [P(0)]) = ⎧⎪⎨ ⎪⎩ 1 2ρj−1 , if Q ∩ Qj = Qj 1 2|Q∩Qj | , otherwise; 2) (T (SF [P(0)]), T (SF [P(1)])) = ⎛ ⎝ ∏ i∈F∩Qj, 1≤j≤γ 1 2|F∩Qj | , ∏ i∈F∩Qj, 1≤j≤γ 1 2|F∩Qj | ⎞ ⎠ for anyF ∈ �Forb. B. Constructing VCRG-GAS Based on ZM Let ZM = {F1, F2, . . . ,Fλ} where Ft ⊆ P for 1 ≤ t ≤ λ. Our second construction of VCRG-GAS, which depends on ZM , comprises three phrases: 1) Set = {1, 2, . . . , λ} where λ = |ZM | and generate λ universal sharesU1, U2, . . . , Uλ by calling VCRG(λ, P, ), i.e., (U1, U2, . . ., Uλ)=VCRG(λ, P, ). 2) Share Ut is distributed to those who are not in Ft , i.e., participant i receives Ut if i /∈ Ft for 1 ≤ i ≤ n and 1 ≤ t ≤ λ. 3) Participant i superimposes all shares distributed to him or her, i.e., Ri = ⊗i/∈Ft ,1≤t≤λUt for 1 ≤ i ≤ n. Note that in Algorithm 2 we dispatch ρj (=|Qj|) constituent shares of P corresponding to Qj∈ �0 to the members in Qj one by one (concerning their qualification), while in Algorithm 3 we give universal share Ut of P corresponding to to those who are not in Ft for 1 ≤ t ≤ λ. This idea is intuitive. Those who are in Ft should not hold Ut (concerning their forbiddance) so that we only give Ut to the others not in Ft (who might have chances to be qualified when cooperated with some other participants). Each participant i may receive more than one universal share because i may be not in more than one Ft . Similarly, each universal share may be distributed to more than one participant. The whole process is formally illustrated in Algorithm 3. To ease the discussion, we may represent the relationship whether participant i receives universal share Ut as a binary variable yi,t defined by yi,t = { 1, if i /∈ Ft 0, otherwise (19) for 1 ≤ i ≤ n and 1 ≤ t ≤ λ. As a mater of fact, yi,t = 1 indicates that participant i does not belong to Ft (or Ft excludes participant i). Then, we obtain a Boolean exclusion matrix Y, based on which the dealer distributes Ut Algorithm 3 Generating VCRG-GAS from ZM Input: a secret image P, a set of n participants P = {1, 2, ..., n} and a strong access structure (�Qual, �Forb) with ZM = {F1,F2, . . . ,Fλ} Output: a set of VCRG-GAS R = {R1, R2, . . . , Rn} with regard to P , P and (�Qual, �Forb) 1. = {1, 2, ..., λ} where λ = |ZM | 2. (U1, U2, . . . , Uλ) = VCRG(λ, P, ) // {U1, U2, . . . , Uλ} is a set of (λ, λ)-VCRG of P 3. for (each participant i, 1≤i≤n ) do 3.1 { Ri = 0 // Initialize Ri as a transparent share //(denoted by 0) 3.2 for (each Ft∈ZM , 1≤t≤λ) do 3.2.1 { if (i /∈ Ft) then Ri = Ri ⊗ Ut // Participant i gets share Ut (due to i/∈Ft) // and superimposes it onto Ri } } // distribute Ri to participant i for 1 ≤ i ≤ n 4. output(R1, R2, . . . , Rn) to participant i only when Y [i, t] (= yi,t) = 1. In the following, we show an example. Example 3: Consider the same access structure as in Example 2, whose ZM = {{1, 3}, {2, 4}}. By Algorithm 3, λ = 2, = {1, 2} and (U1, U2) = VCRG(2, P, ) in which U1 and U2 are dispatched to those who are not in F1 and F2, respectively. The exclusion matrix Y is as follows. F1 F2 {1, 3} {2, 4} 1 2 3 4 ⎡ ⎢⎢⎣ 0 1 1 0 0 1 1 0 ⎤ ⎥⎥⎦ . Thus, participants 1, 2, 3, and 4 hold U2, U1, U2, and U1, respectively. It is easy to verify that the members of any Ft∈ZM or F⊆Ft cannot reconstruct P, while those of each Qj∈ �0 (= {{1, 2}, {1, 4}, {2, 3}, {3, 4}}) or Q⊇Qj can. Theorem 3 proves the correctness of Algorithm 3. Theorem 3: R = {R1, R2, . . . , Rn} produced by Algorithm 3 is a set of VCRG-GAS with regard to P , P and (�Qual, �Forb) with ZM = {F1,F2, . . . ,Fλ} such that: 1) (T (SQ[P(0)]), T (SQ[P(1)])) = ( 1 2λ−1 , 0) for each Q ∈ �Qual; 2) (T (SF [P(0)]), T (SF [P(1)])) = ( 1 2|EF | , 1 2|EF | ) for each F ∈ �Forb where EF = {t|i /∈ Ft for i ∈ F where 1 ≤ t ≤ λ}. Proof: In Step 2, we produce U = {U1, U2, . . . , Uλ}, which is a set of (λ, λ)-VCRG of P. Those who own U1, U2, . . . , Uλ can reconstruct P by superimposing their shares, while those who hold less than all these λ universal shares cannot. We claim that the members in each Q ∈ �Qual obtain all these λ shares, while those in any F ∈ �Forb do not. Consider first F∈ �Forb. There must exist some Ft∈ZM such that F ⊆Ft . By Step 3, all members in Ft do not have share SHYU: VISUAL CRYPTOGRAMS OF RANDOM GRIDS FOR GENERAL ACCESS STRUCTURES 421 Ut , neither for those in F. In other words, it is impossible for the members in F to hold all λ universal shares to reconstruct P. Let EF be the set of the indices of those maximal forbidden sets that some member in F does not belong to, i.e., EF = {t |i/∈Ft for i ∈ F where 1 ≤ t ≤ λ}(⊂ ). Actually, the mem- bers in F could only receive those universal shares indexed by the indices in EF . Thus, (T (SF [P(0)]), T (SF [P(1)])) = ( 12|EF | , 1 2|EF | ) by Theorem 1. Assume that our claim for each Q∈ �Qual obtaining all λ universal shares is incorrect. Then, there must exist at least one universal share, say Uk, which is not given to any one in Q. If this happens, according to our algorithm the members in Q must all belong to Fk (otherwise, at least one of them receives Uk). This implies Q ⊆ Fk and consequently Q∈ �Forb, which results in a contradiction because it is impossible for Q∈ �Qual and Q∈ �Forb. We thus conclude that the members in Q obtain all these λ universal shares so that they are able to reconstruct P with (T (SQ[P(0)]), T (SQ[P(1)])) = ( 12λ−1 , 0). � Following Example 3, consider Q = {1, 2, 3} and F = {3}. SQ = U1⊗U2 with (T (SQ[P(0)]), T (SQ[P(1)])) = (1/2λ−1, 0) = (1/22−1, 0) = (1/2, 0), which implies that SQ reveals P, while SF = U2 with EF = {2} (since 3/∈F2) and (T (SF [P(0)]), T (SF [P(1)])) = (1/2|EF |, 1/2|EF |) = (1/21, 1/21) = (1/2, 1/2), which deduces that SF safeguards P. Other Qs’ qualification and Fs’ forbiddance on the reconstruction of P can be vali- dated as well. These two algorithms utilize the shares of (ρj , ρj)-VCRG or (λ, λ)-VCRG, which takes no extra pixel expansion, as the core to further construct a set of VCS-GAS with a pixel expansion of 1. On condition that conventional (ρj , ρj)- VCS or (λ, λ)-VCS is adopted, the pixel expansion would be maxQj∈�0{2ρj−1} or 2λ−1, respectively, which grows ex- ponentially as ρj (=|Qj|) or λ (=|ZM |). The contribution of our algorithms in reducing the pixel expansion is novel and significant in both theoretical and practical concerns. Furthermore, the aforementioned reasoning and inferences of Algorithms 2 and 3 based on Algorithm 1-a can be easily applied to obtain similar outcomes based on Algo- rithms 1-b and 1-c. It is not hard to realize that the light contrasts by Algorithms 2 and 3 based on Algorithm 1-a would still be better than those based on Algorithms 1-b and 1-c. IV. Experimental Results and Discussions Even though the correctness of the two proposed algorithms in producing sets of VCS-GASs with regard to binary secret image P, P and (�Qual, �Forb) has been proven in the previous section, we would still like to know: 1) whether our ideas are feasible according to our visual perception after implementations; 2) what are the light contrasts in the superimposed results for these two algorithms; 3) what are the light transmissions in the encoded shares for these two algorithms; 4) whether our approaches can be enhanced to share a color secret image; TABLE IV Results of A2 and A3 for ((�0, ZM ) = {{1, 2}, {1, 4}, {2, 3}, {3, 4}}, {{1, 3}, {2, 4}}) especially when different access structures are given. There- fore, we deliberately designed four experiments with different access structures specified by (�Qual, �Forb) with (�0, ZM) for P = {1, 2, 3, 4} to answer the above questions. The programs implementing Algorithms 2 and 3 (referred to as A2 and A3 for short, respectively) were coded in Borland C++ Builder. Experiment 1: Consider the access structure in Example 2 where �0 = {{1, 2}, {1, 4}, {2, 3}, {3, 4}} and ZM = {{1, 3}, {2, 4}}. Table IV illustrates the implementation results using A2 and A3, respectively, including the shared secret image P, four encoded shares R1–R4, all groups of superimposed results and their light transmissions corresponding to P(0) and P(1). It is seen from Table IV that the superimposed results of all forbidden sets are random grids (where T (SF [P(0)]) = T (SF [P(1)]) for F∈ �Forb), from which no information about P can be obtained, while those of all qualified sets reveal P to our eyes (due to T (SQ[P(0)]) > T (SQ[P(1)]) for Q∈ �Qual). The empirical light transmissions corresponding to P(0) and P(1) match with the values derived from Theorems 2 and 3 (note that their differences are tiny and insignificant). Thus, we simply list the values from Theorems 2 and 3 in Table IV. These results provide effective visual evidences to the feasibility and applicability of our algorithms. The light contrasts in the reconstructed results of qualified sets by A3 are all 1/2, which is better than those (1/8 or 1/16) of A2 in this case. In essence, A3 performs (λ, λ)-VCRG to produce λ universal shares, which result in a light contrast of 1/2λ−1 for all qualified sets where λ = |ZM |. Apparently, when |ZM |is small (e.g., 2 here), A3 tends to achieve a better light contrast. On the other hand, A2 performs (ρj , ρj)-VCRG for each Qj∈ �0 separately and distributes the ρj (=|Qj|) constituent shares to those in Qi who superimpose all the shares received. Thus, the light contrast with regard to Qj is 422 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 TABLE V Results of A2 and A3 for (�0, ZM ) = ({{1, 3}, {2, 4}}, {{1, 2}, {1, 4}, {2, 3}, {3, 4}}) no greater than 1/2ρj−1 and may be lower if some participant in Qj is also a member of Qj′ where j �= j′ and Qj,Qj′ ∈ �0 (since more independent constituent shares may be included). For instance, consider {1, 2} ∈ �0. Due to 1 ∈ Q1 = {1, 2},Q2 = {1, 4} and 2 ∈ Q1 = {1, 2}, Q3={2, 3}, we have R1 = A1,1⊗A1,2, R2 = A2,1⊗A2,3 [see the inclusion matrix X in Example 2], and S{1,2} = R1⊗R2 = A1,1⊗A1,2⊗A2,1⊗A2,3 = (A1,1⊗A2,1)⊗A1,2⊗A2,3 (in which the last two constituent shares (separately generated) degrade the light contrast of A1,1⊗A2,1) with L(S{1,2}) = 1/8. Furthermore, the light contrast with regard to Q⊃Qj may be even lower (again, owing to more independent constituent shares), say {1, 2, 3}⊃{1, 2} where L(S{1,2,3}) = 1/16 < 1/8 = L(S{1,2}) (see Example 2 for details). Experiment 2: Consider the access structure with �0 = {{1, 3}, {2, 4}} and ZM = {{1, 2}, {1, 4}, {2, 3}, {3, 4}}. Notice that the roles of �0 and ZM in Experiment 1 are switched here. Table V summarizes the experimental results. As expected, SQ reveals P, while SF cannot for Q∈ �Qual and F∈ �Forb in Table V. The empirical light transmissions corresponding to P(0) and P(1) also match with those from Theorems 2 and 3. The light contrasts of qualified sets by A2 (1/2 or 1/4) are better than those by A3 (1/2|ZM |−1 = 1/24−1 = 1/8) in this case. It is interesting to see that the members in �0 constitute a partition of P. This indicates that the light contrast of Qj∈ �0 produced by A2 is exactly 1/2|Qj |−1 (e.g., 1/2 for both Q1 = {1, 3} and Q2 = {2, 4} here) and each participant holds only one constituent share. Similarly to above, the light contrast of Q (⊃Qj) may be lower than that of Qj by A2 (since more independent constituent shares may be included, say L(S{1,2,3}) = 1/4 < 1/2 = L(S{1,2})), while they are the same by A3 (i.e., 1/8). TABLE VI Results of A2 and A3 for (�0, ZM ) = ({{1, 2}, {1, 4}, {3, 4}}, {{1, 3}, {2, 3}, {2, 4}}) Experiment 3: Consider the case of (�0, ZM) = ({{1, 2}, {1, 4}, {3, 4}}, {{1, 3}, {2, 3}, {2, 4}}). Table VI lists the experimental results. In this experiment, the four encoded shares, by either A2 or A3, are not with the same light transmission (i.e., T (R1) = T (R4) = 1/4 �= 1/2 = T (R2) = T (R3)), whereas those in the previous two are. Nevertheless, the feasibility still holds: SQ reveals P for Q∈ �Qual, while SF cannot for F∈ �Forb. The light contrasts of qualified sets by A2 are all 1/4, whereas those by A3 may be 1/4 or 1/8. Experiment 4: Consider the access structure with �0 = {{1, 3}, {2, 3}, {3, 4}} and ZM = {{3}, {1, 2, 4}} and the color secret image C shown in Table VII. By exploiting the color (n, n)-VCRG in [17] and [18] where the skills includ- ing halftoning, color decomposition (concerning subtractive primitive colors: cyan, magenta, yellow), monographic c-, m-, y-VCRGs encoding, color mixing c, m, y shares, and so on are utilized, we could extend A2 and A3 to generate color VCRG- GAS to cope with the sharing of a color image. Table VII lists the results of our implementations using the refined A2 and A3 for C (along with its halftone version C′ by error diffusion). As seen from Table VII, our color VCRG-GASs produced by the refined A2 and A3 are manifestly feasible by our visual ability. From the superimposed result for each qualified set, our eyes are able to tell the differences among the colors corresponding to different colors in C (strictly speaking C′), whereas from that for any forbidden set we cannot. The correctness of our color VCRG-GAS can be validated by incorporating the statements in the proofs to Theorems 2 and 3 (which hold still for each of the three monographic c, m, y shares), and those in [17] and [18] (where the effect of color mixing and the superimposed outcomes of color shares were SHYU: VISUAL CRYPTOGRAMS OF RANDOM GRIDS FOR GENERAL ACCESS STRUCTURES 423 TABLE VII Results of Refined A2 and A3 for (�0, ZM ) = ({{1, 3}, {2, 3}, {3, 4}}, {{3}, {1, 2, 4}}) thoroughly explained). The color light contrasts obtained by A3 are better than those by A2 in this case since |ZM |(=2) is quite small (whereas “participant 3 belongs to all three subsets in �0” results in the superimposition of three independent constituent shares for R3 and consequently degrades the light contrasts of those qualified sets containing R3 by A2). From the above experimental results, we realize the follow- ing. 1) The feasibility and applicability of these two algorithms are sound in the visual sense. 2) “Which, A2 or A3, achieves the better light contrasts for the qualified sets” depends on the access structure given (i.e., some favor A2, while others prefer A3); nevertheless, for any access structure, A2 may deliver different light contrasts for different qualified sets, while A3 produces a constant one. 3) The light transmissions of the encoded shares by either A2 or A3 may be different; and different participants in A3 may receive the same share, while those in A2 obtain distinct ones. 4) The extensions of A2 and A3 are capable of dealing with the sharing of a color image. To obtain a higher contrast, we could choose A3 when the number of the members in ZM is quite small, whereas we consider A2 when the members in �0 constitute a partition of P, or when the participants belonging to more than one member of �0 are rather few. These features improve the flexibility of VCS-GAS. The dealer could choose his or her favorite algorithm according to the practical needs. V. Conclusion Given a secret image P shared by a set P of n participants in a strong access structure (�Qual, �Forb) with �0 and ZM , we in- troduced two novel and effective VCRG-GAS algorithms to re- solve the problem of visual secret sharing for binary and color images in this paper. One was based on �0 to produce a set of (|Qj|, |Qj|)-VCRG for each Qj∈ �0 and distribute the con- stituent shares according to the inclusion matrix, and the other focused on ZM by generating a set of (|ZM |, |ZM |)-VCRG and dispatching the universal shares according to the exclu- sion matrix. Their feasibility and applicability were formally proved and empirically verified. The most important contribu- tion of our approaches was that no extra pixel expansion was required. Provided that the (n, n)-VCS would be adopted, the pixel expansion became maxQj∈�0{2|Qj |−1} or 2|ZM |−1. When maxQj∈�0{|Qj|} or |ZM | goes larger, the exponentially grown share size in VCS would be less attractive than the one with the same size as the secret in VCRG. For a given access structure, the light contrasts of a par- ticular qualified set derived from the two algorithms may be different. More specifically, the �0-based algorithm may de- liver different light contrasts for different qualified sets, while the ZM-based algorithm gives a constant one. In addition, all shares are different in the former, while some may be the same in the latter. The light transmissions of the shares may also be different. These flexible features enrich the applications of VCS-GAS. The dealer could depend on the practical concerns to choose the one that he or she prefers most. The common core of our proposed algorithm is an (n, n)- VCRG and we adopt Algorithm 1-a to be the role throughout the paper. Undoubtedly, Algorithms 1-b, 1-c, or even other VCSs with a pixel expansion of 1 (by probabilistic, multipixel encoding, and so on) can also be chosen as the core. The analyses and experiments derived from Algorithm 1-a are pertinent and applicable to other alternatives. The approach of VCRG relieves the concern of pixel expansion, yet its reconstruction ability is not flawless as VCS (which flawlessly reconstructs each white and each black pixels without any misperception from the visual sense) due to the reason that a quite small white region might be misreconstructed as black. Therefore, it is not appropriate to deal with those secret images whose critical information is characterized by very small white regions. How to improve such a drawback is surely a challenging research topic. In ad- dition, whether there exist other algorithms that could improve or maximize the light contrast in the reconstructed result is another topic worthy of further study. Furthermore, applying the VCRG approach to other subjects in [8] and [22] is of great significance in visual cryptography. References [1] G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson, “Visual cryptography for general access structures,” Inform. Comput., vol. 129, no. 2, pp. 86–106, 1996. [2] C. Blundo, S. Cimato, and A. De Santis, “Visual cryptography schemes with optimal pixel expansion,” Theor. Comput. Sci., vol. 369, nos. 1–3, pp. 169–182, 2006. [3] C. Blundo, P. D’Arco, A. De Santis, and D. R. Stinson, “Contrast optimal threshold visual cryptography schemes,” SIAM J. Discrete Math., vol. 16, no. 2, pp. 224–261, 2003. [4] C. Blundo, A. De Santis, and D. R. Stinson, “On the contrast in visual cryptography schemes,” J. Cryptology, vol. 12, no. 4, pp. 261–289, 1999. [5] M. Bose and R. Mukerjee, “Optimal (k, n) visual cryptographic schemes for general k,” Designs Codes Cryptography, vol. 55, no. 1, pp. 19–35, 2010. 424 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 23, NO. 3, MARCH 2013 [6] S. Cimato, R. De Prisco, and A. De Santis, “Optimal colored threshold visual cryptography schemes,” Designs Codes Cryptography, vol. 35, no. 3, pp. 311–335, Jun. 2005. [7] S. Cimato, R. De Prisco, and A. De Santis, “Probabilistic visual cryptography schemes,” Comput. J., vol. 49, no. 1, pp. 97–107, 2006. [8] S. Cimato and C.-N. Yang, Visual Cryptography and Secret Image Sharing. Boca Raton, FL: CRC Press/Taylor and Francis, 2011. [9] S. Droste, “New results on visual cryptography,” in Proc. Advances Cryptography (CRYPTO), LNCS 1109. 1996, pp. 401–415. [10] P. A. Eisen and D. R. Stinson, “Threshold visual cryptography schemes with specified whiteness levels of reconstructed pixels,” Designs Codes Cryptography, vol. 25, no. 1, pp. 15–61, 2002. [11] Y.-C. Hou, “Visual cryptography for color images,” Pattern Recognit., vol. 36, no. 7, pp. 1619–1629, 2003. [12] Y.-C. Hou and S.-F. Tu, “A visual cryptographic technique for chromatic images using multi-pixel encoding method,” J. Res. Practice Information Technol., vol. 37, no. 2, pp. 179–191, 2005. [13] T. Katoh and H. Imai, “An extended construction method for visual secret sharing schemes,” Electron. Commun. Japan Part III Fundam. Electron. Sci., vol. 81, no. 7, pp. 55–63, 1998. [14] F. Liu, C. Wu, and X. Lin, “Step construction of visual cryptography schemes,” IEEE Trans. Information Forensics Security, vol. 5, no. 1, pp. 27–38, Mar. 2010. [15] M. Naor and A. Shamir, “Visual cryptography,” in Proc. Advances Cryptology (Eurpocrypt), LNCS 950. 1995, pp. 1–12. [16] S. J. Shyu, “Efficient visual secret sharing scheme for color images,” Pattern Recognit., vol. 39, no. 5, pp. 866–880, May 2006. [17] S. J. Shyu, “Image encryption by random grids,” Pattern Recognit., vol. 40, no. 3, pp. 1014–1031, 2007. [18] S. J. Shyu, “Image encryption by multiple random grids,” Pattern Recognit., vol. 42, no. 7, pp. 1582–1596, Jul. 2009. [19] S. J. Shyu and M. C. Chen, “Optimum pixel expansions for threshold visual secret sharing schemes,” IEEE Trans. Information Forensics Security, vol. 6, no. 3, pp. 960–969, Sep. 2011. [20] S. J. Shyu and K. Chen, “Visual multiple secrets sharing by circle random grids,” SIAM J. Imaging Sci., vol. 3, no. 4, pp. 926–953, 2010. [21] E. R. Verheul and H. C. A. Van Tilborg, “Constructions and properties of k out of n visual secret sharing schemes,” Designs Codes Cryptography, vol. 11, no. 2, pp. 179–196, 1997. [22] J. Weir and W. Yan, “A comprehensive study of visual cryptography,” in Transaction on Data Hiding and Multimedia Security V (Lecture Notes in Computer Science, vol. 6010), Y. Q. Shi, Ed. Berlin/Heidelberg, Germany: Springer, 2010 pp. 70–105. [23] C.-N. Yang and T.-S. Chen, “Size-adjustable visual secret sharing schemes,” IEICE Trans. Fundam., vol. E88-A, no. 9, pp. 2471–2474, 2005. [24] C.-N. Yang, “New visual secret sharing schemes using probabilistic method,” Pattern Recognit. Lett., vol. 25, no. 4, pp. 481–494, 2004. Shyong Jian Shyu received the B.S. degree in computer engineering from National Chiao Tung University, Hsinchu, Taiwan, in 1985, and the M.S. degree in computer and decision sciences and the Ph.D. degree in computer science from National Tsing Hua University, Hsinchu, in 1987 and 1991, respectively. In 1994, he joined the Faculty of Ming Chuan University, Taoyuan, Taiwan, where he is currently a Professor with the Department of Computer Science and Information Engineering. He was a Researcher with the Academia Sinica Computer Center, Taipei, from 1993 to 1994. He was with the National Defense Management College, Taipei, serving in the army from 1991 to 1993. His current research interests include design and analysis of algorithms, visual cryptography, computational biology, and computational intelligence. /ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 600 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages false /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description > /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ > /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams > setpagedevice