10 Cheating Prevention in Visual Cryptography

In 1994, Naor and Shamir proposed a variant of secret sharing called Visual Cryptography (VC) [9], where the shares given to participants are xeroxed onto transparencies. If X is an authorized subset, then the participants in X can visually recover the secret image by stacking their transparencies together without performing any computation. One special property distinguishes VC from conventional secret sharing scheme [16, 17] is that the security of VC is achieved by losing the contrast and the resolution of the secret image. In other words, the quality of the reconstructed secret image is inferior to that of the original secret image. Since the invention of VC, many researchers have devoted themselves to enhancing the contrast and resolution of the reconstructed images [1, 3] and to extending it to general access structures [7]. Moreover, many schemes to visually share nonbinary secret images, such as gray-level secret images [2, 5] and color secret images [12, 13], were also proposed. There are lots of applications based on VC, for example, visual authentication and identification [10], steganography [4, 6, 8], and image encryption [14].

In 2006, Horng et al. showed that cheating is possible in the k-out-of-n VC [8]. The cheating activity could cause unpredictable damage to victims because they will accept a forged image different from the actual secret image as authentic. In this chapter, we survey some recently proposed cheating prevention schemes in VC and provide a comparative evaluation of their advantages and disadvantages.

The rest of this chapter is organized as follows. Section 10.2 provides preliminary background on VC and the cheating activities. Section 10.3 surveys some cheating prevention schemes. Their comparative analyses are in Section 10.4. Finally, conclusions and some research issues are given in Section 10.5.

10.2 Preliminaries

10.2.1 Visual Cryptography

A visual secret sharing scheme is a special variant of a k-out-of-n secret sharing scheme where the shares given to participants are xeroxed onto transparencies. Therefore, a share is also called a transparency. If X is a qualified subset, then the participants in X can visually recover the secret image by stacking their transparencies without performing any cryptographic computation. Usually, the secret is an image. To create the transparencies, each black and white pixel of the secret image is handled separately. It appears as a collection of m black and white subpixels in each of the n transparencies. We will call these m subpixels a block. Therefore, a pixel of the secret image corresponds to nm subpixels. We can describe the nm subpixels by an n × m Boolean matrix, called a base matrix, S = [S_ij] such that S_ij = 1 if and only if the j^th subpixel of the i^th share is black and S_ij = 0 if and only if the j^th subpixel of the i^th share is white. The gray level of the stack of k shared blocks is determined by the Hamming weight H(V) of the “OR”ed m-vector V of the corresponding k rows in S. This gray level is interpreted by the visual system of the users as black if H (V) ≥ d and as white if H (V) ≤ d − α * m for some fixed threshold d and relative difference α. We would like m to be as small as possible and α to be as large as possible.

More formally, a solution to the k-out-of-n VC consists of two collections C⁰ and C¹ of n × m base matrices. To share a white pixel, the dealer randomly chooses one of the matrices from C⁰, and to share a black pixel, the dealer randomly chooses one of the matrices from C¹. The chosen matrix determines the m subpixels in each one of the n transparencies. Figure 10.1 shows the basic concept of visual cryptography.

Images

FIGURE 10.1
Visual cryptography.

Definition 1 A solution to the k-out-of-n VC consists of two collections C⁰ and C¹ of n × m base matrices. The solution is considered valid if the following conditions are met:

Contrast conditions:

1. For any matrix S⁰ in C⁰, the “or” V of any k of the n rows satisfies H(V) ≤ d − a * m.

2. For any matrix S¹ in C¹, the “or” V of any k of the n rows satisfies H(V) ≥ d.

Security condition:

3. For any subset {i₁, i₂, …, i_q} of {1, 2,…, n} with q < k, the two collections D⁰, D¹ of q × m matrices obtained by restricting each n × m matrix in C⁰, C¹ to rows i₁,i₂,K,i_q are indistinguishable in the sense that they contain the same matrices with the same frequencies.

Images

FIGURE 284.10
The concept of 2-out-of-2 VC.

Images

FIGURE 10.3
A 2-out-of-3 visual secret sharing scheme.

Figure 10.2 shows the basic concept of a 2-out-of-2 visual secret sharing scheme. The secret image is shared through two noise-like transparencies: T₁ and T₂. In this case, a block consists of 4 subpixels. Each black(white) pixel of the secret image is turned into two black and two white subpixels of T₁ and T₂. Figure 10.3 shows an example of a 2-out-of-3 visual secret sharing scheme.

10.2.2 Cheating in VC

In [8], Horng et al. showed that cheating is possible in k-out-of-n VC. Let’s take the 2-out-of-3 visual secret sharing scheme shown in Figure 10.3 as an example. A secret image is encoded into three distinct transparencies, denoted T₁, T₂, and T₃. Then, the three transparencies are respectively delivered to Alice, Bob, and Carol. Without loss of generality, Bob and Carol are assumed to be collusive cheaters and Alice is the victim. During the cheating activity, Bob and Carol use S₂ and S₃ to create forged transparency ${S^{'}}_{2}$ ${S^{'}}_{2}$ such that superimposing ${S^{'}}_{2}$ ${S^{'}}_{2}$ and S₃ will visually recover the cheating image as in Figure 10.4. Precisely, by observing the following collections of 3 × 3 matrices that are used to generate transparencies, collusive cheaters can predict the actual structure of the victim’s transparency so as to create ${S^{'}}_{2}$ ${S^{'}}_{2}$ .

\begin{array}{l} C^{0} = {all the matrices obtained by permuting the columns of [\begin{array}{l} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}]} \\ C^{1} = {all the matrices obtained by permuting the columns of [\begin{array}{l} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]} \end{array}

$\begin{array}{l} C^{0} = {all the matrices obtained by permuting the columns of [\begin{array}{l} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}]} \\ C^{1} = {all the matrices obtained by permuting the columns of [\begin{array}{l} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]} \end{array}$

By observing the above matrices, two rows of above C⁰ or C¹ matrix are determined by collusive cheaters. Therefore, the structure of the corresponding block of S₁ is exact the remaining row. For presenting a white pixel of cheating image, the block of ${S^{'}}_{2}$ ${S^{'}}_{2}$ is set to be the same structure of S₁. For presenting a black pixel of cheating image, the block of ${S^{'}}_{2}$ ${S^{'}}_{2}$ is set to be the different structure of S₁. For example, if the block of S₁ is [010], then ${S^{'}}_{2}$ ${S^{'}}_{2}$ is set to be [010] for a white pixel or it is set to be [001] for a black pixel.

We note that if the forged shares deviate too much from the original shares then the victim will notice the difference and suspect being cheated. Therefore, a necessary condition for a cheating activity to be successful is that the forged shares must be indistinguishable from the original shares. There are different cheating activities defined in [15].

Images

FIGURE 286.10
Cheating in visual cryptography.

10.3 Cheating Prevention Schemes

A visual secret sharing scheme is said to be a cheating prevention scheme if the probability of successful cheating is negligible. We will not consider cheating prevention in computational visual cryptographic schemes [21]. We can divide the cheating prevention schemes into two classes. One is based on share authentication where another share (transparency) is used to authenticate other shares (transparencies) and the other is based on blind authentication where some property of the image is used to authenticate the reconstructed secret image. For example, in [8], it is assumed that a smooth image such that its boundary of black and white regions is clearly perceptible is regarded as authentic. Due to practical reasons, most cheating prevention schemes focus on 2-out-of-n schemes. In the following subsections, we will survey 6 recent proposed cheating prevention schemes: two from [8], proposed in 2006 and will be referred to as HCT1 and HCT2, one from [15], proposed in 2007 and will be referred to as HT, one from [18], proposed in 2007 and will be referred to as TCH, and two from [20], proposed in 2009 and will be referred to as PS1 and PS2.

10.3.1 HCT1 and HCT2

In [8], two cheating prevention schemes are proposed: the Authentication Based Cheating Prevention scheme, referred to as HCT1, and the 2-out-of-(n + l) cheating prevention scheme, referred to as HCT2. HCT1, shown in Figure 10.5, is a share-authentication-based cheating prevention scheme and HCT2, shown in Figure 10.7, is a blind-authentication-based cheating prevention scheme. Figure 10.6 shows an experiment of HCT1. In HCT1, each participant uses an extra transparency to verify the integrity of other transparencies by means of the appearance of the verification logo. A participant adopts a verification transparency to verify the integrity of other transparencies through the appearance of his own verification logo. Each verification transparency is generated by a 2-out-of-2 VC. Therefore, each participant receives two transparencies, namely, secret share transparency and verification transparency created by the 2-out-of-n and 2-out-of-2 VC, respectively. Figure 10.6 shows an experiment of HCT1.

HCT2 generates (n+l) transparencies but it only delivers n transparencies to participants. The probability that cheaters can correctly guess the structure of each block generated for a black pixel of the victim’s transparency is down to 1/(1 + l). The secret image is redesigned to consist of two complementary parts. Two binary images are said to be complementary to each other if and only if they have the same size and, for all corresponding pixels, one is black and the other is white. Therefore, the probability that cheaters can correctly guess the structure of victim’s transparency is negligible. The idea can be extended to design a k-out-of-(n + l) cheating prevention scheme.

Images

FIGURE 288.10
HCT1.

Images

FIGURE 10.6
Experiment of HCT1.

Images

FIGURE 10.7
HCT2.

10.3.2 HT

The core of HT, shown in Figure 10.8, uses a generic transformation to create new transparencies by adding two subpixels to every block of every original transparency. Then, HT creates a verification transparency for each participant such that the stacking result of the new transparency with the verification transparency will reveal a verification image. Therefore, HT is a share-authentication-based cheating prevention scheme. Basically, HT will perform the following steps with input C⁰ and C¹ to create verification transparencies

Let $T_{0} = [\begin{matrix} 10 \\ ⋮ \\ 10 \end{matrix} | C^{0}]$ $T_{0} = [\begin{matrix} 10 \\ ⋮ \\ 10 \end{matrix} | C^{0}]$ and $T_{1} = [\begin{matrix} 10 \\ ⋮ \\ 10 \end{matrix} | C^{1}]$ $T_{1} = [\begin{matrix} 10 \\ ⋮ \\ 10 \end{matrix} | C^{1}]$
Use T⁰ and T¹ as the base matrices for creating transparencies
For each participant P_i, choose a verification image and create a verification transparency v_i as follows:

FIGURE 290.10
HT.
1. For each white pixel in the verification image, the block of v_i created based on [1 0 0 … 0] (after corresponding permutation as for generating the secret shares in step 2).
2. b For each black pixel in the verification image, the block of v_i created based on [0 1 0 … 0] (after corresponding permutation as for generating the secret shares in step 2).

In the decoding phase of the secret image, before stacking transparencies, each P_i checks the stacking result of v_i with T_j held by participant P_j revealing his own verification image. Figure 10.9 shows an example of an HT scheme.

10.3.3 TCH

In [18], Tsai et al. proposed a cheating prevention scheme, shown in Figure 10.10, images where shares are generated by Genetic Algorithms. TCH adopts multiple secret images with the same visual meaning. Each qualified subset only reveals the corresponding reconstructed secret image and the others are left unknown to potential cheaters. Any participant accepts the decoding result only if the visually reconstructed secret image is authentic. In TCH, the fitness function of the Generic Algorithm was designed according to a 2-out-of-n visual secret sharing scheme. But, it is not guaranteed that the same quality is obtained because the Generic Algorithm is a kind of heuristic algorithm. Therefore, the dealer should control the quality of all reconstructed secret images before delivering all transparencies. That is, all transparencies should be indistinguishable.

Images

FIGURE 291.10
Experiment of HT.

Images

FIGURE 10.10
TCH.

10.3.4 PS1 and PS2

In 2009, De Prisco and De Santis [20] proposed 2-out-of-n and n-out-of-n cheating prevention schemes, as shown in Figure 10.11. They are obtained by simply adding an extra column with all 0s to the base matrices of the schemes of Naor and Shamir.

In the following, we describe another 2-out-of-n cheating prevention scheme, as shown in Figure 10.12 and proposed in the same paper. This scheme does not require the use of a complementary image. The base matrices of the scheme have dimension n × (2ⁿ + n +1). The white base matrix C⁰ has the following columns: all the possible 2ⁿ binary column vectors of length n, one additional column with all 1s and n additional columns with all 0s. Whereas, the black base matrix C¹ has the following columns: all the possible 2ⁿ binary column-vectors of length n, one additional column with all 0s in the n columns of the identity matrix of dimension n × n.

The base matrices of a 2-out-of-3 PS2 scheme are shown as follows:

\begin{array}{l} C^{0} = [\begin{array}{l} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} | \begin{array}{l} 0 \\ 0 \\ 0 \end{array} | \begin{array}{l} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}] \\ C^{1} = [\begin{array}{l} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} | \begin{array}{l} 0 \\ 0 \\ 0 \end{array} | \begin{array}{l} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] \end{array}

$\begin{array}{l} C^{0} = [\begin{array}{l} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} | \begin{array}{l} 0 \\ 0 \\ 0 \end{array} | \begin{array}{l} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}] \\ C^{1} = [\begin{array}{l} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} | \begin{array}{l} 0 \\ 0 \\ 0 \end{array} | \begin{array}{l} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] \end{array}$

We refer the readers to [20] for more details.

Images

FIGURE 293.10
PS1.

Images

FIGURE 10.12
PS2.

10.4 Analysis of Cheating Prevention Schemes

We begin with a general discussion of the advantages and disadvantages of the share authentication approach and blind authentication approach. The advantages of share-authentication-based cheating prevention approach are twofold. One is that checking the authenticity of shares is optional. It can be done only when someone is suspected of cheating. The other is that the generation of verification shares is done after the generation of secret shares. Therefore, any conventional visual secret sharing schemes (for any access structures) can be turned into a cheating prevention scheme. The quality of the reconstructed secret image is not affected. The disadvantages of this approach are also twofold. One is that additional shares for verification purpose are needed. The other is that these schemes lack a formal proof of security.

The advantages of blind-authentication-based cheating prevention approach are twofold. One is that no additional shares are required. The other is that we can formally prove the security. We can formally argue that the probability of changing a black pixel (or white pixel) by the cheaters is less than 1. The disadvantages of this approach are also twofold. One is that this approach is only suitable for threshold visual secret sharing schemes. The other is that the quality of the reconstructed secret image is degraded.

The comparisons of different cheating prevention schemes are illustrated in Table 10.1. With respect to the total number of subpixels for sharing a pixel, TCH requires the least subpixels for sharing a pixel. HCL1 requires 2n² subpixels, since an extra transparency is used to verify the correctness of other transparencies. HT requires 2n(n + 2) subpixels because this scheme also needs verification transparencies and each original transparency is enlarged. Finally, HCT2 needs 2(n + l)² subpixels. With respect to prevention of shares against cheating, the following schemes are all designed according to authentic conditions (AC). PS and HT both prevent all blocks of each transparency from cheating. HCT1 only prevents these blocks within the corresponding verification logo. And HCT2 only prevents blocks that were created for presenting black pixels. The share-authentication-based cheating prevention approach can be applied to general access structures. Whereas blind-authentication-based cheating prevention approach is more suitable for threshold access structures, with respect to the method for share generation, HT uses a modified VC by the basis matrices T⁰ and T¹. HCL1 and HCL2 use the share construction method of traditional VC. Finally, TCH uses GA for share generation. With respect to security, all schemes are designed for preventing a known secret cheating attack. However, HCL1, HT, and TCH are not formally proved to be secure.

Table 10.1 Comparisons of different cheating prevention visual secret sharing schemes.

Images

10.5 Conclusions

In this chapter, we have surveyed some cheating prevention schemes in visual cryptography and provided a comparative evaluation of their advantages and disadvantages. There are many topics that deserve further instigation, for example, giving formal definition of cheating and cheating attack models and designing new cheating prevention scheme a with less numbers of subpixels for sharing a pixel.

Bibliography

[1] A. Shamir and M. Naor. Visual cryptography II: Improving the contrast via the cover base, security in communication networks, September 16–17, 1996.

[2] C. Blundo, A. De Santis, and M. Naor. Visual cryptography for grey level images. Information Processing Letters, Vol. 75, No. 6, (2000) 255–259.

[3] C. Blundo, P. D’Arco, A. De Santis, D. R. Stinson. Contrast optimal threshold visual cryptography schemes, SIAM J. Discrete Math. 16(2)(2003) 224–261.

[4] C.C. Chang, and J.C. Chuang. An image intellectual property protection scheme for gray-level image using visual secret sharing strategy, Pattern Recognition Letters, Vol. 23 (2002) 931–941.

[5] C.C. Lin, W.H. Tsai. Visual cryptography for gray-level images by dithering techniques, Pattern Recognition Letters. Vol. 24 (1–3) (2003) 349–358.

[6] C.C. Wang, S.C. Tai, and C.S. Yu. Repeating image watermarking technique by the visual cryptography, IEICE Transactions on Fundamentals, Vol. E83-A (2000) 1589–1598.

[7] G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson. Visual Cryptography for general access structures, Information and Computation, (1996) 86–106.

[8] G. Horng, T. H. Chen, and D. S. Tsai. Cheating in visual cryptography, designs, codes and cryptography, Vol. 38, No. 2 (2006) 219–236.

[9] M. Naor and A. Shamir. Visual cryptography, In Proceedings of Advances in Cryptography-EUROCRYPTO’94, LNCS 950 (1994) 1–12.

[10] M. Naor and B. Pinkas. Visual authentication and identification, advances in cryptology - Proceedings of Crypto 97 (Burton, S. KaliskiJr., ed.), Lecture Notes in Computer Science, Springer-Verlag, New York, 1294 (1997) 322–336.

[11] R. Lukac and K.N. Plataniotis, Bit-level based secret sharing for image encryption, Pattern Recognition Vol. 38(5) (2005) 767–772.

[12] V. Rijmen and B. Preneel, Efficient colour visual encryption for shared colors of Benetton, EUROCRYPTO’96, Rump Session, Berlin, 1996.

[13] Y. C. Hou. Visual cryptography for color images, Pattern Recognition, Vol. 36 (2003) 1619–1629.

[14] T. H. Chen and D. S. Tsai. Owner-customer right protection mechanism using a watermarking scheme and a watermarking protocol, Pattern Recognition, Vol. 39, Issue 8, (2006) pp. 1530–1541.

[15] C. Hu and W. Tzeng. Cheating prevention in visual cryptography, IEEE Transactions on Image Processing, Vol. 16, No. 1, 2007, pp. 36–45.

[16] A. Shamir. How to share a secret, Comm. ACM, Vol. 22 (1979) 612–613.

[17] G. Blakley. Safeguarding cryptographic keys, Proc. AFIPS 1979 Natl. Conf.

[18] D.S. Tsai, T.H. Chen, and G. Horng. A cheating prevention scheme for binary visual cryptography with homogeneous secret images, Pattern Recognition, Vol. 40 No. 8, 2007, pp. 2356–2366.

[19] R. C. Gonzalez and R. E. Woods. Digital Image Processing, 2nd Ed., Prentice-Hall, 2002.

[20] R. De Prisco and A. De Santis. Cheating immune threshold visual secret sharing, The Computer Journal, doi:10.1093/comjnl/bxp068.

[21] C. Chang, T. Chen, and L. Liu. Preventing cheating in computational visual cryptography, Fundamenta Informaticae Vol. 92 2009, pp. 27–42.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for
10 Cheating Prevention in Visual Cryptography

10

Cheating Prevention in Visual Cryptography

CONTENTS

10.1 Introduction

10.2 Preliminaries

10.2.1 Visual Cryptography

10.2.2 Cheating in VC

10.3 Cheating Prevention Schemes

10.3.1 HCT1 and HCT2

10.3.2 HT

10.3.3 TCH

10.3.4 PS1 and PS2

10.4 Analysis of Cheating Prevention Schemes

10.5 Conclusions

Bibliography

Table of Contents for 10 Cheating Prevention in Visual Cryptography

Create new playlist

Sign In

Sign Up

CONTENTS

Table of Contents for
10 Cheating Prevention in Visual Cryptography