臺灣博碩士論文加值系統

在這個雲端計算蓬勃發展的時代，可搜尋對稱式加密 (Searchable Symmetric Encryption; SSE) 成為一個日趨重要的技術。透過這個技術，我們可以將重要資料加密後儲存在不受信任的雲端伺服器上，並且能以關鍵字進行資料檢索。遠端伺服器不會知道我們所搜尋的關鍵字，也不會知道我們所要提取的檔案內容，但是卻可以傳回正確的資料給我們。然而，一個支援SSE的資料庫仍然不夠切實，因為資料不是永遠不變動的。一般來說，我們會經常修改資料，即使該資料儲存於遠端的伺服器上。伺服器必須能夠更新該筆資料卻不對這些資料進行解密。動態可搜尋對稱式加密 (Dynamic Searchable Symmetric Encryption; DSSE) 就是被設計來支持上述功能的。我們可以新增或刪除伺服器上的加密資料而不須進行解密。在先前的研究中，許多建構DSSE系統的方法被提出，我們可以透過連結串列或者是一種稱為「盲儲存裝置 (Bind Storage) 」的方法來實做，他們在功能擴充性以及效率上各有優劣。但是，對於一個實際可用的系統來說，最重要的關鍵是效能與安全性之間的權衡。在本篇論文中，我們將實作不同的DSSE，並比較他們的效率和安全性。透過實作系統並分析實驗結果，我們可以找到現有DSSE的缺點，並試圖改善。

Searchable symmetric encryption (SSE) is a more and more important technique for cloud computing. It lets us can store critical data by encryption in the untrusted cloud server but allows us search the encrypted data with the keyword. The server will not know the keyword and the data content but it can retrieval the correct data to us. However, a database with SSE is not enough practical because the data is not invariable. In general, we modify the data frequently even if it stores in the remote server. The server must can update the encrypted data without decryption. Dynamic searchable symmetric encryption (DSSE) is designed to support the above function. We can add or delete the encrypted data on the server but with no need for decryption. The previous research proposes many schemes for constructing a DSSE system. It can be based on link-list structure or a new primitive called Blind Storage. Each of them has respective advantage and drawback about its function extensibility and efficiency. Nevertheless, for a real available system, the most important key is the tradeoff between performance and security. In this paper, we will implement different DSSE systems to compare their efficiency and security. We can find the disadvantage of the existing DSSE scheme and try to improve it by analyzing the experiment result.

口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES viii
Chapter 1 Introduction 1
1.1 Research Motivation 2
1.2 Research Intention 2
Chapter 2 Background 4
2.1 Dynamic Searchable Symmetric Encryption (DSSE) 4
2.1.1 General Model for a DSSE Scheme 6
2.2 Efficiency and Index 8
2.2.1 Forward Index 8
2.2.2 Invert Index 8
2.3 Privacy issue (leakage) 8
2.3.1 Index Information 9
2.3.2 Search Pattern 9
2.3.3 Access Pattern 9
2.3.4 Forward Privacy 9
2.3.5 Backward Privacy 10
2.4 Security Definition Review 10
2.4.1 IND-CPA 10
2.4.2 IND1/2-CKA 11
2.4.3 IND-CKA1/2 11
2.4.4 Other Definitions for Different Model 12
2.4.5 Dynamic IND-CKA2 12
2.4.6 Deterministic encryption 12
2.5 Model 13
2.5.1 Untrusted Server Mode 13
2.5.2 Random Oracle Model versus Standard Model 13
Chapter 3 Related Works 14
3.1 Dynamic Searchable Symmetric Encryption (KPR scheme) [2] 14
3.2 Practical Dynamic Searchable Encryption with Small Leakage (SPS scheme) [4] 17
3.3 Dynamic Searchable Encryption via Blind Storage (NPG scheme) [5] 19
3.4 Searchable Encryption with Secure and Efficient Updates (HK scheme) [6] 21
3.5 Dynamic Searchable Encryption in Very-Large Database (CJJJ Scheme) [3] 23
Chapter 4 Methodology 25
4.1 Search Pattern Hiding Concept 25
4.1.1 Insignificance Keyword 26
4.2 Hybrid DSSE(HDSSE) with Search Pattern Hiding 27
Chapter 5 Experiment and Result 29
5.1 Experiment Environment 30
5.2 Result 30
5.2.1 Building Test 31
5.2.2 Searching Test 31
5.2.3 Adding Test 33
5.2.4 Deleting Test 33
Chapter 6 Conclusion and Future Work 35
REFERENCE 36

[1]D. X. Song, D. Wagner, and A. Perrig, "Practical techniques for searches on encrypted data," in Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on, 2000, pp. 44-55.
[2]S. Kamara, C. Papamanthou, and T. Roeder, "Dynamic searchable symmetric encryption," in Proceedings of the 2012 ACM conference on Computer and communications security, 2012, pp. 965-976.
[3]D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M. Rosu, et al., "Dynamic searchable encryption in very-large databases: Data structures and implementation," in Network and Distributed System Security Symposium, NDSS, 2014.
[4]E. Stefanov, C. Papamanthou, and E. Shi, "Practical Dynamic Searchable Encryption with Small Leakage," in Network and Distributed System Security Symposium, NDSS, 2014.
[5]M. Naveed, M. Prabhakaran, and C. A. Gunter, "Dynamic searchable encryption via blind storage," in Security and Privacy (SP), 2014 IEEE Symposium on, 2014, pp. 639-654.
[6]F. Hahn and F. Kerschbaum, "Searchable Encryption with Secure and Efficient Updates," in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 310-320.
[7]O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications: Cambridge University Press, 2004.
[8]E.-J. Goh, "Secure Indexes," IACR Cryptology ePrint Archive, vol. 2003, p. 216, 2003.
[9]Y.-C. Chang and M. Mitzenmacher, "Privacy Preserving Keyword Searches on Remote Encrypted Data," in Applied Cryptography and Network Security. vol. 3531, J. Ioannidis, A. Keromytis, and M. Yung, Eds., ed: Springer Berlin Heidelberg, 2005, pp. 442-455.
[10]R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky, "Searchable symmetric encryption: Improved definitions and efficient constructions," Journal of Computer Security, vol. 19, pp. 895-934, 2011.
[11]K. Kurosawa and Y. Ohtaki, "UC-Secure Searchable Symmetric Encryption," in Financial Cryptography and Data Security. vol. 7397, A. Keromytis, Ed., ed: Springer Berlin Heidelberg, 2012, pp. 285-298.
[12]A. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters, "Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption," in Advances in Cryptology – EUROCRYPT 2010. vol. 6110, H. Gilbert, Ed., ed: Springer Berlin Heidelberg, 2010, pp. 62-91.
[13]S. Kamara and C. Papamanthou, "Parallel and dynamic searchable symmetric encryption," in Financial Cryptography and Data Security, ed: Springer, 2013, pp. 258-274.
[14]R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky, "Searchable symmetric encryption: improved definitions and efficient constructions," presented at the Proceedings of the 13th ACM conference on Computer and communications security, Alexandria, Virginia, USA, 2006.
[15]C. Bosch, A. Peter, B. Leenders, L. Hoon Wei, T. Qiang, W. Huaxiong, et al., "Distributed Searchable Symmetric Encryption," in Privacy, Security and Trust (PST), 2014 Twelfth Annual International Conference on, 2014, pp. 330-337.
[16]W. Dai. (2013, Feb. 20). Crypto++ Library 5.6.2 [Online]. Available: http:/www.cryptopp.com
[17]J. Song, R. Poovendran, J. Lee, and T. Iwata, "The advanced encryption standard-cipher-based message authentication code-pseudo-random function-128 (AES-CMAC-PRF-128) algorithm for the internet key exchange protocol (IKE)," RFC 4615, Aug. 2006.
[18]W. W. Cohen. (2015). Enron Email Dataset [Online]. Available: https://www.cs.cmu.edu/~./enron/