臺灣博碩士論文加值系統

在這篇論文中，我們探討了兩個研究課題，分別為視覺機密分享以及視覺機密顯示，其目的都在保護機密的設計中結合了人類視覺能力。本論文針對視覺機密分享研究提出像素擴張最佳化的設計方法，而針對視覺機密顯示研究提出同時保護多個機密的設計方法。
對於視覺機密分享研究，加密技術將機密加密後產生多張分享影像並列印輸出在投影片，每位參與者都會拿到一張投影片，在參與者中，只有合法群組才能利用投影片解密辨識出機密。視覺機密分享的特色在於解密技術僅利用人類視覺系統來解密，不需使用任何擁有計算能力的設備、複雜精細的光學儀器或是密碼學技巧。針對不同存取結構、不同機密個數或是不同機密顏色等考量，視覺機密分享研究已經發展出一系列相關課題；其中，視覺機密分享研究的目標之一是設計擁有最少像素擴張的視覺機密分享方法。本論文針對不同存取結構考量探討兩個基本視覺機密分享課題：門檻存取結構以及一般化存取結構。本論文針對這些課題建立線性規劃模型進而設計像素擴張最佳化的視覺機密分享方法，提出的線性規劃模型不僅成功地達到像素擴張最佳化的視覺機密分享，改進了現有最好的像素擴張數值，也可以根據不同考量的視覺機密分享課題輕易地修改建立對應的線性規劃模型。
對於視覺機密顯示研究，目標是在基於螢幕與遮罩架構下利用人類視覺系統來保護在螢幕顯示的機密以防止窺看。在螢幕與遮罩架構下，只有站在預先訂定的限制範圍內，合法瀏覽者利用手上的遮罩才能瀏覽螢幕顯示的機密。探討的課題包含了多個機密、多個遮罩、黑白機密、彩色機密以及螢幕與遮罩的數個關係等考量。本論文首先將視覺機密分享方法應用在視覺機密顯示，達到視覺機密顯示目的和有效的機密大小擴張。本論文也根據人類視覺系統對於調控顏色的視覺反應設計一系列視覺機密顯示方法，即使在螢幕顯示完整機密狀態下，仍能成功地達到在不同考量下的視覺機密顯示。

This dissertation studies both the problems of visual secret sharing and visual secret display which integrate the human visual intelligence into the design of securing the secret. We aim at designing the schemes for visual secret sharing with an efficient pixel expansion and the schemes for visual secret display with respect to multiple binary secrets as well as color secrets.
Visual secret sharing is a cryptographic technique for distributing the secret image among the participants in such a way that the secret is encrypted into the shares of transparencies which are distributed into the participants and is decrypted by the qualified groups of participants by superimposing their shares. The innovative feature of visual secret sharing is that the decoding process relies only on human visual system without any computing device, complicated optical equipment, nor cryptographic knowledge. Many sub-problems concerning the various types of access structures, different number of secrets, particular colors of the secret, etc. are studied. With regard to design of the visual secret sharing scheme, one of the most important factors is the pixel expansion which enlarges the size of the secret in the shares and is expected as small as possible. We study two fundamental problems of visual secret sharing: threshold visual secret sharing and visual secret sharing for general access structures, and propose the approaches to design the schemes achieving the optimization of the pixel expansion. The existing best pixel expansion of both fundamental visual secret sharing problems has never been improved since 1996. The computational studies demonstrate that our approaches are not only effective for minimizing the pixel expansion but also flexible for different considerations of visual secret sharing.
On the other hand, visual secret display is to protect the secret information that is displayed on the screen against the unauthorized peeping attack. Based on the mechanism of the display and the masks, the authorized participant is able to visually perceive the secret from the screen by using their own transparencies while standing within a limited viewing zone. We apply the approaches devised for visual secret sharing to achieve visual secret display on securing one secret with an efficient expanding size. We also examine the visual effects on the binary images as well as the color images and conclude several primitive color features to the human visual system. By utilizing these valuable and interesting features, we provide the schemes for the visual secret display problem under various considerations such as different number of secrets and particular relationships among the display and the masks. Even the display keeps showing the secrets without losing any information; we effectively secure the displayed secrets among the display and the masks and recover the secrets to our eyes from the display through the corresponding masks. Moreover, the experimental results indicate that our schemes successfully achieve the visual secret display for secreting multiple secrets including the binary secret images as well as the color secret images.

1 Introduction 1
1.1 Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Manuscript. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Visual Secret Sharing and Visual Secret Display 6
2.1 Visual Secret Sharing and Related Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Visual Secret Display and Related Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Scope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Optimization in Visual Secret Sharing Schemes 30
3.1 Integer Linear Programming for Visual Secret Sharing Scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Optimization of Pixel Expansion in Threshold Visual Secret Sharing Scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Optimization of Pixel Expansion in Visual Secret Sharing Scheme for General Access Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Application of Visual Secret Sharing Schemes to Visual Secret Display 63
4.1 Visual Secret Display for One Binary Secret. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.1 Visual Secret Display with Threshold Access Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.2 Visual Secret Display with General Access Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Visual Secret Display for Multiple Binary Secrets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1 Visual Effect on the Binary Image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.2 Schemes of Visual Secret Display for Multiple Binary Secrets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3 Visual Secret Display for Multiple Color Secrets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 Visual Effect on the Color Image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.2 Schemes of Visual Secret Display for Multiple Color Secrets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5 Conclusions 103
5.1 Concluding Remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.2 Future Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Bibliography 106

[1] R. Anderson, "Why Cryptosystems Fail," Communications of the ACM, vol. 37, no. 11, 1994, pp. 32-40.
[2] G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson, "Constructions and Bounds for Visual Cryptography," Lecture Notes in Computer Science, vol. 1099, 1996, pp. 416-428.
[3] G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson, "Visual Cryptography for General Access Structures," Information and Computation, vol. 129, 1996, pp. 86-106.
[4] G. R. Blakley, "Safeguarding Cryptographic Keys," Proceedings of the National Computer Conference, vol. 48, 1979, pp. 313-317.
[5] C. Blundo, S. Cimato, and A. De Santis, "Visual Cryptography Schemes with Optimal Pixel Expansion," Theoretical Computer Science, vol. 369, 2006, pp. 169-182.
[6] C. Blundo, P. D''Arco, A. De Santis, and D. R. Stinson, "Contrast Optimal Threshold Visual Cryptography Schemes," SIAM Journal on Discrete Mathematics, vol. 16, 2003, pp. 224-261.
[7] C. Blundo and A. De Santis, "Visual Cryptography Schemes with Perfect Reconstruction of Black Pixels," Computers and Graphics, vol. 22, 1998, pp. 449-455.
[8] C. Blundo, A. De Santis, and D. R. Stinson, "On the Contrast in Visual Cryptography Schemes," Journal of Cryptology, vol. 12, 1999, pp. 261-289.
[9] C. Blundo, A. De Bonis, and A. De Santis, "Improved Schemes for Visual Cryptography," Designs, Codes and Cryptography, vol. 24, 2001, pp. 255-278.
[10] Bongo, available at http://www.captcha.net/captchas/bongo/, The CAPTCHA Project, 2002.
[11] M. Bose and R. Mukerjee, "Optimal (k, n) Visual Cryptographic Schemes for General k," Designs, Codes and Cryptography, vol. 55, 2010, pp. 19-35.
[12] S. Cimato, R. De Prisco, and A. De Santis, "Optimal Colored Threshold Visual Cryptography Schemes," Designs, Codes and Cryptography, vol. 35, 2005, pp. 311-335.
[13] S. Cimato1, R. De Prisco, and A. De Santis, "Probabilistic Visual Cryptography Schemes," The Computer Journal, vol. 49, 2006, pp. 97-107.
[14] A. L. Coates, H. S. Baird, and R. J. Fateman, "Pessimal Print: A Reverse Turing Test," In Proceedings of the 6th International Conference on Document Analysis and Recognition, 2001, pp. 1154-1158.
[15] R. Dhamija and A. Perrig, "D?j? vu: A user study using images for authentication," In Proceedings of the 9th USENIX Security Symposium, 2000, pp. 45-58.
[16] D. Dolev and A. C. Yao, "On the security of public key protocols," IEEE Transactions on Information Theory, vol. 29, 1983, pp. 198-208.
[17] S. Droste, "New Results on Visual Cryptography," Advances in Cryptography-CRYPTO''96, Lecture Notes in Computer Science, vol. 1109, 1996, pp. 401-415.
[18] P. Dunphy, J. Nicholson, and P. Olivier, "Securing PassFaces for Description," Symposium on Usable Privacy and Security, ACM International Conference Proceedings, vol. 337, 2008, pp. 24-35.
[19] P. A. Eisen and D. R. Stinson, "Threshold Visual Cryptography Schemes with Specified Whiteness Levels of Reconstructed Pixels," Designs, Codes and Cryptography, vol. 25, 2002, pp. 15-61.
[20] Gimpy, available at http://www.captcha.net/captchas/gimpy/, The CAPTCHA Project, 2002.
[21] T. Hofmeister, M. Krause, and H. U. Simon, "Contrast-Optimal k out of n Secret Sharing Schemes in Visual Cryptography," Theoretical Computer Science, vol. 240, 2000, pp. 471-485.
[22] Y. C. Hou, "Visual cryptography for color images," Pattern Recognition, vol. 36, 2003, pp. 1619-1629.
[23] C. S. Hsu and Y. C. Hou, "Goal-programming-assisted Visual Cryptography Method with Unexpanded Shadow Images for General Access Structures," Optical Engineering, vol. 45, 2006, pp. 097001-1-10.
[24] The HumanAUT (Human AUThentication) Cryptographic Project, available at http://www.aladdin.cs.cmu.edu/reu/mini_probes/2003/humanaut.html, The Carnegie Mellon University, 2004.
[25] R. Ito, H. Kuwakado, and H. Tanaka, "Image Size Invariant Visual Cryptography," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, vol. E82-A, 1999, pp. 2172-2177.
[26] B. Javidi and T. Nomura, "Securing information by use of digital holography," Optics Letters, vol. 25, 2000, pp. 28-30.
[27] T. Katoh and H. Imai, "An Extended Construction Method for Visual Secret Sharing Schemes," Electronics and Communications in Japan (Part III: Fundamental Electronic Science), vol. 81, 1998, pp. 55-63.
[28] T. Katoh and H. Imai, "An Extended Construction Method of Visual Secret Sharing Scheme," IEICE Transactions on Fundamentals of Electronics, vol. J79-A, no. 8, 1996, pp. 1344-1351.
[29] T. Katoh and H. Imai, "Some Visual Secret Sharing Schemes and Their Share Size," Joint Conference of International Computer Symposium, 1996, pp. 41-47.
[30] K. Kobara and H. Imai, "Limiting the visible space visual secret sharing schemes and their application to human identification," Lecture Notes In Computer Science, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, vol. 1163, 1996, pp. 185-195.
[31] S. Man, D. Hong, and M. Matthews, "A shoulder-surfing resistant graphical password scheme - WIW," International Conference on Security and Management, 2003, pp. 105-111.
[32] O. Matoba and B. Javidi, "Optical retrieval of encrypted digital holograms for secure real-time display," Optics Letters, vol. 27, 2002, pp. 321-323.
[33] X. F. Meng, L. Z. Cai, X. L. Yang, X. X. Shen, and G. Y. Dong, "Information security system by iterative multiple-phase retrieval and pixel random permutation," Applied Optics, vol. 45, 2006, pp. 3289-3297.
[34] P. C. Mogensen and J. Gluckstad, "Phase-only optical decryption of a fixed mask," Applied Optics, vol. 40, 2001, pp. 1226-1235.
[35] P. C. Mogensen and J. Gluckstad, "Phase-only optical encryption," Optics Letters, vol. 25, 2000, pp. 566-568.
[36] G. Mori and J. Malik, "Recognizing Objects in Adversarial Clutter: Breaking a Visual CAPTCHA ," IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, 2003, pp. 134-141.
[37] M. Naor, "Verification of a Human in The Loop or Identification via the Turing Test," unpublished, 1996, available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.6383.
[38] M. Naor and A. Shamir, "Visual Cryptography," in: A. De Santis (Ed.), Advances in Cryptology: Eurpocrypt''94, Lecture Notes in Computer Science, vol. 950, Springer, Berlin, 1995, pp. 1-12.
[39] T. Nomura and B. Javidi, "Optical encryption using a joint transform correlator architecture," Optical Engineering, vol. 39, 2000, pp. 2031-2035.
[40] Pix, Available at http://www.captcha.net/captchas/pix/, The CAPTCHA Project, 2002.
[41] P. Refregier and B. Javidi, "Optical image encryption based on input plane and Fourier plane random encoding," Optics Letters, vol. 20, 1995, pp. 767-769.
[42] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems," Communications of the ACM, vol. 21, no. 2, 1978, pp. 120-126.
[43] A. Shamir, "How to Share a Secret," Communications of the ACM, vol. 22, 1979, pp. 612-613.
[44] S. J. Shyu, "Efficient visual secret sharing scheme for color images," Pattern Recognition, vol. 39, 2006, pp. 866-880.
[45] S. J. Shyu and M. C. Chen, "The Optimized Pixel Expansion and Basis Matrices in (k, n)-VCS by Integer Linear Program," technical report, 2010, available at http://www.csie.mcu.edu.tw/~sjshyu/tvcs_lp/tvcs_lp.html.
[46] S. J. Shyu and M. C. Chen, "The Optimized Pixel Expansion and Basis Matrices in VCS for General Access Structures by Integer Linear Program," technical report, 2010, available at http://www.csie.mcu.edu.tw/~sjshyu/vcsgas_lp/vcsgas_lp.html.
[47] G. J. Simmons, W. A. Jackson, and K. M. Martin, "The Geometry of Shared Secret Schemes," Bulletin of the Institute of Combinatorics and its Applications, 1991, pp. 71-88.
[48] V. Sorensen, "PassPic (formerly ADS Security Wizared) - Visual password management," Available at http://www.authord.com/products/PassPic/.
[49] W. Stallings, "Cryptography and Network Security: Principles and Practice," Prentice Hall, 2006.
[50] W. G. Tzeng and C. M. Hu, "A New Approach for Visual Cryptography," Designs, Codes and Cryptography, vol. 27, 2002, pp. 207-227.
[51] G. Unnikrishnan, M. Pohit, and K. Singh, "A polarization encoded optical encryption system using ferroelectric spatial light modulator," Optics Communications, vol. 185, 2000, pp. 25-31.
[52] E. R. Verheul and H. C. A. Van Tilborg, "Constructions and Properties of k out of n Visual Secret Sharing Schemes," Designs, Codes and Cryptography, vol. 11, 1997, pp. 179-196.
[53] L. von Ahn, M. Blum, and J. Langford, "Telling Humans and Computers Apart (Automatically) or How Lazy Cryptographers Do AI," technical report, The CAPTCHA Project, Available at http://www.captcha.net/, 2002.
[54] C. H. Wang, T. Hwang, and J. J. Tsai, "On the Matsumoto and Imai''s Human Identification Scheme," Advances in Cryptology-EUROCRYPT''95, Lecture Notes in Computer Science, vol. 921, 1995, pp. 382-392.
[55] R. K. Wang, I. A. Watson, and C. R. Chatwin, "Random phase encoding for optical security," Optical Engineering, vol. 35, 1996, pp. 2464-2469.
[56] H. Yamamoto and Y. Hayasaki, "Secure display that limits the viewing space by use of optically decodable encryption," Proceedings of SPIE, vol. 6482, 2007, pp. 64820C-1-10.
[57] H. Yamamoto, Y. Hayasaki, and N. Nishida, "Securing display of grayscale and multicolored images by use of visual cryptography," Proceedings of SPIE, vol. 5306, 2004, pp. 716-724.
[58] H. Yamamoto, Y. Hayasaki, and N. Nishida, "Secure information display by use of multiple decoding masks," Proceedings of SPIE, vol. 5600, 2004, pp. 192-199.
[59] H. Yamamoto, Y. Hayasaki, and N. Nishida, "Securing information display by use of visual cryptography," Optics Letters, vol. 28, 2003, pp. 1564-1566.
[60] H. Yamamoto, Y. Hayasaki, and N. Nishida, "Secure Information Display with Limited Viewing Zone by Use of Multi-Color Visual Cryptography," Optics Express, vol. 12, 2004, pp. 1258-1270.
[61] H. Yamamoto, Y. Hayasaki, and N. Nishida, "Secure Information Display with Two Limited Viewing Zones Using Two Decoding Masks Based on Visual Secret Sharing Scheme," Japanese Journal of Applied Physics, Part 2. Letters, vol. 44, 2005, pp. 1803-1807.
[62] C. N. Yang, "New Visual Secret Sharing Schemes Using Probabilistic Method," Pattern Recognition Letters, vol. 25, 2004, pp. 481-494.
[63] Z. Zalevsky, D. Mendlovic, U. Levy, and G. Shabtay, "A New Optical Random Coding Technique for Security Systems," Optics Communications, vol. 180, 2000, pp. 15-20.