臺灣博碩士論文加值系統

Adi Shamir 提出了一個著名的祕密分享的方法。這個方法可以將一個資料 D 分成 n 份，使得當有 k 份以上時可以輕易的重建 D，但是你無法獲得 D 的任何資訊即使你有了 k-1份。這樣的方法稱為(k,n) threshold scheme。
針對影像的分享，Naor 和 Shamir 更進一步提出了視覺密碼的想法。它可以被視為是(k,n) threshold scheme在視覺上的變形，對於一張祕密影像，n個參與者每個人都會得到一張投影片；當有任意k個以上的參與者可以藉由疊合他們的投影片來看到祕密影像，但是當不足k個參與者時則無法得到任何訊息。
我們在這篇論文裡提出了一個新的視覺密碼的建構演算法。首先，我們將SFCOD做推廣來將一張灰階影像轉換成灰階值較少的影像。除此之外，我們推廣基本的視覺密碼模型使它能處理兩種以上的灰階值。然後，這個推廣後的視覺密碼模型便能被用來編碼這張影像。這個方法滿足了安全和對比的條件。它在解碼過的影像裡可以比一般的視覺密碼的方法顯示更多原圖的細節。最後，還包括了推廣我們的方法去處理彩色影像。

Adi Shamir proposed a well-known technique for secret sharing. This technique can divide data D into n pieces in such a way that any k pieces can easily reconstruct D, but no information about D will be revealed even with complete knowledge of k-1 pieces. Such scheme is called a (k,n) threshold scheme.

Naor and Shamir proposed further the idea of visual cryptography for sharing images. It can be seen as a visual variant of the k out of n secret sharing problem, in which each one of the n users gets a transparency; any k of them can see the image by stacking their transparencies, but any k-1 of them gain no information about it.

In this paper a new construction algorithm of visual cryptography is presented. First, we extend SFCOD (Space Filling Curve Ordered Dither – one of the techniques of halftoning) to transform a gray-level image into an image with fewer grayscale values. In addition, we extend the basic visual cryptography model to handle more than two grayscale values. Then the extended visual cryptography model can be applied to encode this image. This scheme satisfies the security and contrast conditions. It can reveal more details of original images in the decoded images than ordinary visual cryptography scheme. At last, an extension of this scheme for color images is included.

List of Contents


ABSTRACT (in Chinese) i

ABSTRACT (in English) ii

ACKNOWLEDGEMENTS iii

List of Contents iv

List of Figures v

Chapter 1 Introduction 1

Chapter 2 Review of Space Filling Curve Ordered Dither Technique and Basic Visual Cryptography Model 3
2.1 Review of Space Filling Curve Ordered Dither 3
2.2 Review of Basic Visual Cryptography Model 5
Chapter 3 The Proposed Extended SFCOD Technique and Extended Visual Cryptography Model 12
3.1 The Proposed Extended SFCOD 12
3.2 The Proposed Extended Visual Cryptography Model 15
3.3 Algorithm for Encrypting a Gray-level Image 18
3.4 Algorithm for Encrypting a Color Image 19
Chapter 4 Simulations 23

Chapter 5 Conclusion 33

Reference 34




List of Figures
1. The process of using a Hilbert curve to divide the pixels of an 8×8 image into 16 classes. (a) A traversal curve of an 8x8 image. (b) The map of the traversal order of (a). (c) The traversal order of (a) mod 16. (d) The traversal curves of 4 4x4 images 4
2. The shares and decoded white pixel of the example of (3,3)-threshold visual cryptography. (a) The visual pattern of share1, (b) the visual pattern of share2, (c) the visual pattern of share3, (d) decoding result of a white pixel 9
3. The shares and decoded black pixel of the example of (3,3)-threshold visual cryptography. (a) The visual pattern of share1, (b) the visual pattern of share2, (c) the visual pattern of share3, (d) decoding result of a black pixel 10
4. Experiment results of the ESFCOD algorithm. (a) The original image. (b) The image halftoned by the ESFCOD algorithm, where . (c) The image transformed by the SFCOD algorithm. (d) The transformed image with 4 grayscales by simple threshoding 14
5. The flowchart of the new construction principle for grey level images 21
6. The flowchart of the new construction principle for color images 22
7. (a) The original Elaine image, (b) the image after using extended SFCOD, (c) the share1 with grayscale values 0, 20, 200, and 255, (d) the share2 with grayscale values 0, 20, 200, and 255, (e) the decoded image 24
8. (a) The original boat image, (b) the image after using extended SFCOD, (c) the share1 with grayscale values 0, 20, 200, and 255, (d) the share2 with grayscale values 0, 20, 200, and 255, (e) the decoded image 25
9. (a) The original Lena image, (b) the C component of (a), (c) the M component of (a), (d) the Y component of (a) 27
10. (a) The image of Fig. 9(b) after using extended SFCOD, (b) the image of Fig. 9(c) after using extended SFCOD, (c) the image of Fig. 9(d) after using extended SFCOD 28
11. (a) The share1 of Fig. 10(a), (b) the share2 of Fig. 10(a), (c) the share1 of Fig. 10(b), (d) the share2 of Fig. 10(b), (e) the share1 of Fig. 10(c), (f) the share2 of Fig. 10(c) 28
12. (a) The share image 1 by combining Fig. 11(a), Fig. 11(c), and Fig. 11(e), (b) The share image 2 by combining Fig. 11(b), Fig. 11(d), and Fig. 11(f), (c) the decoding image by stacking (a) and (b) 29
13. (a) The original baboon image, (b) the C component of (a), (c) the M component of (a), (d) the Y component of (a) 29
14. (a) The image of Fig. 13(b) after using extended SFCOD, (b) the image of Fig. 13(c) after using extended SFCOD, (c) the image of Fig. 13(d) after using extended SFCOD 30
15. (a) The share1 of Fig. 14(a), (b) the share2 of Fig. 14(a), (c) the share1 of Fig. 14(b), (d) the share2 of Fig. 14(b), (e) the share1 of Fig. 14(c), (f) the share2 of Fig. 14(c) 31
16. (a) The share image 1 by combining Fig. 15(a), Fig. 15(c), and Fig. 15(e), (b) The share image 2 by combining Fig. 15(b), Fig. 15(d), and Fig. 15(f), (c) the decoding image by stacking (a) and (b) 32

[1] A. Shamir, How to share a secret, Communications of the ACM, 22(11): 612- 613, November 1979.
[2] M. Naor, A. Shamir, Visual Cryptography, Advances in Cryptography – Eurocrypt ’94, pp. 1-12, 1995.
[3] G. Ateniese, C. Blundo, A. D. Santis, D. R. Stinson. Visual Cryptography for General Access Structure, Information and Computation, 129 (2), pp. 86--106, 1996.
[4] M. Naor, B. Pinkas, Visual Authentication and Identification, Lecture Notes in Computer Science.
[5] Chang, C. C. and Chuang, J. C., An Image Intellectual Property Protection Scheme for Gray-level Images Using Visual Secret Sharing Stragegy, Pattern Recognition Letters, Vol. 23, No. 8, 2003, pp. 931-941.
[6] E.R.Verheul, Henk C.A. Van Tilborg, Constructions and Properties of k out of n Visual Secret Sharing Schemes, Designs, Codes and Cryptography, Volume 11, Issue 2 (May 1997), Pages: 179 – 196.
[7] C. C. Lin and W. H. Tsai, Visual Cryptography for Gray-level Images by Dithering Technique, Pattern Recognition Letters 24 (2003) 349-358.
[8] Yuefeng Zhang, Space-filling Curve Ordered Dither, Computers & Graphics 22(4): 559-563 (1998).
[9] Young-Chang Hou, Visual Cryptography for color images, Pattern Recognition 36 (2003) 1619-1629.