一種支持屬性撤銷的top-k多關鍵詞密文檢索方案

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

(1.深圳技術大學 大數據與互聯網學院，廣東 深圳 518118；2.鵬城實驗室 網絡空間安全部，廣東 深圳 518000；3.桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541010)

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

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

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

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

1 相關知識

1.1 CP-ABE算法

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

1.2 全同態加密技術

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

1.3 語義空間模型

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

2 系統模型

圖1 系統模型圖

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

3 系統設計

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

3.1 方案流程算法

(1) 初始化算法Setup(λ)→(PK，MK)：算法構建G0是一個以素數p為階的雙線性群，并且p∈[2η2-1，2η2]，η為隨機值。設g為生成元，雙線性映射e：G0×G0→Gr，定義了兩個哈希函數：H0：{0，1}*→G0和H1：{0，1}*→Gzp。在群Gzp中選擇三個隨機數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)：私鑰生成由授權中心AA運行。該算法輸入公鑰PK、主私鑰MK、申請用戶屬性集合SID(屬性包含身份信息)，然后輸出搜索方的屬性私鑰SK(S，ID)。取隨機數r∈Gzp，并對屬性集S中的每個屬性?j∈S選取隨機數tj∈Gzp。計算得：

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

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

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

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

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

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

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

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

3.2 n-bit壓縮數據同態算法

圖2 數據壓縮示意圖

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

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

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

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

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

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

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

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

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

4 方案分析

4.1 安全性分析

4.1.1 前后向安全性

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

4.1.2 近似最大公約數問題

對該方案的同態密文，任何攻擊都可以轉換為近似最大公約數問題的解決方案，因此該方案是安全的。

4.1.3 抗共謀攻擊

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

表1 方案對比

4.2 性能分析

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

4.2.1 理論分析

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

表2 符號定義

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

表3 存儲開銷

表4 計算開銷

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

4.2.2 仿真測試

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

(1) 加密索引大小。這里首先測試生成文件索引的大小，由于內存的限制，選用500份文件進行測試。聯系圖3和圖4分析，Jin和CAO方案生成索引的開銷程度一致，而索引加密的開銷程度不同。下面對比統一取500 文件數的節點為標準，Jin和CAO方案從780 MB加密至35 465 MB和22 152 MB，相當于分別增加了約44.5倍和27.4倍。筆者提出的TKRS方案能夠有效控制密文增長，根據算法來調節壓縮比例。與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方案。此外，筆者提出的方案存儲規模的加密指數不依賴于文檔索引大小，而是依賴于安全級別，是在安全性和性能之間選擇適當的平衡。

圖3 生成索引大小對比

圖4 加密索引大小對比

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

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

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

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

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

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

5 結束語

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