【正文】 . . . .密文數(shù)據(jù)庫檢索技術綜述摘要關鍵詞1 引言2 相關技術3 研究分類 數(shù)值型數(shù)據(jù)2002年，Hakan等人首次提出了在數(shù)據(jù)庫即服務（Database as a service, DaaS） Hacigumus H, Iyer B, Mehrotra S. Providing database as a service[C]//Data Engineering, 2002. Proceedings. 18th International Conference on. IEEE, 2002: 2938.模型下，針對加密數(shù)據(jù)執(zhí)行SQL查詢的方法 Hakan Hacigu ?mu ?s, Balakrishna R. Iyer, Chen Li, and Sharad Mehrotra. Executing sql over encrypted data in the databaseserviceprovider model. In SIGMOD Conference, pages 216–227, 2002.。其核心思想是：提出了一種過濾技術（桶劃分技術）縮小解密范圍，從而快速查詢加密數(shù)據(jù)。并基于桶劃分技術提出了一種對關系數(shù)據(jù)庫進行加密和存儲的模型，在此模型上存儲數(shù)據(jù)時，除了對關系表中的記錄采用常規(guī)加密外，還給每個屬性值增加一個桶號，桶號表示明文數(shù)據(jù)值位于某段區(qū)間內。在該模型中，數(shù)據(jù)擁有者（即用戶）對數(shù)據(jù)庫進行加密后將數(shù)據(jù)庫密文保存在服務提供商處，只有數(shù)據(jù)擁有者能夠解密。用戶提交查詢指令后，服務器端無需對密文解密即可進行粗粒度的查詢，得到包含查詢結果的一個候選結果集合，然后將該候選結果集合返回給用戶，用戶解密該候選結果集合并對明文進行計算即可得到最終的查詢結果。該方法返回一個比正確結果集合更大一些的集合，其中可能包含一些并不匹配查詢條件的密文元組，因此需要再對這個結果集合進行解密和過濾處理，才能得到最終的查詢結果。此外，該方法僅通過值域分區(qū)的方式建立數(shù)據(jù)庫值索引，容易造成數(shù)據(jù)庫信息泄漏。數(shù)據(jù)庫通常采用哈希技術分區(qū)的方式，這種方式的分區(qū)數(shù)量越多，檢索性能越好，但同時會造成更多的數(shù)據(jù)冗余。當每個分區(qū)中的數(shù)據(jù)記錄較多時，檢索效率會受到較大影響。2003年，Damiani等人提出基于索引的密文檢索方法 Damiani E, Vimercati S, Jajodia S, et al. Balancing confidentiality and efficiency in untrusted relational DBMSs[C]//Proceedings of the 10th ACM conference on Computer and munications security. ACM, 2003: 93102.。與桶劃分方法不同，該方法將數(shù)據(jù)進行元組級的加密，因此能夠進行元組級的檢索。該方法不按數(shù)值的順序分類，增加了安全性。其缺點是不能實現(xiàn)范圍搜索。Damiani又使用Btree編碼方式，這種方法可以實現(xiàn)范圍檢索，但是每次進行檢索時需要檢索的次數(shù)等于Btree的高度。2004年，Hakan等人深入研究了采用桶劃分技術以實現(xiàn)對加密數(shù)據(jù)執(zhí)行聚集查詢操作 Hac?g252。m252。? H, Iyer B, Mehrotra S. Efficient execution of aggregation queries over encrypted relational databases[C]//Database Systems for Advanced Applications. Springer Berlin Heidelberg, 2004: 125136.。2004年，Hore等人研究了依據(jù)數(shù)據(jù)分布實現(xiàn)最優(yōu)化桶劃分以減小通信代價 Hore B, Mehrotra S, Tsudik G. A privacypreserving index for range queries[C]//Proceedings of the Thirtieth international conference on Very large data basesVolume 30. VLDB Endowment, 2004: 720731.。Hore等人提出了一種改進的數(shù)據(jù)庫分區(qū)策略，利用數(shù)據(jù)庫分區(qū)的最優(yōu)算法,在數(shù)據(jù)庫檢索過程中最小化傳輸和解密的工作量,進一步提高了數(shù)據(jù)庫密文檢索效率。同時提出一種可控擴散算法,根據(jù)數(shù)據(jù)所有者的需要自適應地調整數(shù)據(jù)安全等級,采取犧牲一定密文檢索性能的方式,定制更為靈活的數(shù)據(jù)庫密文安全策略。2010年，Chase等人提出了結構加密算法來解決加密大矩陣和圖的查詢問題 M. Chase and S. Kamara, “Structured Encryption and Controlled Disclosure,” Advances in CryptologyASIACRYPT 2010, 2010, pp. 577–94.。這種算法是基于SSE的。其不足之處為：只能進行簡單的查詢例如數(shù)值訪問和“鄰居查詢”。2011年，Cao首次提出并解決了在云中查詢加密圖結構數(shù)據(jù)的隱私保護查詢(PPGQ) N. Cao et al., “PrivacyPreserving Query Over Encrypted GraphStructured Data in Cloud Computing,” 31st Int’l. Conf. Distributed Computing Systems, 2011, pp. 393–402.。并建立了嚴格的安全需求來實現(xiàn)云數(shù)據(jù)利用系統(tǒng)。并使用了“過濾驗證”的原則。重新建立了基于特征的索引來提供加密數(shù)據(jù)圖的特征相關信息。選擇了高效的內積作為修剪工具來過濾數(shù)據(jù)。為了保證圖查詢不造成隱私泄漏，提出了內積計算技術，并將其改進后能夠在未知背景維系模型下保證安全。 單關鍵詞檢索 單關鍵詞密文排序查詢加利福利亞大學的Song等人采取了序列加密(stream cipher)方法對文本數(shù)據(jù)進行加密處理，這樣無需解密就可以直接對加密文本搜索關鍵詞 Song D,Wagner D,Perig techniques for searches on encrypted data//Procedings of the IEEE Symposium on Security and Privacy(Samp。P 2000).Berkeley,California,USA,2000:4455。其優(yōu)點是：使用者和數(shù)據(jù)庫需要很少的通信，只需要一輪交互。(對稱密鑰)但是其方法有一些問題：第一，它與當前已有的一些文件加密方案不兼容；第二，它在針對加密數(shù)據(jù)的統(tǒng)計分析攻擊下并不安全，盡管提出了一些有啟發(fā)性的補救方法，但是其安全性證據(jù)在理論上是不夠健壯的；第三，不能進行連接詞檢索，且很難擴展。2003年，Goh等人 Goh E J. Secure Indexes[J]. IACR Cryptology ePrint Archive, 2003, 2003: 216.基于布隆過濾器對Song的效率進行改進，每個文件都有對應的一些獨立的哈希函數(shù)和Bloom Filter 數(shù)據(jù)結構。在文件加密之前，需要對文件中的關鍵字使用私鑰加密，再使用哈希函數(shù)映射到filter之上并記錄，最后，將映射后的filter和文件的密文上傳到服務器中。當用戶需要進行密文搜索時，需要將關鍵字的密文發(fā)送給云端服務器，再由云端服務器使用每個文件的哈希函數(shù)進行關鍵字到filter的映射。如果映射到的位置之前都有記錄的痕跡，則說明這個關鍵字有很大的概率是在該文件中。最后，云端服務器將得到的匹配文件發(fā)給用戶。結果：能夠利用哈希函數(shù)計算快速的特點,快速地查找關鍵字所在的密文文件。不足：它也繼承了Bloom Filter存在錯誤率的特點，有可能導致一些文件本來并不包含關鍵字,最后卻能夠通過哈希函數(shù)的檢測,而被云端作為結果返回給用戶，給用戶帶來一些額外的帶寬開銷和計算開銷。2004年， Boneh D, Di Crescenzo G, Ostrovsky R, et