云邊協同下可排序的屬性基可搜索加密方案

王 正，曹素珍，趙 曉，周大偉，邢丹丹

（西北師范大學 計算機科學與工程學院，蘭州 730070）

0 概述

隨著物聯網和5G 技術的廣泛應用［1-2］，現有云服務器的性能已不能滿足互聯網時代對海量數據的實時處理需求。邊緣設備［3-4］以低時延、移動性支持等優勢逐步成為解決上述問題的一種新途徑。云服務器和邊緣設備是半誠實的［5-7］，因此為保證用戶數據的機密性，數據所有者（Data Owner，DO）通常將數據加密后再存儲于云端或邊緣設備，然而如何檢索密文成為數據用戶面臨的一大難題。文獻［8］提出可搜索加密（Searchable Encryption，SE）概念，有效解決了密文檢索的難題。

在早期的SE 方案中常采用單關鍵字SE 方案［9］，但因存在大量的關鍵字索引重復問題，從而導致搜索效率不高。為了提高搜索的準確性，在后續的研究中用戶搜索的關鍵字通常采取多關鍵字方案［10-12］。文獻［13］提出一種多關鍵字SE 方案，通過匹配多關鍵字的索引和搜索陷門來提高搜索效率，但仍存在關鍵字與主題相關性不大的問題。文獻［14］提出一種多關鍵字排序SE 算法，利用TF-IDF規則根據關鍵字相關的程度排序搜索結果，僅返回最滿足用戶需求的Top-k文件。上述文獻無論是采用對稱或非對稱加密算法均無法滿足數據共享時的細粒度訪問控制需求。

文獻［15］提出屬性基可搜索加密（Attribute-Based Searchable Encryption，ABSE）概念，實現了外包加密數據上的安全搜索和細粒度訪問控制。文獻［16-17］提出一種基于密文策略的ABSE 方案（CPABSE），在CP-ABSE 方案中私鑰與屬性相關聯，密文與訪問結構相關聯，使得訪問密文的用戶由數據所有者設定的訪問策略決定，達到細粒度訪問控制的效果。KP-ABSE［18］方案是將策略嵌入用戶密鑰，屬性嵌入密文，但這兩種ABSE 方案都可能存在訪問策略泄露問題。文獻［19］提出一種基于隱藏策略和外包解密的白盒可跟蹤屬性加密方案，基于LSSS訪問結構，該方案采用策略隱藏的方式只對屬性名進行公開，缺陷在于不支持對多關鍵字的搜索排序，搜索結果不精準。文獻［20-21］提出一種基于邊緣計算框架的高效密文索引檢索方案，結合可搜索加密技術與邊緣計算技術所定義的邊緣緩存網絡模型使密文檢索更加安全高效。文獻［22］提出IIoT 時代可持續邊緣云網絡的多關鍵詞排序搜索隱私保護方案，但該方案無法滿足大規模計算需求。

針對上述問題，本文提出云邊協同下可排序的屬性基可搜索加密方案，主要工作如下：

1）利用云邊協同技術，將加密后的數據上傳到云端，與其對應的加密索引上傳到最近的邊緣節點，提高了搜索效率，降低了用戶的計算負擔。

2）用戶的屬性由屬性名和屬性值組成，在構造訪問結構時，用戶僅通過公開的屬性名進行陷門搜索匹配，從而使得未經授權的用戶無法獲取訪問策略中的任何有效信息。

3）在密文檢索階段，可在排除無關關鍵字的情況下根據檢索關鍵字的重要程度進行排序，最終返回與用戶需求最相關的Top-k密文，實現了多關鍵字排序搜索。

4）利用在線/離線加密技術，數據所有者在上傳密文之前先進行離線加密，降低客戶端的計算成本。

1 預備知識

1.1 雙線性映射

選擇兩個循環群G1、G2，p是它們的素數階，定義一個雙線性映射e：G1×G1→G2滿足以下性質［23］：

1）雙線性。對?x,y?G1,?a,b?，有e(xa,yb)=e(xb,ya)=e(x,y)ab成 立。

2）非退化性。?x,y?G1滿足e(x,y) ≠1。

3）可計算性。對?x,y?G1，存在一個多項式時間算法有效計算e(x,y)。

1.2 訪問結構

設P={P1,P2,…,Pn}表示參與者的集合，令2P={A|A?{P1,P2,…,Pn}}，集合A?2P是單調的，當且僅當對于任意子集B,C?P，如果B?A且B?C，則C?A。若A是P={P1,P2,…,Pn}中的非空子集（單調的），即則 稱A是一個 訪問結構（單調的）。對于任意集合D，若D?A，則D為授權集，否則為非授權集［24］。

1.3 線性秘密共享方案

定義P上的一個線性秘密共享方案π，滿足如下條件［25］：

2）每個線性秘密共享方案都有一個l×n的生成矩陣M，且存在單射函數ρ：{1,2,…,l} →P把M的每一行(i=1,2,…,l)映射到參與者ρ(i)。考慮向量v=(s,v2,v3,…,vn)，s?是共享秘 密值，選 擇隨機數v2,v3,…,vn?隱藏共享秘密值s，則Mv是共享秘密份額，其中λi=(Mv)i是共享秘密值s的第i個秘密份額。

1.4 TF-IDF 規則

TF-IDF 用來評估指定關鍵字對于文檔集合中某一篇文檔的重要程度［26］，值越大，說明該關鍵字w在文檔f中的重要程度越靠前。TF 是計算指定關鍵字w在查詢文檔f中出現的次數，IDF 是該關鍵詞出現在所有文檔中的數據集合。根據下述拆分規則計算Top-k文件。

拆分規則：基于隨機的n維二進制向量P計算n維向量Q，利用P將Q拆分為兩個隨機向量(Q′,Q″)，如式（1）所示：

1.5 困難問題假設

困難問題假設具體如下：

1）DBDH 假設。設一個循環群G，p是它的素數階，g是G的一個生成元。隨機選擇a,b,c,z?Zp，給定多元組，如果不存在一種算法能夠在多項式時間內以不可忽略的概率區分(g,ga,gb,gc,z)，則DBDH 假設成立。

2）q-parallel DBDH 假設。選擇兩個乘法循環群G1、G2，p是它們的素數階，g是G1的一個生成元。隨機選擇q+2 個元素x,a,b1,b2,…,bq?Zp，計算：

1.6 符號描述

文中使用的一些符號和變量如表1 所示。

表1 符號和變量描述Table 1 Description of symbols and variables

2 屬性基可搜索加密方案

2.1 系統模型

所提方案的系統主要包括5 類實體，分別是授權機構（Authorization Attribute，AA）、云服務提供商（Cloud Service Provider，CSP）、邊緣節點（Edge Node，EN）、數據所有者和數據用戶（Data User，DU）。

該方案由一個受信任的AA 公開發布全局參數并對主密鑰保密，DO 將加密文件上傳到CSP 存儲，將相應的關鍵字索引上傳到最近的EN。DU 根據訪問策略生成搜索陷門發送給最近的EN，EN 接收到搜索陷門后先對CSP 中存儲的數據進行搜索，CSP搜索出符合的文件返回給EN，EN 利用用戶生成的部分解密密鑰對其進行部分解密，將Top-k文件返回給用戶解密，最后得到共享的數據文件。系統模型及流程如圖1 所示。

圖1 系統模型及流程Fig.1 System model and procedure

該模型在現實應用中可適應于大部分實際場景，如智能電網。假設電力運營公司使用該模型使某市的各小區之間可相互共享一些電網用戶數據。電網用戶查看自己相關的數據時只需要簡單的身份注冊，受信任的授權機構根據其基本信息分發可解密本人數據的屬性密鑰。電網用戶根據屬性設置訪問策略，系統將其轉換為一個矩陣并將其嵌入密文后上傳云服務器，相應的關鍵字索引上傳到最近的邊緣節點。管理人員等其他想要訪問數據的電網查詢者需要受信任的授權機構審核其身份信息并為其分發屬性密鑰，在系統中輸入相關關鍵字，當屬性滿足電網用戶設置的訪問策略時，則可解密搜索結果，否則無權查看，這在一定程度上保護了數據隱私。

1）AA。AA 是一個完全受信任的實體，由它生成全局參數和系統主密鑰，當用戶想要查詢時，可以根據其屬性集生成對應的用戶私鑰。

2）CSP。CSP 是一個誠實但好奇的半可信實體，會好奇云上存儲的數據但會誠實地執行任務。在該系統中，允許系統中的合法用戶上傳或訪問存儲其上的密文數據。

3）EN。EN 用于存儲密文索引，當從DU 接收搜索陷門時，誠實地執行搜索算法，并將搜索結果發送到CSP。在獲得從CSP 返回的加密文件后，協助DU進行部分密文解密操作，并根據TF-IDF 規則計算并返回給用戶最符合要求的Top-k文件。

4）DO。根據DO 設定的訪問策略對數據和關鍵字進行加密后上傳到EN。

5）DU。每個DU 計算搜索陷門并發送到邊緣節點進行匹配查詢，生成部分解密密鑰發送到邊緣節點以供對返回的搜索結果進行部分解密操作。

2.2 安全模型

所提方案的安全模型通過攻擊者A 和挑戰者C之間的模擬游戲定義。若攻擊者A 在多項式時間算法內不能以不可忽略的優勢在游戲中獲勝，則該方案具有選擇關鍵字攻擊（IND-CKA）安全性。

1）初始化。挑戰者C 調用SetUp 算法，通過安全參數λ計算得全局參數GP和系統主密鑰KM。

2）查詢階段1。攻擊者A 向挑戰者C 請求對應屬性集SA的私鑰和待查詢關鍵字的集合W′的搜索陷門。

3）挑戰。攻擊者A 向挑戰者C 發送兩個大小相同的關鍵字w1、w2，攻擊者A 提供訪 問策略(M,ρ)，挑戰者C 隨機選擇b?{0,1}，利用wb生成加密關鍵字索引Iwb返回給攻擊者A。

4）查詢階段2。攻擊者A 重復進行查詢階段1，查詢更多與w1、w2不同的關鍵字集合的搜索陷門。

5）猜測階段。攻擊者A 輸出b的一個猜想b'?{0,1}，若b=b'，則攻擊者A 獲勝，攻擊者A 成功的優勢為

2.3 算法描述

算法描述具體如下：

1）設 置SetUp(1λ) →(GP,KM)。AA 執行該 算法，輸入安全參數λ，輸出全局參數GP，主密鑰KM。

2）密鑰生成KeyGen(GP,KM,S)→(KS)。AA執行該算法，輸入全局參數GP，根據主密鑰KM和用戶的屬性集S生成用戶的屬性密鑰KS。

3）加密。加密包括離線加密和在線加密。

（1）離線加密Offline.Enc(GP) →(CP)。在沒有確定關鍵字集合以及訪問策略之前，DO 空閑時執行該算法，輸入全局參數GP，根據用戶屬性S及選擇的秘密值s輸出中間密文CP，用于在線加密。

（2）在線加密Online.Enc(GP,CP,F,W,A(M,ρ)) →(CT,Iw)。DO 執行該算法，輸入全局參數GP，離線加密時生成的中間密文CP，明文文件集F，關鍵字集合W，訪問策略A(m,ρ)，輸出對數據加密生成的加密密文CT和對關鍵字加密生成的加密索引Iw，并根據TF-IDF 規則計算索引向量Iw。

4）陷門生成Trapdoor(GP,KS,q) →(Tq)。DU 執行該算法，輸入用戶私鑰KS和在關鍵字集合中隨機選擇的待搜索關鍵字q，生成查詢陷門用于密文搜索。同時，根據TF-IDF 規則計算查詢向量與在線加密時生成的索引向量一同用于Top-k文件的分數排序計算。

5）密文搜索Search(GP,CT,Iw,Tq)→(CT/⊥)。CSP執行該算法，輸入查詢陷門Tq和關鍵字索引Iw，檢測其能否成功匹配，若能則繼續驗證，否則終止。

6）驗證Verify。驗證返回結果的正確性，并根據TF-IDF 規則計算并返回給用戶需要的Top-k文件。

7）轉換Transform(GP,KS) →(KP)。由DU 執行該算法，輸入DU 的私鑰KS，輸出邊緣節點的部分解密密鑰KP，用于協助密文的部分解密。

8）部分解密密文E.Dec(GP,KP,CT) →(CPT)。EN執行該算法，輸入全局參數GP和邊緣節點的部分解密密鑰KP，對所得的Top-k文件密文進行部分解密，輸出部分解密密文CPT。

9）解 密Dec(KS,CPT,Kτ) →(m)。DU 執行該 算法，輸入DU 的私鑰KS，并利用中間解密密鑰中包含的轉換因子Kτ，對步驟8）得到的部分解密密文CPT解密后，獲得所需明文m。

2.4 方案構造

方案構造具體如下：

1）系統建立。先初始化系統，輸入安全參數λ，設置全局參數U={1,2,…,N}，設兩個乘法循環群G1、G2，p是它們 的素數 階，設定雙 線性對e：G1×G1→G2，其中，g是G1的生成元，并選擇哈希函數H：{0,1}*→。AA 隨機選擇α,β,μ?，計算e(g,g)α、gβ、gμ。對于每個屬性i?U，AA 隨機選擇ai?，計算。最后生成系統的全局參數GP和主密鑰KM，如式（2）所示：

其中：GP由AA 公開；KM由AA 秘密保存。

3）離線加密。在沒有確定關鍵字集合以及訪問策略之前先進行離線計算。DO 選擇秘密值，計算密文，如式（4）所示：

4）在線加密。設l×n的訪問矩陣Ml×n，其中對?i?[1,l]，Mi是矩陣M的第i行，定義函數ρ將第i行映射到 相應的 屬性名ai，ρ：ρ(i) →ai。最后將{Ml×n,ρ}以明文的形式作為訪問結構。

（1）數據加密

②計算λi=Ml×n×v。

（3）生成索引向量。DO 根據拆分規則式（1）設置索引向量與關鍵字索引一同作為密文索引發送到EN。

5）查詢

（1）生成查詢陷門。DU 選擇關鍵字集合W，隨機選擇q，計算查詢陷門如式（5）所示：

（2）生成查詢向量。DU 根據拆分規則式（1）設置查詢向量將其與查詢陷門一起發送到EN。

6）密文搜索。EN 檢測查詢陷門與關鍵字索引能否成功匹配，驗證等式e(IWj,T1)e(I1,T3)=e(I2×I3,T2)是否成立，若成立則使用式（6）計算索引向量和查詢向量的相關分數：

將計算得到的相關分數結果排序，僅返回Top-k文件密文CT，否則輸出⊥。

9）明文。DU 收到EN 返回的部分解密密文CPT后，計算明文m=并輸出。

3 正確性與安全性證明

3.1 正確性證明

1）關鍵字匹配正確性

檢查式（7）是否成立來判斷用戶生成的陷門和密文對應的關鍵字是否匹配：

綜上，關鍵字匹配的正確性得證。

2）解密密文正確性

邊緣節點接收到DU 的部分解密密鑰后計算部分解密密文。邊緣節點輔助解密的正確性證明如下：

根據上述可得解密密文的正確性證明如下：

綜上，解密密文的正確性得證。

3.2 安全性證明

定理1若多項式時間內的算法允許攻擊者A以可忽略的優勢獲勝，則該方案具有IND-CKA 安全性。

1）初始化。輸入安全參數λ，選擇一個循環群G1，p是它的素數階，g是G1的生成元，隨機選擇α,β,μ?和哈希函數H：{0,1}*→，挑戰者 C 調 用SetUp(1λ) →(GP,KM)算法。最后生成系統的全局參數GP和主密鑰KM，GP由AA公開，KM由AA秘密保存。

2）查詢階段1。查詢階段1 包括私鑰查詢和陷門查詢。

4）查詢階段2。攻擊者A 重復進行查詢階段1，查詢更多與w1、w2不同的關鍵字集合的搜索陷門。

5）猜測階段。攻擊者A 輸出b的一個猜想b'?{0,1}，若b'=b，則攻擊者A 輸出b'=b的概率為，若b'≠b，則攻擊者A 輸出b'≠b的概率為因此攻擊者A 成功的優勢如下：

由于攻擊者A 成功的優勢是可忽略的，因此所提方案是安全的，證畢。

4 性能分析

4.1 功能分析

為了證明所提方案的有效性，進行在線/離線加密、策略隱藏、搜索結果排序等方面的比較實驗，比較方案選擇文獻［12-14，19］方案，比較結果如表2 所示，其中，√表示具備該功能，×表示不具備該功能。

表2 功能比較Table 2 Function comparison

由表2 可知，除文獻［19］方案外的其他方案都支持多關鍵字搜索，從而提高了方案對文件檢索的準確性，特別是文獻［14］方案和所提方案可以對搜索后得到的文件進行Top-k排序，但只有所提方案在加密時引入了在線/離線加密機制，因而實現了較低的計算開銷。此外，在所提方案中，運用邊緣節點輔助解密的設計，密文在被DU 解密之前會被EN 部分解密，大大減少了DU 的計算開銷，減輕了客戶端負擔。文獻［19］方案引入外包輔助加/解密的技術，雖降低了客戶端的成本，但外包密鑰的生成和驗證需要額外的開銷導致效果不理想。文獻［12-13］方案并未實現對訪問策略的隱藏，對用戶的敏感信息有巨大的安全隱患。相比較而言，所提方案不僅可滿足多關鍵字的密文排序搜索，以及實現策略隱藏和細粒度訪問控制，同時與其他方案相比，在降低用戶開銷方面具有更好的性能。

4.2 計算與存儲開銷分析

將所提方案與文獻［12-14，19］方案在計算、存儲開銷方面進行對比，結果如表3 和表4 所示，其中，分別表 示中元素 的長度，n1、n2分別表示訪問策略中的屬性個數、與用戶相關的屬性個數，i表示關鍵字集中關鍵字的個數，E1、E2表示G1、G2上的群指數運算，P表示雙線性對運算。

表3 計算開銷比較Table 3 Computational cost comparison

表4 存儲開銷比較Table 4 Storage cost comparison

對于計算開銷的比較，所提方案在加/解密階段采用了在線/離線加密技術，與其他方案相比開銷較低。對于存儲開銷的比較，因為云服務器的存儲容量不受限，所以所提方案并不考慮云中的密文存儲開銷。由于用戶的密鑰長度只與屬性相關，因此在所有方案中用戶只存儲其長度隨n2增加而線性增加的屬性。雖然當屬性較少時所提方案需要的存儲空間較大，但是當屬性數隨著n2線性增加時，所提方案的密鑰存儲開銷低于其他方案。以上表明，所提方案在計算和存儲開銷方面較其他方案有一定優勢。

4.3 性能仿真分析

為了更準確地評估方案的實際性能，實驗平臺配置在Intel?CoreTMi5-8250U CPU @ 160 GHz 8.00 GB RAM 的筆記本上，基于Java 配對加密庫（JPBC），采用Type A 型素數階橢圓曲線y2=x3+x進行仿真實驗。為了方便定量分析，假定關鍵字集中關鍵字的數量為50，屬性數量的取值范圍為［10，50］，當屬性數量取值為10、20、30、40、50 時，各方案在加密和陷門生成階段的計算時間隨屬性數量的變化情況分別如圖2 和圖3 所示。

圖2 各方案加密階段的計算時間比較Fig.2 Comparison of computing time in encryption stage of each scheme

圖3 各方案陷門生成階段的計算時間比較Fig.3 Comparison of computing time in trapdoor generation stage of each scheme

由圖2 和圖3 可知，各方案的加密和陷門生成時間都與屬性數量成線性正比關系，所提方案在加密和陷門生成階段的計算時間相比于次優的文獻［12］方案降低了10%和25%。在加密階段，雖然當屬性數量較少時所提方案的計算時間不是最少，但隨著屬性數量的增加計算時間一直少于其他方案。在陷門生成階段，與其他方案相比，所提方案的計算時間一直保持在最低的常數級水平。

實驗結果分析表明，所提方案不僅實現了高效的多關鍵字搜索和密文的訪問控制，而且具有更好的性能和實用價值。

5 結束語

本文提出云邊協同下可排序的屬性基可搜索加密方案。采用在線/離線加密和邊緣節點輔助計算，在確定訪問策略前進行預加密，通過將加密后的數據上傳到云端，與其對應的加密索引上傳到最近的邊緣節點來降低用戶的計算負擔。將關鍵字拆分成關鍵字名和關鍵字值，用戶只能通過公開的關鍵字名進行匹配，保證了方案安全性。在實現多關鍵字搜索的情況下對關鍵字的重要程度進行排序，提高了搜索效率。分析與對比結果表明，所提方案滿足IND-CKA 安全性，并且與同類方案相比更具高效性。后續將進一步加強所提方案的搜索效率及實用性。