雲端外包儲存(cloud outsourced storage)是一項重要的雲端運算服務，雲端用戶將檔案儲存至雲端伺服器以減少檔案管控與維運所需的成本，而且為了保護檔案的私密性，由雲端用戶自行將檔案進行加密再儲存至雲端伺服器。本論文以kNN的技術為基礎對已加密的檔案可以進行多關鍵字搜尋，可以判斷出每關鍵字與檔案相關程度之高低，使雲端伺服端可以漸進地依序自相關程度較高的檔案開始回傳給雲端用戶，以減少檔案傳輸的通訊成本，並且為了更進一步增加系統的容錯能力與可用性，利用建立相似關鍵字集合的方法達到相似搜尋的功能，甚至雲端用戶輸入錯誤關鍵字，但在錯誤未超過門檻值的前提下，仍舊可以找出相關的檔案。此外本研究也考量在機制運行的過程中也能夠滿足必要的安全需求。

Cloud outsource storage is one of important services in cloud computing. Cloud user uploads data to cloud server in order to reduce data management cost and maintenances cost of hardware and software. To protect data confidentiality, cloud user encrypts files before outsourcing. However, it is difficult for the cloud server to retrieve the corrected encrypted file based on the query of cloud user.  This paper proposes the protocol which is based on kNN technology. It can perform multi-keyword search in encrypted cloud data, and it determine relevance of encrypted files and keywords. The cloud server cannot learn the keywords including in the query of cloud user. In order to reduce communication cost of file transport, cloud server can return higher relevance of encrypted files to the cloud user. Moreover, if cloud user type wrong keywords and wrong keyword does not exceed threshold, he still retrieves files from cloud server. In addition, this study also considered that security requirements have to be satisfied.

目錄
第一章 前言	1
第二章 符號定義與相關研究	5
2.1 系統模式與潛在威脅	5
2.2 符號的定義以及名詞解釋	6
2.3 技術介紹	8
2.4 Wang等學者的方法[9]	9
2.5 Cao等學者的方法[10]	12
2.6 Wang等學者的方法[12]	15
第三章 多相似關鍵字的容錯排序搜尋機制	18
3.1 上傳階段	18
3.2 建立暗門階段	20
3.3 搜尋階段	21
第四章 安全性、功能以及效能分析	23
4.1 安全分析	23
4.2 功能比較	25
4.3 計算量的分析與比較	26
4.4 通訊量的比較	29
第五章 結論和未來研究方向	31
參考文獻	32
Appendix	34

表目錄
表 2-1 角色表	6
表 2-2 符號表	7
表 4-1 功能性的比較	26
表 4-2 計算量之比較	28
表 4-3 暗門通輸量之比較	30

[1]	P. Mell and T. Grance, “The NIST Definition of Cloud Computng” NIST, Information Technology Laboratory, NIST SP 800-145, 2011, [Online]. Available: http://www.nist.gov/itl.
[2]	D. Song, D. Wagner, and A. Perrig, “Practical Techniques for Searches on Encrypted Data,” in Proceedings of IEEE Symposium on Security and Privacy’00, 2000, pp. 44-55.
[3]	E.-J. Goh, “Secure Indexes,” Cryptology ePrint Archive, 2003, [Online]. Available: http://eprint.iacr.org/2003/216.
[4]	Y.-C. Chang and M. Mitzenmacher, “Privacy Preserving Keyword Searches on Remote Encrypted Data,” Applied Cryptography and Network Security, LNCS 3531, Springer-Verlag, 2005, pp. 442-445.
[5]	R. Curtmola, J. A. Garay, S. Kamara, and R. Ostrovsky, “Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,” in Proceedings of 13 th ACM Conference on Computer and Communications Security’06, 2006, pp.79-88.
[6]	D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano, “Public Key Encryption with Keyword Search,” Advances in Cryptology - EUROCRYP 2004, LNCS 3027, Springer-Verlag, 2004, pp.506-522.
[7]	P. Golle, J. Staddon, and B. Waters, “Secure Conjunctive Keyword Search over Encrypted Data,” Applied Cryptography and Network Security, LNCS 3089, Springer-Verlag, 2004, pp. 31–45.
[8]	J. Katz, A. Sahai, and B. Waters, “Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products,” Advances in Cryptology – EUROCRYPT 2008, LNCS 4965, Springer-Verlag, 2008, pp. 146-162.
[9]	C. Wang, N. Cao, K. Ren and W. Lou ” Enable Secure and Efficient Ranked Keyword Search over Encrypted Cloud Data” IEEE Transactions on Parallel and Distributed Systems, Volume 23, Issue 8, pp.1467-1479, Aug. 2012. 
[10]	N. Cao, C. Wang, M. Li, K. Ren, and W. Lou, “Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data,” in Proceedings of IEEE International Conference on Computer Communications’11, 2011, pp. 829-837.
[11]	W. K. Wong, D. W. Cheung, B. Kao, and N. Mamoulis, “Secure kNN computation on encrypted databases,” in Proceedings of ACM SIGMOD International Conference on Management Data’09, 2009, pp. 139-152.
[12]	C. Wang, K. Ren, S. Yu, and K. Urs ” Achieving Usable and Privacy-Assured Similarity Search over Outsourced Cloud Data” in proceedings of IEEE International Conference on Computer Communications’12, 2012, pp.451-459.
[13]	I. H. Witten, A. Moffat, and T. C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, 1st Ed. San Francisco: Morgan Kaufmann, 1999.
[14]	J. Li, Q. Wang, C. Wang, N. Cao, K. Ren, and W. Lou, “Fuzzy Keyword Search over Encrypted Data in Cloud Computing,” in Proceedings of IEEE International Conference on Computer Communications’10, 2010, pp. 1–5.
[15]	A. Boldyreva, N. Chenette, Y. Lee, and A. O’Neill, “Orderpreserving Symmetric Encryption,” Advances in Cryptology – Eurocrypt 2009, LNCS 5479, Springer-Verlag, 2009, pp. 224-241.