周藝華，扈新宇，李美奇，楊宇光

（1. 北京工業(yè)大學信息學部 北京 100124；2. 可信計算北京市重點實驗室 北京 100124）

0 引言

隨著云計算的快速普及，許多組織將其數(shù)據(jù)和服務外包給云，但帶來了嚴重的隱私泄露問題。因此，很多用戶將敏感數(shù)據(jù)外包給云服務之前對其進行加密。然而，加密用戶的數(shù)據(jù)妨礙了云應用程序的搜索功能。為了解決此類問題，Song等[1]首次提出了可搜索加密，它允許以加密形式外包數(shù)據(jù)，同時仍然能夠進行搜索。這些方案通常包括以下步驟：數(shù)據(jù)擁有者（DO，date owner）生成其加密文檔和可搜索加密索引，將加密文檔和加密索引外包給云。當搜索關鍵字時，用戶（DU，data user）生成一個陷門提交到云服務器上，云服務器可以搜索加密索引并返回相關文檔。

目前，大多數(shù)方案以模糊關鍵詞[2-4]和排序搜索關鍵字[5-6]為核心，Liu等[2]采用向量內(nèi)積方式實現(xiàn)關鍵字搜索，文件解密密鑰需要用戶間進行密鑰協(xié)商；Ahmed等[5]采用可搜索對稱加密方式，根據(jù)文檔與查詢的相關性對文檔進行排序，任何用戶通過上傳搜索陷門，都可以獲取所需的文檔。但近年來，受基于屬性的加密（ABE，attribute-based encryption）概念的啟發(fā)，將訪問控制與可搜索加密相結合，加密索引可以通過關鍵字進行搜索，搜索權限由ABE控制，用戶實現(xiàn)了更細粒度的關鍵字搜索。文獻[7-10]提出基于屬性的可搜索加密方案，由云端直接完成訪問策略的驗證，若成功，則只將密文返回給用戶端解密，密文的解密與策略不相關，導致攻擊者可能跳過訪問策略直接進行索引匹配和文件解密。

Niu等[11]和Miao[12]、Wu等[13]分別將訪問策略轉化為訪問樹和“AND”門，與其方案相比，本文方案采取線性秘密共享矩陣的訪問結構，能夠支持任意表達的訪問策略，并進行了策略隱藏。Yan等[14]和Waters[15]的方案采用訪問策略對每個文件進行加密，并未通過關鍵字搜索，雖將訪問策略轉化為線性秘密共享矩陣，然后進行文件的加密，但并未通過對關鍵字搜索，文件獲取效率不高。

針對現(xiàn)有問題，本文主要貢獻如下。

1) 利用基于屬性的加密和可搜索加密技術，采取線性秘密共享矩陣構造訪問策略，將訪問控制與關鍵字搜索、文件加密相結合，保證訪問策略與關鍵字都正確才匹配成功，進行文件存儲地址的解密。同時，對屬性值進行隱藏，訪問策略中任何有價值的屬性信息都不會透露給未經(jīng)授權的接收者。

2) 不同的文件采用不同的密鑰加密，用戶接收一個聚合密鑰，就能解密出所需的文件。

3) 陷門不可連接性。保證即使多次查詢的屬性或關鍵字相同，攻擊者也無法區(qū)分。

在Linux Ubuntu64位操作系統(tǒng)下利用雙線性對包，并用 Python語言進行編程。實驗結果表明，本文方案的效率高于文獻[8]方案和文獻[13]方案。

1 預備知識

1.1 雙線性映射

令G和GT是兩個階為素數(shù)p的乘法循環(huán)群，存在雙線性映射e：G×G→GT滿足以下3個性質(zhì)[16]。

1) 雙線性。對于任意x,y∈G，存在a,b∈Zp，使等式e(xa,yb) =e(x,y)ab成立。

2) 非退化性。存在x,y∈G，滿足e(x,y) ≠ 1。

3) 可計算性。對于任意x,y∈G，存在有效的算法計算e(x,y)。

1.2 線性秘密共享矩陣

令U是一個屬性集，則

1) 選擇秘密值s∈Zp；

2) 共享向量中每個元素對應U中的一個屬性，共享向量中的所有元素都在域Zp中；

3) 對于U中的每個訪問結構，存在一個l×n的矩陣M，稱為共享生成矩陣。

在矩陣Ml×n中，有一個映射函數(shù)ρ，它將第i行映射到U中的屬性Attr，即ρ(i) → Attr，Attr∈U，i= {1,2,… ,l}。再生成秘密值s∈Zp，考慮一個列向量v=(s,r2,… ,rn)T，r2,… ,rn∈Zp。λ=Ml×nv是l個秘密因子的向量，每個秘密因子λi對應屬性ρ(i)。通常稱(Ml×n,ρ)為訪問策略。

線性重構特性：假設方案的訪問結構是線性秘密共享矩陣[17]。設S是一個被授權的屬性集，且I= {i:ρ(i) ∈S}。存在一組常數(shù){ωi∈Zp}i∈I，滿足，使如果{λi}是訪問結構的有效秘密因子，則可以用來計算秘密值s，即。

1.3 基于LSSS的隱藏結構

在隱藏結構中，與矩陣M第i行相關聯(lián)的屬性{ti:vi}由屬性類別ti和屬性值vi組成，定義一個映射函數(shù)π:π(i) →ti，將每一行i映射到相應的類別ti，將{Ml×n,π}以明文形式作為訪問結構，對屬性值vi加密。云服務器根據(jù)用戶的屬性類別匹配到相應的矩陣行數(shù)，判別是否符合訪問策略，從而無法獲知用戶的具體屬性值，保證屬性值的隱藏。

1.4 困難假設

CDH（computational Diffie-Hellman）假設[18]。根據(jù)系統(tǒng)安全參數(shù)選擇一個階為素數(shù)p的乘法循環(huán)群G,g是G的一個生成元，隨機選擇a,b∈Zp，如果不存在一種算法能夠在多項式時間內(nèi)以不可忽略的概率區(qū)分(ga,gb)和gab，則CDH假設成立。

DBDH（decisional bilinear Diffie-Hellman assumption）假設[19]。g是群G的一個生成元，給定兩個元組(g,ga,gb,gc,e(g,g)abc)和(g,ga,gb,gc,e(g,g)z)，隨機選擇a,b,c,z∈Zp，如果不存在一種算法能夠在多項式時間內(nèi)以不可忽略的概率區(qū)分e(g,g)abc和e(g,g)z，則DBDH 假設成立。

DDH（decisional Diffie-Hellman）假設。g是群G的生成元，給定兩個元組(ga,gb,gz)和(ga,gb,gab)，隨機選擇a,b,z∈Zp，如果不存在概率多項式時間的攻擊者以不可忽略的優(yōu)勢區(qū)分gab和gz，則DDH假設成立。

1.5 符號描述

本節(jié)介紹本文中使用的一些符號和變量，符號描述如表1所示。

表1 符號描述Table 1 symbol description

2 本文方案

2.1 系統(tǒng)模型

本系統(tǒng)主要包括4類實體，分別是數(shù)據(jù)擁有者、用戶、云服務提供商（CSP，cloud service provider）、屬性授權中心（AA，attribute authorization）。系統(tǒng)模型及其流程如圖1所示。

圖1 系統(tǒng)模型及其流程 Figure 1 System model and its process

1) 屬性授權中心。屬性授權中心是一個完全可信的實體，負責生成系統(tǒng)的公鑰、主密鑰和公共參數(shù)。此外，負責為用戶的屬性分發(fā)屬性密鑰。

2) 數(shù)據(jù)擁有者。數(shù)據(jù)擁有者對共享文件進行加密，將密文上傳到云服務器，獲取文件存儲地址。然后，用訪問策略對關鍵字加密，生成關鍵字索引，與加密后的文件存儲地址一并上傳到云服務器。

3) 用戶。每一用戶都擁有與其屬性集相關的私鑰。同時，用戶在AA的授權下，生成關鍵字搜索陷門，由云服務器進行搜索匹配。當符合訪問策略、關鍵字匹配時，接收到返回的部分解密密鑰和存儲地址密文，解密得到文件存儲地址，從而進一步訪問云端。云服務器返回加密文件，用戶對其進行解密，獲取所需文件。

4) 云服務提供商。云服務提供商負責存儲加密文件，并將所有匹配的文件密文發(fā)送給用戶。同時負責關鍵字的匹配工作，檢查用戶屬性值與訪問策略是否匹配，關鍵字是否匹配，最后將存儲地址密文與部分解密密鑰返回給用戶。

2.2 算法形式化定義

本文提出的方案包括以下算法。

1) 系統(tǒng)建立。SetUp(1γ) → (PP,MSK)：該算法由屬性授權中心執(zhí)行，輸入安全參數(shù)γ，生成系統(tǒng)公共參數(shù)PP和主密鑰MSK。

2) 密鑰生成。Keygen(PP,MSK,?) → (SK)：該算法由屬性授權中心執(zhí)行，輸入公共參數(shù)PP、主密鑰MSK和用戶屬性集?，為用戶生成私鑰SK。

3) 搜索陷門。Trapdoor(PP,SK,q) →Tw：該算法由用戶執(zhí)行，輸入公共參數(shù)PP、用戶密鑰SK、關鍵字q，輸出陷門Tw。

4) 加密。 Encrypt(PP,A, KW,F) →(CT,Iw,C2)：該算法由數(shù)據(jù)擁有者執(zhí)行，輸入公共參數(shù)PP、訪問結構A、關鍵字集KW、數(shù)據(jù)文件F，生成文件密文CT、關鍵字索引Iw和存儲地址密文C2存儲于云服務器。

5) 搜索。S earch(PP,Iw,Tw) → (Z,C2/⊥)：該算法由云服務器執(zhí)行，輸入公共參數(shù)PP、關鍵字索引Iw和搜索陷門Tw，若用戶滿足訪問策略并關鍵字匹配成功，則返回部分解密密鑰Z和存儲地址密文C2；否則，輸出⊥。

6) 解密。D ecrypt(PP,SK,Z,C2,CT) → (Add,F)：該算法由用戶執(zhí)行，輸入公共參數(shù)PP、用戶的私鑰SK、部分解密密鑰Z、存儲地址密文C2，解出文件存儲地址Add，然后解密文件密文CT，輸出共享數(shù)據(jù)文件F。

2.3 安全模型

在本文方案中，假定授權中心是完全可信的，且在為數(shù)據(jù)用戶生成密鑰前驗證數(shù)據(jù)用戶的身份，而云服務器是“誠實但好奇”的實體，即它會誠實地為用戶提供服務，但也會利用其擁有的信息從密文及陷門中探尋任何私有信息。

本文方案主要考慮關鍵字和陷門不可區(qū)分。通過攻擊者A和挑戰(zhàn)者B之間游戲來定義，保證語義安全和密文的不可區(qū)分。

游戲1關鍵字不可區(qū)分性。

1) SetUp階段。挑戰(zhàn)者B通過調(diào)用SetUp算法獲取公共參數(shù)PP。A自適應地向B發(fā)出不同的詢問。

2) 詢問階段。A向B請求對應屬性集的私鑰，B運行Keygen算法得到相應的私鑰SK并返回給A。

3) 挑戰(zhàn)。執(zhí)行過一定數(shù)量的上述詢問后，A向B發(fā)送兩個大小相同的關鍵字 kw0和 kw1，B隨機選擇b∈ { 0,1}，利用kwb生成加密關鍵字Iwb且返回Iwb給A。

A能夠向B對任意屬性集?進行密鑰詢問，任意關鍵字 kw(kw ≠ kw0*,kw ≠ kw1*)進行密文詢問。

4) 猜測階段。A輸出b'∈{ 0,1}，當且僅當b'=b時A贏得游戲1。

游戲2陷門不可區(qū)分性。

1) SetUp階段。挑戰(zhàn)者B通過調(diào)用SetUp算法獲取公共參數(shù)PP。A自適應地向B發(fā)出不同的詢問。

2) 密鑰詢問階段。A向B發(fā)出注冊請求，B運行Keygen算法得到相應的私鑰SK并返回給A。陷門詢問階段。A對關鍵字q做出詢問，B運行Trapdoor算法得到搜索令牌Tw并返回Tw給A。

3) 挑戰(zhàn)。執(zhí)行過一定數(shù)量的上述詢問后，A向B發(fā)送兩個大小相同的關鍵字q0和q1，B隨機選擇b∈ { 0,1}，利用qb生成加密關鍵字Tqb且返回Tqb給A。A能夠向B對任意關鍵字q(q≠q0,q≠q1)進行陷門詢問。

4) 猜測階段。A輸出b′∈{ 0,1}，當且僅當b'=b時A贏得游戲2。A成功贏得這個游戲的優(yōu)勢為。

2.4 算法設計

步驟1屬性授權中心分發(fā)屬性密鑰。

1) 系統(tǒng)初始化

輸入安全參數(shù)γ，給定雙線性映射e:G×G→GT，g為G的生成元，G和GT是素數(shù)階為p的兩個乘法循環(huán)群。此外，定義兩個哈希函數(shù)H1:{0 ,1}*→G,H2:{0 ,1}*→G。隨機選擇μ,β,a∈Zp，生成系統(tǒng)公共參數(shù)PP和主密鑰MSK，PP由AA公開，MSK由AA秘密保存。PP ={e(g,g)μ,gβ,ga,H1,H2},MSK = {μ,β,a}。

2) 用戶密鑰生成

① 用戶注冊時，屬性授權中心為用戶選擇一個隨機值r∈Zp，生成用戶密鑰k=gμgar,。同時，用戶將其屬性集?以映射{Catex:形式提交給AA，AA根據(jù)屬性集?，對每個屬性選取隨機值t∈Zp，計算用戶屬性密鑰D1,x=gat,D2,x=grH1?({Catex:Valuex})?t。

② 輸出DU密鑰，通過安全信道傳送給用戶。

步驟2數(shù)據(jù)擁有者上傳加密文件。

文件加密：DO對每一個文件Fi∈F，文件所屬id為Iid，為其隨機選擇τi∈Zp，計算加密密鑰，生成密文D=Enc(F,k)。計算iisi，用于用戶解密密文密鑰。

步驟3數(shù)據(jù)擁有者上傳存儲地址密文和關鍵字索引。

關鍵字加密：DO將訪問策略轉換為LSSS訪問矩陣Ml×n，與Mi相關聯(lián)的屬性{ti:vi}li由屬性類別ti和屬性值vi組成，Mi是M的第i行。映射函數(shù)π:π(i) →ti將每一行i映射到相應的類別ti。

因此，將{Ml×n,π}以明文形式作為訪問結構，vi隱藏在密文中，保證屬性值的隱藏。

1) 隨機選擇s∈Zp和一個向量v=(s,r2,…,rn)T∈Zp。

2) 計算λ=Ml×nv。

3) 將文件存儲地址Add加密，C2= Add?e(g,g)μs,C3=gs；

對文件所屬id進行加密，目的是云服務器為匹配文件生成聚合密鑰，Y=g?τiIidi；1,i

用訪問策略的秘密值s對關鍵字kw加密，

DO對關鍵字和存儲地址加密，將{Iw,C2}上傳到CSP。

步驟4用戶上傳搜索陷門。

陷門生成：設關鍵字集為 {q1,q2,q3,…,qn}∈Q,用戶選取隨機值ra∈Zp，保證陷門的不可連接。計算Valuex})?tra，對關鍵字q加密所以，陷門為

并將其存儲于云服務器。

步驟5云服務器搜索

首先根據(jù)用戶提交的搜索陷門，并根據(jù)用戶屬性密鑰檢測是否符合訪問策略，進一步驗證關鍵字是否匹配。

1) 根據(jù)用戶上傳的屬性類別Catex和數(shù)據(jù)擁有者上傳的映射函數(shù)π:π(i) →ti，找到第x個屬性在矩陣Ml×n中對應的第i行。計算Ft，當符合訪 問 策 略 時，存 在 一 組 常 數(shù) {ωi∈Zp}i∈|?|，使

2) 計算

驗證H是否等于Cw=e(gβ,H2(kw)s)，若等式成立，表明搜索成功；若等式不成立，則表明搜索失敗。用戶的屬性集不滿足訪問策略或者搜索時關鍵字不同，都會導致算法終止，返回⊥。

部分解密密鑰

將 {Z,C2}返回給用戶，用來解密存儲地址Add和文件F。

步驟6用戶解密

1) 解密存儲地址

用戶使用私鑰k、ra、Ft對存儲地址密文C2進行解密，保證只有用戶自己才能計算，且需要用到訪問結構中的秘密值s，防止攻擊者跳過訪問策略。用戶計算

2) 解密文件密文

當用戶解出存儲地址Add后，用戶訪問云服務器，云服務器返回存儲地址對應的密文CT ={Di,Y0,i}i∈CT，用戶計算

解密Fi=Dec(Di,ksi)，得到相應文件Fi。云服務器只需返回一個聚合密鑰kagg給用戶，無須為每個文件都返回一個解密密鑰，用戶就可以解密出所有符合搜索條件的文件。

3 安全性分析

3.1 關鍵字安全

定義1 如果DBDH假設成立，所提方案在關鍵字攻擊下和選擇明文攻擊博弈中是安全的。沒有多項式的對手可以用挑戰(zhàn)結構 (M*,ρ*)來破壞所提方案。

通過一個挑戰(zhàn)者B和一個攻擊者A模擬游戲來證明安全性。

1) 初始化：挑戰(zhàn)者B隨機選擇θ∈{0,1},θ=1時，ZZ =e(g,g)c；θ= 0時，ZZ =e(g,g)μ，μ,c∈Zp，生成系統(tǒng)公共參數(shù)和主密鑰，將PP ={ZZ,gβ,ga}發(fā)送給攻擊者。

2) 階段：A根據(jù)自己的屬性集S適應地向B進行詢問用戶私鑰，要求S不滿足 (M*,ρ*)，B首先檢查屬性集S，對每個屬性值計算SK，將SK發(fā)送給A。

3) 挑戰(zhàn)：A提交兩個長度相等的關鍵字 kw0和 kw1。B隨機選擇c∈{ 0,1}，隨機選擇s∈Zp和向 量v=(s,r2,… ,rn)T∈Zp。計 算λi=Miv,若θ=1，=Add ?e(g,g)cs； 若θ= 0，=Add ?e(g,g)μs。?i∈Att，。

4) 猜測。因為A詢問到的屬性集均不滿足訪問策略，故A必須恢復關鍵字信息來判定是kw0還是k w1。A輸出其猜測c′。若c′ =c，A輸出c′ =c的概率為Pr[c′ =c|θ= 1]= 1/2。

因此攻擊者打破DBDH問題的優(yōu)勢是可忽略的。

3.2 陷門安全

定義2如果DDH假設成立，所提方案在選擇明文攻擊博弈中是安全的。

通過一個挑戰(zhàn)者B和一個攻擊者A模擬游戲來證明安全性。

1) 初始化：挑戰(zhàn)者B隨機選擇θ∈{0,1},θ=1時，ZZ =gc；θ= 0時，ZZ =ga，a,c∈Zp。生成系統(tǒng)公共參數(shù)和主密鑰，將PP ={e(g,g)μ,gβ,ZZ}發(fā)送給攻擊者。

2) 密鑰詢問階段。B首先檢查屬性集S，對每個屬性值計算SK，將SK發(fā)送給A。若θ= 0, SK = {D1,x=gat,D2,x=gr(H1({Catex:Valuex}))?t,x∈(1,2,… ,|S|),k=gμgar,，陷門詢問階段。A生成搜索陷門

3) 挑戰(zhàn)：A提交兩個長度相等的關鍵字q0和q1。B隨機選擇c∈ { 0,1}，B計算陷門Tw，并返回給A。

4) 猜測。A輸出其猜測c′。若c′ =c，A輸出c′ =c的概率為Pr[c′ =c|θ= 0]=1/2+ε。若c′ ≠c，A 輸 出c′ =c的 概 率 為Pr[c′ =c|θ= 1]= 1/2。

因此，攻擊者打破DDH問題的優(yōu)勢是可忽略的。

3.3 密文存儲安全性

1) DO對文件加密，將密文CT={Di,Y0,i}i∈F上傳到CSP，CSP返回文件對應的存儲地址Add，但CSP無法知曉每個加密文件對應的Iid，無法解密密文。

2) DO對返回的存儲地址加密，并將其與對應的關鍵字索引和文件Iid一并上傳到CSP，當攻擊者或者云服務器由于好奇心學習符合匹配條件的密文時，由于存儲地址加密，CSP擁有Iid也無法匹配到對應的加密文件，CSP無法直接返回密文。因此，用戶端需要解密存儲地址密文，并通過CSP返回的部分解密密鑰，計算加密文件密鑰，才能獲取對應的文件，保證密文存儲的安全性。

3.4 策略隱私

在本文方案中，將DO的屬性值進行隱藏，只公開所對應的屬性類別以及對應的矩陣行號，以防止屬性信息泄露。屬性采用哈希函數(shù)加密，攻擊者無法恢復有價值的屬性信息。

定理1如果CDH假設成立，本文方案在離線字典攻擊下是真正的匿名性。

分析：攻擊者已知gs,ga，但攻擊者無法計算gas，因此攻擊者不能通過e(gas,grra)=發(fā)動離線字典攻擊。

4 性能分析和實驗仿真

4.1 功能特性比較

將本文方案與文獻[8,11-13]方案進行對比，如表2所示。文獻[11-13]都是基于關鍵字的可搜索加密，但不支持任何表達式的訪問策略。與文獻[8]相比，本文方案對不同文件分配不同加密密鑰，采用聚合密鑰方式對密文解密。

表2 功能對比Table 2 Functional Comparison

4.2 理論分析

將本文方案與現(xiàn)有方案在系統(tǒng)初始化、密鑰生成、索引生成、陷門生成4個方面進行計算量對比，結果如表3所示。分別表示G、GT、ZP元素的長度，分別用|S|、|X|、 |N|表示用戶的屬性集、數(shù)據(jù)擁有者的屬性集和系統(tǒng)總屬性集。L表示陷門中搜索關鍵字的數(shù)量，W表示關鍵字密文中關鍵字的數(shù)量。由表3可知，本文方案與文獻[12]方案計算開銷代價基本相同，優(yōu)于文獻[11]方案和文獻[8]方案；但在系統(tǒng)初始化方面，計算量略高于文獻[13]方案。

表3 計算量對比Table 3 Comparison of the calculated quantities

4.3 實驗分析

本文實驗是基于Linux系統(tǒng)，在8 GB的內(nèi)存，4核處理器下運行。采用Python語言，利用pbc等密碼學工具庫進行編程，實驗使用的雙線性對包是基于512 bit橢圓曲線群，G和GT中元素的大小是128 byte。實驗對比了3個方案的兩個主要算法（密鑰生成、關鍵字加密）的計算開銷，結果如圖2所示。此外，固定屬性個數(shù)為20個，通過改變關鍵字個數(shù)，對比索引生成階段和搜索階段的計算開銷，結果如圖3所示。本文方案效率高于文獻[13]方案和文獻[8]方案。在文件加密方面，與不采用聚合密鑰方式加解密文件相比，本文方案效率較高，結果如圖4所示。

圖2 密鑰生成階段和關鍵字加密階段計算開銷 Figure 2 The key generation phase and the keyword encryption phase calculation overhead

圖3 索引生成階段和搜索階段計算開銷 Figure 3 Index generation phase and search phase calculation overhead

圖4 無聚合密鑰與本文方案(聚合密鑰)計算開銷 Figure 4 No aggregate key and the present scheme (aggregate key) calculation overhead

5 結束語

本文提出了云環(huán)境下基于屬性策略隱藏的可搜索加密方案。本文方案采用搜索、訪問控制與文件加密三者相結合的思想，利用LSSS技術實現(xiàn)訪問控制，并將策略進行隱藏，保護了用戶和數(shù)據(jù)擁有者的隱私。云服務器將聚合密鑰發(fā)送給用戶，數(shù)據(jù)擁有者無須與用戶交互，用戶端減輕了密鑰管理的負擔，同時，給出了安全性證明和性能分析。實驗結果表明，本文方案有效地提高了密文檢索效率。