臺灣博碩士論文加值系統

關鍵字索引(Keyword Index)搜尋為一種加速文件關鍵字搜尋的一種架構，但是隨著文件的安全性越來越受到重視，文件開始以加密的型態儲存於資料庫，但是目前的索引架構並沒有針對加密文件作考量，也因此索引有可能會透露出文件的相關資訊，造成安全上的問題。本文提出了為加密文件設計的索引搜尋架構(PRP-Index, P-Index)，即使加密的文件資料及索引儲存於不被信任的伺服器端(Server)上，也不會有安全上的疑慮；另一個特點是索引架構不會影響文件的加密方式，讓使用者可以依據各種需求來使用不同的加密技術，使加密更有彈性。本論文主要貢獻為在保有索引搜尋效率下，明顯減少索引空間之使用、降低搜尋錯誤率及達成加密搜尋的隱私要求。

Keyword index is a data structure that allows us to search in constant time for documents containing specified keywords. Unfortunately, standard index constructions are not designed for encrypted documents, because they may leak some information about the document. In this thesis, we propose two index structures called PRP-Index and P-Index which are designed for encrypted documents. Even if these encrypted documents and their indexes are stored on an untrusted server, there are no security problems. Another characteristic is that the index structures and the document’s encryption techniques are independent. User can choose any encryption technique they want to use for their different kind of requirements. The advantages of our schemes include less space usage, lower false positive rate, and high privacy.

摘要 I
Abstract II
誌謝 III
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1前言 1
1.2加密搜尋的隱私維護 3
1.3加密文件的執行目標 4
1.4研究貢獻 5
1.5論文架構 6
第二章 相關研究 7
2.1背景知識 7
2.2 SWP加密文件搜尋機制 8
2.2.1 SWP的基礎架構 8
2.2.2 SWP的最終架構 9
2.3 Goh的Z-IDX 13
第三章 架構分析 16
3.1 背景知識 17
3.1.1 擬亂排列 17
3.1.2 虛擬亂數產生器 17
3.1.3 串流加密 18
3.2 PRP-Index(Pseudorandom Permutation-Index)機制 19
3.3 P-Index(Position-Index)機制 22
第四章 使用空間及錯誤率分析 25
4.1 PRP-Index使用空間及錯誤率 25
4.2 P-Index使用空間及錯誤率 26
4.3 比較與實際例子 27
第五章 安全性分析 29
第六章 結論 33
參考文獻 34

[1]B. H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” In Communications of the ACM, pp.422-426, July 1970.
[2]Brinkman, R. and Schoenmakers, B. and Doumen, J.M. and Jonker, W, “Experiments with Queries over Encrypted Data Using Secret Sharing,” In Secure Data Management (SDM), pp.33-46, 2005.
[3]D. Boneh, G.D. Crescenzo, R. Ostrovsky and G. Persiano, “Public Key Encryption with Keyword Search,” In Proceedings of IEEE Symposium on Security and Privacy, pp.44-45 IEEE, Apr 2004.
[4]D. Song, D. Wagner and A. Perrig, “Practical Techniques for Searches on Encrpted Data,” In Advances in Cryptology - EUROCRYPT 2004, pp.506-522, May 2000.
[5]E-J. Goh, “Secure Indexes,” In The Cryptology ePrint Archive, Report 2003/216, Mar 16, 2004.
[6]G. Amanatidis, A. Boldyreva, and A. O’Neill, “New security models and provably-secure schemes for basic query support in outsourced databases,” In Working Conference on Data and Applications Security (DBSec ’07), 2007.
[7]J. Baek, R. Safavi-Naini, and W. Susilo, “Public key encryption with keyword search revisited,” In Cryptology ePrint Archive, 2005.
[8]L.T.A. Joseph, A. Samsudin and B. Belaton, “Efficient Search on Encrypted Data”, In Networks, 2005. Jointly held with the 2005 IEEE 7th Malaysia International Conference on Communication, pp.6, Nov 2005.
[9]M. Bellare, A. Boldyreva and A. O’Neill, “Deterministic and Efficiently Searchable Encryption”, In Advances in Cryptology - CRYPTO 2007, pp.535-552, Aug 2007.
[10]M. Freedman, Y. Ishai, B. Pinkas and O. Reingold, “Keyword Search and Oblivious Pseudorandom Functions,” In Proceedings of 2nd Theory of Cryptography Conference (TCC ''05) Cambridge, Feb 2005.
[11]R. Brinkman, L. Feng, J. M. Doumen, P. H. Hartel, and W. Jonker, “Efficient tree search in encrypted data,” In Technical Report TR-CTIT-04-15, Mar 2004.
[12]R. Brinkman, L. Feng, S. Etalle, P.H. Hartel and W. Jonker, “Experimenting with linear search in encrypted data,” In Center for Telematics and Information Technology, University of Twente, Dec 2005.
[13]R. Curtmola, J. Garay, S. Kamara and R. Ostrovsky, “Searchable symmetric encryption: improved definitions and efficient constructions,” In ACM conference on Computer and communications security, pp.79-88 ACM CCS 2006.
[14]S. Bellovin and W. Cheswick, “Privacy-enhanced searches using encrypted bloom filters,” In Cryptology ePrint Archive, 2004.
[15]S. Artzi, A. Kiezun, C. Newport and D. Schultz, “Encrypted Keyword Search in a Distributed Storage System,” Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory, 2006.
[16]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, Introduction to Algorithms, 2th ed., MIT Press and McGraw-Hill, pp.221-252, 2001.