Shyong Jian Shyu
Ming Chuan University, Taiwan
Visual cryptography proposed by Naor and Shamir [7] discloses the possibility for using human visual ability to perform the decryption process. Specifically, one secret image is encoded into two shares that are seemingly random pictures. By xeroxing them onto transparencies, the dealer distributes the two random transparencies to two participants (one share for each participant). Each participant cannot tell the secret from his own transparency, but when the two participants superimpose their transparencies pixel by pixel, they recognize the secret from the superimposed result by their visual system. Neither computational devices nor cryptographic knowledge is required for the decryption process.
With such an interesting characteristic that the decryption process is by the human visual system only, instead of any computational device, visual cryptography attracts much attention from researchers. In particular, it is much useful in situations where computing devices are not available or not possible to use. Naor and Shamir [7] first presented k out of n visual secret-sharing schemes, which ensure that the secret is concealed from groups of less than k participants, while it can be seen by groups of at least k participants when they stack their shares altogether. Since this pioneer research, many theoretical results on the construction or contrast (the relative difference between the reconstructed white and black pixels in the superimposed image) of visual secret sharing schemes for binary images have been proposed in the literature [1, 10, 11, 2]. Some studies [4, 5, 9] focused on the practical realization of visual cryptographic schemes for gray-level or color images. So far, the above-mentioned results concern sharing “one” secret in a visual sense.
Wu and Chen [12] might be the first researchers to consider the problem of sharing two secret images in two shares in visual cryptography. They concealed two secret binary images into two seemingly random shares, namely S1 and S2, such that the first secret can be seen by stacking the two shares, denoted by S1 ⊗ S2, and the second secret can be obtained by Sθ1⊗S2
Wu and Chang [13] refined the idea of Wu and Chen [12] by consciously designing the encoded shares to be circles so that the restrictions to the rotating angles (θ = 90°, 180°, or 270°) can be removed. Let the two encoded circle shares in their approach be denoted as A and B. The first secret is revealed by A ⊗ B, while the second secret is obtained by A−θ ⊗ B where θ may be any angle within (0°, 360°) and A−θ is the result of rotating A θ clockwise. Both of the studies successfully share two secrets in two shares in a visual sense.
Shyu et al. [8] devised an elegant algorithm to achieve the sharing of multiple sercte images using two circle shares. It is the first true approach that shares any general number of multiple secrets in two shares. Consider x secret images. Consider a set of x ≥ 2 secret images. Their scheme produces two circle shares A and B such that none of them individually leaks any secret and the x secrets can be obtained one by one A ⊗ B, Aθ ⊗ B, A2θ ⊗ B,…, A(x−1)θ⊗ B where A(i−1)θ is the result of rotating A(i−1)θ counterclockwise for 1 ≤ i ≤ x for θ = 360θ /x and A0° − A This is the first true result of sharing multiple secrets in visual cryptography for any× ≥ 2 secrets in two shares. Their pixel expansion is 2x, which is the best result so far in the model that each pixel would be expanded.
Based on a different set of encoding patterns, Feng et al. [3] developed another scheme to achieve the same goal using two cylinder shares. The pixel expansion needed is 3x.
In this chapter, we introduce these interesting algorithms. The rest of the paper is organized as follows. In Section 3.2, we briefly review the visual one-secret sharing scheme in two shares proposed by Naor and Shamir [7]. The visual two-secret sharing scheme by Wu and Chen [12] and Wu and Chang [13] are discussed in Sections 3.3.1 and 3.3.2, respectively. The schemes for visual multisecret are examined in Section 3.4 in which the experimental results and discussions are also presented. Section 3.5 gives some concluding remarks.
The basic idea of Naor and Shamir’s encoding scheme [7] for sharing a single pixel, say p, in a binary image P into two shares s1 and s2 is illustrated in Table 3.1. If p is white, the dealer randomly chooses one of the first two rows of Table 3.1 to encode s1 and s2. If p is black, the dealer randomly chooses one of the last two rows in Table 3.1 to encode s1 and s2. The possibilities of the two encoding cases are equally likely to occur, independently of whether the original pixel is black or white. Thus, neither s1 nor s2 exposes any clue about the binary color of p. When these two shares are stacked together, i.e., s1 ⊗ s2, two black subpixels appear if p is black, while one black subpixel and one white subpixel appear if p is white as indicated in the rightmost column in Table 3.1. Based upon the contrast between these two kinds of reconstructed pixels, our visual system can tell whether p is black or white by observing s1 ⊗ s2
Note that s1 (or s2) in Table 3.1 is not a single pixel, but two subpixels. We call s1 (or s2) an extended block and the pair (s1, s2) the pair of two extended blocks with respect to p. The number of the subpixels in each of the two extended blocks (s1, s2) for encoding p is referred to as the pixel expansion. In Table 3.1, the pixel expansion is 2. In realistic implementations, it may be chosen as 4 (= 2 × 2) in order to retain the aspect ratio of the original secret image. Since there are six possible patterns for a 2 × 2 extended block, all pairs of two extended blocks (s1, s2)’s for encoding a specific binary pixel p (visual one-secret sharing) are summarized in Table 3.2.
When p is white (black), the dealer randomly chooses one of the first (last) six rows of Table 3.2 to encode p into s1 and s2. It is seen from the last column of Table 3.2 that the reconstructed pixel r = s1 ⊗ s2 may contain two white and two black subpixels if p is white, or all four black subpixels when p is black. When all pixels in p are encoded in this way, where each p’s random choice for encoding alternatives is independent, the encoded shares S1 (containing all s1’s) and S2 (containing all s2’s) are indeed random pictures, respectively. When S1 and S2 are superimposed, all of the four subpixels are black in the reconstructed blocks corresponding to each black pixel in P, while two subpixels are white and the other two are black corresponding to each white pixel in P. Based upon such a difference, our visual system recognizes the white and black pixels in P from S1 ⊗ S2. We say that the reconstructed image S1 ⊗ S2 recovers P.
Table 3.1 Encoding a binary pixel p into two shares s1 and s2.
Table 3_2 Implementing the visual one secret sharing scheme with a pixel expansion of 4.
Figure 3.1 shows the implementation results of the encoding scheme in Table 3.2. Figure 3.1(a) is a secret binary image P, Figures 3.1(b) and (c) are the two encoded shares S1 and S2 , which are random pictures revealing no information about P and Figure 3.1(d) illustrates the reconstructed image S1 ⊗ S2 that recovers P visually.
FIGURE 3.1
Implementation results of visual one-secret sharing in two shares: (a) P, (b) S1, (c) S2, (d) S1 ⊗ S2.
Following the research of Naor and Shamir, Wu and Chen [12] developed a visual secret sharing scheme that encrypts two secrets into two shares. Given two N× N (square) secret binary images P1 and P2, their scheme produces two shares, namely S1 and S2, which reveal no information about P1 or P2 individually. Yet when stacking S1 and S2, we obtain P1 visually; moreover, when stacking S90°1
Consider a pair of pixels p1 = P1[i, j] and p2 = P2[u, v] in P1 and P2, respectively. We refer to (p1, p2) as the corresponding pixels of P1 and P2 if and only if i = u and j = v. Given a set of corresponding pixels (p1, p2),Wu and Chen’s encoding scheme for visual two-secret sharing in two shares is summarized in Table 3.3.
It is seen from Table 3.3 that each pair of corresponding pixels (p1 , p2) of (P1, P2) is encoded into extended blocks s1 (as well as S90°1
Let us pay attention to the four pixels at the top-right, top-left, bottom-left, and bottom-right corners in sequence (counterclockwise) in P1 and P2. Assume that those pixels in P1 (P2) are □, □, ■. ■ (□, ■. □, ■) as shown in Figure 3.3(a) and (Figure 3.3(b)). Assume that corresponding block at b126
Table 3_3 Wu and Chen’s encoding scheme for visual two-secret sharing in two shares.
FIGURE 3.2
Encoding S1 in Wu and Chen’s scheme: (a) Four triangle-like areas. (b) Indexing the blocks in each of the four areas. (c) Blocks to be assigned.
Note that S1 and S2 are in the shape of squares of the same size. S1 ⊗ S2 reveals P1, while Sθ1⊗S2
Based upon the idea of Wu and Chen [12], Wu and Chang [13] devised another visual two-secret sharing scheme that allows the rotation angle to be an arbitrary one between 0° and 360° by adopting circle shares. Given an angle and two secret images P1 and P2, their approach produces two circle shares A and B such that any single A or B is a seemingly random picture that leaks nothing about P1 or P2; while A ⊗ B reconstructs P1 and A−θ ⊗ B recovers P2 where A−θ denotes the result of rotating A θ clockwise. Note that A−θ ⊗ B is equivalent to A ⊗ Bθ. Intuitively, it is reasonable to choose circles as the encoded shares since they ease the correct alignments between A and B as well as A−θ and B pixel by pixel where 0° < θ < 360°.
FIGURE 65.3
Example for illustrating the idea of Wu and Chen [12]: (a) P1, (b) P2, (c) S1, (d) S2, (e) S1 ⊗ S2, (f) S90°1
They deliberately decomposed circle share A into 360°/θ areas where each area contains an equal amount of 2 × 2 sector blocks. Figure 3.4(a) shows the four typical patterns for sector blocks, namely S11, S21, S31
FIGURE 3.4
2 × 2 sector blocks for A in Wu and Chang’s approach: (a) 2 × 2 sector blocks for A, (b) prev(s) and next(s) of sector block s.
Let the number of areas in circle share A be α(= 360°/θ) and the number of sector blocks in each area be ß. These a areas are indexed clockwise. Let akj
Given a pair of corresponding pixels p1 and p2 in P1 and P2, respectively, each sector block bkj
Note that in Wu and Chen’s scheme each extended block s2 in S2 would be superimposed with s1 and S90°1
Table 3_4 Wu and Chang’s encoding scheme for visual two-secret sharing in two shares.
As mentioned above, square share S1 in Wu and Chen’s scheme is not a totally random image. Strictly speaking, neither is circle share A in Wu and Chang’s scheme due to the reason that sector block atj
Both of the above-mentioned schemes accomplish visual secret sharing for only two secrets in two shares. In this section we discuss two more generalized visual secret sharing scheme for x ≥ 2 secrets in two shares by Shyu et al. [8] and Feng et al. [3] in Sections 3.4.1 and 3.4.2, respectively.
Let us start by using a simple example. Assume that the number of secret images to be shared is x = 3. Let P1, P2, and P3 be the three binary secret images with the same size h × w. Let p1, p2, and p3 denote the corresponding pixels in P1, P2, and P3, respectively. Let A and B denote the two circle shares encoded by the scheme. Our aim is to assure A ⊗ B recovers P1, A120°⊗B
Since there are three secrets, we decompose circle share A and B into three (x = 3) chord-areas (chords for short), respectively, in which the angle of each chord extends up to 120°(= 360°/x = 360°/3). Each chord is divided into a set of 2 × 3 (2 × x) chord blocks. Let the number of 2 × 3 blocks in each chord be ß. Let akj
We first define three 2 × 3 elementary blocks, namely S1A, S2A
In order to guarantee the randomness when using SkA
We call the set of three blocks (a1j, a2j, a3j)
(a1j,a2j,a3j)=(permute(s1AΣj),permute(ssA,Σj),permute(s3A,Σj))(3.1)
for 1 ≤ j ≤ ß.
For the purpose of illustration, we show how the first set of the related blocks (a11, a21, a31)
Let [k, j] denote the absolute location with respect to block j of chord k in a circle share (see Figure 3.9) and Aθ [k, j] denote the content of block [k, j] in Aθ (i.e., the results of rotating A θ counterclockwise) where 1 ≤ k ≤ 3 (= x), 1 ≤ j ≤ ß and θ = 120°(= 360°/3)(A0°[k,j]=A[k,j])
FIGURE 70.3
Decomposing circle shares A and B into chords, which are further divided into blocks: (a) A, (b) B.
FIGURE 71.3
Elementary blocks for circle share A for sharing 3 secrets: (a) S1A
FIGURE 3.7
Subpixels in 2 × 3 elementary block s and permute(s, ∑): (a) a certain ordering of the subpixels in s, (b) the ordering of those in permute(s, ∑) where ∑ = (3, 5,1, 6, 2, 4).
A[1,j]=a1j,A120°[1,j]=a2j,A240°[1,j]=a3jA[2,j]=a2j,A120°[2,j]=a3j,A240°[2,j]=a1jA[3,j]=a3j,A120°[3,j]=a1j,A240°[3,j]=a2j(3.2)
for 1 ≤ j ≤ ß.
First of all, with regard to the three given h × w secret images P1, P2, and P3, we divide Pi evenly into ß = h× (w/3) = h × (w/x)strips. Let (pi)kj
Consider a particular block b1j
It is observed from Table 3.5 that given a set of corresponding pixels (p1, p2, p3), the results of S1A⊗SB (S2A⊗SB, S3A⊗SB)
FIGURE 72.3
Encoding the first three blocks in each of the three chords by ∑1 in A: (a) A, (b) A120°, (c) A240°.
Table 3_5 Encoding a set of corresponding pixels (p1, p2, p3)1j
In actual implementation, the set of three related blocks (a1j, a2j, a3j)
We call the blocks in column sB of Table 3.5 the elementary blocks circle share B for sharing 3 secrets, which consists of three white and three black subpixels. They are named by , S0B, S1B,…, S7B
FIGURE 3.10
Elementary blocks of share B for sharing 3 secrets: (a) S0B
Now, we take the instances in Figure 3.11, in which the first three pixels of the three divided strips in Pi are depicted for 1 ≤ i ≤ 3, as an example to show how the corresponding blocks in B are encoded. From Figure 3.11, we have (p1,p2,p3)11=(□,■,□).
FIGURE 3.11
Instances of the first three pixels of the three strips in (a) P1, (b) P2, and (c) P3.
FIGURE 3.12
Encoding b11
Therefore, the first blocks in the first chords of A ⊗ B, A120° ⊗ B, and A240° ⊗ B reconstruct (p1)11
In summary, given a certain (p1,p2,p3)1j
Now, consider a certain block b2j
Table 3_6 Encoding a set of corresponding pixels (p1,p2,p3)2j
In fact, we can rearrange Table 3.6 to make the columns 4–10 exactly the same as those in Table 3.5. Table 3.7 is such a consequence. Note that Tables 3.5 and 3.7 are the same except for the headings of columns 1-3. From Table 3.7, we observe that given a set of corresponding pixels (p1,p2,p3)2j
Following the above example shown in Figure 3.11, we have (p1,p2,p3)21=(■,■,□)
Table 3_7 Encoding scheme equivalent to Table 6 for the second chords of A and B for visual 3-secret sharing.
FIGURE 3.13
Encoding b21
That is, a21 ⊗b21,a31 ⊗b21
Based upon the experience above, Table 3.8 summarizes the encoding scheme for the blocks in the third chord of B for sharing 3 secrets. We can see from Table 3.8 that given a set of corresponding pixels (p1,p2,p3)3j
Table 3_8 Encoding a set of corresponding pixels (p1,p2,p3)3j
Following the previous example in Figure 3.11, consider the particular case (p1,p2,p3)31=(□,■,■)
We have that a31 ⊗b31,a11 ⊗b31
Figure 3.15 depicts the results of the first three blocks in the three chords of A ⊗ B, A120° ⊗ B and A240° ⊗ B, which reconstruct (p1)k1
FIGURE 3.14
Encoding (p3)k1
FIGURE 3.15
Results of (a) A ⊗ B, (b) A120° ⊗ B, and (c) A240° ⊗ B.
Based upon the above discussions, we obtain bkj=permute(slB,∑j)
l={btod(p1p2p3)if k=1;btod(p3p1p2)if k=2;btod(p2p3p1)otherwise,
for the given set of corresponding pixels (p1,p2,p3)kj
Let rotate(r1r2 … rx, d) denote a function that rotates r1r2 … rx right d bits where ri ∈ {0, 1}, 1 ≤ i ≤ x and 0 ≤ d ≤ x − 1; that is,
rotate(r1r2…rx,d)={r1r2…rx if d=0;rx−d+1rx−d+2…rxr1r2…rx−d otherwise(1≤d≤x−1).(3.3)
Then the above formula can be simplified as
bkj=permute(sbtod(rotate(p1p2p3,k−1))B,Σj)(3.4)
with respect to the set of corresponding pixels (p1,p2,p3)kj
Since the number of subpixels in both of the elementary blocks of A and B is 6(= 2x) in the above case, the pixel expansion (i.e., the number of subpixels in the shares needed to encode a set of corresponding pixels in the secret images) in this algorithm is 6 for x = 3. The visual x-secret sharing scheme for any general number x ≥ 2 will be formalized in the following section.
The definitions of the elementary blocks for circle shares A (formula (3.1)) and B (formula (3.4)) and the encoding scheme in Tables 3.5, 3.7, and 3.8 for visual 3-secret sharing can be generalized to accomplish the visual multisecret sharing for x ≥ 1 (including x =1) secrets. Furthermore, there is no need to store any codebook like Tables 3.5, 3.7, and 3.8. Thus, this scheme formally presented in the following is not only general but also efficient for physical implementation.
Assume that there are x secrets to be shared by two participants. The two circle shares A and B are evenly decomposed into x chords, respectively. Let θ denote the degree expanded in each chord of A and B. It is computed as
θ=360°/x.
We refer to the elementary block of the x secrets as a block with 2x ordered subpixels as shown in Figure 3.16. It is noted that the pixel expansion in the scheme is 2x when x secrets are shared. The width and height of the elementary block can be any combination as long as their multiplication is 2x (or even any number larger than 2x for some special purposes, such as retaining aspect ratios, to ease the production of the circle shares, and so on). The order of the 2x subpixels in the elementary block can also be arbitrarily defined. In the following discussions, we follow the shape and order of the elementary block as shown in Figure 3.16.
FIGURE 3.16
Elementary block for x secrets.
We define the set of the elementary blocks for share A as follows:
ExA={skA|1≤k≤x},
where skA
skA[j]={0if j=x+1−k;1otherwise,(3.5)
for 1 ≤ j ≤ 2x and 1 ≤ k ≤ x.
Figure 3.17 shows the elementary blocks of A for encoding x = 4 secrets. As an example, we show how the subpixels in s2A
FIGURE 3.17
Elementary blocks in E4A
We define the set of the elementary blocks for share B as follows:
ExB={sγB|0≤γ≤2x−1},
where sγB
sγB[j]={rj1≤j≤x;ˉr2x+1−jotherwise,(3.6)
where γ = btod(rxrx−1 … r2r1), rt is the tth least significant bit of γ is represented in binary (x-bit) in which 1 ≤ t ≤ x and 0 ≤ γ ≤ 2x − 1 for 1 ≤ j ≤ 2x and ˉrt
Figure 3.18 illustrates the elementary blocks of B for x = 4. Consider s4B
Formulae (3.1) and (3.4) about the encoding of blocks in A and B, respectively, for x = 3 can now be formulated in a more generalized form as follows. The blocks in A are encoded by
(a1j,a2j,…,axj)=(permute(s1A,Σj),permute(s2A,Σj),…,permute(sxA,Σj)),(3.7)
where ∑j is a random permutation of {1, 2, . . . , 2x} for 1 ≤ j ≤ β.
Given a set of corresponding pixels (p1,p2,…,px)kj
bkj=permute(sbtod(rotate(p1p2…px,k−1))B,Σj)(3.8)
FIGURE 82.3
Elementary blocks in E4B:(a)s0B,(b)s1B,(c)s2B,(d)s3B,(e)s4B,(f)s5B,(g)s6B,(h)s7B,(i)s8B,(j)s9B,(k)s10B,(l)s11B,(m)s12B,(n)s13B,(i)s14B,(i)s15B
for 1 ≤ j ≤ β and 1 ≤ k ≤ x where function ratote(p1p2 ….px, k − 1) is defined by formula (3.3).
Based upon the above definitions and formulae (3.5)–(3.8), our visual multi-secrets sharing scheme is formally presented in Algorithm 1.
Algorithm 1. Encoding x secret images into two circle shares
Input: x h × w binary secret image P1, P2, …, Px
Output: two circle shares A and B such that any single A or B leaks no information about any one of the secret images, while A(j−1)θ ⊗ B recovers Pi for 1 ≤ i ≤ x in the human visual system where θ = 360°/x and A0°
1. Create A and B as circle shares, which are decomposed into x chords where each chord is composed by β = h× (w/x) chord-shaped blocks referred to as akj
2. Generate ExA
3. for (each block j, 1 ≤ j ≤ β) do
3.1 { Determine ∑j = (σ1, σ2, …, σ2x), a random permutation of {1, 2, …, 2x}
3.2 for (each chord k, 1 ≤ k ≤ x) do
{ //all β blocks in x chords of A and B adopt the same permutation ∑j
3.2.1 akj=permute(skA,∑j)
3.2.2 for (each secret image i, 1 ≤ i ≤ x) do qi=(pi)kj
3.2.3 γ = btod(rotate(q1q2 … qx, k − 1))
3.2.4 bkj=permute(sγB,∑j)
}
4. output(A, B) // A and B are composed by all ak,jS
Note that a new permutation ∑j is determined to permute the subpixels in each pair of akj
The pixel expansion of Shyu et al.’s scheme is 2x when x secrets are shared. In the case of x = 2, the pixel expansion is 2x = 4 which is the same as that of Wu and Chen [12] as well as Wu and Chang [13]. The number of all possible patterns in an extended block in S1 [12] (see Figure 3.2(c)) or any sector block in A [13] (see Figure 3.4(a)) is 4, which contains two white and two black subpixels, while that in bkj
It is seen from Algorithm 1 that we do not physically store any information about Tables 3.5, 3.7, and 3.8 in memory. The elementary blocks Sk,AS
Regarding Feng et al.’s (2, 2, x) scheme [3], x secret images P1, P2, …, Px are encoded into two shares A and B. Each set of x corresponding pixels (in x secret images) is encoded into two blocks, namely sA ∈ A and sB ∈ B, each of which consists of x rows containing 3 pixels each. The pixel expansion is thus 3x. The rotation relationship for revealing each of the x secrets is similar to Shyu et al.’s scheme where the ith secret is revealed by A ⊗ B(i−1)θ for 1 ≤ i ≤ x. One special design in their scheme is that the encoded shares are in the form of cylinders to avoid the distortion of the revealed secrets.
They chose four types of 3-pixel patterns, referred to as the effective block ineffective block white block and black block to construct SA and sB. It is evident that and .
Figure 3.19 specifically illustrated the stacked results of these chosen patterns in their scheme.
FIGURE 84.3
Stacking results of the chosen visual patterns for Feng et al.’s scheme.
Table 3.9 lists a possible set of encoded patterns for s1A,s2A,s3A,
Table 3_9 Possible set of encoded patterns for s1A,s2A,s3A,
Here, we implement Shyu et al.’s visual multisecret sharing scheme due to its generality on the abstraction and the superiority on the pixel expansion (over Feng et al.’s scheme).
We coded the program by using Borland C++ Builder (BCB) in a personal computer running MS Windows. Since the blocks are in the shape of chords, we called the embedded functions in BCB such as circle drawing, line drawing, flood-filling a closed area, and so on, to build the chord-shaped blocks in the scheme.
Four experiments were designed to explore the feasibility and applicability of the visual multisecret sharing scheme. Experiment 1 verifies the correctness of the scheme for x = 3 where the starting position for encoding on the circle shares are fixed as above-mentioned. Experiment 2 demonstrates that the scheme can be easily extended in such a way that the starting position for encoding can be arbitrarily assigned. This increases the secrecy of the proposed scheme. Experiment 3 gives the implementation results of the visual 4-secret sharing scheme. Experiment 4 presents implementation results of encoding the shares using cylinder (instead of circle) shares.
Experiment 1: Figure 3.20 illustrates the results of a computer implementation of the proposed scheme for sharing three secret images. Figures 3.20(a)–(c) are the three secrets to be shared, namely P1, P2, and P3, respectively. Figures 3.20(d) and (e) show the circle shares A and B encoded by Algorithm 1, which expose no information about P1 , P2 , and P3 individually. Figures 3.20(f)–(h) reveal the superimposed results of A ⊗ B, A120 ⊗ B°, and A240° ⊗ B, which reconstruct P1, P2, and P3 in our visual system, respectively. Figure 3.20(i) gives another superimposed result, A85° ⊗ B that leaks no information about any of the three secrets. In fact, any result of Aθ ⊗ B, for θ = 0 , 120°, 240°, is merely a seemingly random picture.
Experiment 2: The encoding processes of A and B in the algorithm start from the 0 position and move on in a clockwise direction (see Figure 3.5). However, the starting position for encoding in A (or B) can be predefined arbitrarily.
Figure 3.21 shows the implementation results of using the same example as in Experiment 1 with a different starting starting position in B; that is, we encoded B by starting from the 85 position (85 counterclockwise to the 0 position) while we encoded A by starting from the 0 position as mentioned. The three secret images are the same as those in Figures 3.20(a)–(c). Figures 3.21(a) and (b) are the circle shares A′ and B′ encoded by Algorithm 1. Figure 3.21(c) shows the result of A′ ⊗ B′, which reveals nothing about the secrets, while Figures 3.21(d)–(f) display the superimposed results of (A′)85° ⊗ B′, (A′)205° ⊗ B′ and (A′)325° ⊗ B′ that reconstruct P1, P2, and P3, respectively, in our visual system. Note that both A ⊗ B (Figure 3.20(f)) and (A′)85 ⊗ B′ is 85 counterclockwise away from that in A ⊗ B.
FIGURE 86.3
Implementation results for the proposed visual 3-secret sharing scheme: (a) P1, (b) P2, (c) P3,(d) A, (e) B, (f) A ⊗ B, (g) A120° ⊗ B, (h) A240° ⊗ B, (i) A85° ⊗ B.
Experiment 3: Figure 3.22 gives the implementation results of the proposed scheme for sharing four secrets. Figures 3.22(a)–(d) are the four secrets to be shared, namely P1, P2, P3, and P4, respectively. Figures 3.22(e) and (f) are the encoded circle shares A and B. Figures 3.22(g)–(j) show the superimposed results of A ⊗ B, A90° ⊗ B, A180° ⊗ B, and A270° ⊗ B that recover P1, P2, P3, and P4 in our visual system, respectively.
Experiment 4: One disadvantage in applying circle shares is that the reconstructed secrets might be distorted. This shortcoming could be easily refined by introducing cylinder shares.
Suppose that we encode each set of x pixels into square blocks (instead of chord blocks) in Shyu et al.’s scheme. The encoded shares evolve into the shape of rectangles. Each of the two rectangle shares can be easily rolled up into a cylinder by aligning the rightmost column next to the leftmost one. Figure 3.23 shows an example of applying cylinder shares to reveal the corresponding distorted secrets where (a) and (b) are distorted reconstructed secrets (which are the same as those in Figure 3.22(g) and (j), respectively) using circular shares, while (c) and (d) are the corresponding counterparts using cylinder shares which avoid any distortion when exposing the secrets.
The results in Experiments 1–4, as expected, demonstrate the feasibility and applicability of Shyu et al.’s visual multisecret sharing scheme. We compare the performances of the aformentioned schemes in terms of the capability of sharing secrets, pixel expansion, contrast, and shape of shares in the next subsection.
When we deal with x secrets, the pixel expansion of Shyu et al.’s scheme [8] is 2x and the contrast (i.e., the relative difference between the reconstructed white and black pixels in the superimposed image) of the scheme is 1/(2x) since all 2x subpixels in a reconstructed black pixel are black, while those in a reconstructed white pixel are 2x. Suppose that Feng et al.’s scheme is applied. The pixel expansion becomes 3x and the contrast is 1/(3x). Note that when x = 2, the pixel expansions (contrasts) in Wu and Chen’s [12], Wu and Chang’s [13], and Shyu et al’s schemes are all 4 (1/4); while in Feng et al.’s scheme is 6 (1/6).
Table 3.10 summarizes the numbers of secrets shared (denoted as x), pixel expansions(denoted as m), contrasts, and the shapes of shares in these visual multiple-secret sharing schemes for the comparison purpose.
The pixel expansion of Shyu et al.’s scheme [8] is 2x when x secrets are shared. It would be challenging to prove whether or not it is optimal. Is there any algorithm that improves the contrast in the scheme? It is surely worthy of further study. How to extend Shyu et al.’s scheme such that multiple secrets can be shared by more than two shares is also an interesting topic. Potentially, sharing multiple secrets may have more flexibilities and applications than sharing only one secret. Visual identification and visual authentication are some typical applications in visual cryptography [6]. It would be of much significance to reexamine these topics from a viewpoint of sharing multiple secrets.
FIGURE 88.3
Implementation results for the proposed visual 3-secret sharing scheme with a different starting encoding position: (a) A′, (b) B′, (c) A′ ⊗ B′, (d) (A′)85° ⊗ B′, (e) (A′)205° ⊗ B′, (f) (A′)325° ⊗ B′.
FIGURE 89.3
Results of computer implementation for 4-secret sharing: (a) P1, (b) P2, (c) P3, (d) P4, (e) A, (f) B, (g) A ⊗ B, (h) A90° ⊗ B, (i) A180° ⊗ B (j) A270° ⊗ B.
FIGURE 90.3
Transforming circle shares (a) and (b) into cylinder counterparts (c) and (d), respectively.
Table 3.10 Comparison of visual multiple secrets sharing schemes.
Schemes | x | m | contrast | shares’ shape |
Wu and Chen [12] | 2 | 4 | 1/4 | square |
Wu and Chang [13] | 2 | 4 | 1/4 | square |
Feng et al.[3] | ≥2 | 3x | 1/3x | cylnder |
Shyu et al.[8] | ≥2 | 2x | 1/2x | circle or cylinder |
As a matter of fact, the sharing of multiple secrets visually brings forth new problems to be considered. For instance, with regard to the “starting position for encoding” in A or/and B in Experiment 2, we may design such a concern to be some kind of private key, which is only accessible between the dealer and authorized participant(s). Without the correct starting positions in A or/and B, the alignment of A and B cannot recover the secret yet. In addition, the second secret of the three secrets in Experiment 1 might be designed to be fake for the purpose of diffusion. That is to say whether the whole secret message is “Help is never on its way"or “Help is on its way” may be treated to be another private key between the dealer and authorized participant(s). Mainly, the number of secrets, the degree of the starting position for encoding, the combination of the true or fake reconstructed secrets, and so on, can be designed as private keys to increase the level of security in the visual multi-secret sharing system.
By adopting circle or cylinder shares, we discuss general visual secret sharing schemes for x ≥ 1 (indeed, these schemes work well for x = 1) secrets in two shares in this chapter. The previous studies considered sharing only two secrets in two shares [12, 13]. Shyu et al.’s scheme can be implemented easily and it takes only some constant working space. All encoding information can be determined in run time. By introducing an independent random permutation (i.e., ∑j, see formulae (3.1) and (3.4)) when encoding each pair of the corresponding blocks (i.e., akj
In traditional visual secret-sharing schemes, rectangle shares are encoded to conceal one shared secret. They are easily superimposed by aligning the rectangular corners. As compared to the rectangle shares, the circle or cylinder shares are relatively hard to superimpose since there are no reference points to align with. Basically, the usage of the circle or cylinder shares increases the complexity in decoding the secrets. In practical applications, the dealer might add additional information in the circle shares, such as some supplementary points, lines, or markers, to ease the superimposition (decoding process) for the participants. Figure 3.24 shows one possible arrangement in the case of sharing three secrets as in Experiment 1. Note that circle share A has three markers (see Figure 3.24(a)), while B has only one (see Figure 3.24(b)) based upon which A, A120° , and A240° can be superimposed with B easily. Or, the dealer can deliberately organize such information as private key(s) such that only the legal receivers are informed how to obtain the key(s). The same reasoning could be applied if the cylinder shares are adopted.
FIGURE 3.24
Shares (based upon Experiment 1) with supplementary lines to ease the alignments: (a) A with three markers, (b) B with one marker.
Generally speaking, the use of circle or cylinder shares to convey several secrets discloses some new issues that have not yet been considered in traditional visual cryptography, such as “How many secrets are there?,”“How to superimpose the shares (where to align with or in what rotation angles)?,”“Is there any fake secret(s) for diffusion?,”and so on. These concerns can be designed as a set of private keys. The consideration and distribution of these private keys can be further discussed.
[1] G. Ateniese, C. Blundo, A. De Santis, and D.R. Stinson. Visual cryptography for general access structures. Inf. Comput., 129:86–106, 1996.
[2] C. Blundo, A. De Santis, and D.R. Stinson. On the contrast in visual cryptography schemes. J. Cryptogr., 12:261–289, 1999.
[3] J. B. Feng, H. C. Wu, C. S. Tsai, Y. F. Chang, and Y. P. Chu. Visual secret sharing for multiple secrets. Pattern Recognition, 41:3572–3581, 2008.
[4] Y.C. Hou. Visual cryptography for color images. Pattern Recognition, 36:1619–1629, 2003.
[5] C.C. Lin and W.H. Tsai. Visual cryptography for grey-level images by dithering techniques. Pattern Recognition Lett., 24:349–358, 2003.
[6] M. Naor and B. Pinkas. Visual authentication and identification. in: B.S. KaliskiJr. (Ed.), Advances in Cryptology: CRYPTO97, Lecture Notes in Computer Science, 1294:322–336, 1997.
[7] M. Naor and A. Shamir. Visual cryptography. in: A. De Santis (Ed.), Advances in Cryptology: Eurpocrypt'94, Lecture Notes in Computer Science, 950:1–12, 1995.
[8] S. J. Shyu, S.Y. Huang, Y.K. Lee, R.Z. Wang, and K. Chen. Sharing multiple secrets in visual cryptography. Pattern Recognition, 40:3633–3651, 2007.
[9] S.J. Shyu. Efficient visual secret sharing scheme for color images. Pattern Recognition, 39:866–880, 2006.
[10] D.R. Stinson. An introduction to visual cryptography. Public Key Solution ’97, pages 20–30, April 1997.
[11] E.R. Verheul and H.C.A. Van Tilborg. Constructions and properties of k out of n visual secret sharing schemes. Designs Codes Cryptography, 11:179–196, 1997.
[12] C.C. Wu and L.H. Chen. A study on visual cryptography, Master Thesis. PhD thesis, Institute of Computer and Information Science, National Chiao Tung University, Taiwan, R.O.C., 1998.
[13] H.C. Wu and C.C. Chang. Sharing visual multi-secrets using circle shares. Comput. Stand. Interfaces, 134((28):123–135, 2005.
3.129.22.135