臺灣博碩士論文加值系統

由於雲端運算（Cloud Computing）在近年來成為全球注目的重要議題，相關的雲端服務（Cloud Service）也跟著蓬勃發展，例如雲端儲存服務、計算資源及各種的軟體，都已被全球的使用者廣泛的採納。當人們開始習慣使用雲端伺服器來當作資料儲存空間，而逐漸取代實體的硬體設備，雲端環境中的安全問題則成為近年來最重要的研究議題。為了讓個人檔案擁有最基本的安全保護，使用者通常會先將檔案加密後，再上傳於雲端儲存空間。然而，當檔案經過加密形成密文之後，檔案就轉變成不可辨識的內容，包括有合法下載及解密權的使用者在內，都無法辨識其內容為何。

在本研究中，我們探討運用關鍵字查詢加密檔案之議題及其發展，並針對兩種型態的關鍵字搜尋法進行深入的了解，分別是單關鍵字搜尋法及多關鍵字搜尋法，同時進一步地討論其在雲端環境中相關的安全需求。為了建構更有效率及安全的關鍵字搜尋機制，我們分別提出基於ElGamal公開金鑰系統的單關鍵字搜尋法及基於ElGamal公開金鑰系統之雙線性映射（Bilinear pairing）的多關鍵字搜尋法。此外，我們使用不須Random oracle model的正規安全性模型來分析兩種方法之安全性。

Since cloud computing has become the most popular issue in recent years, more and more cloud services have bloomed and been used worldwide such as cloud storage space, computing resource and kinds of software. When people use a cloud storage server as the daily data storage space which will replace hard discs in the desktop computer gradually, the problem of cloud security has become the most important issue in the recent studies. In order to gain the basic protection for personal documents, users usually encrypt the documents before storing them in the cloud storage server. However, as the documents are changed into the ciphertexts, no one can distinguish the content including the users who actually have the rights to download and decrypt those documents.

In this thesis, we study the issue that searching over the encrypted documents by using keyword. This research focus on two types of keyword search scheme: simple keyword search and conjunctive keyword search, and further discuss the relative requirements for security in cloud storage environment. In order to construct the more efficient and secure keyword search scheme mechanism, we proposed a simple keyword search scheme based on ElGamal public key system and a conjunctive keyword search scheme based on bilinear paring for ElGamal public key system. Furthermore, we analyze the security of each scheme in standard model without random oracle.

摘要 i
Abstract ii
Contents iii
List of table vi
List of figure vii
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Objectives 3
1.3 Research Scope 4
1.4 Organization 5
Chapter 2 Preliminary 6
2.1 Cryptographic Preliminary 6
2.1.1 Hard Assumptions 6
2.1.2 ElGamal Cryptosystem 6
2.1.3 Bilinear Pairing 8
2.1.4 Bilinear Pairing for ElGamal Public Key System 8
2.2 Public Key Encryption with Keyword Search 9
2.2.1 Remove Secure Channel 10
2.2.2 Consistency and Security Definitions 11
2.3 Conjunctive Keyword Searchable Scheme 17
2.3.1 Security Definitions 19
2.3 Off-Line Keyword-Guessing Attacks 23
Chapter 3 Simple Keyword Search Scheme Based on ElGamal System 24
3.1 The Proposed Scheme 24
3.1.1 Overview 24
3.1.2 Requirements 25
3.1.3 Notations 26
3.1.4 Construction 27
3.2 Consistency and Security Analysis 29
3.2.1 Consistency 29
3.2.2 Security Analysis 31
3.3 Performance Evaluation 37
3.4 Summary 39
Chapter 4 Conjunctive Field Keyword Searchable Scheme Based on Bilinear ElGamal System 40
4.1 The Proposed Scheme 40
4.1.1 Overview 40
4.1.2 Requirements 40
4.1.3 Notations 42
4.1.4 Construction 43
4.2 Consistency and Security Analysis 45
4.2.1 Consistency 45
4.2.2 Security Analysis 46
4.3 Performance Evaluation 52
4.4 Summary 53
Chapter 5 Conclusions and Future Works 54
5.1 Conclusions and Contributions 54
5.2 Future Works 55
5.2.1 Delegated Search 55
5.2.2 Multi-User Keyword Search 55
Reference 57

[1] M. Abdalla, M. Bellare, D. Catalano, E. Kitz, T. Kohno, T. Lange, J. M. Lee, G. Neven, P. Paillier, and H. Shi, “Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions,” Advances in Cryptology – CRYPTO 2005, LNCS, vol. 3621, pp. 205-222, 2005.
[2] J. Baek, R. Safavi-Naini, and W. Susilo, “Public Key Encryption with Keyword Search Revisited,” in ICCSA 2008, vol. 5072, LNCS, pp. 1249-1259, Perugia, Italy, 2008.
[3] D. Boneh, G. D. Crescenzom, R. Ostrovsky, and G. Rersiano, “Public Key Encryption with Keyword Search,” in Advances in Cryptology – EUROCRYPT 2004, LNCS, vol. 3027, pp. 506-522, Interlaken, Seitzerland, 2004.
[4] D. Boneh and M. Franklin, “Identity-Based Encryption From the Weil Pairing,” in Advances in Cryptology CRYPTO 2001, LNCS, vol. 2139, pp. 213-229, 2001.
[5] D. Boneh and B. Waters, “Conjunctive, Subset, and Range Queries on Encrypted Data,” in 4th Theory of Cryptography Conference, TCC 2007, LNCS, vol. 4392, pp. 535-554, 2007.
[6] J. W. Byun, H. S. Rhee, H.-A. Park, and D. H. Lee, “Off-Line Keyword Guessing Attacks on Recent Keyword Search Schemes over Encrypted Data,” in Secure Data Management, LNCS, vol. 4165, pp. 75-83, Seoul, Korea, 2006.
[7] R. Canetti, O. Goldreich, and S. Halavi, “The Random Oracle Methodology, Revisited,” in Proceedings of 30th ACM STOC, pp. 209-218, New York, 2004.
[8] Y. Chen and G. Horng, “Timestamped Conjunctive Keyword-Searchable Public Key Encryption,” in Forth International Conference on Innovation Computing Information and Control (ICICIC), pp. 729-732, 2009.
[9] Z. Chen, C. Wu, D. Wang, and S. Li, “Conjunctive Keywords Searchable Encryption with Efficient Pairing, Constant Ciphertext and Short Trapdoor,” in Proceedings of PAISI 2012, LNCS, vol. 7299, pp. 176-189, 2012.
[10] M. Ding, F. Gao, Z. Jin, and H. Zhang, “An Efficient Public Key Encryption with Conjunctive Keyword Search Scheme Based on Pairings,” in Network Infrastructure and Digital Content (IC-NIDC), 2012 3rd IEEE International Conference on, 2012.
[11] T. ElGamal, “A Public-Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, vol. IT-31, no. 4, pp. 469-472, 1985.
[12] L. Fang, W. Susilo, C. Ge, and J. Wang, “A Secure Channel Free Public Key Encryption with Keyword Search Scheme Without Random Oracle,” in Cryptology and Network Security, LNCS, vol. 5888, pp. 248-258, Kanazawa, Japan, 2009.
[13] P. Golle, J. Staddon, and B. Waters, “Secure Conjunctive Keyword Search over Encrypted Data,” in Proceedings of Applied Cryptography and Network Security Conference, LNCS, vol. 3089, pp. 31-45, 2004.
[14] C. Gu and Y. Zhu, “New Efficient Searchable Encryption Schemes From Bilinear Pairings,” International Journal of Network Security, vol. 10, no. 1, pp. 25-31, 2010.
[15] S. T. Hsu, C. C. Yang, and M. S. Hwang, “A Study of Public Key Encryption with Keyword Search,” International Journal of Network Security, vol. 15, no. 2, pp. 71-79, March 2013.
[16] C. Hu and P. Liu, “A Secure Searchable Public Key Encryption Scheme with A Designated Tester Against Keyword Guessing Attacks and Its Extension,” in Advances in Computer Science, Environment, Ecoinformatics, and Education, vol. 215 of Communications in Computer and Information Science, pp. 131-136, Wuhan, China, 2011.
[17] Y. H. Hwang and P. J. Lee, “Public Key Encryption with Conjunctive Keyword Search and Its Extension to A Multi-User System,” in Pairing-Based Cryptography – Pairing 2007, LNCS, vol. 4575, pp. 2-22, 2007.
[18] L. Ibraimi, S. Nikova, P. Hartel, and W. Honker, “Public-Key Encryption with Delegated Search,” in Applied Cryptography and Network Security – 9th International Conference, ACNS 2011, LNCS, vol. 6715, pp. 532-549, 2011.
[19] C. C. Lee, S. T. Hsu, and M. S. Hwang, “A Study of Conjunctive Keyword Searchable Schemes,” International Journal of Network Security, vol. 15, pp. 311-320, 2013.
[20] L. Nguyen, “A Trapdoor-Free and Efficient Group Signature Scheme From Bilinear Pairings,” in Advances in Cryptology – ASIACRYPT 2004, 2004.
[21] D. J. Park, K. Kim and P. J. Lee, “Public Key Encryption with Conjunctive Field Keyword Search,” in Information Security Applications, 5th International Workshop, WISA 2004, LNCS, vol. 3325, pp. 73-86, 2005.
[22] H. S. Rhee, J. H. Park, W. Susilo, and D. H. Lee, “Improved Searchable Public Key Encryption with Designated Tester,” in ASIACCS ’09 Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, pp. 376-379, Sydney, Australia, 2009.
[23] H. S. Rhee, J. H. Park, W. Susilo, and D. H. Kee, “Trapdoor Security in A Searchable Public-Key Encryption Scheme with A Designated Tester,” The Journal of Systems and Software, vol. 83, no. 5, pp. 763-771, 2010.
[24] E. K. Ryu and T. Takagi, “Efficient Conjunctive Keyword-Searchable Encryption,” in Advanced Information Networking and Application Workshops, 2007, AINAW ;07, 21st International Conference on, vol. 1, pp. 409-414, 2007.
[25] D. X. Song, D. Wagner, and A. Perrig, “Practical Techniques For Searches on Encrypted Data,” in Proceedings of IEEE Symposium Security and Privacy 2000, pp. 44-55, 2000.
[26] Q. Tang, Y. Zhao, X. Chen, and H. Ma, “Refine the Concept of Public Key Encryption with Delegated Search,” Cryptology ePrint Archive: Report 2012/654, 2012.
[27] A.H.P. Van Vliet. Secure Data Storage Outsourcing with Conjunctive Keyword Search. Thesis, Delft University of Technology, 2009.
[28] P. Wang, H. Wang, and J. Pieprzyk, “Threshold Privacy Preserving Keyword Searches,” in SOFSEM 2008: Theory and Practice of Computer Science, LNCS, vol. 4910, pp. 646-658,2008
[29] H. M. Yang, C. X. Xu, and H. T. Zhao, “An Efficient Public Key Encryption with Keyword Search Not Using Pairing,” in 2011 First International Conference on Instrumentation, Measurement, Computer, Communication and Control, pp. 900-904, Beijing, China, 2011.
[30] Y. Zhao, X. Chen, H. Ma, Q. Tang, and H. Zhu, “A New Trapdoor-Indistinguishable Public Key Encryption with Keyword Search,” Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, vol. 3, no. 1/2, pp. 72-81, 2012.
[31] B. Zhang and F. Zhang, “An Efficient Public Key Encryption with Conjunctive-Subset Keywords Search,” Journal of Network and Computer Application, vol. 34, no. 1, pp. 262-267, 2011.