云存儲應用中的加密存儲及其檢索技術

摘要 云計算自身的數據安全問題阻礙其推廣應用。通過對數據進行加密可以保護企業及個人用戶的數據隱私。對加密數據有效檢索難以通過傳統信息檢索方式實現。文章在分析云存儲應用中的存儲安全技術基礎上，針對加密存儲的需求，基于常見的加密檢索方法和相關技術，結合自己的研究成果，提出了一種基于全同態加密的檢索方法，該方法能在一種程度上提高檢索效率。

[關鍵詞]云存儲;向量空間模型;相關排序

Abstract: The problem of data security impedes the spread and application of cloud computing. While corporate and personal data can be protected through data encryption， effective retrieval of encrypted data is difficult to achieve by traditional means. This paper analyzes storage security technology in cloud storage and also the demands of encrypted storage (using common methods of encryption and related technologies). In light of research results， this paper proposes a retrieval method based on fully homomorphic encryption—which can markedly improve efficiency.

Key words: cloud storage; vector space model; relevance ranking

云計算是一種通過網絡以按需、易擴展的方式獲取所需服務的在線網絡服務交付和使用模式，它是分布式計算的一種形式。是網絡上的服務以及提供這種服務的數據中心的軟硬件集合[1]。云計算是并行計算、分布式計算和網格計算的演進。云計算的實現形式包括軟件即服務、效用計算、平臺即服務、基礎設施即服務。目前云計算已經有部分應用，如Google公司的GoogleDocs[2]，另外微軟、Amazon[3-4]也有類似的云計算服務設施。

云計算主要目標是提供高效的計算服務。云計算基礎設施之一是提供可靠、安全的數據存儲中心。因此，存儲安全是云計算領域的安全話題之一。為解決數據隱私的保護問題，常見的方法是由用戶對數據進行加密，把加密后的密文信息存儲在服務端。當存儲在云端的加密數據形成規模之后，對加密數據的檢索成為一種迫切需要解決的問題。

在加密信息檢索的相關研究工作中，對加密信息的檢索有單用戶線性搜索、基于關鍵詞的公鑰搜索、安全索引等幾種算法。這幾種算法可以快速地檢索出所需信息，但其代價較高，不適用大規模數據檢索的情況，而且，在云存儲中，檢索時相關的文檔較多，對其進行相關排序是進一步需要解決的問題，以上幾種算法均不能解決問題。

通過保序加密可以利用文檔中的詞頻信息對文檔依相關度進行排序，提高了檢索準確率和返回率。然而在文檔中某些關鍵詞出現的頻率非常高，指代性不強，這一類詞稱為常用詞，常用詞的存在歪曲了文檔和實際查詢相關度。而準確反映文檔、查詢相關度的向量空間模型無法直接應用。全同態加密提供可以對密文進行操作的加密算法。而且通過全同態加密，一方面可以保證密文信息不被統計分析，另一方面可以對加密信息進行加法和乘法運算，同時保持其對應明文的順序。

1 云存儲應用中的加密存儲技術

大規模高性能存儲系統安全需求，特別是云存儲應用中，可擴展和高性能的存儲安全技術，是推動網絡環境下的存儲應用(如云存儲應用)最根本的保證，已經成為當前網絡存儲領域的研究熱點。云存儲應用中的存儲安全包括認證服務、數據加密存儲、安全管理、安全日志和審計。

訪問控制服務實現用戶身份認證、授權，防止非法訪問和越權訪問。主要功能包括:用戶只能對經管理員或文件所有者授權的許可文件進行被許可的操作;管理員只能進行必要的管理操作，如用戶管理、數據備份、熱點對象遷移，而不能訪問用戶加密了的私有數據。

加密存儲是對指定的目錄和文件進行加密后保存，實現敏感數據存儲和傳送過程中的機密性保護。

安全管理主要功能是用戶信息和權限的維護，如用戶帳戶注冊和注銷等，授權用戶、緊急情況下對用戶權限回收等。

安全日志和審計是記錄用戶和系統與安全相關的主要活動事件，為系統管理員監控系統和活動用戶提供必要的審計信息。

對用戶來說，在上述4類存儲安全服務中，存儲加密服務尤為重要。加密存儲是保證用戶私有數據在共享存儲平臺的機密性核心技術。

隨著存儲系統和存儲設備越來越網絡化，存儲系統在保證敏感數據機密性的同時，必須提供相應的加密數據共享技術。保護用戶隱私性要求存儲安全建立在對存儲系統的信任基礎之上。必須研究適用于網絡存儲系統的加密存儲技術，提供端到端加密存儲技術及密鑰長期存儲和共享機制，以確保用戶數據的機密性和隱私性，提高密鑰存儲的安全性、分發的高效性及加密策略的靈活性。在海量的加密信息存儲中，加密檢索是實現信息共享的主要手段，是加密存儲中必須解決的問題之一。

2 加密信息檢索技術

對加密信息檢索的研究始于2000年，Song等人提出加密數據搜索的實用算法[5]，Boneh等人提出基于關鍵詞的公鑰加密算法[6]，Park等人提出安全索引搜索算法[7]。

2.1 線性搜索算法

在線性搜索算法中，首先用對稱加密算法對明文信息加密。對于每個關鍵詞對應的密文信息，生成一串長度小于密文信息長度的偽隨機序列，并生成一由偽隨機序列及密文信息確定的校驗序列。偽隨機序列的長度與檢驗序列長度之和等于密文信息的長度。偽隨機序列及檢驗序列對密文信息再次加密。在搜索過程中，用戶提交明文信息對應的密文信息序列。在服務器端，密文信息序列被線性地同每一段序列模2加。如果得到的結果滿足校驗關系，那么說明密文信息序列出現，否則，說明密文信息不存在。

線性搜索方法是一種一次一密的加密信息檢索算法，因此有極強的抵抗統計分析的能力。但其有一個致命的缺點，即逐次匹配密文信息，這使得這種檢索方法在大數據集的情況下難以應用。

2.2 基于關鍵詞的公鑰搜索

基于關鍵詞的公鑰加密搜索算法由Boneh等人提出，其目的是可以在用戶端存儲、計算資源不足的情況下，通過訪問遠端數據庫獲取數據信息。存儲、計算資源分布具有不對稱性，即用戶的計算存儲能力不能實時滿足其需求。另一方面用戶在移動情況下存儲、索引數據的需求也有增加，比如Email服務等。在這種特定情況下，需要保護用戶的數據隱私。加密數據有多個不同來源，針對這一問題的解決方法是加密算法使用公鑰加密。

算法的過程如下，首先生成公鑰、私鑰，然后對待存儲的明文關鍵詞用公鑰進行加密，生成可搜索的密文信息。

2.3 安全索引

安全索引由Park等人提出，解決了簡單索引方式易受統計攻擊的問題。其機制是每次加密所用的密鑰是事先生成的一組逆Hash序列，加密后的索引被放入布隆過濾器中。當檢索的時候，首先用逆Hash序列密鑰生成多個陷門，然后進行布隆檢測。對返回的密文文檔解密即可得到所需檢索的文檔。

針對有新用戶加入、舊用戶退出的多用戶加密信息檢索，這是一種解決方法。但其存在的缺陷是需要生成大量的密鑰序列，隨著檢索次數的增加，每多進行一次檢索，其計算復雜度均線性增加。這在實際應用中很難被接受。

在以上提到的多種加密信息檢索算法中，所用的檢索模型都是布爾模型，因而無法根據查詢與待檢索文檔的相關度進行排序操作。在實際情況中，尤其是在數據規模較大的云存儲應用中，包含某一查詢關鍵詞的文檔可能有很多個，如何在多個可能相關的文檔中找出最相關的一個或若干個文檔是需要解決的問題。對加密的文檔，是否可以應用成熟的向量空間模型，進而進行相關排序，是一個開放的問題。

2.4 引入相關排序的加密搜索算法

Swaminathan等人提出了保護隱私的排序搜索算法[8]。在這一算法中，每一文檔中關鍵詞的詞頻都被保序加密算法加密。加密文檔被提交查詢給服務器端后，首先計算檢索出含有關鍵詞密文的加密文檔;然后對用保序算法加密的詞頻對應的密文信息進行排序處理;最后把評價值高的加密文檔返回給用戶，由用戶對其進行解密。

這一種方法可以在給定多個可能相關文檔的情況下對加密文檔進行排序，進而把最可能相關的文檔返回給用戶。但這一種算法首先不適用于一個查詢包含多個查詢詞的情況，其次算法只利用了文檔中的詞頻信息，無法利用詞的逆文檔頻率，進而向量空間模型無法直接應用。解決前一種問題的一種方法是用加法同態加密算法[9]對詞頻信息進行加密處理。

3 一種基于全同態加密的檢索方法

在加密信息檢索研究中，結果的排序是衡量檢索算法性能的重要指標之一。當前隨著云計算技術的提倡和應用，加密文檔必將呈爆炸式增加。排序的準確性成為對檢索系統性能的客觀要求，其主要目的是提高檢索系統服務質量和檢索效率。分析現有的加密信息檢索算法發現，在保證查準和查全兩方面性能的同時，對排序問題以及準確性方面考慮不夠。針對該問題，本文提出了一種面向云存儲應用中的全同態加密的檢索方法。全同態加密的檢索方法是采用信息檢索中的向量空間模型，計算檢索出的文檔與待查詢信息之間的相關度，對檢索詞詞頻和倒排文檔頻率進行統計，然后采用全同態方法對文檔進行加密并建立索引方法。檢索后將加密文檔與索引項密文一起上傳到服務器端。

全同態加密檢索及排序過程如圖1所示。提交檢索之前，同樣先對檢索語句進行分詞、詞干化，得到關鍵詞明文序列并對明文進行加密。云端服務器對提交密文序列進行檢索時，提交加密后的檢索詞。

文檔由每個關鍵詞的權重向量表示，權重是詞頻與倒排文檔頻率對數的乘積的歸一化。對用全同態加密后的詞頻、倒排文檔頻率進行操作可以得到權重。文檔向量由公式(1)計算得到。

對于檢索詞采用同樣方法來描述，取兩者的內積即可得到兩者的相關度，然后根據大小進行排序，將有效排序后的文檔返回給用戶。用戶得到加密文檔后，用私鑰對文檔解密得到原始文檔。

通過全同態加密算法加密的明文數據可以在不恢復明文信息的情況被有效檢索出來，即把最相關的文檔返回給用戶。既保護了用戶的數據安全，又提高了檢索的性能。

4 結束語

本文分析了加密檢索技術在云存儲應用中的重要意義，綜合分析了當前加密檢索和相關技術研究現狀和存在問題。在此基礎上，本文提出了全同態加密檢索方法并簡要介紹全同態加密檢索方法的基本原理。已有的實驗數據表明，全同態加密檢索方法與其他加密檢索算法相比，能在一定程度上提高檢索效率。

5 參考文獻

[1] ARMBRUST M， FOX A， GRIFFITH R， et al. Above the Clouds: A Berkeley View of Cloud Computing [R]. Berkeley， CA，USA: University of California， 2009.

[2] Google docs - Online Documents， Spreadsheets， Present [EB/OL]. [2009-07-29]. http://docs.google.com.

[3] Windows Azure Platform [EB/OL]. [2009-07-12]. http://www.microsoft.com/windowsazure/.

[4] Amazon Elastic Compute Cloud [EB/OL]. [2009-06-24]. http://aws.amazon.com/ec2.

[5] SONG D， WAGNER D， PERRIG A. Practical Techniques for Searches on Encrypted Data [C]//Proceedings of the IEEE Symposium on Security and Privacy(SP’00)， May 14-17，2000， Berkeley， CA，USA. Piscataway， NJ， USA: IEEE， 2000:44-55.

[6] BONEH D， CRESCENZO G， OSTROVSKY R， et al. Public Key Encryption With Keyword Search [C]//Advances in Cryptology. Proceedings of the 23rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04)， May 2-6， 2004， Interlaken， Switzerland. LNCS 3027. Berlin， Germany: Springer-Verlag， 2004:506-522.

[7] PARK D， KIM K， LEE P. Public Key Encryption With Conjunctive Field Keyword Search [C]//Proceedings of the 2004 Workshop on Information Security Applications (WISA’04)， Oct 29-31， 2004， Wuhan， China. LNCS 3325. Berlin， Germany: Springer-Verlag， 2004:73-86.

[8] SWAMINATHAN A， MAO Y， SU G M， et al. Confidentiality-Preserving Rank-Ordered Search [C]//Proceedings of the 2007 ACM Workshop on Storage Security and Survivability (StorageSS’07)， Oct 29， 2007， Alexandria， VA， USA. New York， NY， USA:ACM， 2007:7-12.

[9] GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices [C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing(STOC’09)， May 31 - Jun 2， 2009， Bethesda， MD， USA. New York， NY， USA:ACM， 2009: 169-178.

收稿日期:2010-05-13

黃永峰，華中科技大學博士畢業，清華大學電子工程系博士后;清華大學NGN實驗室副教授;研究領域為互聯網及其信息處理。

張久嶺，清華大學NGN實驗室在讀博士，研究領域為加密信息檢索。

李星，美國DREXEL大學電機與計算機工程系博士畢業;清華大學電子工程系教授、博士生導師，清華大學信息網絡工程研究中心副主任，電子工程系網絡與人機語音通信研究所所長，中國教育和科研計算機網(CERNET)國家網絡中心副主任，CERNET專家委員會成員;承擔的中國教育和科研計算機網示范工程項目獲國家教委科技進步一等獎，國家科技進步二等獎。