王凱文，王樹蘭，王海燕，丁 勇，3

(1.深圳技術(shù)大學(xué) 大數(shù)據(jù)與互聯(lián)網(wǎng)學(xué)院，廣東 深圳 518118；2.鵬城實驗室 網(wǎng)絡(luò)空間安全部，廣東 深圳 518000；3.桂林電子科技大學(xué) 計算機與信息安全學(xué)院，廣西 桂林 541010)

隨著計算機領(lǐng)域的飛速發(fā)展，數(shù)據(jù)量日益劇增，人們越來越傾向于使用第三方數(shù)據(jù)庫云服務(wù)來進行存儲。但在云服務(wù)的數(shù)據(jù)存儲過程中，會面臨數(shù)據(jù)丟失、惡意竊取數(shù)據(jù)或者篡改數(shù)據(jù)等安全隱患。因此，確保云服務(wù)中數(shù)據(jù)保密和操作安全是云安全領(lǐng)域中的重大挑戰(zhàn)之一。當前，一種行之有效的方法是在上傳之前對數(shù)據(jù)進行加密，把加密后的密文信息存儲在服務(wù)端。而加密數(shù)據(jù)的檢索成為一個迫切需要解決的問題，申請查詢指定內(nèi)容，會要求先解密后確定文件，導(dǎo)致搜索代價極大。因此，如何既能保護云端數(shù)據(jù)安全又能支持高效數(shù)據(jù)處理能力成為新的難題。

最早的可搜索加密是從單個關(guān)鍵字的搜索起步，文獻[1]在2000年采用偽隨機函數(shù)和流密碼對單關(guān)鍵字進行對稱加密，但是方案遍歷時要檢索全文，安全性低；而文獻[2]在此基礎(chǔ)上提出了安全性索引模型，采用Bloom Filter偽隨機函數(shù)，實現(xiàn)高效搜索；CAO等人提出加密云數(shù)據(jù)上的多關(guān)鍵字排序搜索方案[3]，使用了KNN算法向文檔向量中添加虛擬尺寸和隨機參數(shù)以保護數(shù)據(jù)隱私；MIAO等人通過利用{0，1}編碼來支持可比較的屬性機制，實現(xiàn)保護隱私的方式的關(guān)鍵字搜索方案[4]。但上述方案都只局限于針對文件集的加密搜索研究，沒有實現(xiàn)對密文的細粒度訪問控制和權(quán)限管理，沒有考慮嵌合云服務(wù)，而且無法實現(xiàn)對云端數(shù)據(jù)的高效檢索。

另一方面，在細粒度訪問控制的可搜索加密方案中，常用的屬性基加密技術(shù)[5-6]適用于基于用戶屬性而不是用戶列表授予訪問權(quán)限。因此，在對屬性基加密技術(shù)的深入研究中，屬性撤銷機制越來越受到關(guān)注。特別是在實際應(yīng)用中，多個用戶可以共享屬性，一旦共享的任何一個屬性被撤銷，必然會影響到其他擁有撤銷屬性的用戶。在傳統(tǒng)解決方案中，數(shù)據(jù)需要重新加密，并且用戶密鑰需要更新。但是，這種方法的缺點是當云端數(shù)據(jù)量規(guī)模大或者多用戶授權(quán)時，需要大量的計算開銷。因此，研究支持高效率、訪問控制的多關(guān)鍵字可搜索加密方案具有較高的理論價值和實踐意義。

為了解決這些問題，筆者使用屬性基加密、同態(tài)加密技術(shù)和語義空間模型，提出一種支持屬性撤銷的top-k多關(guān)鍵詞密文檢索方案(A Top-kmulti Keyword ciphertext Retrieval Scheme supporting attribute revocation，TKRS)。主要貢獻如下：① 支持多關(guān)鍵字高效搜索。基于屬性基加密搭建屬性-文件索引表，實現(xiàn)對密文的細粒度訪問控制和權(quán)限管理，允許多關(guān)鍵字檢索，top-k排序。② 支持屬性撤銷。引入同態(tài)加密模糊數(shù)據(jù)，確保數(shù)據(jù)隱私，低開銷同態(tài)加操作實現(xiàn)撤銷，滿足大規(guī)模數(shù)據(jù)下多用戶屬性授權(quán)管理。③ 標準模型下的安全性。通過安全分析，文中方案能夠?qū)崿F(xiàn)前向和后向安全性，并且能夠抗共謀攻擊。

1 相關(guān)知識

1.1 CP-ABE算法

屬性加密在實際中有廣泛的應(yīng)用場景，比如分布式文件系統(tǒng)的訪問控制，安全在線社交網(wǎng)絡(luò)，高效廣播加密等。此外，目前大部分身份基加密的擴展均可看作屬性基加密的特例，已被用來解決身份基加密中的身份撤銷問題以及用來構(gòu)造負責身份基加密方案。2011年，文獻[7]提出了密文策略的屬性基加密(Ciphertext-Policy Attribute-Based Encryption，CP-ABE)算法。在此基礎(chǔ)上，研究者通過對訪問樹的優(yōu)化，混合加密的操作和隱藏策略等的方式，提出了各類改進方案[8-10]。而在該方案中，用戶的屬性撤銷和數(shù)據(jù)完整性仍有待研究。因此在改進算法過程中，切實把握算法安全性和功能性的平衡是重點。

1.2 全同態(tài)加密技術(shù)

全同態(tài)加密能夠在不知道密鑰的情況下對密文進行任意計算[11-13]，這種特殊的性質(zhì)使得全同態(tài)加密有廣泛的應(yīng)用需求。2009年，文獻[11]首次基于“理想格”提出全同態(tài)加密方案，在條件下的任意運算函數(shù)進行設(shè)定的同態(tài)操作，并且滿足操作后的密文解密出的明文是預(yù)設(shè)值。因為每次同態(tài)計算將引起密文噪音的增長，當噪音超過正確解密所允許的界限后，將無法執(zhí)行同態(tài)操作。因此，必須設(shè)置大的參數(shù)使得密文有足夠的空間容納噪音，這直接導(dǎo)致了密文尺寸的劇增。參考相關(guān)文獻[12-13]，筆者提出一種n-bit壓縮數(shù)據(jù)同態(tài)加密算法，通過模交換技術(shù)控制噪聲，將密文大小限定在范圍內(nèi)，同時保證其全同態(tài)性質(zhì)。

1.3 語義空間模型

語義向量空間模型(Vector Space Model，VSM)是解放計算機分析和處理文本能力的開端。VSM的思想是把文檔集合表示為空間的點陣，用戶的一個查詢被表示為同一空間里的一個點，文檔按照和該查詢的距離遞增排序。然而語義向量空間模型還有很多的不足，比如文檔的主題分類、關(guān)鍵字、同義詞等，會造成搜索效率低，精度誤差高的問題。這里根據(jù)參考文獻[14]，選用潛在語義向量空間模型(Latent Semantic Analysis，LSA)，可以刻畫同義詞，同義詞集合會對應(yīng)著相同或相似的主題。SVD降維可去除部分噪聲，更具有魯棒性，充分利用冗余數(shù)據(jù)，完全自動化。

2 系統(tǒng)模型

圖1 系統(tǒng)模型圖

TKRS方案如圖1所示，由4個部分組成，在該方案模型中云服務(wù)器被認為是誠實且好奇。下面對各個實體在該方案中的詳細介紹：數(shù)據(jù)所有者(Data Owners，DO)，數(shù)據(jù)用戶(Data User，DU)，權(quán)限認證中心(Attribute Authority，AA)，云服務(wù)(Cloud Service Provider，CSP)。圖1方案模型流程：DO將加密的密文集合發(fā)送到CSP，再基于詞頻-逆文本頻率指數(shù)技術(shù)(Term Frequency-Inverse Document Frequency，TF-IDF)[15]的潛在語義向量空間模型搭建一個屬性-文件索引的檢索表發(fā)送到CSP端，將設(shè)定的訪問權(quán)限傳輸給AA，之后的DU將申請搜索認證發(fā)送到AA，獲取認證結(jié)果(包含私鑰)，構(gòu)建搜索令牌，發(fā)送CSP請求搜索。CSP執(zhí)行搜索，通過檢索表得出預(yù)解密密文傳輸給DU，解密出明文。

3 系統(tǒng)設(shè)計

該方案主要解決了以下3個問題：① 高效的多關(guān)鍵字檢索；② 密文細粒度訪問控制；③ 用戶屬性撤銷[16-20](基于同態(tài)算法3.2實現(xiàn))。下面對算法進行詳細描述。

3.1 方案流程算法

(1) 初始化算法Setup(λ)→(PK，MK)：算法構(gòu)建G0是一個以素數(shù)p為階的雙線性群，并且p∈[2η2-1，2η2]，η為隨機值。設(shè)g為生成元，雙線性映射e：G0×G0→Gr，定義了兩個哈希函數(shù)：H0：{0，1}*→G0和H1：{0，1}*→Gzp。在群Gzp中選擇三個隨機數(shù)a，b，c∈Gzp。

公鑰：PK={G0，Gzp，e，H0，H1，g，h1=ga，h2=gb，h3=gc，h4=g1/b，e(g，g)ab} ，

主密鑰：MK={a，b，c} 。

(2) 密鑰生成算法KeyGen(PK，MK，SID)→SK(S，ID)：私鑰生成由授權(quán)中心AA運行。該算法輸入公鑰PK、主私鑰MK、申請用戶屬性集合SID(屬性包含身份信息)，然后輸出搜索方的屬性私鑰SK(S，ID)。取隨機數(shù)r∈Gzp，并對屬性集S中的每個屬性?j∈S選取隨機數(shù)tj∈Gzp。計算得：

(3) 索引生成算法Indexgen(PK，S，W)→(Inw，L)：將DO的屬性集合S構(gòu)建成對應(yīng)權(quán)限的訪問向量L，而將對明文集合中的關(guān)鍵字W集合搭建一個基于TF-IDF的潛在語義向量空間(LSA)，通過SVD公式計算降維，分解成對應(yīng)明文的文檔向量集，并將兩者構(gòu)建成屬性-文件索引表，經(jīng)過同態(tài)模糊數(shù)據(jù)上傳云端CSP，并將索引相關(guān)參數(shù)上傳到AA授權(quán)中心，此處的參數(shù)用于DU向AA申請檢索向量組時參與計算。

(4) 加密算法Encrypt(PK，M，A)→CT：輸入明文M、訪問策略A和公鑰PK，生成密文CT。算法實現(xiàn)如下：

(5) 令牌生成算法Trapdoor(w，SID，R)→TR：搜索令牌生成算法由DU的本地服務(wù)器運行。該算法輸入關(guān)鍵字集w、DU的屬性集合SID、可搜索關(guān)鍵字樹R，然后輸出搜索令牌TR后發(fā)送至CSP。

③ 先取隨機值tj∈Gzp，對屬性集合SID進行計算，有?j∈SID：Dj=grtH0(att(j))tj*t，Dj′=gtj*t。

④ 此處根據(jù)關(guān)鍵字集w生成申請向量，向AA申請生成訪問向量組V(ID，SID)；該向量組內(nèi)包含用戶屬性授權(quán)向量I(ID，S)和關(guān)鍵字搜索向量IID。

(6) 搜索算法Search(CT，TR，L，Inw)→(1/⊥)：搜索算法由CSP運行。該算法使用上傳搜索令牌TR中的訪問向量組V(ID，SID)與CSP中的屬性-文件索引表進行驗證(3.2節(jié)具體實現(xiàn))，確定用戶的權(quán)限和搜索密文的范圍，進行文檔相似度向量計算，得出該文檔的相似度，通過對余弦計算相似度度量的篩選，選取對應(yīng)的密文，生成待解密密文集合。在進行密文篩選過程中，根據(jù)DU的設(shè)定參數(shù)，可以選擇top-k的匹配密文集合。若搜索出滿足要求的密文返回1，否則返回⊥。

(7) 預(yù)解密算法Pre-Decryt(CT，TR)→M′：將檢索到符合要求的密文進行計算，CSP將返回密文中間值給搜索方服務(wù)器。

③ 根據(jù)兩個值ER和ER′進行相對應(yīng)公式運算：E=e(C，Dpai)ER/ER′=e(g，g)abdr0。則最后返回：

3.2 n-bit壓縮數(shù)據(jù)同態(tài)算法

圖2 數(shù)據(jù)壓縮示意圖

基于文中方案的需求，提出了一種n-bit壓縮數(shù)據(jù)同態(tài)算法：設(shè)為明文，由于初始同態(tài)算法是取二進制明文加密的，即m={0，1}。筆者使用比特壓縮折疊理念，如圖2所示，將二進制化的明文切割后壓縮到0～255的映射表中，通過字符映射的方式來減少二進制轉(zhuǎn)化數(shù)據(jù)增大的弊端，通過這樣的壓縮折疊方式生成的待加密明文會比原明文小。并且根據(jù)切割的壓縮指數(shù)，對應(yīng)地進行同態(tài)加密，這里進行二次壓縮，極大地降低了同態(tài)加密生成的密文大小。而且為了避免多次同態(tài)操作增噪的問題，使用了模交換技術(shù)來降低噪聲，控制密文中噪聲的增加。

根據(jù)安全參數(shù)λ生成私鑰p和大素數(shù)整數(shù)q。c為密文，r是加密過程中的隨機生成的噪聲整數(shù)，k為一次加密的比特數(shù)，表示比特的縮減程度。加密時要求k的值保持一致，要求q>r，p/2>m+2kr，取得：加密算法：c=m+2krq+pq和解密算法：m=(cmodp)mod 2k(滿足全同態(tài)定義)。

3.2.1DO的申請與檢索表的匹配操作

屬性-文件索引表和訪問向量組V(ID，SID)都是同態(tài)加密密文，可以使用同態(tài)性質(zhì)進行判斷，這里取隨機r′p和N=pq作為公鑰，參與匹配計算：

Value=((hm.CTattr-hm.CTDU)r′p)modN=(Mattr-Mtoken)r′p。

可見，由于不為0，因此，如果Value為0，則表示匹配成功，即訪問向量組的類存在于云服務(wù)器的檢索表內(nèi)。此外，生成明文為0的密文集合：{xi：xi=2nri+pqi}，在加密時隨機從其中選取子集加入加密算法中，加進去的是0的密文，對解密并沒有影響，同時通過引入最大公約數(shù)問題，證實方案是安全的。

3.2.2 密文細粒度訪問控制與屬性撤銷

在方案中，DO將屬性-文件索引表同態(tài)上傳，輸入指定的訪問向量組或者Data，通過DO發(fā)送的對應(yīng)同態(tài)操作的函數(shù)f(upfdate)，可以實現(xiàn)對云服務(wù)器CSP上索引表上同態(tài)加密數(shù)據(jù)的加同態(tài)或乘同態(tài)計算，實現(xiàn)屬性撤銷(此處授權(quán)中心AA的屬性撤銷直接發(fā)送請求即可)。通過同態(tài)計算控制屬性-文件索引表實現(xiàn)對密文的細粒度訪問控制，精確到具體用戶身份屬性識別訪問授權(quán)，并且通過對索引表上的參數(shù)進行同態(tài)操作，能夠?qū)崿F(xiàn)云上的文件刷新和刪除功能。由于函數(shù)運行在云服務(wù)器上，充分利用了云的強大算力，能夠以低開銷同態(tài)操作實現(xiàn)撤銷，滿足大規(guī)模數(shù)據(jù)下多用戶授權(quán)管理。

由于DO使用的同態(tài)操作是針對擁有文件的處理，不共享同態(tài)解密密鑰，所以云端無法獲得解密私鑰，只能依照申請發(fā)送的函數(shù)對同態(tài)模糊數(shù)據(jù)進行操作，從而保證云服務(wù)器數(shù)據(jù)的保密性和安全性。

4 方案分析

4.1 安全性分析

4.1.1 前后向安全性

在設(shè)計方案屬性管理機制中，當用戶的屬性發(fā)生變動時，DO可以對授權(quán)機構(gòu)AA和云服務(wù)器CSP發(fā)送同態(tài)操作的函數(shù)，利用簡單的加/乘操作計算出新的數(shù)值，并實現(xiàn)對沒有被撤銷屬性的用戶私鑰的更新。依據(jù)同態(tài)算法的大素數(shù)困難問題，即使在知道原參數(shù)值的情況下也無法推算出新屬性參數(shù)值的定義。同理，用戶無法通過更新后的屬性值推算出更新前的屬性值。因此新方案滿足前向后向安全性。

4.1.2 近似最大公約數(shù)問題

對該方案的同態(tài)密文，任何攻擊都可以轉(zhuǎn)換為近似最大公約數(shù)問題的解決方案，因此該方案是安全的。

4.1.3 抗共謀攻擊

DO對數(shù)據(jù)文件的加密方式是參照自己的意愿選定屬性集合來設(shè)定訪問結(jié)構(gòu)，并且將利用此訪問結(jié)構(gòu)來加密文件。因此只有滿足訪問結(jié)構(gòu)的用戶才能計算出e(g，g)abdr0。假設(shè)多個未授權(quán)用戶的屬性集合并在一起才能滿足訪問結(jié)構(gòu)，由于不同用戶的身份屬性不同，生成屬性私鑰組件不相同，所以無法計算e(g，g)abdr0，從而無法恢復(fù)出明文。因此方案具有抗串謀攻擊性。

表1 方案對比

4.2 性能分析

參考相關(guān)文獻，針對Jin的多關(guān)鍵字的CP-ABE方案[16]、CAO的可搜索加密方案[17]、Fateh的反向索引的CP-ABE方案[18]以及文中提出的TKRS方案，進行了理論分析和仿真測試。

4.2.1 理論分析

針對評估設(shè)計方案在云計算系統(tǒng)中的安全性和實用性，從3個方案與設(shè)計方案的功能上進行對比。通過表1可以看出，筆者提出的TKRS方案功能更加強大，更加適用于實際應(yīng)用。表2給出了相關(guān)符號的定義。

表2 符號定義

如表3所示，算法IndexGen、Token的存儲開銷對比，TKRS方案要明顯小于其余3個方案。另外Jin的方案的|SK| 要小于其他的方案的|SK|，因為Jin方案中簡化私鑰構(gòu)造，降低對密文的訪問策略的控制，這點是通過引入第三方機構(gòu)實現(xiàn)彌補，但會不可避免地造成傳輸過程的復(fù)雜及其他步驟的數(shù)據(jù)冗余，而TKRS方案和Fateh方案生成|SK|是依據(jù)安全性進行設(shè)計的，多了一次用戶U的屬性量的群上的運算操作值，存儲開銷在考慮范圍內(nèi)。

表3 存儲開銷

表4 計算開銷

根據(jù)表4的分析可以得到，在通信過程中計算傳輸開銷，Jin方案因為算法簡化的原因，Keygen計算量比TKRS方案減少接近|Au|G，但同之前存儲開銷分析的原因一樣，Jin方案的其他步驟的計算開銷要遠遠大于TKRS方案不止|Au|G的計算量。另外，算法Search和Update對比中，TKRS方案計算開銷最小。關(guān)于Dec算法數(shù)據(jù)解密過程，即數(shù)據(jù)文件訪問解密階段的開銷，分為云端計算DecCloud和本地計算DecDu兩部分，云服務(wù)器的算力高，不能做參考點，與參考文獻方案對比，TKRS方案明確體現(xiàn)了將云端算力和數(shù)據(jù)處理相結(jié)合的特點，能以低本地計算開銷保證數(shù)據(jù)安全。綜上所述，TKRS方案通過犧牲一點存儲代價換取方案的安全和高效率是值得的，所提方案就綜合性能而言，是4種方案中最好的。

4.2.2 仿真測試

對筆者所提方案的實際性能進行仿真實驗，是在具有2.30 GHz Intel?CoreTMi7-10875H CPU和8 GB內(nèi)存的Windows機器上執(zhí)行的，運行環(huán)境為JDK 1.8.0_271、eclipse和JPBC庫支持。文件數(shù)據(jù)集源自于英文維基百科的部分歷史數(shù)據(jù)，text格式。

(1) 加密索引大小。這里首先測試生成文件索引的大小，由于內(nèi)存的限制，選用500份文件進行測試。聯(lián)系圖3和圖4分析，Jin和CAO方案生成索引的開銷程度一致，而索引加密的開銷程度不同。下面對比統(tǒng)一取500 文件數(shù)的節(jié)點為標準，Jin和CAO方案從780 MB加密至35 465 MB和22 152 MB，相當于分別增加了約44.5倍和27.4倍。筆者提出的TKRS方案能夠有效控制密文增長，根據(jù)算法來調(diào)節(jié)壓縮比例。與Jin和CAO方案對比，生成索引7.65 MB，壓縮到約0.98%，加密索引645 MB，壓縮到約1.8%和2.9%。Fateh方案的生成索引23.55 MB，壓縮到Jin和CAO方案的3%，加密索引2 072 MB，壓縮到5.8%和9.3%，性能明顯低于TKRS方案。此外，筆者提出的方案存儲規(guī)模的加密指數(shù)不依賴于文檔索引大小，而是依賴于安全級別，是在安全性和性能之間選擇適當?shù)钠胶狻?/p>

圖3 生成索引大小對比

圖4 加密索引大小對比

(2) 檢索效率。為了檢測搜索密文的效率，針對筆者提出的密文檢索模型和參考方案進行對比，該次檢索測試5 000份文件矢量。對比方案的模型結(jié)構(gòu)和檢索算法，圖5中Jin和CAO的基于矢量的遍歷檢索時長隨著數(shù)量增長而增長，總耗時要比主題模型高。圖6中 Fateh方案和TKRS方案基于主題模型，提取語義關(guān)鍵字建立主題類，兩個方案檢索方式都是先確定檢索密文范圍再遍歷匹配，測試取限定密文文檔范圍為預(yù)估最大值(109)進行遍歷的效果進行對比。根據(jù)圖中遍歷效率對比，TKRS方案模型主題指標的構(gòu)建較Fateh方案是趨于穩(wěn)定的，而且使用的計算量要低于Fateh方案近3倍的耗時差。

圖5 矢量模型遍歷檢索效率

圖6 主題模型遍歷檢索效率

(3) 檢索精度。這里對TKRS方案和參考方案進行對比測試分析，取5 000個文檔矢量進行實驗。圖7中是使用了定長的多關(guān)鍵字申請矢量進行檢索，5 000份文件的分段檢索，針對各個方案的匹配反饋文件數(shù)進行對比，可以明顯看出Jin方案和CAO方案反饋密文數(shù)量接近于50%，而Fateh的方案和TKRS方案提供top-k的篩選功能，能夠有效地控制匹配密文的反饋數(shù)量。圖8針對5 000個文檔矢量進行重復(fù)多關(guān)鍵字搜索，取均值(取60～100關(guān)鍵字區(qū)間，準確率波動小)。Fateh方案多次進行檢索得出精度在38.76%左右。而TKRS方案更為高效，準確度接近44.26%，因為方案使用的LSA語義模型在低維空間刻畫同義詞，充分利用冗余數(shù)據(jù)提取主題，當查詢關(guān)鍵字數(shù)量越多時，越能有效確定檢索文檔。

圖7 方案檢索密文匹配對比

圖8 方案命中文檔準確率對比

5 結(jié)束語

筆者提出了一種支持屬性撤銷的top-k多關(guān)鍵詞密文檢索方案，使用了屬性基加密、同態(tài)加密和語義空間模型技術(shù)，并相對應(yīng)地進行優(yōu)化，構(gòu)建屬性-文件檢索表來提高檢索效率，實現(xiàn)了多關(guān)鍵字檢索和屬性撤銷功能。并且該方案支持前后向安全性和云端數(shù)據(jù)操作的隱私保護，抗共謀攻擊。對該方案進行了理論分析，與參考方案進行了實驗對比，證明了該方案性能的優(yōu)越性。最后，隨著可搜索加密的理論和技術(shù)不斷進步，使用的加密算法和語義模型都有很大的創(chuàng)新潛力，增強性能和安全性，可以結(jié)合云平臺進行相關(guān)探索研究。