密文數據庫檢索技術綜述.docx

精品文檔密文數據庫檢索技術綜述摘要關鍵詞1 引言2 相關技術3 研究分類3.1 數值型數據2002年，Hakan等人首次提出了在數據庫即服務（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.模型下，針對加密數據執(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.。其核心思想是：提出了一種過濾技術（桶劃分技術）縮小解密范圍，從而快速查詢加密數據。并基于桶劃分技術提出了一種對關系數據庫進行加密和存儲的模型，在此模型上存儲數據時，除了對關系表中的記錄采用常規(guī)加密外，還給每個屬性值增加一個桶號，桶號表示明文數據值位于某段區(qū)間內。在該模型中，數據擁有者（即用戶）對數據庫進行加密后將數據庫密文保存在服務提供商處，只有數據擁有者能夠解密。用戶提交查詢指令后，服務器端無需對密文解密即可進行粗粒度的查詢，得到包含查詢結果的一個候選結果集合，然后將該候選結果集合返回給用戶，用戶解密該候選結果集合并對明文進行計算即可得到最終的查詢結果。該方法返回一個比正確結果集合更大一些的集合，其中可能包含一些并不匹配查詢條件的密文元組，因此需要再對這個結果集合進行解密和過濾處理，才能得到最終的查詢結果。此外，該方法僅通過值域分區(qū)的方式建立數據庫值索引，容易造成數據庫信息泄漏。數據庫通常采用哈希技術分區(qū)的方式，這種方式的分區(qū)數量越多，檢索性能越好，但同時會造成更多的數據冗余。當每個分區(qū)中的數據記錄較多時，檢索效率會受到較大影響。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.。與桶劃分方法不同，該方法將數據進行元組級的加密，因此能夠進行元組級的檢索。該方法不按數值的順序分類，增加了安全性。其缺點是不能實現范圍搜索。Damiani又使用B-tree編碼方式，這種方法可以實現范圍檢索，但是每次進行檢索時需要檢索的次數等于B-tree的高度。2004年，Hakan等人深入研究了采用桶劃分技術以實現對加密數據執(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等人研究了依據數據分布實現最優(yōu)化桶劃分以減小通信代價 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等人提出了一種改進的數據庫分區(qū)策略，利用數據庫分區(qū)的最優(yōu)算法,在數據庫檢索過程中最小化傳輸和解密的工作量,進一步提高了數據庫密文檢索效率。同時提出一種可控擴散算法,根據數據所有者的需要自適應地調整數據安全等級,采取犧牲一定密文檢索性能的方式,定制更為靈活的數據庫密文安全策略。2010年，Chase等人提出了結構加密算法來解決加密大矩陣和圖的查詢問題 M. Chase and S. Kamara, “Structured Encryption and Controlled Disclosure,” Advances in Cryptology-ASIACRYPT 2010, 2010, pp. 57794.。這種算法是基于SSE的。其不足之處為：只能進行簡單的查詢例如數值訪問和“鄰居查詢”。2011年，Cao首次提出并解決了在云中查詢加密圖結構數據的隱私保護查詢(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.。并建立了嚴格的安全需求來實現云數據利用系統(tǒng)。并使用了“過濾-驗證”的原則。重新建立了基于特征的索引來提供加密數據圖的特征相關信息。選擇了高效的內積作為修剪工具來過濾數據。為了保證圖查詢不造成隱私泄漏，提出了內積計算技術，并將其改進后能夠在未知背景維系模型下保證安全。3.2 單關鍵詞檢索3.2.1 單關鍵詞密文排序查詢加利福利亞大學的Song等人采取了序列加密(stream cipher)方法對文本數據進行加密處理，這樣無需解密就可以直接對加密文本搜索關鍵詞 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)點是：使用者和數據庫需要很少的通信，只需要一輪交互。(對稱密鑰)但是其方法有一些問題：第一，它與當前已有的一些文件加密方案不兼容；第二，它在針對加密數據的統(tǒng)計分析攻擊下并不安全，盡管提出了一些有啟發(fā)性的補救方法，但是其安全性證據在理論上是不夠健壯的；第三，不能進行連接詞檢索，且很難擴展。2003年，Goh等人 Goh E J. Secure IndexesJ. IACR Cryptology ePrint Archive, 2003, 2003: 216.基于布隆過濾器對Song的效率進行改進，每個文件都有對應的一些獨立的哈希函數和Bloom Filter 數據結構。在文件加密之前，需要對文件中的關鍵字使用私鑰加密，再使用哈希函數映射到filter之上并記錄，最后，將映射后的filter和文件的密文上傳到服務器中。當用戶需要進行密文搜索時，需要將關鍵字的密文發(fā)送給云端服務器，再由云端服務器使用每個文件的哈希函數進行關鍵字到filter的映射。如果映射到的位置之前都有記錄的痕跡，則說明這個關鍵字有很大的概率是在該文件中。最后，云端服務器將得到的匹配文件發(fā)給用戶。結果：能夠利用哈希函數計算快速的特點,快速地查找關鍵字所在的密文文件。不足：它也繼承了Bloom Filter存在錯誤率的特點，有可能導致一些文件本來并不包含關鍵字,最后卻能夠通過哈希函數的檢測,而被云端作為結果返回給用戶，給用戶帶來一些額外的帶寬開銷和計算開銷。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.(簡稱:PEKS方案),為此業(yè)界把2004年定義為可搜索公鑰加密的元年。在論文中他們提出了一種基于雙線性對函數的單關鍵可搜索公鑰加密方案,該方案指出,第三方服務器根據單關鍵字的密文信息在整個服務器數據庫中檢索相關的文章,保證對檢索的信息一無所知。這項新技術的提出開啟了可搜索公鑰加密技術的新時代。優(yōu)點：支持數據接收者對多個發(fā)送者所加密的密文中進行搜索的應用場景，而且由于隨機數的作用，系統(tǒng)的加密效果為非確定性加密，導致了服務器端無法通過密文是否相同來判斷索引表(或搜索憑證)中是否具有相同的關鍵字。缺點：計算開銷因為雙線性對的引進而加大，特別是對操作(pairing operation)的計算開銷較大，使得該方法在海量數據處理場景中的應用性受到一定的限制；另外，PEKS的安全性是在隨機語言機模型(random oracle model)下成立，并不適合現實應用。2005年，Abdalla等人提出一種使用臨時性關鍵字可檢索的公鑰加密方案(簡稱: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.。在該方案的驗證階段,用戶一旦需要驗證就要進行必須的、相關的解密操作,這樣無形中就增大了服務器的開銷。2005年，J.Baek等人提出了一種不需要使用安全信道來傳輸數據的基于關鍵字的公鑰加密可搜索方案(簡稱: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.,這種方案保證信息在客戶端和服務器端的傳送過程中,不會受到攻擊或發(fā)生泄漏等問題,保證了搜索信息、加密數據的安全性。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.提出一種基于對偶編碼的特征值提取方法,將字符型明文數據拆分為多個字符對偶,根據這些字符對偶提取字符型數據的特征值,存儲到一個新的字段中,在數據庫密文檢索時,根據這個輔助字段將不符合關鍵詞字符特征的數據庫記錄過濾掉,再對剩余的數據庫記錄做解密處理,得到明文的解密結果,最后在解密結果中進行明文檢索,獲得最終檢索結果。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的基礎上給出更嚴格的安全性定義和更高效的對稱密鑰可檢索加密方法構造，利用加密Hash表存儲關鍵詞和密文文件標識的映射關系實現密文數據查詢。2007年，Zhu等人提出一種基于字符特征矩陣的數據庫加密策略 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.。這種加密策略也將數據庫的密文檢索分為過濾和解密兩個階段,字符特征矩陣記錄了每個字符型數據中包含的字符,同時也記錄了每個字符與哪些字符相鄰,這種加密策略可以檢索任意長度的字符關鍵詞,解決了基于對偶編碼的數據庫加密策略不能檢索單個字符的問題,第一階段的過濾效率較高,但字符特征矩陣中存儲了大量特征數據,產生了較多的數據冗余,因此,在這種數據庫加密策略中采取A.Tan提出的矩陣壓縮方法存儲特征索引,降低了索引存儲的占用空間,在安全性和密文檢索效率間取得了較好的平衡.2007年，Zhang等人基于數值型數據的數據庫分區(qū)方法,提出一種字符型數據密文的分區(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.。這種索引通過將字符信息轉換為數值型來記錄字符間的關系特征,利用索引過濾掉部分不符合檢索條件的數據庫記錄,再對剩余一記錄解密,進行二次檢索后返回檢索結果。2008年，Zhang等人提出了一種數據庫密文索引策略 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.,將字符數據映射為索引值,通過SQL語句翻譯器將SQL檢索語句轉換為對索引的快速匹配,為了保證密文索引的安全性,策略采用了哈希技術和數字擾亂的方法,這樣不同記錄中的相同字符將會對應不同的索引值,索引值不再具有統(tǒng)計特征,從而避免基于頻率統(tǒng)計的數據庫攻擊。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ā)現即使列表元素（倒序包含每個關鍵詞的文檔ID）被加密，仍然可以根據發(fā)布列表的詞頻分布來重新確認關鍵詞。所以他們改變了相關性分數，使每個關鍵詞的詞頻相等。在此基礎上，提出了在加密數據中進行安全的排序搜索的方法。這個方案在統(tǒng)計意義上滿足安全定義，被稱之為R-機密性(r-confidentiality)。不足之處為：它需要大量的預處理，而且不能簡單地處理動態(tài)分數，所以安全級別很低。3.2.2 模糊匹配查詢2009年，Liu等人提出一種基于Bloom Filter的數據庫索引方法 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能夠支持數據庫模糊檢索，根據數據庫索引的匹配可將部分不符合檢索條件的數據庫記錄排除。2010年，Li等人針對關鍵詞精確匹配的不足，提出云計算環(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.。它使用編輯距離來量化字符串的相似度，并為每個字符串附加一個基于通配符的模糊字符串組，用多個精確匹配來實現模糊檢索。其不足為：該方法需要語義庫的支持，且僅僅針對“all-or-nothing”的查詢方式，并返回給用戶完全無區(qū)分性的查詢結果。對于Li等人提出的基于編輯距離d的加密字符串模糊檢索方案,他們解決的是d1的情況，當d1時，Wang等人提出了方案 Wang C, Ren K, Lou W, et al. Toward publicly auditable secure cloud data storage servicesJ. Network, IEEE, 2010, 24(4): 19-24.來擴展它。當d很大時，他們所用的通用抑制技術就節(jié)省了很多空間。他們使用單詞查找樹（一種數據結構）來保存序列跟編碼，把檢索的復雜度從O(N)降到了O(1)。這兩者的缺點都是返回給用戶的查詢結果不可區(qū)分，并且因為都使用了SSE框架，因此均沒有實現查詢的不可連接性。（王偉，單關鍵詞or多關鍵詞）3.2.3 分級檢索（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.考慮關鍵詞詞頻信息,提出基于對稱密鑰保序加密技術 OPSE Boldyreva A, Chenette N, Lee Y, et al. Order-preserving symmetric encryptionM/Advances in Cryptology-EUROCRYPT 2009. Springer Berlin Heidelberg, 2009: 224-241.的單關鍵詞分級密文排序查詢方法（RSSE），采取了OPSE方案來提高實際性能，采用此方案后，明文的數值順序在加密后將被維持原狀。具體來說，在查詢過程中，每個文檔的相關性順序（用OPSE加密過的相關性分數）將被告知服務器。通過這個方式，相關性分數的排序將會像在明文中一樣高效。然而，因為原始的OPSE算法是確定性的加密方案，這仍然會泄漏很多信息。如果服務器上的數據集中包含很多此類背景信息，例如每個明文關鍵詞的相關性分數的分布，那么就能反向推導出關鍵詞。為了打破這種確定性，作者提出了一對多保序映射(OPM),它把相同的相關性分數映射到不同的加密數值上。因此，相同的明文不再是確定的加密成確定的密文。他們更進一步對不同的列表使用了不同的密鑰來加密相關性分數，這使得OPM更加可靠。RSSE方案正是通過使用OPSE和OPM來實現數據和索引的隱私保護。該方法的不足之處為：該方法對相似度計算并未全面考慮，因為需要掃描所有文檔而不易進行索引更新，且僅支持關鍵詞的排序查詢。2012年，Wang等人為解決以往密文檢索中布爾檢索（Boolean search）的局限性，提出了一種分級檢索（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.。該方法按照檢索結果的相關性，設置一種分類標準，例如對相關性進行評分，建立安全的可檢索的索引，形成一對多的保序映射。與不分類的返回結果相比，能夠提高系統(tǒng)的穩(wěn)定性。3.3 多關鍵詞檢索3.3.1 多關鍵詞密文排序查詢2005年，D.J.Park等人提出多關鍵字可搜索公鑰加密方案(簡稱: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.,這個可搜索加密方案是對現有可搜索加密技術的一種改進,符合現實可搜索加密的場景,不過后來被被人證明這種多關鍵字可搜索加密方案不能抵抗關鍵字猜想攻擊。2012年，程芳權等提出了云環(huán)境下在大規(guī)模加密云數據上進行高效且具有隱私保護能力的個性化密文排序查詢方法 程芳權, 彭智勇, 宋偉, 等. 云環(huán)境下一種隱私保護的高效密文排序查詢方法J. 計算機學報, 2012, 35(11): 2215-2227.。其貢獻為：a) 提出了針對云環(huán)境下多數據擁有者數據外包及選擇性數據查詢授權特征的多屬性多關鍵詞密文排序查詢,并定義其系統(tǒng)模型和攻擊模型.基于無證書認證思想設計不依賴于可信第三方和安全傳輸信道的可認證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.(支持關鍵詞檢索的公鑰加密),并構建支持系統(tǒng)模型的RQED框架以增強查詢隱私保護。b) 基于RQED框架,設計支持多屬性數據隱私保護詞權重、查詢詞權重及用被授權可訪問數據范圍等更客觀、合理的密文查詢排序函數。c) 考慮到單數據不確定性、數據和授權更新不確定性以及大規(guī)模密文數據查詢，提出基于層次動態(tài)布隆過濾器的RQED索引機制，來提高密文查詢執(zhí)行與密文索引的時空效率。結果：RQED 機制中動態(tài)布隆過濾器索引大大降低了索引空間開銷.對于索引私鑰, RQED機制中用戶只需存儲一對公私鑰,現有方法則需存儲密鑰矩陣且隨著關鍵詞詞典規(guī)模增大而帶來巨大空間開銷,并且當涉及多數據擁有者選擇性 查詢授權時,客戶端更是無法承受?？偨Y所有實驗結果可以看出，RQED機制較之現有多關鍵詞密文排序查詢方法有明顯的時空效率優(yōu)勢.2012年，丁茂震針對現有部分關鍵字公鑰可搜索加密方案效率不高、安全性較低、必須使用安全信道傳輸數據等缺陷，提出了一種新的、高效的多關鍵字可搜索公鑰加密方案(NSCF-PECK) 丁茂震. 云環(huán)境中密文搜索技術的研究D. 北京郵電大學, 2013.。這種方案基于雙線性對構造,并采用公共信道來傳輸密文。在整個算法的設計上,僅僅使用了兩次雙線性對運算,極大的減小了可搜索公鑰加密技術的計算開支。同時在客戶端和云服務器之間釆用公共信道來傳送加密的數據,減少了建設安全信道的費用。在上述NSCF-PECK可搜索公鑰加密方案的基礎上,本文提出了一種云端密文搜索系統(tǒng)的應用方案。該應用方案利用MapReduce并行計算模型技術設計該應用方案的并行搜索引擎,把一些開源技術和分布式計算思想應用到該應用方案之中,充分利用云計算技術優(yōu)勢提高對海量密文的搜索效率。該系統(tǒng)采用分層化和模塊化的設計思路保證了方案的可維護性、可擴展性和應用的靈活性。為了進一步滿足用戶個性化查詢需求，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.，并基于安全KNN查詢技術 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.中索引向量與查詢向量間“內積相似度”來實現排序查詢并進行隱私保護增強。其不足為：該方法并未考慮數據中索引關鍵詞權重及查詢關鍵詞權重等因素，從而不能返回滿足用戶查詢請求的準確排序結果；并且該方法需要構建系統(tǒng)枚舉索引關鍵詞詞典并在用戶端存儲，這無疑不符合實際應用且造成較大客戶端負擔。例如，當詞典規(guī)模為N時，其用戶需要安全傳輸和存儲的密鑰矩陣空間開銷為O(N2)則隨著N增大將帶給客戶端難以承受的負擔。3.3.2 語義關鍵詞檢索在實際的應用場景中，用戶的輸入不一定是預定義的關鍵字，而是關鍵字的同義詞，這些同義詞無法通過精確或者模糊查找的方法搜索。2013年，Fu等人首次提出了一種有效的語義查詢的解決方案 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.。通過建立一個高效靈活的可搜索加密機制，它允許基于多關鍵字分級的搜索和語義搜索。使用VSM(Vector Space Model)建立索引文件。為了提高查詢的效率，使用了樹狀索引結構，即平衡二叉樹。通過構造搜索樹和文件索引樹，能夠找到相關文件。該加密模型能夠滿足兩方面的安全需求：已知密文和已知后臺。分級(rank): In information retrieval, a ranking function is usually used to evaluate relevant scores of matching files to a request.對于搜索文件進行評級，搜索最接近用戶輸入的文件。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.提出了一種能夠實現可靠語義查詢的方法。根據可能出現的詞語，建立一個語義庫，記錄詞語之間的相近關系。同時利用兩種云結構，一種是私有云，另一種是公有云。查詢的過程分為兩個階段。第一階段，我們將搜索關鍵詞進行擴展（在私有云上）；第二階段，我們按照擴展后的關鍵詞搜索（在公有云上）。最終，匹配的文件會按序回傳。2014年，Fu等人提出了在加密云數據中進行語意關鍵詞檢索的方法 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.。其過程為：數據擁有者向云服務商上傳經過控制算法（基于前綴樹）生成的“關鍵詞限制集”索引文件和加密后的文件，授權用戶發(fā)起查詢指令后，云服務商利用索引文件在密文數據中進行指定的查詢操作，并將查詢到的有關加密文件返回給查詢者。其能達到的效果為：能給返回包含跟查詢詞語語意相近的詞匯的文檔。采用了控制算法消除了在索引機構和在查詢中列舉所有相近關鍵詞的需求，并且減少了索引的維度。平衡單詞查找樹也通過建立索引提高了搜索效率。3.3.3 多關鍵詞連接查詢2004年，Golle等人提出了在加密數據中進行關鍵詞連接查詢的協議 Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted dataC/Applied Cryptography and Network Security. Springer Berlin Heidelberg, 2004: 31-45.，使用了“指數模塊（modular exponentiation）”（因此比song等人需要更多的計算開銷）和隨機化搜索功能來確保搜索到的文件中包含的連接關鍵詞。作者提出了兩個方案，第一種方案的通信開銷和文件的數量有關，但是這些開銷可以在查詢發(fā)生之前的離線階段產生。這種方案的安全性能是基于決策性迪菲-赫爾曼(DDH)假設的。第二種方案的通信開銷取決于關鍵詞段的數量，它的安全性是基于新的硬件假設的。2007年，Hwang和Lee等人在隨機語言機模型中基于決策線性迪菲-赫爾曼(DDLH)假設提出了更簡單高效的公鑰加密方案，實現了連接詞查詢 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)將所有接受者的公鑰對關鍵字集合進行加密,通過支持連接關鍵字的公鑰加密方法,實現了支持每個接受者只需要使用自己的私鑰就能對連接關鍵字進行搜索,實現了在“單個發(fā)送者-多個接受者”場景下支持密文搜索的效果。他們的方案在服務器和用戶之間有高效的通信和存儲開銷，并且有合理的計算開銷。4 密文數據庫系統(tǒng)一般情況下構建安全數據庫系統(tǒng)的三種方式：(1) 靜止數據加密（Encryption at Rest）：數據加密存儲在商用存儲系統(tǒng)（如硬盤）中，查詢時將密文數據發(fā)送給可信域，在可信域中解密、處理或者緩存。這是主流數據庫產品如Oracle和MS SQL Server的使用原則，加密特定的數據（數據表或者分區(qū)），認為硬盤不可靠，而系統(tǒng)其他組件可靠（如CPU、內存等）?；谕皠澐值腟QL查詢（2002 SIGMOD）也屬于這一類。盡管這種方式可以保證服務器端數據的私密性，但將密文數據（如完整的數據表）發(fā)送給客戶終端會帶來過高的通信代價。(2) 安全服務器：通過在服務器端增加特殊的高安全性處理節(jié)點，解決(1)中的不足。如AWS GovCloud（Amazon Web Services）由商用服務器構成，通過運行特殊的受審查的軟件棧、限制性的安全策略和主機隔離（網路連接及物理位置）增強了安全性。缺點：物理和邏輯上的隔離限制了應用的類型和客戶端的類型；使云碎片化；最終導致構建和維護云設施成本增加、使云計算的一些特性如無縫故障切換、動態(tài)可擴展性等復雜化。其他的安全服務器解決方案采用了IBM secure coprocessors(SCPs)或者Hardware Security Modules(HSMs)等設備，這些設備是和服務器獨立的，可作為擴展卡方便地部署到商用服務器內部，形成一個可信計算區(qū)域。缺點是安全協處理器內存及處理能力有限，不實用于運行工業(yè)強度的數據庫系統(tǒng)。(3) 全同態(tài)加密：直接對密文進行計算而無需解密，可用于傳統(tǒng)不可信服務器，密文結果由服務器發(fā)送給可信客戶端。但是，目前最先進的全同態(tài)加密方法成本過高因此不實用。目前有一些部分同態(tài)加密方法（限制運算操作，如加法同態(tài)或者乘法同態(tài)；限制特定運算的次數，如最多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.是第一個可實用的、能夠對加密數據執(zhí)行大多數SQL查詢的數據庫系統(tǒng)。CryptDB在應用和數據庫管理系統(tǒng)之間加入了代理服務器，通過代理服務器截取所有的SQL查詢語句，將其轉換后再進行密文數據查詢。優(yōu)點：可應用于現有的DBMS服務器而無需進行內部更改，并且支持大多數現有的標準SQL數據庫管理系統(tǒng)。缺點：CryptDB假定所有的查詢都經過代理，因此無法應用于現有的云DaaS模型。在云計算環(huán)境下，所有用戶只要連接上因特網即可隨時隨地獲取、修改以及存儲云中的數據。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.綜合了安全服務器和靜止數據加密兩種方式，提出了一種新的架構：由IBM SCP和商用服務器構成。它在SCP中運行輕量級的SQLite數據器，在商用服務器中運行功能更加完善的MySQL數據庫。TrustedDB不實用于在SCP中運行工業(yè)級的數據庫。查詢處理過程被分配到兩個數據庫中：通過SCP中的SQLite執(zhí)行加密數據的處理，在商用服務器中的MySQL數據庫中執(zhí)行明文數據處理。TrustedDB充分利用了目前可用的構建模塊（安全硬件設備、商用硬件設備、SQLite、MySQL）參考文獻：(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)加密。不實用。（Rosario Gennaro, Craig Gentry, and Bryan Parno.Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Tal Rabin, editor, CRYPTO, vol