摘要 云計(jì)算自身的數(shù)據(jù)安全問題阻礙其推廣應(yīng)用。通過對(duì)數(shù)據(jù)進(jìn)行加密可以保護(hù)企業(yè)及個(gè)人用戶的數(shù)據(jù)隱私。對(duì)加密數(shù)據(jù)有效檢索難以通過傳統(tǒng)信息檢索方式實(shí)現(xiàn)。文章在分析云存儲(chǔ)應(yīng)用中的存儲(chǔ)安全技術(shù)基礎(chǔ)上，針對(duì)加密存儲(chǔ)的需求，基于常見的加密檢索方法和相關(guān)技術(shù)，結(jié)合自己的研究成果，提出了一種基于全同態(tài)加密的檢索方法，該方法能在一種程度上提高檢索效率。

[關(guān)鍵詞]云存儲(chǔ);向量空間模型;相關(guān)排序

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

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

云計(jì)算主要目標(biāo)是提供高效的計(jì)算服務(wù)。云計(jì)算基礎(chǔ)設(shè)施之一是提供可靠、安全的數(shù)據(jù)存儲(chǔ)中心。因此，存儲(chǔ)安全是云計(jì)算領(lǐng)域的安全話題之一。為解決數(shù)據(jù)隱私的保護(hù)問題，常見的方法是由用戶對(duì)數(shù)據(jù)進(jìn)行加密，把加密后的密文信息存儲(chǔ)在服務(wù)端。當(dāng)存儲(chǔ)在云端的加密數(shù)據(jù)形成規(guī)模之后，對(duì)加密數(shù)據(jù)的檢索成為一種迫切需要解決的問題。

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

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

1 云存儲(chǔ)應(yīng)用中的加密存儲(chǔ)技術(shù)

大規(guī)模高性能存儲(chǔ)系統(tǒng)安全需求，特別是云存儲(chǔ)應(yīng)用中，可擴(kuò)展和高性能的存儲(chǔ)安全技術(shù)，是推動(dòng)網(wǎng)絡(luò)環(huán)境下的存儲(chǔ)應(yīng)用(如云存儲(chǔ)應(yīng)用)最根本的保證，已經(jīng)成為當(dāng)前網(wǎng)絡(luò)存儲(chǔ)領(lǐng)域的研究熱點(diǎn)。云存儲(chǔ)應(yīng)用中的存儲(chǔ)安全包括認(rèn)證服務(wù)、數(shù)據(jù)加密存儲(chǔ)、安全管理、安全日志和審計(jì)。

訪問控制服務(wù)實(shí)現(xiàn)用戶身份認(rèn)證、授權(quán)，防止非法訪問和越權(quán)訪問。主要功能包括:用戶只能對(duì)經(jīng)管理員或文件所有者授權(quán)的許可文件進(jìn)行被許可的操作;管理員只能進(jìn)行必要的管理操作，如用戶管理、數(shù)據(jù)備份、熱點(diǎn)對(duì)象遷移，而不能訪問用戶加密了的私有數(shù)據(jù)。

加密存儲(chǔ)是對(duì)指定的目錄和文件進(jìn)行加密后保存，實(shí)現(xiàn)敏感數(shù)據(jù)存儲(chǔ)和傳送過程中的機(jī)密性保護(hù)。

安全管理主要功能是用戶信息和權(quán)限的維護(hù)，如用戶帳戶注冊(cè)和注銷等，授權(quán)用戶、緊急情況下對(duì)用戶權(quán)限回收等。

安全日志和審計(jì)是記錄用戶和系統(tǒng)與安全相關(guān)的主要活動(dòng)事件，為系統(tǒng)管理員監(jiān)控系統(tǒng)和活動(dòng)用戶提供必要的審計(jì)信息。

對(duì)用戶來說，在上述4類存儲(chǔ)安全服務(wù)中，存儲(chǔ)加密服務(wù)尤為重要。加密存儲(chǔ)是保證用戶私有數(shù)據(jù)在共享存儲(chǔ)平臺(tái)的機(jī)密性核心技術(shù)。

隨著存儲(chǔ)系統(tǒng)和存儲(chǔ)設(shè)備越來越網(wǎng)絡(luò)化，存儲(chǔ)系統(tǒng)在保證敏感數(shù)據(jù)機(jī)密性的同時(shí)，必須提供相應(yīng)的加密數(shù)據(jù)共享技術(shù)。保護(hù)用戶隱私性要求存儲(chǔ)安全建立在對(duì)存儲(chǔ)系統(tǒng)的信任基礎(chǔ)之上。必須研究適用于網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)的加密存儲(chǔ)技術(shù)，提供端到端加密存儲(chǔ)技術(shù)及密鑰長期存儲(chǔ)和共享機(jī)制，以確保用戶數(shù)據(jù)的機(jī)密性和隱私性，提高密鑰存儲(chǔ)的安全性、分發(fā)的高效性及加密策略的靈活性。在海量的加密信息存儲(chǔ)中，加密檢索是實(shí)現(xiàn)信息共享的主要手段，是加密存儲(chǔ)中必須解決的問題之一。

2 加密信息檢索技術(shù)

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

2.1 線性搜索算法

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

線性搜索方法是一種一次一密的加密信息檢索算法，因此有極強(qiáng)的抵抗統(tǒng)計(jì)分析的能力。但其有一個(gè)致命的缺點(diǎn)，即逐次匹配密文信息，這使得這種檢索方法在大數(shù)據(jù)集的情況下難以應(yīng)用。

2.2 基于關(guān)鍵詞的公鑰搜索

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

算法的過程如下，首先生成公鑰、私鑰，然后對(duì)待存儲(chǔ)的明文關(guān)鍵詞用公鑰進(jìn)行加密，生成可搜索的密文信息。

2.3 安全索引

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

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

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

2.4 引入相關(guān)排序的加密搜索算法

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

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

3 一種基于全同態(tài)加密的檢索方法

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

全同態(tài)加密檢索及排序過程如圖1所示。提交檢索之前，同樣先對(duì)檢索語句進(jìn)行分詞、詞干化，得到關(guān)鍵詞明文序列并對(duì)明文進(jìn)行加密。云端服務(wù)器對(duì)提交密文序列進(jìn)行檢索時(shí)，提交加密后的檢索詞。

文檔由每個(gè)關(guān)鍵詞的權(quán)重向量表示，權(quán)重是詞頻與倒排文檔頻率對(duì)數(shù)的乘積的歸一化。對(duì)用全同態(tài)加密后的詞頻、倒排文檔頻率進(jìn)行操作可以得到權(quán)重。文檔向量由公式(1)計(jì)算得到。

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

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

4 結(jié)束語

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

5 參考文獻(xiàn)

[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

黃永峰，華中科技大學(xué)博士畢業(yè)，清華大學(xué)電子工程系博士后;清華大學(xué)NGN實(shí)驗(yàn)室副教授;研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)及其信息處理。

張久嶺，清華大學(xué)NGN實(shí)驗(yàn)室在讀博士，研究領(lǐng)域?yàn)榧用苄畔z索。

李星，美國DREXEL大學(xué)電機(jī)與計(jì)算機(jī)工程系博士畢業(yè);清華大學(xué)電子工程系教授、博士生導(dǎo)師，清華大學(xué)信息網(wǎng)絡(luò)工程研究中心副主任，電子工程系網(wǎng)絡(luò)與人機(jī)語音通信研究所所長，中國教育和科研計(jì)算機(jī)網(wǎng)(CERNET)國家網(wǎng)絡(luò)中心副主任，CERNET專家委員會(huì)成員;承擔(dān)的中國教育和科研計(jì)算機(jī)網(wǎng)示范工程項(xiàng)目獲國家教委科技進(jìn)步一等獎(jiǎng)，國家科技進(jìn)步二等獎(jiǎng)。