臺灣博碩士論文加值系統

視覺密碼學是一種達成視覺秘密分享的加解密方法，這個方法不需要任何計算便可以解碼得到被隱藏的影像。例如：給定某一目標影像，經加密後形成n張印製於透明片(transparencies)上的子圖(shares)，參與分享的n個使用者各會得到一張影像，各透明片所顯示的是一些無法辨識或與主題無關影像，唯有重疊了至少k張的原始子圖，才能以肉眼辨識出目標影像的內容，這樣的視覺加解密法則稱為(n, k)法則。視覺密碼學最原始的概念在1995年由Naor和Shamir提出，它存在了若干缺點。使用我們所提出的類神經網路，這些缺點都可以解決，以下摘要式列出本方法的特性：(1) 灰階影像的分享，並不侷限在黑白影像的處理 (2) 加密時不需依賴編碼冊來編成不同加解密結構所要求的子圖 (3) 編碼後的子圖和原始目標影像一樣大。
我們提出了一個利用量子類神經網路模型來分享灰階影像的新方法，這是一個以能量驅動執行(energy-driven)的類神經網路，量子類神經網路模型最大的特點在於其特殊的“恆久性雜訊注入機制”，使得解品質可以控制在理想的範圍內，這樣的機制可以解決網路停滯於局部最低能量狀態(local minimum)。給定一個加解密結構，我們依據影像半色調轉換規則(image-halftoning rule)和子圖重疊規則(share-stacking rule)，將問題轉換成為量子類神經網路模型的能量函式，進而建造出一對應於該加解密結構的量子類神經網路。編碼時，輸入量子類神經網路的是灰階目標影像，待網路穩定時，我們可從對應的類神經元得到與目標影像同樣大小的各個子圖。此方法適用於各種複雜的加解密結構(access structure)，我們將在本論文中描述如何利用Q’tron類神經網路完成視覺密碼學的實例應用，包括資訊隱藏(message concealment)、視覺授權(visual authorization)及半公開加密法 (semipublic encryption)，實驗結果將在論文裡呈現。

Visual cryptography is a cryptographic scheme to achieve
secret sharing. For example, it decomposes a secret image
into n shares which are distributed to the participants,
such that only qualified subsets of participants can "visually"
recover the secret image. The "visual" recovery consists of
xeroxing the shares onto transparencies, and then stacking them.
The secret image will reveal without any cryptographic
computation. Originally, the cryptographic paradigm introduced by Naor and Shamir has some drawbacks. This dissertation proposes a novel technique using neural networks (NNs) to fulfill visual cryptography schemes with some extended capabilities: i) the access schemes are described using a set of graytone images, and ii) the codebooks to fulfill them are
not required; and iii) the size of share images is the
same as the size of target images.
The neural network model to conduct this research is called
quantum neural-network (Q'tron NN; for short) model. It is
an energy-driven NN model. A Q'tron NN is able to achieve
local-minima free if it is constructed as a known-energy system and noise-injected, to be detailed in the dissertation. To fulfill an access scheme of visual cryptography, two energy sub-terms, which describe the image-halftoning rule and share-stacking rule, are considered to build the Q'tron NN. The proposed Q'tron NN structures are quite general and, hence, can be applied to fulfill any access schemes of visual cryptography. Some applications of visual cryptography based on the Q'tron NN approach are also discussed, including message concealment, visual authorization, and semipublic encryption.

Chapter 1 Introduction
Chapter 2 The Q'tron Neural Network Model
Chapter 3 Image Halftoning --- A Preliminary for Visual cryptography
Chapter 4 The (2,2) Visual Cryptography and Application
Chapter 5 The General Neural Network Paradigm for Visual Cryptography
Chapter 6 Conclusion
Bibliography

[1] E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machine, Wiley and Sons, Chichester, England, 1989.
[2] D. H. Ackley, G. E. Hinton, and T. J. Sejnowski, "A Learning Algorithm for Boltzmann Machine," Cognitive Science, vol. 9, pp. 147-169, 1985.
[3] Y. Akiyama, A. Yamashita, M. Kajiura, and H. Aiso, "Combinatorial Optimization with Gaussian Machines," Proceedings IEEE International Joint Conference on Neural
Networks, vol. 1, pp. 533-540, 1989.
[4] I. Arizono, A. Yamamoto, and H. Ohta, "Scheduling for Minimizaing Total Actural Flow Time by Neural Network," International Journal of Production Research, vol. 30, no. 3,
pp. 503-511, March 1992.
[5] D. Artz, "Digital steganography: hiding data within data," Internet Computing, IEEE, vol. 5, no. 3, pp. 75-80, May-June 2001.
[6] G. Ateniese, C. Blundo, A. D. Santis, D. R. Stinson, "Visual Cryptography for General Access Structures", Information and Computation, vol. 129, no. 2, pp. 86-106, 1996.
[7] G. Ateniese, C. Blundo, A. D. Santis, and D. R. Stinson, "Extended Schemes for Visual Cryptography," Theoretical Computer Science, 1996.
[8] G. Ateniese, C. Blundo, A. D. Santis, and D. R. Stinson, "Extended Capabilities for Visual Cryptography," Theoretical Computer Science, 1999.
[9] M. Barni, "What Is the Future for Watermarking? (Part I)," IEEE Signal Processing Magazine, vol. 20, no. 5, pp. 55-60, Sep. 2003.
[10] M. Barni, "What Is the Future for Watermarking? (Part II)," IEEE Signal Processing Magazine, vol. 20, no. 6, pp. 53-59, Nov. 2003.
[11] C. Blundo, A. D. Santis, M. Naor. "Visual cryptography for grey level images," Information Processing Letters, vol. 75, pp. 255-259, 2000.
[12] C. Blundo, A. D. Santis, and D. R. Stinson, "On the Contrast in Visual Cryptography Schemes," Journal of Cryptology, vol. 12, pp. 261-289, 1999.
[13] C. C. Chang and J. C. Chuang, "An Image Intellectual Property Protection Scheme For Gray-Level Images Using Visual Secret Sharing Stragegy," Pattern Recognition Letters, vol. 23, No. 8, pp. 931-941, 2003.
[14] L. O. Chua, K. R. Crounse, and T. Roska, "Image Halftoning with Celluar Neural Networks," IEEE Trans. on Circuits and System-II: Analog and Digital Processing, vol.
40, no. 4, pp. 267-283, April 1993.
[15] B. DeBacker and H. Beringer, "Combinatorial Problem Solving in Constraint Logic Programming with Cooperating Solvers", In C. Beierle and L. Plumer, editors. Logic
Programming: Formal Methods and Practical Applications, pp. 245-272, 1996.
[16] O. Eriksson, Y. Zhou, and A. Elofsson, "Side Chain-Positioning As An Integer Programming Problem," 1st Workshop on Algorithms in BioInformatics, WABI 2001, Proceedings, Lecture Notes in Computer Science 2149, ISBN 3-540-42516-0, pp. 128-141, Springer 2001.
[17] M. R. Garey, R. L. Graham, and D. S. Johnson. "Some NP-Complete Geometric Problems," In Conference Record of the Eighth Annual ACM Symposium on Theory of Com-
puting, pp. 10-22, Hershey, Pennsylvania, 3-5 May 1976.
[18] M. R. Garey and D. S. Johnson, Computer and Tntractability: A Guide to the Theory of NP-Completeness, New York, NY: Freeman, 1979.
[19] G. W. Gavis, "Sensitivity Analysis in Neural Net Solutions," IEEE Tran. on Systems, Man, and Cybernetics, vol. 19, No. 5, pp. 1078-1090, Sep 1989.
[20] B. Hajek, "Cooling schedules for optimal annealing," Mathematics of Operational Re-search, vol 13, pp. 311-329, 1988.
[21] J. J. Hopfield, "Neural Networks and Physical Systems with Emergent Collective Computational Abilities," Proc. Natl. Acad. Sci. USA, vol.79, pp. 2554-2558, April 1982.
[22] J. J. Hopfield, "Neural Networks and Physical Systems with Emergent Collective Computational Abilities," Proc. Natl. Acad. Sci. USA, vol. 79, pp. 2554-2558, April 1982.
[23] J. J. Hopfield, "Neurons with Graded Response Have Collective Computational Properties Like Those of Two-State Neurons," Proc. Natl. Acad. Sci. USA, vol. 81, pp.
3088-3092, May 1984.
[24] J. J. Hopfield and D. W. Tank, "Neural Computation of Decisions in Optimization Problems," Biological Cybernetics, vol. 52, pp. 141-152, 1985.
[25] H. Jeong, J. H. Park, "Lower Bounds of Annealing Schedule for Boltzmann and Cauchy Machines," Proceeding IEEE International Joint Conference on Neural Networks, vol. 1, pp. 581-586, 18-22 June 1989.
[26] E. D. Karnin, J. W. Green and M. E. Hellman, "On Secret Sharing Systems," IEEE Trans. on Information. Theory, IT-29, pp. 35-41, 1982.
[27] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[28] B. Lee and B. Sheu, "Modified Hopfield Neural Networks for Retrievig the Optimal Solution," IEEE Transactions on Neural Networks, vol. 2, no. 1, pp. 137-142, January 1991.
[29] H. R. Lewis, C. H. Papadimitriou, "Elements of The Theory of Computation, pp. 275-351, Prentice Hall International Editions, 1998.
[30] S. L. Lin, J. M. Wu and C. Y. Liou, "Annealing by Perturbing Synapses," IEICE Transactions on Information and Sytems, vol. E75-D, no. 2, pp. 210-218, March 1992.
[31] C. C. Lin and W. H. Tsai, "Visual Cryptography for Gray-Level Images by Dithering technique," Pattern Recognition Letters, vol. 24, pp. 349-358, 2003.
[32] R. P. Lippmann, "An Introduction to Computing with Neural Nets," IEEE ASSP Magazine, pp. 4-22, April 1987.
[33] M. Lu, Y. Zhan and G. Mu, "Bipolar Optical Neural Network with Adaptive Threshold," Optik, vol. 91, no. 4, pp. 178-182, 1992.
[34] L. A. MacPherson, "Grey Level Visual Cryptography for General Access Structures, Master Thesis, Master of Mathematics in Computer Science, Waterloo, Ontario, Canada,
2002.
[35] R. J. Mceliece, E. C. Posner, E. R. Rodemich, and S. S. Venkatesh, "The Capacity of the Hopfield Associative Memory," IEEE Transactions on Information Theory, pp461-482, 1987.
[36] K. Nakano, "AssociatronwA Model of Associative Memory," IEEE Transactions on Systems, Man, and Cybernetics, pp380-388, 1972.
[37] M. Naor and A. Shamir, "Visual Cryptography," Advances in Cryptology-Eurocrypt '94, Lecture Notes in Computer Science, vol. 950, pp. 1-12, 1995.
[38] M. Naor, B. Pinkas, "Visual Authentication and Identi cation," CRYPTO, pp. 322-336, 1997.
[39] N. Paul, D. Evans, A. Rubin, D. Wallach, "Authentication for Remote Voting," Workshop on Human-Computer Interaction and Security Systems, April 2003.
[40] N. Provos, P. Honeyman, "Hide and seek: an introduction to steganography," IEEE Security and Privacy Magazine, vol. 1, no. 3, pp. 32-44, May-June 2003.
[41] B. Schneier, Applied Cryptography, John Wiley, second ed., 1996.
[42] A. Shamir, "How to Share a Secret," Communications of the ACM, vol. 22, no. 11, pp. 612-613, 1979.
[43] Y. Takefuji and H. Szu, "Design of Parallel Distributed Cauchy Machines," Proceedings of IEEE International Joint Conference on Neural Networks, vol. 1, pp. 529-532, 1989.
[44] T. M. Thompson, Visual Cryptography, Master's Project, R.I.T. Department of Computer Science, Rochester Institute of Technology, May 2000.
[45] K. Tsutsumi and K. Nakajima, "Dynamics and local minima of a simple neural network for optimization,", Proceedings. IJCNN, vol. 1 , pp. 353-358, 2001.
[46] R. Ulichney, Digital Halftoning, Cambridge, MA: MIT Press. third ed., 1990.
[47] E. Verheul and H. V. Tilborg, "Constructions and Properties Of k out Of n Visual Secret Sharing Schemes," Designs, Codes and Cryptography, vol. 11, No. 2, pp. 179-196, 1997.
[48] C. C. Wang, S. C. Tai, and C. S. Yu, "Repeating Image Watermarking Technique by the Visual Cryptography," IEICE Trans. Fundamentals, vol. E83-A, no. 8, pp. 1589-1598,
August 2000.
[49] G. V. Wilson and G. S. Pawley, "On the Stability of the Traveling Salesman Algorithm of Hop eld and Tank," Biological Cybernetics, vol. 58. pp. 63-70, 1988.
[50] E. Wong, "Stochastic Neural Networks," Algorithmica, pp. 466-478, June 1991.
[51] T. W. Yue, A Goal-Driven Neural Network Approach for Combinatorial Optimization and Invariant Pattern Recognition, Phd's Thesis, Department of Computer Engineering,
National Taiwan University, Taiwan, 1992.
[52] T. W. Yue and G. T. Chen, "An Auto-Invertible Neural Network for Image Halftoning and Restoration," Proceedings of IEEE International Conference on Neural Networks, vol. 3, no. 27, pp. 1450-1455, 1995.
[53] T. W. Yue and S. C. Chiang, "Quench, Goal-Matching and Converge | The Three-Phase Reasoning Of a Q'tron Neual Network," Proceedings of the IASTED International Conference on Arti cial and Computational Intelligence, pp. 54-59, 2002.
[54] T. W. Yue and S. C. Chiang, "The General Neural-Network Paradigm for Visual Cryptograph," IWANN 2001, LNCS 2048, pp. 196-206, 2001.
[55] G.S. Vernam, "Ciper Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications," J. Amer. Inst. Elec. Eng., vol. 55, pp. 109-115, 1926.
[56] Y. Zhang, R.E. Webber, "Space Di usion An Improved Parallel Halftoning Technique Using Space lling Curves," Proc. of SIGGRAPH 93, ACM Computer Graphics, Annual
Conference Series, pp. 305-312, 1993.
[57] Y. Zhang, "Adaptive Ordered Dither," CVGIP: Graphical Model and Image Processing vol. 59, no. 1, pp. 49-53, 1997.
[58] Y. T. Zhou, R. Chellappa, A. Vaid, and B. K. Jenkins, "Image Resoration Using a Neural Network," IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 36, pp.
1141-1151, 1998.
[59] Z. Zhou, G. R. Arce, G. Di Crescenzo, "Halftone Visual Cryptography," Proceedings of International Conference on Image Processings, vol. 1, pp. 521-524, 2003.