像素擴展之灰階視覺密碼方法

1、 107 An Unexpanded Visual Cryptography Method forGray-level ImagesYoung-Chang Hou Department of Information Management, National Central UniversityChing-Sheng Hsu Department of Information Management, National Central Universityn 108AbstractVisual cryptography is a method to encrypt a secret image i

2、nto n shares so that any qualified set of shares can recover the secret, whereas any forbidden set of shares cannot leak out any secret information. Since visual cryptography uses human visual system to decrypt the secret, it becomes an appropriate scheme while computers or other decryption devices

3、are not available. Most visual cryptographic methods use the concept of pixel expansion; therefore, the size of shares is larger than that of the secret image. Pixel expansion not only results in distortion of shares, but also consumes more storage space. In addition, most studies of visual cryptogr

4、aphy were about black-and-white images, whereas few studies were made on gray-level images. In this paper, we proposed an unexpanded visual cryptography method for gray-level images. Our method used the concept of probability to achieve the goal of non-pixel-expansion. Moreover, we employed digital

5、image halftoning to deal with gray-level images. Finally, we also proposed a method to cope with the problem of loss of contrast in visual cryptography. Experimental results showed that our method might get better contrast and better visual effect of the stacked images.Keywords: visual cryptography,

6、 visual secret sharing, halftoning, gray-level images Naor Shamir (1995) (visual secret sharing scheme; VSSS) n (participants) n×m (Boolean matrices) M0 M1 (basis matrices) ( ) ( ) 109M0 (M1) i m ( ) i n (Droste 1996; Iwamoto and (Ateniese et al 1996b; Yamamoto 2003) Naor and Shamir 1995)(acces

7、s structures) (threshold access structures) (general access structures) Naor Shamir (1995) (k, n)-threshold (k, n)-threshold n P = 1, 2, , n k k k Ateniese et al. (1996b) (k, n)-threshold (Qual, Forb) (qualified set) Y Qual (forbidden set) X Forb (Ateniese et al. 2001; Naor and Shamir 1995) (pixel-e

8、xpansion)(non-pixel-expansion) (Ateniese et al. 1996a, 1996b, 2001; Blundo and De Santis 1998; Blundo et al. 1999; Blundo et al. 2001; Droste 1996; Eisen and Stinson 2002; Hou 2003; Hofmeister et al. 2000; Naor and Shamir 1995; Tzeng and Hu 2002; Verheul and van Tilborg 1997) (Hou and Hsu2004; Hou e

9、t al. 2001; Ito et al. 1999) mm Ito et al. (1999) n×m M0 M1 ( ) M0 (M1) i ( ) i110 (Ateniese et al. 1996a, 1996b, 2001; Blundo and De Santis 1998; Blundo et al. 1999; Blundo et al. 2001; Droste 1996; Eisen and Stinson 2002; Hofmeister et al. 2000; Hou and Hsu 2003; Ito et al. 1999; Naor and Sha

10、mir 1995; Tzeng and Hu 2002) (Hou 2003; Hou et al. 2001; Koga and Yamamoto 1998; Lin and Tsai 2003; Verheul and van Tilborg 1997) Verheul van Tilborg (1997) (k, n)-threshold j = 0, 1, , g 1 n×m Aj j Aj Aj i i Hou et al. (2001) (2, 2)-threshold (2, 2)-threshold Hou Hsu (2004) (loss of contrast)(

11、Naor and Shamir 1995) P = 1, 2, , n (participants) 2P P (power set) P = (P, F, Q) (access structure) (Tzeng and Hu 2002) F, Q 2P (forbidden sets) (qualified sets) Q F = X F Y Q Q = 2P F (P, F, Q) (complete) X F X X X FF (monotonically decreasing) Y Q Y Y Y Q Q (monotonically increasing) F Q (monoton

12、ic) F Q 0 1 X |X| X “” “OR” E Ei E i SH1, SH2, , SHn (SH1 + SH2 + + SHn) SH1, SH2, , SHn 111 ( 0 1 ) 10×10 70 70% ( ) 70% 70% 80% B B 50% W W B B W W B W 112 1 (2, 2)-thresholdSHSH(SH+SH) n n 2n (2, 2)-threshold (P = 1, 2, F = 1, 2, Q = 1, 2) 1 2 1 (encryption rule) X F 0, 1|X| |X|UX 0, 1|X| X

13、Y Q (2, 2)-threshold(2, 2)-threshold = (P, F, Q) P = 1, 2 F = 1, 2 Q = 1, 2 n = 2 22 = 4 (0, 0) (0, 1) (1, 0) (1, 1) (ej,1, ej,2) 1 (SH1) 2 (SH2) j j = 1, 2, 3, 4 p0(UX) p1(UX) 1132 (2, 2)-thresholdjn1,12,1e = 1 e4,1 = 1 1,11,22,2e = 0e4,2 = 11,2cij0,10,2cc0,41,1c1,2ccSecurity:c0,1 + c0,2 = c1,1 + c

14、1,2c0,3 + c0,4 = c1,3 + c1,4Securityc0,1 + c0,3 = c1,1 + c1,3c0,2 + c0,4 = c1,2 + c1,4Contrast: = q1(1, 2) q0(1, 2)X = 1 p0(0) = c0,1 + c0,2p0(1) = c0,3 + c0,4XX = 2Y = 1, 2q0(1, 2) = c0,2 + c0,3 + c0,4p0(0) = c0,1 + c0,3p0(1) = c0,2 + c0,41e2,1 = 0 e2,2 = 1e = 1 e = 0e = 1 e = 1P1(0) = c1,1 + c1,2P

15、1(1) = c1,3 + c1,4P1(0) = c1,1 + c1,3P1(1) = c1,2 + c1,4q1(1, 2) = c1,2 + c1,3 + c1,4X F UX 0, 1|X| q0(Y) q1(Y) Y Q p0(UX) p1(UX) q0(Y) q1(Y) 2 X p0(UX) = p1(UX) SH1 c0,1 + c0,2 = c1,1 + c1,2 c0,3 + c0,4 = c1,3 + c1,4 SH2 c0,1 + c0,3 = c1,1 + c1,3 c0,2 + c0,4 = c1,2 + c1,4 SH1 SH2 c0,1 + c0,2 + c0,3

16、 + c0,4 = 1 c1,1 + c1,2 + c1,3 + c1,4 = 1 c0,3 + c0,4 = c1,3 + c1,4 c0,2 + c0,4 = c1,2 + c1,4 (SH1+SH2) q1(1, 2) q0(1, 2) = q1(1, 2) q0(1, 2) = (c1,2 + c1,3 + c1,4) (c0,2 + c0,3 + c0,4) (2, 2)-threshold (1)max.=(c1,2+c1,3+c1,4)(c0,2+c0,3+c0,4).s.t.(c0,3+c0,4)(c1,3+c1,4)=0; (1) (c0,2+c0,4)(c1,2+c1,4)

17、=0;4ci,j=1, for i=0, 1;j=10ci,j1, for all i,j. (2,114 2)-threshold c0,1c0,2c0,3c0,4=0.50.00.00.5 (2)c1,1c1,2c1,3c1,40.00.50.50.0 = 0.5 (2, 2)-threshold E = ej,k 2n×n ej,k 0, 1 E P E Ej = ej,1, ej,2, , ej,n n = 3 Ej = 1, 0, 0 j C = ci,j 2×2n ci,j 0, 1 i 0, 1 j 1, 2, , 2nn2j=1ci,j=1 (3) C c0

18、,j c1,j j Ej 2 (2, 2)-threshold 00E =01(4) 10 11C=c0,1c0,2c0,3c0,4c(5)1,1c1,2c1,3c 1,4 C c0,1 0, 0 c1,2 0, 1 p0(UX) p1(UX) X = l1, l2, , lr F UX 0, 1|X| X X F UX 0, 1|X| p0(UX) = p1(UX) p0(UX) = p1(UX) X p0(UX) p1(UX) (k, n)-threshold k = 3 SHi SHj (0, 0) (0, 1) (1, 0) (1, 1) SHi SHj SHi SHj (0, 0)

19、(0, 1) (1, 0) (1, 1) SHi SHj (0, 0) (0, 1) (1, 0) (1, 1) x = (x1,x2, x3, x4) y = (y1,y2, y3, y4) x = y SHi SHj p0(UX) p1(UX) 2npi(UX) =ci,jg(UX,Vj) (6) j=1i 0, 1 Vj = (ej,l1, ej,l2, , ej,lr)g(U1if UX=VjX,Vj)=(7) 0elseq0(Y) q1(Y) Y = l1, l2, , lr Q 2nqi(Y)=ci,j(ej,lej,l.ej,lj12r) (8) =1i 0, 1 YY = q1

20、(Y) q0(Y) (9)Y Y Y Y 115Y (inverse) (Tzeng and Hu 2002)Y = |q1(Y) q0(Y)| (10)(9) = (P, F, Q) = (P, F, Q) (11) (11) 2n 2n+1 0 1 1 X F X 2|X| |XF2|X Y Q |Q| (1) 116 maxY=q1(Y)q0(Y), for all YQ.s.t.p)=p U|X|0(UnX1(UX), for all XF,X0, 1; (11) 2c, for i=0, 1;i,j=1j=1c 1, for all i,j.i,j0,(11) (multi-obje

21、ctive optimization model) (multi-objective linear programming model) Droste (1996) S-Extended n out of n Schemes n out of n n out of n 1/2n1(Naor and Shamir1995) Droste 2n+1 n n Hou & Hsu (2004) P = 1, 2, 3, 4 Q = 1, 4, 3, 4, 1, 2, 3, 1, 2, 4, 1, 3, 4, 2, 3, 4, 1, 2, 3, 4 F = 2P Q E0000000011111

22、111TE=000011110000111100110011001100110101010101010101 Hou & Hsu CC=0.30.00.00.00.10.00.00.10.00.00.00.40.00.10.00.00.00.20.00.10.00.20.00.00.00.10.30.00.00.00.10.01, 4 = 0.4 3, 4 = 0.4 1, 2, 3 = 0.1 1, 2, 4 = 0.3 1, 3, 4 = 0.4 2, 3, 4 = 0.3 1, 2, 3, 4 = 0.3 1, 4 3, 4 1, 2, 4 1, 3, 4 2, 3, 4 1,

23、2, 3, 4 100% ( 1 ) Ateniese et al. (1996b)1, 4 = 0.2 3, 4 = 0.2 1, 2, 3 = 0.2 1, 2,4 = 0.2 1, 3, 4 = 0.2 2, 3, 4 = 0.21, 2, 3,4 = 0.41, 2, 3, 4 100% Ateniese et al. 37.5% Ateniese et al. 5 117(a) (b) SH1(c) SH2(d) SH3(e) SH4(f) SH1+SH2(g) SH1+SH3(h) SH1+SH4(i) SH2+SH3(j) SH2+SH4(k) SH3+SH4(l) SH1+SH

24、2+SH3(m) SH1+SH2+SH4(n) SH1+SH3+SH4(o) SH2+SH3+SH4(p) SH1+SH2+SH3+SH41 (400×200 pixels, 300 dpi) 25 ( ) C ( ) n ( ) n 1/2x×y x y 1 400×200 pixels ( SH1 SH2) ( 1(a) 1/280000 (halftoning) 118 (a) (b)2 (512×512 pixels, 300 dpi)(continuous-tone image)(bi-level image) ( )() ( 2(a) ( 2

25、(b) 2(b) ordered dither error diffusion blue noise masks green noise halftoning direct binary search dot diffusion (Mese and Vaidyanathan 2002) 119 2(b) (2) C 3 3(c) (SH1+SH2) 2(a) | |/ (2, 2)-threshold = 1/2 50%*( 2(b) 3(c) ) (2, 3)-threshold * = 1/3 (Blundo et al. 1999) 67% 100% (dynamic range) (a

26、) SH1(b) SH2(c) SH1+SH23 (512×512 pixels, 300dpi)120 x×y (x×y)/(t×t) t×t b < t2/2 b > t2/2 b = t2/2 a) x×y HI (x×y)/(t×t) t×tb) HI t×t B bc) B if b < t2/2 thenB C else if b > t2/2 thenB CelseB Cd)(b)-(c) 121(a) SH1(b) SH2(c) SH1+SH24 2

27、15;2 (512×512 pixels, 300dpi) 2(b) 512×512 pixels 65536 2×2 2×2 (2) C 4 16384 4×4 4×4 (2) C 5 3(c) 4(c) 5(c) 3(c) 4(c) 5(c) 2×2 4×4 (a) SH1(b) SH2(c) SH1+SH25 4×4 (512×512 pixels, 300dpi)122 2×2 Hou & Hsu (2004) j = 0, 1, , g 1 n×m Aj j

28、 Aj Aj i i m 2×2 1231. Ateniese, G., Blundo, C., De Santis, A., and Stinson, D. R. “Constructions and Bounds for Visual Cryptography,” in 23rd International Colloquium on Automata, 8.Cryptology-CRYPTO 96, LNCS 1109, Springer-Verlag, 1996, pp. 401-415. Eisen, P. A., and Stinson, D. R. “Threshold

29、 Visual Cryptography Schemes Languages and Programming (ICALP 96), LNCS 1099, 1996a, pp. 416-428.2. Ateniese, G., Blundo, C., De Santis, A., and Stinson, D. R. “Visual Cryptography for General Access Structures,”Information and Computation (129:2), 1996b, pp. 86-106.3. Ateniese, G., Blundo, C., De S

30、antis, A., and Stinson, D. R. “Extended Capabilities for Visual Cryptography,” Theoretical Computer Science (250:1-2), 2001, pp. 143-161.4. Blundo, C., De Bonis, A., and De Santis, A. “Improved Schemes for Visual Cryptography,” Designs, Codes and Cryptography (24), 2001, pp. 255-278.5.Blundo, C., an

31、d De Santis, A. “Visual Cryptography Schemes with Perfect Reconstruction of Black Pixels,” Computer & Graphics (12:4), 1998, pp. 449-455. 6.Blundo, C., De Santis, A., and Stinson, D. R. “On the Contrast in Visual Cryptography Schemes,” Journal of Cryptology (12:4), 1999, pp. 261-289. 7.Droste, S

32、. “New Results on Visual Cryptography,” in Advances inwith Specified Whiteness Levels of Reconstructed Pixels,” Designs, Codes and Cryptography (25), 2002, pp. 15-61. 9.Gonzalez, R. C., and Woods, R. E. Digital Image Processing, 2nd Edition, Prentice-Hall, New Jersey, 2002.10. Hofmeister, T., Krause

33、, M., and Simon, H.U. “Contrast-optimal k out of n Secret Sharing Schemes in Visual Cryptography,” Theoretical Computer Science (240), 2000, pp. 471-485. 11. Hou, Y. C. “Visual Cryptography forColor Images,” Pattern Recognition (36), 2003, pp. 1619-1629.12. Hou, Y. C., and Hsu, C. S. “A Probability-

34、based Model for Visual Secret Sharing Schemes without Pixel Expansion,” accepted by Journal of Information Management, 2004 (In Chinese).13. Hou, Y. C., Lin, F., and Chang, C. Y.“Visual Cryptography for Color Images without Pixel Expansion,” Journal of Technology (16:4), 2001, pp. 595-603 (In Chinese).14. Iwamoto, M. and Yamamoto, H. “AConstruction Method of Visual Secret124 Sharing Schemes for Plural Secret Images,” Fundamentals (86-A:10), 2003, pp.Springer-Verlag, 1995, pp. 1-12.Approach for Visual Cryptography,” IEICE Transactions on 20. Tzeng, W. G., and Hu, C. M. “A New