臺灣博碩士論文加值系統

雲端儲存提供了普羅大眾非常方便的服務，透過雲端儲存服務可以讓各種需求的使用者將資料儲存到雲端空間上，而需要取用時不需要受到區域性的限制。但是在方便服務的背後，卻隱藏著許多安全問題：使用者擔心在傳送資料到雲端伺服器的過程中可能會被網路上第三者攔截；雲端儲存服務所使用的設備或環境都不是使用者可以控制的，或是某些使用者儲存了敏感性的資料，讓提供這些儲存服務的內部人員可能會有惡意行為出現，導致伺服器不被使用者信任。所以雲端伺服器紛紛宣稱自己的服務是將使用者的檔案加密，藉此建立服務的信譽。然而加密程序與加密金鑰都在雲端伺服器執行的作法並不能保證使用者的資料不會被伺服器內部人員私底下解密的惡意行為。

因此使用者為了保護資料，通常會選擇先把檔案加密之後再存放到雲端空間，但是原有的搜尋方式無法有效的搜尋到密文檔案，因此如何不影響搜尋功能又滿足儲存資料的機密性需求就成為使用者與服務提供者的重要課題。可搜尋加密法在這個背景下成為雲端儲存領域中一項特別的研究議題，其特性可以讓雲端伺服器不需要經過解密過程就可以搜尋到檔案。然而可搜尋加密法在早期的研究提出的架構存在著搜尋階段效率不佳和固定性搜尋樣式衍生的個人隱私性風險。

為了解決早期可搜尋加密法架構的缺點，許多學者紛紛提出改進的架構，而在這些研究所提出的改進架構中，可以依照加密程序所使用的密碼系統來區分成兩大類：對稱式可搜尋加密法和非對稱式可搜尋加密法，前者是採用對稱式金鑰密碼系統來對資料明文與搜尋關鍵字加密；後者則是利用公開金鑰密碼系統來對資料明文與搜尋關鍵字加密。然而在這些改進架構中，仍然存在著搜尋階段所使用的固定性搜尋樣式衍生的隱私性風險，讓網路上的第三者或是雲端伺服器可以統計分析使用者的搜尋關鍵字與密文資料的關連性。

近年來開始有學者的研究提出以公開金鑰密碼系統的方式來產生無連結性的搜尋樣式，希望可以解決固定性搜尋樣式帶來的隱私性風險，但是公開金鑰密碼系統的特性也讓無連結性搜尋樣式運算效率並無法達到實務上的需求。因此本研究提出一個無連結性的密文搜尋機制，不須用公開金鑰密碼系統來運算來產生無連結性搜尋樣式，而是以冗餘密文搜尋區塊的擴展與置換技術的對稱式方法讓搜尋關鍵字成為無連結性搜尋樣式。而在機制搜尋階段設計中利用錯誤肯定 (false positive) 的效果使得搜尋結果達到無連結性，藉此混淆有心攔截資料的網路第三者，並且透過linked list和索引表的架構來限縮搜尋時的範圍，提高搜尋階段的效率。

研究過程中也藉由理論分析來計算搜尋樣式被統計分析的機率，並且模擬實作機制的流程進行安全與效率分析。而模擬實作的架構是利用一台個人電腦來模擬架構中的使用者端和伺服器端，並且在這台個人電腦上將機制透過 JAVA程式語言來實現並且模擬操作過程，最後將過程中的數據進行儲存運算效率和搜尋效率進行分析，藉此驗證該架構是否達到雲端儲存空間中的資料機密性、隱私性和實務上可被接受的運算與搜尋效率。希望透過本研究提出的機制讓雲端儲存服務能夠兼顧便利性與安全性。

The cloud storage service provides users a very convenient and omnipresent way to store and access data. Behind the convenient service, however, there exist many security issues. Services hardware equipment is not a user can control or during the transfer of files may be intercepted. In order to protect data, many users will encrypt their files in advance before uploading them to the cloud storage. But the original search method has been unable to effectively search the cipher text. Therefore, how to achieve an efficient and secure search on cipher text becomes an important topic of cloud storage services.

Because of these several security issues, let searchable encryption has become a particular field of research. This technology allows the server to search for files without decrypting. Moreover, the interested parties may perform statistical analysis by using fixed searching patterns.

In order to solve the early searchable encryption architecture shortcomings, many scholars put forward their own schemas that can be used in accordance with the encryption algorithms divided into two categories: symmetric searchable encryption and asymmetric searchable encryption. The former is use symmetric encryption encrypt the plaintext and keywords and latter is the use of asymmetric encryption to encrypt the plaintext and keywords. However, in these architectures still have privacy issues. Transmitted fixity search pattern in the search process will produce privacy risks, leading to a third party on the network or cloud servers can statistical analysis user''s search keywords and the association between the cipher text.

This research proposes an unlinkable cipher text search scheme used symmetric encryption. The proposed scheme constructs unlinkable searching patterns from redundant and keywords by expansion and permutation technologies. And the cloud server will respond false positive searching results due to the collision of searching patterns. The searching performance is efficient by means of using linked lists and indexed searching tables.

Course of the study will also use JAVA to implement this architecture. According to the results of implementation to analyze operation and search efficiency. Through theoretical calculations to analyze search pattern is statistical and analytical possibilities. According to the results of calculation and implementation, and then analyzes the security and performance. The analysis of security and performance confirms the proposed scheme provides higher efficiency and user privacy.

Keywords: Cloud storage, Searchable encryption, Unlinkable, false positive.

中文摘要 i
英文摘要 iii
誌謝 v
目錄 vi
圖目錄 viii
表目錄 ix
一、 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的及貢獻 3
1.4 論文架構 3
二、 密文搜尋相關研究 5
2.1 簡介 5
2.2 密文搜尋研究之演進 5
2.3 密文搜尋演算法 6
2.3.1 對稱式可搜尋加密法 6
2.3.2 非對稱式可搜尋加密法 8
2.4 搜尋樣式 9
2.5 合取關鍵字搜尋 9
三、 無連結性搜尋樣式 13
3.1 搜尋樣式研究之演進 13
3.2 無連結性的重要性 13
3.3 無連結性搜尋樣式產生方式 14
3.3.1 以非對稱金鑰方式產生 14
3.3.2 以對稱式方法產生 16
四、 主要參考研究 18
4.1 Kamara等人提出的對稱式密文搜尋 ─ CS2 18
4.1.1 架構與流程 18
4.1.2 優點與缺點 20
4.2 植基於False Positive的無連結性密文搜尋 20
4.2.1 架構與流程 20
4.2.2 優點與缺點 23
五、 本論文研究成果 24
5.1 研究需求與目標 24
5.2 Encrypt and Store 24
5.3 Create Search Tables 26
5.4 Search and Decrypt 27
5.5 合取關鍵字搜尋 28
六、 安全與效率分析 30
6.1 安全性分析 30
6.1.1 機密性 30
6.1.2 隱私性 30
6.1.3 無連結性搜尋樣式 30
6.1.4 無連結性搜尋結果 31
6.2 效率分析 32
6.2.1 運算效率 32
6.2.2 搜尋效率 32
七、 研究成果實作 33
7.1 系統環境與架構 33
7.1.1 實作環境 33
7.1.2 架構 33
7.1.3 操作概念 35
7.2 系統流程 39
7.2.1 Encrypt and Store 39
7.2.2 Create Search Tables 40
7.2.3 Search and Decrypt 42
7.3 實作結果與分析 44
八、 結論與未來展望 47
8.1 結論 47
8.2 未來展望 48
參考文獻 49
簡歷 52

[1]S. Kamara and K. Lauter, “Cryptographic Cloud Storage,” in Proceedings of Financial Cryptography: Workshop on Real-Life Cryptographic Protocols and Standardization 2010, January 2010.
[2]Google Drive, https://drive.google.com/
[3]D. Song, D. Wagner, and A. Perrig, “Practical techniques for searching on encrypted data,” In IEEE Symposium on Research in Security and Privacy, pp. 44-55. IEEE Computer Society, 2000.
[4]S.M. Bellovin and W.R. Cheswick, “Privacy-Enhanced Searches Using Encrypted Bloom Filters,” ePrint Archive, http://eprint.iacr.org/2004/022/, 2004.
[5]E-J. Goh, “Secure indexeses,” Technical Report 2003/216, IACR ePrint Cryptography Archive, 2003, http://eprint.iacr.org/2003/216
[6]Y.C. Chang and M. Mitzenmacher, “Privacy Preserving Keyword Searches on Remote Encrypted Data,” Proceedings of 3rd Applied Cryptography and Network Security Conference (ACNS), pp. 442-455, 2005.
[7]R. Curtmola, J. Garay, S. Kamara and R. Ostrovsky, ”Searchable symmetric encryption: improved definitions and efficient constructions,” ACM Conference on Computer and Communications Security, pp. 79-88, 2006.
[8]S. Kamara, C. Papamanthou, and T. Roeder, “CS2: A searchable cryptographic cloud storage system,” Technical Report MSR-TR-2011-58, Microsoft Research, 2011. http://research.microsoft.com/apps/pubs/?id=148632.
[9]D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” In Advances in Cryptology - Eurocrypt 2004, volume 3027 of Lecture Notes in Computer Science, pp. 506-522, Springer-Verlag, 2004.
[10]P. Golle, J. Staddon, and B. Waters, “Secure conjunctive keyword search over encrypted data,” In Applied Cryptography and Network Security Conference (ACNS), volume 3089 of Lecture Notes in Computer Science, pp. 31-45, Springer, 2004.
[11]M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, 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,” In Proc, of CRYPTO, pp. 205-222, 2005.
[12]Y. C. Chang and M. Mitzenmacher, “Privacy Preserving Keyword Searches on Remote Encrypted Data,” In Proc, of 3rd Applied Cryptography and Network Security Conference (ACNS), pp. 442-455, 2005.
[13]L. Ballard, S. Kamara and F. Monrose, “Achieving Efficient Conjunctive Keyword Searches over Encrypted Data,” In Proceedings of the Seventh International Conference on Information and Communication Security (ICICS 2005), pp. 414-426, 2005.
[14]J. Byun, D. Lee and J. Lim, “Efficient Conjunctive Keyword Search on Encrypted Data Storage System,” In Proceedings of EuroPKI 2006, LNCS 4043, Springer-Verlag, pp. 184-196, 2006.
[15]E. Ryu and T. Takagi, “Efficient Conjunctive Keyword-Searchable Encryption,” Advanced Information Networking and Applications Workshops, pp. 409-414, 2007.
[16]D. Boneh, “The Decision-Diffie Hellman Problem,” In Third International Symposium on Algorithmic Number Theory (ANTS-III), vol. 1423 of Lecture Notes in Computer Science, pp. 48-63, Springer-Verlag, 1998.
[17]D. Boneh and M. Franklin, “Identity based encryption from the Weil pairing,” In SIAM J. of Computing, vol. 32, no. 3, pp. 586-615, 2003.
[18]A. Joux, “The Weil and Tate pairings as building blocks for public key cryptosystems,” In Proceedings Fifth Algorithmic Number Theory Symposium, 2002.
[19]C.L. Lin and Y.C. Chen, “不具連結性搜尋樣式之加密資料搜尋,” 2009 International Conference on Advanced Information Technologies (AIT 2009), April 24th ~ 25th, 2009.
[20]M. Blum and S. Goldwasser, “An efficient probabilistic public key encryption scheme which hides all partial information,” Proceedings of Advances in Cryptology - CRYPTO ’84, pp. 289–299, 1985.
[21]C.L. Lin, “A False Positive-Based Unlinkable Ciphertext Searching for Cloud Storage Services,” 2012 International Conference on Business and Information (BAI 2012), July 3-5, 2012, Sapporo, Japan.
[22]Dropbox, https://www.dropbox.com/
[23]Block cipher mode of operation, Electronic codebook mode(ECB mode), https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_.28ECB.29
[24]Bouncy Castle, http://www.bouncycastle.org/