(k, n)視覺密碼機制( Visual Cryptography Scheme; VCS )是將秘密影像加密於n張子影像，特定組合的子影像能解回秘密影像，若不是特定的子影像組合則無法回復秘密影像，有別於傳統加密法需要大量的運算，視覺密碼具有「相疊即視」的簡單解碼功能。此處的k 值為解密的門檻值，當k張子影像相疊時就能解回秘密影像，若是少於k張子影像則無法取得任何有關秘密影像的資訊。
雖然視覺密碼不可以將原影像還原到無失真，但是它具有「門檻特性」及「相疊即視」特性，因此有多樣化的應用。例如，應用於電子投票、浮水印、Google 街景服務、指紋辨識及二維條碼等多種領域，皆是因為VCS 不需計算即可解密之特性。而且子影像的保存方式為實體持有，不需擔心別人透過網路竊取，或是電腦遭到惡意攻擊。最近，Ou和Sun等人將視覺密碼與壓縮域結合，提出了一種可逆式AMBTC壓縮域的視覺密碼機制。Ou和Sun等人的(2, 2)視覺密碼將秘密影像分享到兩張AMBTC壓縮影像中，相疊後(OR或XOR)可解回一個祕密訊息，並且可以得回無損的AMBTC壓縮影像。Ou和Sun也將(2, 2)機制擴張(2, n)機制，此時參與者需持有 ⌈log2 N⌉ 張AMBTC壓縮影像。
在本篇論文中我們提出（k, k）機制，將秘密影像藏進k個AMBTC的壓縮影像。植基於（k, k）機制並考慮不同的n值，我們設計了不同的方法建立(k, n)機制，讓參與者能持有最少的AMBTC壓縮影像。我們的兩大主要貢獻是: (1) 設計了符合AMBTC壓縮影像格式的（k, k）視覺密碼的基本矩陣 (2) 設計了將（k, k）機制擴張至(k, n) 機制的方法。本文實驗結果顯示了所提的方法的效用和優點，也做了充分的理論分析和討論。

A (k, n) Visual Cryptography scheme (VCS) shares a secret image into n shadow images (referred to as shadows) in a way that requires the shadows in a predefined coalition for the secret reconstruction. However, the secret image cannot be revealed if they are not combined in the prescribed way. VCS has a novel stacking-to-see property where decoding requires neither knowledge of cryptography nor computer. The value of k is the threshold. The secret image can be reconstructed by k or more shadows, while it cannot be revealed from less than k shadows.
Although VCS cannot obtain the distortion-less secret image, it provides both characteristics of "threshold property" and "stacking-to-see property", and thus may have many intended applications. Other VCS applications in combining electronic voting, watermarking, Google Street View, fingerprint, and barcode were also introduced. These applications come from the benefit of the decryption without computation, and meanwhile shadows are physically possessed by participants, which may not be compromised. Recently, Ou and Sun combined Visual Cryptography with compressed domains and proposed the reversible AMBTC Visual Cryptography scheme. Ou and Sun’ (2, 2) scheme shared the secret image into two AMBTC compressed images. The secret image can be reconstructed by OR (or XOR) operation, and meanwhile the AMBTC images can be obtained. In addition, Ou and Sun expanded their (2, 2)scheme to the (2, n) scheme, but participants need ⌈log2 N⌉ AMBTC compressed images.
In this thesis, we propose the (k, k) threshold VCS to encode secret image into k AMBTC compressed images. Based on the (k, k) scheme and various values of n, we designed different methods to construct (k, n) scheme with the least compressed AMBTC images. Our main contributions have: (1) design base matrices of (k, k)-VCS satisfying AMBTC format, and (2) extend (k, k) scheme to (k, n) scheme. Experimental results demonstrate the effectiveness of our schemes, and theoretical analyses are also given.

Chapter 1 Introduction 1
Chapter 2 Preliminaries 5
2.1 (k, n)-VCS 5
2.2 AMBTC 6
Chapter 3 The Proposed Scheme 9
3.1 The Framework 9
3.2 (k, k) Threshold RAVCS 10
3.2.1 Share Construction 10
3.2.2 Decryptions and AMBTC Image Recovery 13
3.3 Shadow Distribution Algorithms 14
3.4 OR and XOR Decryptions 21
3.5 Reversible Recovery of AMBTC Images 21
3.6 Contrast 22
Chapter 4 Experimental Results and Discussions 25
4.1 Examples for the (k, k) and (k, n) RAVCS 25
4.2 Performance Analysis 29
4.2.1 Visual Quality 29
4.2.2 Number of Reference Images 29
4.3 Feature Comparison 30
Chapter 5 Conclusion and Future Work 33
Appendix 35
References 43

[ATEN01] G. Ateniese, C. Blundo, A. Santis, D. Stinson, “Extended capabilities for visual cryptography,” Theor. Comput. Sci., vol.250, 143-161, 2001.
[ATEN96] G. Ateniese, C. Blundo, “A. De Santis, D. Stinson,” Visual cryptography for general access structures, Inform. Comput., vol. 129, pp. 86-106, 1996.
[BLUN99] C. Blundo, A. De Santis, D. Stinson, “On the contrast in visual cryptography schemes,” J. Cryptol., vol. 12, pp. 241-289, 1999.
[CHEN11] T. Chen, K. Tsao, “Threshold visual secret sharing by random grids,” J. Syst. Softw., vol.84, pp.1197-1208, 2011.
[FU16] Z. Fu, K. Ren, J. Shu, X. Sun, F. Huang, “Enabling personalized search over encrypted outsourced data with efficiency improvement,” IEEE Trans. Parallel Distrib. Syst., vol. 27, pp. 2546-2559, 2016.
[KAFRI87] O. Kafri, E. Keren, “Encryption of pictures and shapes by random grids,” Opt. Lett., vol.12, pp.377-379, 1987.
[KANG11] I. Kang, G. Arce, H. Lee, “Color extended visual cryptography using error diffusion,” IEEE Trans. Image Process., vol. 20, 132-145, 2011.
[LEE12] K. Lee, P. Chiu, “An extended visual cryptography algorithm for general access structures,” IEEE Transactions on Information Forensics and Security, vol. 7, pp.219-229, 2012.
[LI15] J. Li, X. Li, B. Yang, X. Sun, “Segmentation-based image copy-move forgery detection scheme,” IEEE Transactions on Information Forensics and Security, vol. 10, pp. 507-518, 2015.
[LIN03] C. Lin, W. Tsai, “Visual cryptography for gray-level images by dithering techniques,” Pattern Recogn. Lett., vol. 24, pp. 349-358, 2003.
[LIU11] F. Liu, C. Wu, “Embedded extended visual cryptography schemes,” IEEE Transactions on Information Forensics and Security, vol. 6, pp. 307-322, 2011.
[LIU12] F. Liu, C. Wu, L. Qian, et al., “Improving the visual quality of size invariant visual cryptography scheme,” J. Visual Commun. Image Represent., vol. 23, pp.331-342, 2012.
[NAOR95] M. Naor, A. Shamir, “Visual cryptography,” Lecture Notes Comput. Sci., vol. 950, pp. 1-12, 1995.
[OU14] D. Ou, W. Sun, “Reversible AMBTC-based secret sharing scheme with abilities of two decryptions,” J. Visual Commun. Image Represent., vol. 25, pp.1222-1239, 2014.
[SHEN16] G. Shen, F. Liu, Z. Fu, B. Yu, “Perfect contrast XOR-based visual cryptography schemes via linear algebra,” Des. Codes Cryptogr., pp.1-23, 2016.
[TUYLS05] P. Tuyls, H. Hollmann, J. Lint, L. Tolhuizen, “XOR-based visual cryptography schemes,” Des. Codes Cryptogr., vol. 37, pp.169-186, 2005.
[WANG09] D. Wang, F. Yi, X. Li, “On general construction for extended visual cryptography schemes,” Pattern Recogn, vol. 42, pp. 3071-3082, 2009.
[WANG09] Z. Wang, G. Arce, G. Di Crescenzo, “Halftone visual cryptography via error diffusion,” IEEE Transactions on Information Forensics and Security, vol. 4, pp.383-396, 2009.
[WEIR10] J. Weir, W. Yan, “A comprehensive study of visual cryptography,” Trans. Data Hiding Multimedia Security V, pp.70-105, 2010.
[WU12] X. Wu, W. Sun, “Visual secret sharing for general access structures by random grids,” IET Inform. Security, vol. 6, pp. 299-309, 2012.
[WU13] X. Wu, W. Sun, “Improving the visual quality of random grid-based visual secret sharing,” Signal Process., vol. 93 pp. 977-995, 2013.
[WU13] X. Wu, W. Sun, “Generalized random grid and its applications in visual cryptography,” IEEE Transactions on Information Forensics and Security, vol. 8, pp.1541-1553, 2013.
[WU14] X. Wu, W. Sun, “Extended capabilities for XOR-based visual cryptography,” IEEE Transactions on Information Forensics and Security, vol. 9, vol.1592-1605, 2014.
[XIA16] Z. Xia, X. Wang, L. Zhang, Z. Qin, X. Sun, K. Ren, “A privacy-preserving and copydeterrence content-based image retrieval scheme in cloud computing,” IEEE Transactions on Information Forensics and Security, vol.11, pp. 2594-2608, 2016.
[XIA16] Z. Xia, X. Wang, X. Sun, Q. Wang, “A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data,” IEEE Trans. Parallel Distrib. Syst., vol. 27, pp. 340-352, 2016.
[YANG00] C. N. Yang, C. Laih, “New colored visual secret sharing schemes,” Des. Codes Cryptogr., vol. 20, pp.325-036, 2000.
[YANG04] C. N. Yang, “New visual secret sharing schemes using probabilistic method,” Pattern Recogn. Lett., vol. 25, pp.486-494, 2004.
[YANG14] C. N. Yang, D.-S. Wang, “Property analysis of XOR-based visual cryptography,” IEEE Trans. Circ. Syst. Video Technol., vol. 24, pp.189-197, 2014.
[ZHOU06] Z. Zhou, G. Arce, G. Di Crescenzo, “Halftone visual cryptography,” IEEE Trans. Image Process., vol. 15, pp.2441-2453, 2006.
[ZHOU16] Z. Zhou, C. N. Yang, X. Sun, Q. Liu, Q. J. WU, “Effective and efficient image copy detection with resistance to arbitrary rotation,” IEICE Trans. Inform. Syst., vol. 99, pp. 1531-1540, 2016.
[ZHOU17] Z. Zhou, Y. Wang, Q. J. Wu, C. N. Yang, X. Sun, “Effective and efficient global context verification for image copy detection,” IEEE Transactions on Information Forensics and Security, vol. 12, pp. 48-63, 2017.