密文數(shù)據(jù)庫檢索技術(shù)綜述.docx

精品文檔密文數(shù)據(jù)庫檢索技術(shù)綜述摘要關(guān)鍵詞1 引言2 相關(guān)技術(shù)3 研究分類3.1 數(shù)值型數(shù)據(jù)2002年，Hakan等人首次提出了在數(shù)據(jù)庫即服務(wù)（Database as a service, DaaS） Hacigumus H, Iyer B, Mehrotra S. Providing database as a serviceC/Data Engineering, 2002. Proceedings. 18th International Conference on. IEEE, 2002: 29-38.模型下，針對(duì)加密數(shù)據(jù)執(zhí)行SQL查詢的方法 Hakan Hacigu mu s, Balakrishna R. Iyer, Chen Li, and Sharad Mehrotra. Executing sql over encrypted data in the database-service-provider model. In SIGMOD Conference, pages 216227, 2002.。其核心思想是：提出了一種過濾技術(shù)（桶劃分技術(shù)）縮小解密范圍，從而快速查詢加密數(shù)據(jù)。并基于桶劃分技術(shù)提出了一種對(duì)關(guān)系數(shù)據(jù)庫進(jìn)行加密和存儲(chǔ)的模型，在此模型上存儲(chǔ)數(shù)據(jù)時(shí)，除了對(duì)關(guān)系表中的記錄采用常規(guī)加密外，還給每個(gè)屬性值增加一個(gè)桶號(hào)，桶號(hào)表示明文數(shù)據(jù)值位于某段區(qū)間內(nèi)。在該模型中，數(shù)據(jù)擁有者（即用戶）對(duì)數(shù)據(jù)庫進(jìn)行加密后將數(shù)據(jù)庫密文保存在服務(wù)提供商處，只有數(shù)據(jù)擁有者能夠解密。用戶提交查詢指令后，服務(wù)器端無需對(duì)密文解密即可進(jìn)行粗粒度的查詢，得到包含查詢結(jié)果的一個(gè)候選結(jié)果集合，然后將該候選結(jié)果集合返回給用戶，用戶解密該候選結(jié)果集合并對(duì)明文進(jìn)行計(jì)算即可得到最終的查詢結(jié)果。該方法返回一個(gè)比正確結(jié)果集合更大一些的集合，其中可能包含一些并不匹配查詢條件的密文元組，因此需要再對(duì)這個(gè)結(jié)果集合進(jìn)行解密和過濾處理，才能得到最終的查詢結(jié)果。此外，該方法僅通過值域分區(qū)的方式建立數(shù)據(jù)庫值索引，容易造成數(shù)據(jù)庫信息泄漏。數(shù)據(jù)庫通常采用哈希技術(shù)分區(qū)的方式，這種方式的分區(qū)數(shù)量越多，檢索性能越好，但同時(shí)會(huì)造成更多的數(shù)據(jù)冗余。當(dāng)每個(gè)分區(qū)中的數(shù)據(jù)記錄較多時(shí)，檢索效率會(huì)受到較大影響。2003年，Damiani等人提出基于索引的密文檢索方法 Damiani E, Vimercati S, Jajodia S, et al. Balancing confidentiality and efficiency in untrusted relational DBMSsC/Proceedings of the 10th ACM conference on Computer and communications security. ACM, 2003: 93-102.。與桶劃分方法不同，該方法將數(shù)據(jù)進(jìn)行元組級(jí)的加密，因此能夠進(jìn)行元組級(jí)的檢索。該方法不按數(shù)值的順序分類，增加了安全性。其缺點(diǎn)是不能實(shí)現(xiàn)范圍搜索。Damiani又使用B-tree編碼方式，這種方法可以實(shí)現(xiàn)范圍檢索，但是每次進(jìn)行檢索時(shí)需要檢索的次數(shù)等于B-tree的高度。2004年，Hakan等人深入研究了采用桶劃分技術(shù)以實(shí)現(xiàn)對(duì)加密數(shù)據(jù)執(zhí)行聚集查詢操作 Hacgm H, Iyer B, Mehrotra S. Efficient execution of aggregation queries over encrypted relational databasesC/Database Systems for Advanced Applications. Springer Berlin Heidelberg, 2004: 125-136.。2004年，Hore等人研究了依據(jù)數(shù)據(jù)分布實(shí)現(xiàn)最優(yōu)化桶劃分以減小通信代價(jià) Hore B, Mehrotra S, Tsudik G. A privacy-preserving index for range queriesC/Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment, 2004: 720-731.。Hore等人提出了一種改進(jìn)的數(shù)據(jù)庫分區(qū)策略，利用數(shù)據(jù)庫分區(qū)的最優(yōu)算法,在數(shù)據(jù)庫檢索過程中最小化傳輸和解密的工作量,進(jìn)一步提高了數(shù)據(jù)庫密文檢索效率。同時(shí)提出一種可控?cái)U(kuò)散算法,根據(jù)數(shù)據(jù)所有者的需要自適應(yīng)地調(diào)整數(shù)據(jù)安全等級(jí),采取犧牲一定密文檢索性能的方式,定制更為靈活的數(shù)據(jù)庫密文安全策略。2010年，Chase等人提出了結(jié)構(gòu)加密算法來解決加密大矩陣和圖的查詢問題 M. Chase and S. Kamara, “Structured Encryption and Controlled Disclosure,” Advances in Cryptology-ASIACRYPT 2010, 2010, pp. 57794.。這種算法是基于SSE的。其不足之處為：只能進(jìn)行簡(jiǎn)單的查詢例如數(shù)值訪問和“鄰居查詢”。2011年，Cao首次提出并解決了在云中查詢加密圖結(jié)構(gòu)數(shù)據(jù)的隱私保護(hù)查詢(PPGQ) N. Cao et al., “Privacy-Preserving Query Over Encrypted Graph-Structured Data in Cloud Computing,” 31st Intl. Conf. Distributed Computing Systems, 2011, pp. 393402.。并建立了嚴(yán)格的安全需求來實(shí)現(xiàn)云數(shù)據(jù)利用系統(tǒng)。并使用了“過濾-驗(yàn)證”的原則。重新建立了基于特征的索引來提供加密數(shù)據(jù)圖的特征相關(guān)信息。選擇了高效的內(nèi)積作為修剪工具來過濾數(shù)據(jù)。為了保證圖查詢不造成隱私泄漏，提出了內(nèi)積計(jì)算技術(shù)，并將其改進(jìn)后能夠在未知背景維系模型下保證安全。3.2 單關(guān)鍵詞檢索3.2.1 單關(guān)鍵詞密文排序查詢加利福利亞大學(xué)的Song等人采取了序列加密(stream cipher)方法對(duì)文本數(shù)據(jù)進(jìn)行加密處理，這樣無需解密就可以直接對(duì)加密文本搜索關(guān)鍵詞 Song D,Wagner D,Perig A.Practical techniques for searches on encrypted data/Procedings of the IEEE Symposium on Security and Privacy(S&P 2000).Berkeley,California,USA,2000:44-55。其優(yōu)點(diǎn)是：使用者和數(shù)據(jù)庫需要很少的通信，只需要一輪交互。(對(duì)稱密鑰)但是其方法有一些問題：第一，它與當(dāng)前已有的一些文件加密方案不兼容；第二，它在針對(duì)加密數(shù)據(jù)的統(tǒng)計(jì)分析攻擊下并不安全，盡管提出了一些有啟發(fā)性的補(bǔ)救方法，但是其安全性證據(jù)在理論上是不夠健壯的；第三，不能進(jìn)行連接詞檢索，且很難擴(kuò)展。2003年，Goh等人 Goh E J. Secure IndexesJ. IACR Cryptology ePrint Archive, 2003, 2003: 216.基于布隆過濾器對(duì)Song的效率進(jìn)行改進(jìn)，每個(gè)文件都有對(duì)應(yīng)的一些獨(dú)立的哈希函數(shù)和Bloom Filter 數(shù)據(jù)結(jié)構(gòu)。在文件加密之前，需要對(duì)文件中的關(guān)鍵字使用私鑰加密，再使用哈希函數(shù)映射到filter之上并記錄，最后，將映射后的filter和文件的密文上傳到服務(wù)器中。當(dāng)用戶需要進(jìn)行密文搜索時(shí)，需要將關(guān)鍵字的密文發(fā)送給云端服務(wù)器，再由云端服務(wù)器使用每個(gè)文件的哈希函數(shù)進(jìn)行關(guān)鍵字到filter的映射。如果映射到的位置之前都有記錄的痕跡，則說明這個(gè)關(guān)鍵字有很大的概率是在該文件中。最后，云端服務(wù)器將得到的匹配文件發(fā)給用戶。結(jié)果：能夠利用哈希函數(shù)計(jì)算快速的特點(diǎn),快速地查找關(guān)鍵字所在的密文文件。不足：它也繼承了Bloom Filter存在錯(cuò)誤率的特點(diǎn)，有可能導(dǎo)致一些文件本來并不包含關(guān)鍵字,最后卻能夠通過哈希函數(shù)的檢測(cè),而被云端作為結(jié)果返回給用戶，給用戶帶來一些額外的帶寬開銷和計(jì)算開銷。2004年，D.Boneh等人提出了真正意義上的可搜索公鑰加密方案 Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword searchC/Advances in Cryptology-Eurocrypt 2004. Springer Berlin Heidelberg, 2004: 506-522.(簡(jiǎn)稱:PEKS方案),為此業(yè)界把2004年定義為可搜索公鑰加密的元年。在論文中他們提出了一種基于雙線性對(duì)函數(shù)的單關(guān)鍵可搜索公鑰加密方案,該方案指出,第三方服務(wù)器根據(jù)單關(guān)鍵字的密文信息在整個(gè)服務(wù)器數(shù)據(jù)庫中檢索相關(guān)的文章,保證對(duì)檢索的信息一無所知。這項(xiàng)新技術(shù)的提出開啟了可搜索公鑰加密技術(shù)的新時(shí)代。優(yōu)點(diǎn)：支持?jǐn)?shù)據(jù)接收者對(duì)多個(gè)發(fā)送者所加密的密文中進(jìn)行搜索的應(yīng)用場(chǎng)景，而且由于隨機(jī)數(shù)的作用，系統(tǒng)的加密效果為非確定性加密，導(dǎo)致了服務(wù)器端無法通過密文是否相同來判斷索引表(或搜索憑證)中是否具有相同的關(guān)鍵字。缺點(diǎn)：計(jì)算開銷因?yàn)殡p線性對(duì)的引進(jìn)而加大，特別是對(duì)操作(pairing operation)的計(jì)算開銷較大，使得該方法在海量數(shù)據(jù)處理場(chǎng)景中的應(yīng)用性受到一定的限制；另外，PEKS的安全性是在隨機(jī)語言機(jī)模型(random oracle model)下成立，并不適合現(xiàn)實(shí)應(yīng)用。2005年，Abdalla等人提出一種使用臨時(shí)性關(guān)鍵字可檢索的公鑰加密方案(簡(jiǎn)稱:PETKS方案) Abdalla M, Bellare M, Catalano D, et al. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensionsC /Advances in CryptologyCRYPTO 2005. Springer Berlin Heidelberg, 2005: 205-222.。在該方案的驗(yàn)證階段,用戶一旦需要驗(yàn)證就要進(jìn)行必須的、相關(guān)的解密操作,這樣無形中就增大了服務(wù)器的開銷。2005年，J.Baek等人提出了一種不需要使用安全信道來傳輸數(shù)據(jù)的基于關(guān)鍵字的公鑰加密可搜索方案(簡(jiǎn)稱:SCF-PEKS方案) Baek J, Safavi-Naini R, Susilo W. Public key encryption with keyword search revisitedM/Computational Science and Its ApplicationsICCSA 2008. Springer Berlin Heidelberg, 2008: 1249-1259.,這種方案保證信息在客戶端和服務(wù)器端的傳送過程中,不會(huì)受到攻擊或發(fā)生泄漏等問題,保證了搜索信息、加密數(shù)據(jù)的安全性。2005年，Wang等人 Wang Z F, Dai J, Wang W, et al. Fast query over encrypted character data in databaseM/Computational and Information Science. Springer Berlin Heidelberg, 2005: 1027-1033.提出一種基于對(duì)偶編碼的特征值提取方法,將字符型明文數(shù)據(jù)拆分為多個(gè)字符對(duì)偶,根據(jù)這些字符對(duì)偶提取字符型數(shù)據(jù)的特征值,存儲(chǔ)到一個(gè)新的字段中,在數(shù)據(jù)庫密文檢索時(shí),根據(jù)這個(gè)輔助字段將不符合關(guān)鍵詞字符特征的數(shù)據(jù)庫記錄過濾掉,再對(duì)剩余的數(shù)據(jù)庫記錄做解密處理,得到明文的解密結(jié)果,最后在解密結(jié)果中進(jìn)行明文檢索,獲得最終檢索結(jié)果。2006年，Curtmola等人 Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: improved definitions and efficient constructionsC/Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006: 79-88.在Song的基礎(chǔ)上給出更嚴(yán)格的安全性定義和更高效的對(duì)稱密鑰可檢索加密方法構(gòu)造，利用加密Hash表存儲(chǔ)關(guān)鍵詞和密文文件標(biāo)識(shí)的映射關(guān)系實(shí)現(xiàn)密文數(shù)據(jù)查詢。2007年，Zhu等人提出一種基于字符特征矩陣的數(shù)據(jù)庫加密策略 Zhu H, Cheng J, Jin R, et al. Executing Query over Encrypted Character Strings in DatabasesC/Frontier of Computer Science and Technology, 2007. FCST 2007. Japan-China Joint Workshop on. IEEE, 2007: 90-97.。這種加密策略也將數(shù)據(jù)庫的密文檢索分為過濾和解密兩個(gè)階段,字符特征矩陣記錄了每個(gè)字符型數(shù)據(jù)中包含的字符,同時(shí)也記錄了每個(gè)字符與哪些字符相鄰,這種加密策略可以檢索任意長(zhǎng)度的字符關(guān)鍵詞,解決了基于對(duì)偶編碼的數(shù)據(jù)庫加密策略不能檢索單個(gè)字符的問題,第一階段的過濾效率較高,但字符特征矩陣中存儲(chǔ)了大量特征數(shù)據(jù),產(chǎn)生了較多的數(shù)據(jù)冗余,因此,在這種數(shù)據(jù)庫加密策略中采取A.Tan提出的矩陣壓縮方法存儲(chǔ)特征索引,降低了索引存儲(chǔ)的占用空間,在安全性和密文檢索效率間取得了較好的平衡.2007年，Zhang等人基于數(shù)值型數(shù)據(jù)的數(shù)據(jù)庫分區(qū)方法,提出一種字符型數(shù)據(jù)密文的分區(qū)索引 Zhang Y, Li W, Niu X. A method of bucket index over encrypted character data in databaseC/Intelligent Information Hiding and Multimedia Signal Processing, 2007. IIHMSP 2007. Third International Conference on. IEEE, 2007, 1: 186-189.。這種索引通過將字符信息轉(zhuǎn)換為數(shù)值型來記錄字符間的關(guān)系特征,利用索引過濾掉部分不符合檢索條件的數(shù)據(jù)庫記錄,再對(duì)剩余一記錄解密,進(jìn)行二次檢索后返回檢索結(jié)果。2008年，Zhang等人提出了一種數(shù)據(jù)庫密文索引策略 Zhang Y, Li W, Niu X M. Secure cipher index over encrypted character data in databaseC/Machine Learning and Cybernetics, 2008 International Conference on. IEEE, 2008, 2: 1111-1116.,將字符數(shù)據(jù)映射為索引值,通過SQL語句翻譯器將SQL檢索語句轉(zhuǎn)換為對(duì)索引的快速匹配,為了保證密文索引的安全性,策略采用了哈希技術(shù)和數(shù)字?jǐn)_亂的方法,這樣不同記錄中的相同字符將會(huì)對(duì)應(yīng)不同的索引值,索引值不再具有統(tǒng)計(jì)特征,從而避免基于頻率統(tǒng)計(jì)的數(shù)據(jù)庫攻擊。2009年，Zerr等人 Zerr S, Olmedilla D, Nejdl W, et al. Zerber+ r: Top-k retrieval from a confidential indexC/Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. ACM, 2009: 439-449.發(fā)現(xiàn)即使列表元素（倒序包含每個(gè)關(guān)鍵詞的文檔ID）被加密，仍然可以根據(jù)發(fā)布列表的詞頻分布來重新確認(rèn)關(guān)鍵詞。所以他們改變了相關(guān)性分?jǐn)?shù)，使每個(gè)關(guān)鍵詞的詞頻相等。在此基礎(chǔ)上，提出了在加密數(shù)據(jù)中進(jìn)行安全的排序搜索的方法。這個(gè)方案在統(tǒng)計(jì)意義上滿足安全定義，被稱之為R-機(jī)密性(r-confidentiality)。不足之處為：它需要大量的預(yù)處理，而且不能簡(jiǎn)單地處理動(dòng)態(tài)分?jǐn)?shù)，所以安全級(jí)別很低。3.2.2 模糊匹配查詢2009年，Liu等人提出一種基于Bloom Filter的數(shù)據(jù)庫索引方法 Liu L, Gai J. Bloom filter based index for query over encrypted character strings in databaseC/Computer Science and Information Engineering, 2009 WRI World Congress on. IEEE, 2009, 1: 303-307.。Bloom Filter能夠支持?jǐn)?shù)據(jù)庫模糊檢索，根據(jù)數(shù)據(jù)庫索引的匹配可將部分不符合檢索條件的數(shù)據(jù)庫記錄排除。2010年，Li等人針對(duì)關(guān)鍵詞精確匹配的不足，提出云計(jì)算環(huán)境下基于編輯距離的加密字符串模糊檢索方案 Li J, Wang Q, Wang C, et al. Fuzzy keyword search over encrypted data in cloud computingC/INFOCOM, 2010 Proceedings IEEE. IEEE, 2010: 1-5.。它使用編輯距離來量化字符串的相似度，并為每個(gè)字符串附加一個(gè)基于通配符的模糊字符串組，用多個(gè)精確匹配來實(shí)現(xiàn)模糊檢索。其不足為：該方法需要語義庫的支持，且僅僅針對(duì)“all-or-nothing”的查詢方式，并返回給用戶完全無區(qū)分性的查詢結(jié)果。對(duì)于Li等人提出的基于編輯距離d的加密字符串模糊檢索方案,他們解決的是d1的情況，當(dāng)d1時(shí)，Wang等人提出了方案 Wang C, Ren K, Lou W, et al. Toward publicly auditable secure cloud data storage servicesJ. Network, IEEE, 2010, 24(4): 19-24.來擴(kuò)展它。當(dāng)d很大時(shí)，他們所用的通用抑制技術(shù)就節(jié)省了很多空間。他們使用單詞查找樹（一種數(shù)據(jù)結(jié)構(gòu)）來保存序列跟編碼，把檢索的復(fù)雜度從O(N)降到了O(1)。這兩者的缺點(diǎn)都是返回給用戶的查詢結(jié)果不可區(qū)分，并且因?yàn)槎际褂昧薙SE框架，因此均沒有實(shí)現(xiàn)查詢的不可連接性。（王偉，單關(guān)鍵詞or多關(guān)鍵詞）3.2.3 分級(jí)檢索（Ranked Search）2010年，Wang等人 Wang C, Cao N, Li J, et al. Secure ranked keyword search over encrypted cloud dataC/Distributed Computing Systems (ICDCS), 2010 IEEE 30th International Conference on. IEEE, 2010: 253-262.考慮關(guān)鍵詞詞頻信息,提出基于對(duì)稱密鑰保序加密技術(shù) OPSE Boldyreva A, Chenette N, Lee Y, et al. Order-preserving symmetric encryptionM/Advances in Cryptology-EUROCRYPT 2009. Springer Berlin Heidelberg, 2009: 224-241.的單關(guān)鍵詞分級(jí)密文排序查詢方法（RSSE），采取了OPSE方案來提高實(shí)際性能，采用此方案后，明文的數(shù)值順序在加密后將被維持原狀。具體來說，在查詢過程中，每個(gè)文檔的相關(guān)性順序（用OPSE加密過的相關(guān)性分?jǐn)?shù)）將被告知服務(wù)器。通過這個(gè)方式，相關(guān)性分?jǐn)?shù)的排序?qū)?huì)像在明文中一樣高效。然而，因?yàn)樵嫉腛PSE算法是確定性的加密方案，這仍然會(huì)泄漏很多信息。如果服務(wù)器上的數(shù)據(jù)集中包含很多此類背景信息，例如每個(gè)明文關(guān)鍵詞的相關(guān)性分?jǐn)?shù)的分布，那么就能反向推導(dǎo)出關(guān)鍵詞。為了打破這種確定性，作者提出了一對(duì)多保序映射(OPM),它把相同的相關(guān)性分?jǐn)?shù)映射到不同的加密數(shù)值上。因此，相同的明文不再是確定的加密成確定的密文。他們更進(jìn)一步對(duì)不同的列表使用了不同的密鑰來加密相關(guān)性分?jǐn)?shù)，這使得OPM更加可靠。RSSE方案正是通過使用OPSE和OPM來實(shí)現(xiàn)數(shù)據(jù)和索引的隱私保護(hù)。該方法的不足之處為：該方法對(duì)相似度計(jì)算并未全面考慮，因?yàn)樾枰獟呙杷形臋n而不易進(jìn)行索引更新，且僅支持關(guān)鍵詞的排序查詢。2012年，Wang等人為解決以往密文檢索中布爾檢索（Boolean search）的局限性，提出了一種分級(jí)檢索（Ranked search）方法 Wang C, Cao N, Ren K, et al. Enabling secure and efficient ranked keyword search over outsourced cloud dataJ. Parallel and Distributed Systems, IEEE Transactions on, 2012, 23(8): 1467-1479.。該方法按照檢索結(jié)果的相關(guān)性，設(shè)置一種分類標(biāo)準(zhǔn)，例如對(duì)相關(guān)性進(jìn)行評(píng)分，建立安全的可檢索的索引，形成一對(duì)多的保序映射。與不分類的返回結(jié)果相比，能夠提高系統(tǒng)的穩(wěn)定性。3.3 多關(guān)鍵詞檢索3.3.1 多關(guān)鍵詞密文排序查詢2005年，D.J.Park等人提出多關(guān)鍵字可搜索公鑰加密方案(簡(jiǎn)稱:PECK方案) Park D J, Kim K, Lee P J. Public key encryption with conjunctive field keyword searchM/Information Security Applications. Springer Berlin Heidelberg, 2005: 73-86.,這個(gè)可搜索加密方案是對(duì)現(xiàn)有可搜索加密技術(shù)的一種改進(jìn),符合現(xiàn)實(shí)可搜索加密的場(chǎng)景,不過后來被被人證明這種多關(guān)鍵字可搜索加密方案不能抵抗關(guān)鍵字猜想攻擊。2012年，程芳權(quán)等提出了云環(huán)境下在大規(guī)模加密云數(shù)據(jù)上進(jìn)行高效且具有隱私保護(hù)能力的個(gè)性化密文排序查詢方法 程芳權(quán), 彭智勇, 宋偉, 等. 云環(huán)境下一種隱私保護(hù)的高效密文排序查詢方法J. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(11): 2215-2227.。其貢獻(xiàn)為：a) 提出了針對(duì)云環(huán)境下多數(shù)據(jù)擁有者數(shù)據(jù)外包及選擇性數(shù)據(jù)查詢授權(quán)特征的多屬性多關(guān)鍵詞密文排序查詢,并定義其系統(tǒng)模型和攻擊模型.基于無證書認(rèn)證思想設(shè)計(jì)不依賴于可信第三方和安全傳輸信道的可認(rèn)證PKES Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword searchC/Advances in Cryptology-Eurocrypt 2004. Springer Berlin Heidelberg, 2004: 506-522.(支持關(guān)鍵詞檢索的公鑰加密),并構(gòu)建支持系統(tǒng)模型的RQED框架以增強(qiáng)查詢隱私保護(hù)。b) 基于RQED框架,設(shè)計(jì)支持多屬性數(shù)據(jù)隱私保護(hù)詞權(quán)重、查詢?cè)~權(quán)重及用被授權(quán)可訪問數(shù)據(jù)范圍等更客觀、合理的密文查詢排序函數(shù)。c) 考慮到單數(shù)據(jù)不確定性、數(shù)據(jù)和授權(quán)更新不確定性以及大規(guī)模密文數(shù)據(jù)查詢，提出基于層次動(dòng)態(tài)布隆過濾器的RQED索引機(jī)制，來提高密文查詢執(zhí)行與密文索引的時(shí)空效率。結(jié)果：RQED 機(jī)制中動(dòng)態(tài)布隆過濾器索引大大降低了索引空間開銷.對(duì)于索引私鑰, RQED機(jī)制中用戶只需存儲(chǔ)一對(duì)公私鑰,現(xiàn)有方法則需存儲(chǔ)密鑰矩陣且隨著關(guān)鍵詞詞典規(guī)模增大而帶來巨大空間開銷,并且當(dāng)涉及多數(shù)據(jù)擁有者選擇性 查詢授權(quán)時(shí),客戶端更是無法承受。總結(jié)所有實(shí)驗(yàn)結(jié)果可以看出，RQED機(jī)制較之現(xiàn)有多關(guān)鍵詞密文排序查詢方法有明顯的時(shí)空效率優(yōu)勢(shì).2012年，丁茂震針對(duì)現(xiàn)有部分關(guān)鍵字公鑰可搜索加密方案效率不高、安全性較低、必須使用安全信道傳輸數(shù)據(jù)等缺陷，提出了一種新的、高效的多關(guān)鍵字可搜索公鑰加密方案(NSCF-PECK) 丁茂震. 云環(huán)境中密文搜索技術(shù)的研究D. 北京郵電大學(xué), 2013.。這種方案基于雙線性對(duì)構(gòu)造,并采用公共信道來傳輸密文。在整個(gè)算法的設(shè)計(jì)上,僅僅使用了兩次雙線性對(duì)運(yùn)算,極大的減小了可搜索公鑰加密技術(shù)的計(jì)算開支。同時(shí)在客戶端和云服務(wù)器之間釆用公共信道來傳送加密的數(shù)據(jù),減少了建設(shè)安全信道的費(fèi)用。在上述NSCF-PECK可搜索公鑰加密方案的基礎(chǔ)上,本文提出了一種云端密文搜索系統(tǒng)的應(yīng)用方案。該應(yīng)用方案利用MapReduce并行計(jì)算模型技術(shù)設(shè)計(jì)該應(yīng)用方案的并行搜索引擎,把一些開源技術(shù)和分布式計(jì)算思想應(yīng)用到該應(yīng)用方案之中,充分利用云計(jì)算技術(shù)優(yōu)勢(shì)提高對(duì)海量密文的搜索效率。該系統(tǒng)采用分層化和模塊化的設(shè)計(jì)思路保證了方案的可維護(hù)性、可擴(kuò)展性和應(yīng)用的靈活性。為了進(jìn)一步滿足用戶個(gè)性化查詢需求，Cao等人第一次提出多關(guān)鍵詞密文排序查詢問題 Cao N, Wang C, Li M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud dataJ. Parallel and Distributed Systems, IEEE Transactions on, 2014, 25(1): 222-233.，并基于安全KNN查詢技術(shù) Wong W K, Cheung D W, Kao B, et al. Secure kNN computation on encrypted databasesC/Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ACM, 2009: 139-152.中索引向量與查詢向量間“內(nèi)積相似度”來實(shí)現(xiàn)排序查詢并進(jìn)行隱私保護(hù)增強(qiáng)。其不足為：該方法并未考慮數(shù)據(jù)中索引關(guān)鍵詞權(quán)重及查詢關(guān)鍵詞權(quán)重等因素，從而不能返回滿足用戶查詢請(qǐng)求的準(zhǔn)確排序結(jié)果；并且該方法需要構(gòu)建系統(tǒng)枚舉索引關(guān)鍵詞詞典并在用戶端存儲(chǔ)，這無疑不符合實(shí)際應(yīng)用且造成較大客戶端負(fù)擔(dān)。例如，當(dāng)詞典規(guī)模為N時(shí)，其用戶需要安全傳輸和存儲(chǔ)的密鑰矩陣空間開銷為O(N2)則隨著N增大將帶給客戶端難以承受的負(fù)擔(dān)。3.3.2 語義關(guān)鍵詞檢索在實(shí)際的應(yīng)用場(chǎng)景中，用戶的輸入不一定是預(yù)定義的關(guān)鍵字，而是關(guān)鍵字的同義詞，這些同義詞無法通過精確或者模糊查找的方法搜索。2013年，F(xiàn)u等人首次提出了一種有效的語義查詢的解決方案 Fu Z, Sun X, Xia Z, et al. Multi-keyword ranked search supporting synonym query over encrypted data in cloud computingC/2013 IEEE 32nd International Performance Computing and Communications Conference (IPCCC). IEEE, 2013: 1-8.。通過建立一個(gè)高效靈活的可搜索加密機(jī)制，它允許基于多關(guān)鍵字分級(jí)的搜索和語義搜索。使用VSM(Vector Space Model)建立索引文件。為了提高查詢的效率，使用了樹狀索引結(jié)構(gòu)，即平衡二叉樹。通過構(gòu)造搜索樹和文件索引樹，能夠找到相關(guān)文件。該加密模型能夠滿足兩方面的安全需求：已知密文和已知后臺(tái)。分級(jí)(rank): In information retrieval, a ranking function is usually used to evaluate relevant scores of matching files to a request.對(duì)于搜索文件進(jìn)行評(píng)級(jí)，搜索最接近用戶輸入的文件。2014年，Cao等人 Cao N, Wang C, Li M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud dataJ. Parallel and Distributed Systems, IEEE Transactions on, 2014, 25(1): 222-233.提出了一種能夠?qū)崿F(xiàn)可靠語義查詢的方法。根據(jù)可能出現(xiàn)的詞語，建立一個(gè)語義庫，記錄詞語之間的相近關(guān)系。同時(shí)利用兩種云結(jié)構(gòu)，一種是私有云，另一種是公有云。查詢的過程分為兩個(gè)階段。第一階段，我們將搜索關(guān)鍵詞進(jìn)行擴(kuò)展（在私有云上）；第二階段，我們按照擴(kuò)展后的關(guān)鍵詞搜索（在公有云上）。最終，匹配的文件會(huì)按序回傳。2014年，F(xiàn)u等人提出了在加密云數(shù)據(jù)中進(jìn)行語意關(guān)鍵詞檢索的方法 Fu Z, Shu J, Sun X, et al. Semantic keyword search based on trie over encrypted cloud dataC/Proceedings of the 2nd international workshop on Security in cloud computing. ACM, 2014: 59-62.。其過程為：數(shù)據(jù)擁有者向云服務(wù)商上傳經(jīng)過控制算法（基于前綴樹）生成的“關(guān)鍵詞限制集”索引文件和加密后的文件，授權(quán)用戶發(fā)起查詢指令后，云服務(wù)商利用索引文件在密文數(shù)據(jù)中進(jìn)行指定的查詢操作，并將查詢到的有關(guān)加密文件返回給查詢者。其能達(dá)到的效果為：能給返回包含跟查詢?cè)~語語意相近的詞匯的文檔。采用了控制算法消除了在索引機(jī)構(gòu)和在查詢中列舉所有相近關(guān)鍵詞的需求，并且減少了索引的維度。平衡單詞查找樹也通過建立索引提高了搜索效率。3.3.3 多關(guān)鍵詞連接查詢2004年，Golle等人提出了在加密數(shù)據(jù)中進(jìn)行關(guān)鍵詞連接查詢的協(xié)議 Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted dataC/Applied Cryptography and Network Security. Springer Berlin Heidelberg, 2004: 31-45.，使用了“指數(shù)模塊（modular exponentiation）”（因此比song等人需要更多的計(jì)算開銷）和隨機(jī)化搜索功能來確保搜索到的文件中包含的連接關(guān)鍵詞。作者提出了兩個(gè)方案，第一種方案的通信開銷和文件的數(shù)量有關(guān)，但是這些開銷可以在查詢發(fā)生之前的離線階段產(chǎn)生。這種方案的安全性能是基于決策性迪菲-赫爾曼(DDH)假設(shè)的。第二種方案的通信開銷取決于關(guān)鍵詞段的數(shù)量，它的安全性是基于新的硬件假設(shè)的。2007年，Hwang和Lee等人在隨機(jī)語言機(jī)模型中基于決策線性迪菲-赫爾曼(DDLH)假設(shè)提出了更簡(jiǎn)單高效的公鑰加密方案，實(shí)現(xiàn)了連接詞查詢 Hwang Y H, Lee P J. Public key encryption with conjunctive keyword search and its extension to a multi-user systemM/Pairing-Based CryptographyPairing 2007. Springer Berlin Heidelberg, 2007: 2-22.。其核心思想是：通過使用多接受者公鑰加密方法(multi-receiver public key encryption)將所有接受者的公鑰對(duì)關(guān)鍵字集合進(jìn)行加密,通過支持連接關(guān)鍵字的公鑰加密方法,實(shí)現(xiàn)了支持每個(gè)接受者只需要使用自己的私鑰就能對(duì)連接關(guān)鍵字進(jìn)行搜索,實(shí)現(xiàn)了在“單個(gè)發(fā)送者-多個(gè)接受者”場(chǎng)景下支持密文搜索的效果。他們的方案在服務(wù)器和用戶之間有高效的通信和存儲(chǔ)開銷，并且有合理的計(jì)算開銷。4 密文數(shù)據(jù)庫系統(tǒng)一般情況下構(gòu)建安全數(shù)據(jù)庫系統(tǒng)的三種方式：(1) 靜止數(shù)據(jù)加密（Encryption at Rest）：數(shù)據(jù)加密存儲(chǔ)在商用存儲(chǔ)系統(tǒng)（如硬盤）中，查詢時(shí)將密文數(shù)據(jù)發(fā)送給可信域，在可信域中解密、處理或者緩存。這是主流數(shù)據(jù)庫產(chǎn)品如Oracle和MS SQL Server的使用原則，加密特定的數(shù)據(jù)（數(shù)據(jù)表或者分區(qū)），認(rèn)為硬盤不可靠，而系統(tǒng)其他組件可靠（如CPU、內(nèi)存等）?；谕皠澐值腟QL查詢（2002 SIGMOD）也屬于這一類。盡管這種方式可以保證服務(wù)器端數(shù)據(jù)的私密性，但將密文數(shù)據(jù)（如完整的數(shù)據(jù)表）發(fā)送給客戶終端會(huì)帶來過高的通信代價(jià)。(2) 安全服務(wù)器：通過在服務(wù)器端增加特殊的高安全性處理節(jié)點(diǎn)，解決(1)中的不足。如AWS GovCloud（Amazon Web Services）由商用服務(wù)器構(gòu)成，通過運(yùn)行特殊的受審查的軟件棧、限制性的安全策略和主機(jī)隔離（網(wǎng)路連接及物理位置）增強(qiáng)了安全性。缺點(diǎn)：物理和邏輯上的隔離限制了應(yīng)用的類型和客戶端的類型；使云碎片化；最終導(dǎo)致構(gòu)建和維護(hù)云設(shè)施成本增加、使云計(jì)算的一些特性如無縫故障切換、動(dòng)態(tài)可擴(kuò)展性等復(fù)雜化。其他的安全服務(wù)器解決方案采用了IBM secure coprocessors(SCPs)或者Hardware Security Modules(HSMs)等設(shè)備，這些設(shè)備是和服務(wù)器獨(dú)立的，可作為擴(kuò)展卡方便地部署到商用服務(wù)器內(nèi)部，形成一個(gè)可信計(jì)算區(qū)域。缺點(diǎn)是安全協(xié)處理器內(nèi)存及處理能力有限，不實(shí)用于運(yùn)行工業(yè)強(qiáng)度的數(shù)據(jù)庫系統(tǒng)。(3) 全同態(tài)加密：直接對(duì)密文進(jìn)行計(jì)算而無需解密，可用于傳統(tǒng)不可信服務(wù)器，密文結(jié)果由服務(wù)器發(fā)送給可信客戶端。但是，目前最先進(jìn)的全同態(tài)加密方法成本過高因此不實(shí)用。目前有一些部分同態(tài)加密方法（限制運(yùn)算操作，如加法同態(tài)或者乘法同態(tài)；限制特定運(yùn)算的次數(shù)，如最多N次乘法），具有一定的實(shí)用性，但不能提供完整的正交安全需求。參考文獻(xiàn)1) C. Gentry. Computing arbitrary functions of encrypted data. Commun. ACM, 53(3), 2010.2) S. BajajandR. Sion. TrustedDB: a trusted hardware based database with privacy and data confidentiality. In SIGMOD, 2011.3) R. A. Popa, C. M. S. Redfield, N. Zeldovich, et al. Cryptdb: protecting confidentiality with encrypted query processing. In SOSP, pages 85100, 2011.4.1 CryptDBCryptDB R. A. Popa, C. M. S. Redfield, N. Zeldovich, et al. Cryptdb: protecting confidentiality with encrypted query processing. In SOSP, pages 85100, 2011., Popa R A, Redfield C, Zeldovich N, et al. CryptDB: Processing queries on an encrypted databaseJ. Communications of the ACM, 2012, 55(9): 103-111.是第一個(gè)可實(shí)用的、能夠?qū)用軘?shù)據(jù)執(zhí)行大多數(shù)SQL查詢的數(shù)據(jù)庫系統(tǒng)。CryptDB在應(yīng)用和數(shù)據(jù)庫管理系統(tǒng)之間加入了代理服務(wù)器，通過代理服務(wù)器截取所有的SQL查詢語句，將其轉(zhuǎn)換后再進(jìn)行密文數(shù)據(jù)查詢。優(yōu)點(diǎn)：可應(yīng)用于現(xiàn)有的DBMS服務(wù)器而無需進(jìn)行內(nèi)部更改，并且支持大多數(shù)現(xiàn)有的標(biāo)準(zhǔn)SQL數(shù)據(jù)庫管理系統(tǒng)。缺點(diǎn)：CryptDB假定所有的查詢都經(jīng)過代理，因此無法應(yīng)用于現(xiàn)有的云DaaS模型。在云計(jì)算環(huán)境下，所有用戶只要連接上因特網(wǎng)即可隨時(shí)隨地獲取、修改以及存儲(chǔ)云中的數(shù)據(jù)。4.2 TrustedDBTrustedDB Sumeet Bajaj and Radu Sion. TrustedDB: a trusted hardware based database with privacy and data confidentiality. In SIGMOD Conference, pages 205216, 2011.綜合了安全服務(wù)器和靜止數(shù)據(jù)加密兩種方式，提出了一種新的架構(gòu)：由IBM SCP和商用服務(wù)器構(gòu)成。它在SCP中運(yùn)行輕量級(jí)的SQLite數(shù)據(jù)器，在商用服務(wù)器中運(yùn)行功能更加完善的MySQL數(shù)據(jù)庫。TrustedDB不實(shí)用于在SCP中運(yùn)行工業(yè)級(jí)的數(shù)據(jù)庫。查詢處理過程被分配到兩個(gè)數(shù)據(jù)庫中：通過SCP中的SQLite執(zhí)行加密數(shù)據(jù)的處理，在商用服務(wù)器中的MySQL數(shù)據(jù)庫中執(zhí)行明文數(shù)據(jù)處理。TrustedDB充分利用了目前可用的構(gòu)建模塊（安全硬件設(shè)備、商用硬件設(shè)備、SQLite、MySQL）參考文獻(xiàn)：(1) Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Henri Gilbert, editor, EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 2443. Springer, 2010.全同態(tài)加密。不實(shí)用。（Rosario Gennaro, Craig Gentry, and Bryan Parno.Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Tal Rabin, editor, CRYPTO, vol