臺灣博碩士論文加值系統

在這數位化的資訊時代，資訊安全已成為一個重要的議題，視覺密碼 (visual cryptography) 這個新興的資訊安全技術便在此背景下產生。視覺密碼引人注目之處在於不需要任何密碼學的知識；只須將機密影像編碼成多張雜亂的分享影像 (投影片)，解密時也沒有複雜的計算過程，直接疊合這些分享影像，即可利用人類視覺系統判讀顯示的機密影像。
Naor 與 Shamir [3] 在 EuroCrypt’94 提出視覺密碼至今已超過 15 年，相關研究文獻已相當豐富，包括：門檻型 (threshold) 視覺密碼機制、一般存取結構 (general access structure)、擴充型 (extended) 視覺密碼機制、隨參與者漸增可看內容的漸增型 (incremental) 視覺密碼機制、雜亂格點 (random grids) 為基礎的視覺密碼機制、分享多張機密影像的 (multiple secrets) 視覺密碼機制、…… 等等。研究者通常以分享影像之像素擴張、還原之機密影像的對比及分享影像的雜亂程度，做為視覺密碼機制優劣的衡量標準。
本碩士論文提出三種視覺多重機密分享機制，以整數線性規劃 (integer linear programming) 分別求取最小化像素擴張解，並分別提出適合整數線性規劃的視覺多重機密分享機制之定義。

As the amount of digital information and the spread via various communication networks grow nowadays, the information security becomes an important issue. Visual Cryptography was proposed in this circumstance. The most attractive merit of Visual Cryptography is that the decoding process relies on the human visual system instead of any computing device.
It has been more than fifteen years since Naor and Shamir proposed Visual Cryptography in EuroCrypt’94. Fruitful research results in this area can be found in the literature reviews including threshold visual cryptographic schemes (VCS), VCS for general access structures, VCS for extended capabilities, incremental VCS, visual cryptograms of random grids, VCS for multiple secrets, just to name a few. The measurements of a VCS include the pixel expansion, contrast and randomness.
This thesis adopts integer linear programming to minimize pixel expansions for the proposed three kinds of visual multiple secret sharing schemes by lp_solve and proposes the new defitions such that we can model our approaches into an integer linear programming easily.

摘　要 i
ABSTRACT ii
誌　謝 iii
目　錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 2
1.4 論文架構 3
第二章 文獻探討 4
2.1 (k, n) 視覺密碼機制 4
2.1.1 線性系統建構 (k, n) 視覺密碼機制 7
2.1.2 線性規劃建構 (k, n) 視覺密碼機制 11
2.2 一般存取結構 17
2.3 視覺多重機密分享機制 19
2.4.1 S-extended n out of n scheme 20
2.4.2 (2, 3, 3) 視覺密碼機制 23
2.4 彩色視覺密碼 26
2.5.1 色彩表示法 26
2.5.2 半色調技術 29
2.5.3 分色半色調 29
2.5.4 Hou 的彩色視覺密碼機制 30
第三章 視覺多重機密分享機制 33
3.1 (k, n, s) 視覺密碼機制 33
3.1.1 單元矩陣建構 (k, n, s) 視覺密碼機制 35
3.1.2 原始矩陣建構 (k, n, s) 視覺密碼機制 41
3.2 一般存取結構中的視覺多重機密分享 48
3.3 S-extended 視覺密碼機制 57
第四章 實驗結果 64
4.1 程式簡介 64
4.2 (k, n, s) 視覺密碼機制實驗結果 64
4.3 一般存取結構中的視覺多重機密分享實驗結果 73
4.4 S-extended 視覺密碼機制實驗結果 77
4.5 lp_solve 執行效率探討 82
第五章 結論與未來研究 85
參考文獻 86
附錄 A、程式操作 92

[1] A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, pp. 612-613, 1979.
[2] G. R. Blakley, “Safeguarding cryptographic keys,” Proc. National Computer Symp., vol. 48, pp. 313-317, 1979.
[3] M. Naor and A. Shamir, “Visual cryptography,” Advances in Cryptography: Eurpocrypt’1994, Lecture Notes in Computer Science, vol. 950, pp. 1-12, 1995.
[4] G. Ateniese, C. Blundo, A. De Santis and D. R. Stinson, “Constructions and bounds for visual crptography,” International Colloquium on Automata, Languages and Programming (ICALP’1996), vol. 1099, pp. 416-428, 1996.
[5] S. Droste, “New results on visual cryptography,” Advances in Cryptography-CRYPTO’1996, Lecture Notes in Computer Science, vol. 1109, pp. 401-415, 1996.
[6] E. R. Verheul and H. C. A. Van Tilberg, “Constructions and properties of k out of n visual secret sharing schemes,” Design, Codes and Cryptography, vol. 11, pp. 179-196, 1997.
[7] 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, pp. 55-63, 1998.
[8] C. Blundo, A. De Santis and D. R. Stinson, “On the contrast in visual cryptography,” Journal of Cryptology, vol. 12, pp.261-289, 1999.
[9] 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, pp.471-485, 2000.
[10] C. Blundo, A. De Bonis and A. De Santis, “Improved schemes for visual cryptography, ” Design, Codes and Cryptography, vol. 24, pp. 255-278, 2001.
[11] P. A. Eisen and D. R. Stinson, “Threshold visual cryptography schemes with specified whiteness levels of reconstructed pixels,” Design, Codes and Cryptography, vol. 25, pp. 15-61, 2002.
[12] H. Koga, “A general formula of the (t, n)-threshold visual secret sharing scheme,” Cryptology-ASIACRYPT’2002, Lecture Notes in Computer Science, vol. 2501, pp. 847-855, 2002.
[13] W. -G. Tzeng and C. -M. Hu, “A new approach for visual cryptography,” Design, Codes and Cryptography, vol. 27, pp. 207-227, 2002.
[14] C. Blundo, P. D’Arco, A. De Santis and D. R. Stinson, “Contrast optimal threshold visual cryptography schemes,” SIAM Journal on Discrete Math, vol. 16, pp. 224-261, 2003.
[15] Y. -C. Hou, “Visual cryptography for color images,” Pattern Recognition, vol. 36, pp. 1619-1629, 2003.
[16] M. Iwamoto and H. Yamamoto, “A construction method of visual secret sharing schemes for plural secret images,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E86-A, pp. 2577-2588, 2003.
[17] S. Climato, R. De Prisco and A. De Santis, “Optimal colored threshold visual cryptography schemes,” Design, Codes and Cryptography, vol. 35, pp. 311-335, 2005.
[18] H. U. Simon, “Perfect reconstruction of black pixels revisited,” 15th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 3623, pp. 221-232, 2005.
[19] C. Blundo, S. Climato and A. De Santis, “Visual cryptography schemes with optimal pixel expansion,” Theorical Computer Science, vol. 396, pp. 169-182, 2006.
[20] M. Bose and R. Mukerjee, “Optimal (2, n) visual cryptographic schemes,” Design, Codes and Cryptography, vol. 40, pp. 255-267, 2006.
[21] S. J. Shyu, “Efficient visual secret sharing scheme for color images,” Pattern Recognition, vol. 39, pp. 866-880, 2006.
[22] F. Liu, C. K. Wu and X. J. Lin, “Colour visual cryptography schemes,” IET Information Security, vol. 2, pp. 151-165, 2008.
[23] M. Iwamoto, “Weakly secure visual secret sharing schemes,” Information Theory and Applications, pp.1-6, 2009.
[24] M. Bose and R. Mukerjee, “Optimal (k, n) visual cryptograohic schemes for general k,” Design, Codes and Cryptography, vol. 55, pp. 19-35, 2010.
[25] H. Hajiabolhassan and A. Cheraghi, “Bounds for visual cryptography schemes,” Discrete Applied Mathematics, vol. 158, pp. 659-665, 2010.
[26] F. Liu, C. K. Wu and X. J. Lin, “Step construction of visual cryptography schemes,” IEEE Transactions on Information Forensics and Security, vol. 5, pp. 27-38, 2010.
[27] S. J. Shyu and M. C. Chen, “Optimum pixel expansions for threshold visual secret sharing schemes,” IEEE Transactions on Information Forensics and Security (accepted: May, 2011).
[28] G. Ateniese, C. Blundo, A. De Santis and D. R. Stinson, “Visual cryptography for general access structures,” Information and Computation, vol. 129, pp. 86-106, 1996.
[29] A. De Bonis and A. De Santis, “New results on the randomness of visual cryptography schemes,” Progress in Computer Science and Applied Logic, vol. 20, pp. 187-201, 2001.
[30] A. De Bonis and A. De Santis, “Randomness in secret sharing and visual cryptography schemes,” Theoretical Computer Science, vol. 314, pp.351-374, 2004.
[31] C. -S. Hsu and T. -C. Hou, “Goal-programming-assisted visual cryptography method with unexpanded shadow images for general access structures,” Optical Engineering, vol. 45, pp. 097001, 2006.
[32] S. Lu, D. Manchala and R. Ostrovsky, “Visual cryptography on graphs,” Journal of Combinatorial Optimization, preprint, 2009.
[33] G. Ateniese, C. Blundo, A. De Santis and D. R. Stinson, “Extended capabilities for visual cryptography,” Theoretical Computer Science, vol. 250, pp. 143-161, 2001.
[34] Z. Zhou, G. R. Arce and G. Di Crescenzo, “Halftone visual cryptography,” IEEE Transactions on Image Processing, vol. 15, pp. 2441-2453, 2006.
[35] A, Klein and M. Wessler, “Extended visual cryptography schemes,” Information and Computation, vol. 205, pp. 716-732, 2007.
[36] Z. Wang, G. R. Arce and G. Di Crescenzo, “Halftone visual cryptography via error diffusion,” IEEE Transactions on Information Forensics and Security, vol. 4, pp. 383-396, 2009
[37] C. Kuhlmann, H. U. Simon, “Determining the optimal contrast for secret sharing schemes in visual cryptography,” LATIC’2000: Theoretical Informatics, Lectures Notes in Computer Science, vol. 1776, pp. 208-291, 2000.
[38] R. Z. Wang, “Region incrementing visual cryptography,” IEEE Signal Processing Letters, vol. 16, pp. 659-662, 2009.
[39] R. -Z. Wang, Y. -C. Lan, Y. -K. Lee, S. -Y. Huang, S. J. Shyu and T. -L. Chia, “Incrementing visual cryptography using random grids,” Optical Communications, vol. 283, pp. 4242-4249, 2010.
[40] S. J. Shyu, “Image encryption by random grids,” Pattern Recognition, vol. 40, pp. 1014-1031, 2007.
[41] S. J. Shyu, “Image encryption by multiple random grids,” Pattern Recognition, vol. 42, pp. 1582-1596, 2009.
[42] T. -H. Chen and K. -H. Tsao, “Visual secret sharing by random grids revisited,” Pattern Recognition, vol. 42, pp. 2203-2217, 2009.
[43] T. -H. Chen and K. -H. Tsao, “User-Friendly random grid-based visual secret sharing,” IEEE Transactions on Circuits and Systems for Video Technology, (accepted: Dec. 2, 2010).
[44] C. C. Wu and L. H. Chen, “A study on visual cryptography,” Institute of Computer and Information Science, National Chiao Tung University, Taiwan, R.O.C., Master’s thesis.
[45] J. Chen, T. -S. Chen, H. -C. Hsu and H. -W. Chen, “New visual cryptography system based on circular shadow image and fixed angle segmentation,” Journal of Electronic Imaging, vol. 14, pp. 033018-033023, 2005.
[46] M. Iwamoto, L. Wang, K. Yoneyama, N. Kunihiro and O. Kazuo, “Visual secret sharing schemes for multiple secret images allowing the rotation of shares,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, vol. E89-A, pp. 1382-1395, 2006.
[47] S. J. Shyu, S. -Y. Huang, Y. -K. Lee, R. -Z. Wang and K. Chen, “Sharing multiple secrets in visual cryptography,” Pattern Recognition, vol. 40, pp. 3633-3651, 2007.
[48] J. -B. Feng, H. -C. Wu, C. -S. Tsai, Y. -F Chang and Y. -P. Chu, “Visual secret sharing for multiple secrets,” Pattern Recognition, vol. 41, pp. 3572-3581, 2008.
[49] S. -J. Lin, S. -K. Chen and J. -C. Lin, “Flip visual cryptography with perfect security, conditionally-optimal contrast, and no expansion,” Journal of Visual Communication and Image Representation. vol. 21, pp. 900-916, 2010.
[50] T. -L. Lin, S. -J. Horng, K. -H. Lee, P. -L. Chiu, T. -W. Kao, Y. -H. Chen, R. -S. Run, J. -L. Lai and R. -J. Chen, “A novel visual secret sharing scheme for multiple secrets without pixel expansion,” Expert Systems with Applications, vol. 37, pp. 7858-7869, 2010.
[51] C. -N. Yang and T. -H. Chung, “A general multi-secret visual cryptography scheme,” Optics Communications, vol. 283, pp. 4949-4962, 2010.
[52] S. J. Shyu and K. Chen, “Visual multiple secrets sharing by circle random grids,” SIAM Journal on Imaging Sciences, vol. 3, pp. 926-953, 2010.
[53] lp_solve reference guide menu. Available: http://lpsolve.sourceforge.net/5.5/