在線/離線密文策略屬性基可搜索加密

陳冬冬 曹珍富 董曉蕾

(上海市高可信計算重點實驗室(華東師范大學計算機科學與軟件工程學院) 上海 200062) (51141500002@ecnu.cn)

?

在線/離線密文策略屬性基可搜索加密

陳冬冬 曹珍富 董曉蕾

(上海市高可信計算重點實驗室(華東師范大學計算機科學與軟件工程學院) 上海 200062) (51141500002@ecnu.cn)

在云計算環境中，越來越多的手機用戶通過移動網路來共享自己的數據文件.但是由于云不是完全可信的，所以會出現一些安全隱私上的問題，針對這些問題，隨之提出了各種基于屬性基加密的解決方案.然而，其中大部分的工作要么是在加解密階段存在大量的在線計算成本，要么是不支持加密數據的關鍵字搜索功能.而且大多的屬性基加密機制會對數據共享、信息查詢、數據細粒度管理等方面的效率性產生影響.為了解決這些問題帶來的挑戰，提出了一種新的密碼學原語：在線離線密文策略屬性基可搜索加密方案(onlineoffline ciphertext-policy attribute-based searchable encryption scheme, OO-CP-ABSE).通過利用現有的在線離線屬性加密技術和屬性基加密的外包解密技術，構造出高效的OO-CP-ABSE方案，使得數據擁有者端的在線計算代價最小化，同時使得數據用戶端的解密計算代價最低；還給出了在云計算環境下，OO-CP-ABSE方案在移動設備上的應用；最后，給出了OO-CP-ABSE方案的安全性分析(數據機密性、關鍵字隱私安全、搜索可控性、陷門安全性)以及同現有其他方案的效率比較.

云計算；安全和隱私；在線離線密文策略屬性基加密；關鍵字搜索；移動設備

目前，云計算已經廣泛應用到了學術領域和工業領域，由于云計算強大的存儲能力和計算資源，促使越來越多的私人和企業將一些數據和一些服務外包給云服務器.同時，隨著移動網絡的發展，在云計算環境中，通過移動設備來進行數據的分享和查詢也變得越來越普遍.雖然將數據存儲在云端，方便用戶管理和操作，但是同時也會帶來一些安全上的隱患，比如說數據的隱私安全和訪問控制.因為云不是完全可信的，一個惡意的云服務器可能會將一些有價值的信息泄露給第三方或者攻擊者，從而從中獲得一些利益或者超越自己權限的權利等.而如今，數據的隱私保護在很多應用場景中變得越來越重要，比如在線電子現金支付、支付寶轉賬、電子醫療系統等.因此，數據的安全性和隱私保護性在云環境中越來越受到人們的關注.

為了保護數據的安全和隱私性，一種最普遍的方式就是先將數據進行加密，然后再將加密過的數據上傳到云服務器上.然而，這樣將會給數據的管理帶來一些問題，比如加密數據的分享和查詢將會受到很大的限制.為了在加密數據上也可以做到安全且有效的細粒度訪問控制，Sahai和Waters第1次提出了屬性基加密(attribute based encryption, ABE)機制[1]，數據擁有者利用訪問控制策略對數據進行加密從而達到對數據訪問控制的目的，只有當數據用戶的屬性滿足訪問策略時才能夠對數據進行解密.之后，屬性基加密(ABE)發展為2種形式：密鑰策略的屬性基加密(key-policy attribute based encryption, KP-ABE)[2]和密文策略的屬性基加密(ciphertext-policy attribute based encryption, CP-ABE)[3].CP-ABE是使用訪問控制策略對密文進行加密，而其私鑰與數據用戶的屬性集相關.只有當用戶私鑰中的屬性滿足嵌入在密文中的訪問策略時，用戶才能夠解密；而在KP-ABE系統中，與之相反，密鑰與訪問策略相關，用屬性對數據進行加密，當密文中的屬性滿足密鑰中的訪問控制策略時才能夠對數據進行解密.因此，CP-ABE經常用于具有訪問控制功能的應用中，而KP-ABE則常用于帶有查詢功能的應用場景中.

由于對存儲在云服務器上的數據進行了加密，所以會給數據的搜索和查詢帶來巨大的挑戰.傳統的關鍵字搜索都是在明文上進行操作的，而在密文上進行搜索將不再適用.Boneh等人提出了公鑰加密的關鍵字搜索方案[4]，實現了對密文數據的關鍵字搜索功能，但是該方案并不支持數據的細粒度訪問控制.隨后，一些屬性基加密的關鍵字可搜索方案不斷被提出，比如文獻[5-8]等.在文獻[5]中，提出了一種同時基于KP-ABE和CP-ABE的關鍵字可搜索方案，數據用戶可以通過KP-ABE機制，自己定義關鍵字搜索策略，搜索感興趣的數據文件；在文獻[6]中，提出了基于密文策略屬性基加密的關鍵字可搜索方案；在文獻[7]中，提出了可驗證的屬性基關鍵字搜索方案；在文獻[8]中，作者應用屬性基構造出了適應群組的公鑰加密搜索.然而，由于屬性基加密機制中有大量的配對運算操作(配對運算比其他運算的計算代價要大很多)，而且配對操作隨著屬性個數的增加呈線性增長，屬性基加密和解密的計算代價也會隨著屬性個數或者訪問結構復雜程度的增加而增加.所以，以上方案[5-8]加解密的計算代價很大，方案的效率并不理想，不適合在實際當中應用.針對ABE機制中加解密計算代價大的問題，Green等人[9]和Hohenberger等人[10]提出了密鑰轉換技術和在線離線ABE技術.前者將ABE的解密操作外包給云服務器，云服務器將ABE密文通過密鑰轉換技術轉換成簡單的密文，雖然進行了部分的解密操作，但是并不會泄露有關明文的任何信息.后者提出了一種新的ABE技術，將加密算法分為2個階段：1)離線階段，在不知道相關屬性集合或者訪問控制策略的情況下，將自動完成大量加密計算的預處理工作;2)在線階段，可以快速地完成整個加密過程，因為在準備階段，大量的計算操作已經被完成，在線階段只需要簡單地計算，就可以快速地完成屬性基的加密.通過這種方法，可以將計算量大的操作盡可能多地提前處理，減少在線階段的工作.在文獻[11]的方案中，利用這2種技術實現了在移動設備上的數據分享，還通過重代理加密的方法來處理數據用戶的屬性撤銷問題.本文，我們將結合這2種技術來提出一種新的高效的關鍵字搜索加密方案.

2) 在本文的方案中，大量的計算操作將會在離線階段執行或者外包給云服務器來執行，比如ABE加密過程中大量的預計算將在離線階段完成，關鍵字搜索和密文轉換操作也將外包給云服務器來處理.總之，在加密和解密階段，數據擁有者和數據用戶不需要做任何昂貴的在線計算操作.

3) 我們給出了OO-CP-ABSE方案的安全性分析，分析表明我們的方案具有數據機密性、關鍵字隱私保護性、查詢關鍵字的隱私保護性和搜索的可控性.我們還給出了方案的效率比較，表明我們方案的高效性.

1 系統模型

圖1展現了我們方案的系統模型，在系統模型中，分為4個實體部分：可信機構、云服務器端、數據擁有者、數據用戶.

1) 可信機構(trusted authority, TA).它負責系統參數的初始化和私鑰的生成，根據用戶的屬性集合生成屬性私鑰并返還給用戶.

2) 云服務器端(cloud services provider, CSP).假設云服務器是半可信的，也就是說，它在一般情況下會遵循協議的規則，但是，它也有可能去試圖查找并泄露一些隱私的信息.它具有強大的存儲能力和計算資源.它負責用戶身份的驗證、關鍵字的搜索以及ABE密文的轉換.

3) 數據擁有者(data owner, DO).數據擁有者負責數據的加密以及關鍵字索引的加密.首先用對稱加密密鑰加密數據文件，然后結合ABE將對稱加密密鑰進行封裝,同時建立關鍵字索引集合并進行加密，最后將它同密文數據一起上傳到云端.

4) 數據用戶(data user, DU).數據用戶將自己的屬性集合發送給可信機構，獲取屬性私鑰.利用私鑰生成加密的查詢關鍵字，并發送到云端.當接收到云端返還的密文之后，恢復出對稱加密密鑰并解密數據文件.

Fig. 1 The system architecture of our construction.圖1 系統模型圖

2 預備知識

2.1 雙線性映射

1) 雙線性.對?a,b∈p以及?g1,g2∈，滿足.

2) 非退化性.e(g,g)≠1.

3) 可計算性.對于?u,v∈,e(u,v)可以有效地計算出來.

則稱e是一個有效的從到T的雙線性映射.

2.2 訪問結構

定義2. 訪問結構.假定U是一個屬性全集，訪問結構A是集合U上的一個非空子集合，即A?2U{?}.在A中的集合被稱為授權集合，否則稱作非授權集合.我們認為A是單調的，若對?B,C∈A，有B∈A且B?C，那么C∈A.

2.3 線性秘密分享

定義3. 線性秘密分享.一個秘密分享方案Π在屬性全集U上是線性的，需要滿足2個條件：

有關線性秘密分享(linear secret sharing scheme, LSSS)的詳細介紹，可以參閱文獻[12].

f(Ikey,Ienc)

1) Setup(λ,U)→(PK,MK).該算法為初始化算法，安全參數λ、一個屬性全集U(這里定義為系統授權的所有屬性集合)作為系統的輸入，生成系統的公開參數PK和主密鑰MK.

2) Extract(MK,Ikey)→SK.該算法為私鑰提取算法，輸入主密鑰MK、一個訪問控制結構(分別地，屬性集合)Ikey，生成與屬性相關聯的私鑰.

3) Offline.Encrypt(PK)→IT.該算法為離線加密算法，以系統公開參數PK作為輸入，生成一個中間密文IT.

4) Online.Encrypt(PK,IT,Ienc)→(ke,CT).該算法為在線加密算法，輸入系統公開參數PK、中間密文IT和屬性集合(分別地，訪問結構)Ienc，生成一個會話密鑰ke和一個最終的ABE密文CT.

5) Decrypt(SK,CT)→ke.該算法為解密算法，算法輸入Ikey的私鑰SK、與Ienc相關的密文CT.如果屬性S滿足訪問結構A，算法恢復出來一個會話密鑰ke；否則，算法終止，輸出⊥.

正確性：對一個固定的屬性集合U，并且λ∈，算法KP-ABE的正確性：對所有的S?U,所有的(PK,MK)∈Setup(λ,U)，以及SK∈Extract(MK,A),如果(ke,CT)∈Online.Encrypt(PK,IT,S)(這里的Offline.Encrypt(PK)→IT)成立，并且S滿足A，那么解密算法Decrypt(SK,CT)正確輸出封裝密鑰ke.CP-ABE的正確性定義與KP-ABE相似，除了Extract和Online.Encrypt最后的輸入與KP-ABE相反之外.

2.5 外包解密ABE

定義5. 外包解密ABE[9].這里，S代表一個屬性集合，A表示一個訪問控制結構，Ikey為密鑰提取函數，Ienc為在線加密函數.函數f的定義與OO-ABKEM相同.外包解密ABE算法由5個算法部分構成：

1) Setup(λ,U).該算法輸入系統安全參數和屬性集合，生成系統公開參數PK和一個主密鑰MK.

2) Encrypt(PK,M,Ienc).該算法為加密算法，輸入系統公開參數PK、消息M和訪問控制結構(分別地，屬性集合)Ienc，輸出一個密文CT.

3) KeyGenout(MK,Ikey).該算法為密鑰生成算法，輸入主密鑰MK和一個屬性集合(分別地，訪問結構)，生成一個私鑰SK和一個轉換密鑰TK.

4) Transform(TK,CT).該算法進行密文的轉換，以由Ikey生成的轉換密鑰TK和由Ienc加密生成的密文CT作為輸入.如果S∈A，那么輸出部分解密密文CT′；否則，算法終止，輸出⊥.

5) Decryptout(SK,CT′).該算法為解密算法，算法輸入一個由Ikey生成的私鑰SK和由Ienc加密生成，然后部分解密后得到的密文CT′.如果S∈A，那么輸出消息M；否則，算法終止，輸出⊥.

3 模型定義

3.1 方案模型

本節介紹了方案的框架模型，通過密鑰封裝機制來實現對稱加密和公鑰加密的混合加密，首先，選取一個現有的對稱加密方案對數據文件進行加密，然后再用在線離線屬性基加密對對稱加密密鑰進行加密.OO-CP-ABSE方案利用在線離線屬性基加密和外包解密屬性基加密2種新的密碼學技術，同時實現了加密數據在云端的分享、云端數據的關鍵字查詢，以及對云端數據的訪問控制.應用在線離線屬性基加密技術的目的在于用戶可以在不知道具體的訪問策略或者屬性集合的前提下將屬性基加密中大量的加密工作放在線下提前完成，而用戶在線時，只需要進行簡單的計算就可以完成整個加密過程，從而節省用戶設備的電量消耗；應用外包解密屬性基的目的在于可以將屬性基密文外包給云服務器去處理(部分的解密)，將之轉換成簡單的密文，使得解密過程中大量的配對操作在云端完成，在用戶端只需要簡單的計算就可以完成解密過程.

在本方案中S表示屬性集合，A表示訪問策略.方案由這9個算法部分組成：Setup，KeyGen，KeyGenout，Offline.Encrypt，Online.Encrypt，Encrypt_Index，Trapdoor，Search(Test和Transformout)和Decrypt.我們可以將OO-CP-ABSE方案分為3個框架模型來定義：在線離線ABE加密模型、ABE外包解密模型和關鍵字可搜索加密模型.這3個模塊組成了在線離線密文策略屬性基可搜索加密方案(OO-CP-ABSE).雖然可以分別用不同的ABE加密方案、不同的外包解密方案和不同的關鍵字可搜索方案來構造出一套新的方案，但是OO-CP-ABSE方案的效率最理想，可以做到用戶端計算代價的最小化.下面給出方案的3個框架模型：

該模型由5個算法組成：Setup，KeyGen，Offline.Encrypt，Online.Encrypt，Test.這里給出在線離線屬性基加密的一般算法定義，也是在OO-CP-ABSE方案中應用到的主要算法步驟.該框架模型也可以用不同的ABE方案替代.

① Setup(λ,U)→(PP,MSK).該算法是初始化算法，由TA系統運行，輸入安全參數λ和屬性全集U，生成系統公開參數PP、主密鑰MSK.

② KeyGen(MSK,PP,S)→SK.該算法是私鑰生成算法，由TA來執行，系統公開參數PP、主密鑰MSK、數據用戶的屬性集合S作為輸入，生成屬性私鑰SK.

③ Offline.Encrypt(PP,Ke)→IT.該算法是離線加密算法，由數據擁有者來執行，在這個階段該算法在不知道相關屬性集合或者訪問控制策略的情況下， 將自動完成大量加密計算的預處理工作，以系統公開參數PP、封裝密鑰Ke作為輸入，生成中間密文IT.

④ Online.Encrypt(PP,IT,A)→CT.該算法是在線加密算法，由數據擁有者來執行，在這個階段，算法只需要很少的計算量就可以很快地完成屬性基加密的過程，該算法輸入公開參數PP、中間密文IT、訪問控制結構A，生成最終的屬性基密文CT.

⑤ Test(PP,CTw,Tw)→DT.該算法是Search算法中第1個階段執行的算法，由云服務器執行，輸入公開參數PP、與密文數據相關聯的安全關鍵字索引集合CTw以及由搜索關鍵字加密生成的陷門函數值Tw，生成部分解密數據DT.

2) 屬性基加密的外包解密模型

該模型有2個算法構成：KeyGenout和Transformout.采用屬性基加密的外包解密方案的核心思想，利用轉換密鑰來實現密文的轉化.我們給出主要算法步驟，同時也是嵌入在本方案中的算法.該模型也可以用不同的外包ABE方案與在線離線屬性基加密模型相結合生成新的方案.

① KeyGenout(MSK,PP,S)→SKt.該算法為轉換密鑰生成算法，由TA執行.首先TA運行算法KeyGen生成屬性私鑰SK，輸入公開參數PP、主密鑰MSK、屬性集合S，然后設置轉換密鑰，一般形式為TK=SK，最終生成的私鑰為SKt(包含有屬性集合S和轉換密鑰TK).

② Transformout(CT,TK,DT)→CT′.該算法為密文轉換算法，將ABE屬性密文轉換為一般加密的密文，由云服務器運行.該算法在Search算法中的第2個階段執行，輸入密文CT、轉換密鑰TK以及由Test算法生成的部分解密密文DT，生成轉換密文CT′(由ABE屬性密文轉換生成).

3) 關鍵字可搜索加密模型

該模型有3個算法構成：Encrypt_Index，Trapdoor，Search.這里給出關鍵字加密的一般算法步驟，同時也是應用在本方案中基本算法步驟.該模型也可以用其他關鍵字可搜索方案來實現.

① Encrypt_Index(PP,W)→CTw.該算法是關鍵字索引加密算法，由數據擁有者運行，數據文件的關鍵字索引集合生成之后，運行該加密算法，輸入系統公開參數PP、關鍵字索引集合，生成與加密數據文件相關的加密關鍵字索引CTw.

② Trapdoor(PP,SKt,w)→Tw.該算法是陷門生成算法，由數據用戶運行，輸入系統公開參數PP、私鑰SKt(包含有轉換密鑰TK)以及用戶要查詢的關鍵字w，生成陷門函數值(也稱為標記)Tw.

③ Search(PP,CTw,Tw)→CT′.該算法是關鍵字查詢算法，由云服務器運行，該算法由2個算法組成:Test和Transformout，輸入公開參數PP、與加密數據文件相關的加密關鍵字索引CTw以及包含查詢關鍵字的陷門函數值Tw，由Test算法執行，生成部分解密數據DT，然后作為Transformout算法的輸入再進行屬性密文的轉換，最終生成轉換后的簡單密文CT′.

3.2 安全模型

本文方案的安全模型步驟如下：

開始設置階段：挑戰者運行Setup算法，并給敵手公開參數PK.

詢問階段1：挑戰者初始化一個空表Ttable，一個空集合D和一個計數整數j=0.自適應性過程中，敵手可以重復以下的任何詢問:

① Create(Ikey)：挑戰者設置jj+1，并運行密鑰生成算法獲得SK，然后挑戰者在Ikey上運行外包密鑰生成算法去獲得(SKt,TK),并將它存儲在表Ttable的(j,Ikey,SKt,TK)條目中.挑戰者將轉換密鑰TK返還給敵手(注意：Create可以對相同的輸入進行重復查詢).

② Corrupt(i)：如果表Ttable中存在第i條目，那么挑戰者獲得條目(i,Ikey,SKt,TK),并設置DD∪{Ikey},然后將私鑰SKt返還給敵手；如果不存在，輸出⊥.

③ Decrypt(i,CT)：如果表Ttable中存在第i條目，那么挑戰者獲得條目(i,Ikey,SKt,TK)，并以(SKt,CT)作為解密算法的輸入，將得到的結果返還給敵手.如果不存在，輸出⊥.

詢問階段2：除了以下的限制條件，階段2敵手的詢問與階段1相同.這里限制敵手不能夠：

② 發布對挑戰密文CT*的解密詢問.

猜測階段：敵手給出對b′的猜測b.當且僅當b=b′時，敵手獲勝.

定義6. 方案OO-CP-ABSE是安全的，當且僅當對于上述攻擊游戲，任何概率多項式時間的敵手有可忽略的優勢在上述游戲中獲勝.

4 具體方案

本節介紹了本方案的詳細構造.本文借鑒了Waters等人[9-11]方案中的思想，以Waters等人的在線離線ABE方案與ABE的外包解密方案為基礎，同時借鑒Wang等人[6]方案中的思想，以Boneh等人[4]的公鑰加密關鍵字可搜索方案為基礎，構造出在線離線密文策略屬性基可搜索加密方案(OO-CP-ABSE).

4.1 基本思想

4.2 方案的構造

OO-CP-ABSE方案由9個算法構成:

1) Setup(λ,U)→(PP,MSK).令U為屬性集合空間，e:×→T為雙線性映射，p是循環群和T的階，且與安全系數λ相關.TA隨機選取g,h,u,v,w∈，然后挑選一個隨機值α∈P并計算e(g,g)α，H:{0,1}→p為一個安全的Hash函數，F為常見的消息認證函數.算法輸出系統公開參數和主密鑰：

PP=(,T,p,g,h,u,v,w,e(g,g)α,H,F),

MSK=(α).

2) KeyGen(MSK,PP,S)→SK.數據用戶將自己的屬性集合S={A1,A2,…,Ak}?p發送給TA，TA選取隨機數r,r1,r2,…,rk?P，然后計算,對于?τ∈[1,k]，TA計算:

3) KeyGenout(MSK,PP,S)→SKt.密鑰生成算法先運行KeyGen(MSK,PP,S)得到SK，然后TA選取一個隨機數t∈p，計算D′=wrgtα,D=D，然后計算轉換密鑰TK如下：

算法輸出私鑰SKt=(t,S,D,TK).

4) Offline.Encrypt(PP,Ke)→IT.在這里我們引入文獻[10]中“pooling”的概念，用來建立一個大屬性集的CP-ABE系統，將中間密文分成2類邏輯主體:1)ITmain;2)ITatt.用這種方法來消除離線階段由于不同類型屬性(屬性值長度不一致)造成存儲空間的浪費.在這個階段，數據用戶分別計算出任意個數的ITmain和ITatt.

離線加密算法加密對稱加密密鑰Ke，數據用戶選擇一個隨機數s∈p并計算：

C=Kee(g,g)αs,

C0=gs.生成ITmain=(C,C0).用戶選取隨機數λ′,x,z∈p并計算：

C1=wλ′vz,

C2=(uxh)-z,

C3=gz.

生成ITatt=(λ′,x,z,C1,C2,C3),算法輸出中間密文IT=(ITmain,ITatt).

Cτ,5=-zτ(ρ(τ)-xτ),

最終，算法生成密文:

CT=((M,ρ),C,C0,{Cτ,1,Cτ,2,Cτ,3,

Cτ,4,Cτ,5}τ∈[1,l]).

6) Encrypt_Index(PP,W)→CTw.加密關鍵字索引生成算法輸入系統公開參數和由數據文件生成的關鍵字索引集合W，對每一個關鍵字wi∈W，算法選一個隨機位字符串ti并計算ki=e(g,g)αs×e(g,H(wi)s)，然后將ti和ki作為消息認證函數的輸入，算法輸出加密的關鍵字索引：

CTw={(ti,F(ki,ti))}wi∈W,i={1,2,…,n}.

7) Trapdoor(PP,SKt,w)→Tw.陷門生成算法輸入系統公開參數PP和私鑰SKt(包含轉換密鑰TK)以及用戶要查詢的關鍵字w，計算Qw=H(w)×D，生成查詢關鍵字w的陷門函數值：Tw=(Qw,TK)，其中：

TK=(D0,D1,{Dτ,2,Dτ,3}τ∈[1,k]).

8) Search(PP,CTw,Tw)→CT′.數據用戶將生成的陷門Tw以及自己的屬性集合S發送給云服務器，云服務器運行關鍵字搜索算法.首先，在算法的第1個階段，云服務器執行算法：Test(PP,CTw,Tw)→DT，該算法輸入系統公開參數PP、門限值Tw以及加密的關鍵字索引集合CTw.云服務器首先驗證用戶的屬性集合是否滿足密文中的訪問控制策略，如果不滿足，算法終止，返回用戶⊥；如果滿足，找出一個集合I?{1,2,…,l}，使得I={i:ρ(i)∈S}，假設{λi}是秘密s分享之后的結果，那么一定存在一個可計算的常數向量{ωi∈p}i∈I，使得ωiλi=s成立，云端服務器計算：

e(Ci,2uCi,5,Dτ,2)e(Ci,3,Dτ,3))ωi=e(g,w)rst

和

kw=e(C0,Qw)DT=e(g,g)αse(g,H(w)s)，

其中，τ是屬性集合S中屬性值ρ(i)的下標(它取決于i).然后，云服務器計算F(kw,ti)并且與在云端存儲的加密關鍵字索引CTw(F(ki,ti)，i∈[1,n])進行比較，如果匹配成功，云服務器將利用計算出的結果進一步執行算法第2階段：Transformout(CT,TK,DT)→CT′.算法輸入密文CT，轉換密鑰TK，以及第一階段的部分解密數據DT，云服務器計算：e(C0,D0)DT=e(g,g)αst.最終，算法輸出轉換密文:CT′=(C,e(g,g)αst)(C是密文CT中的一部分，即加密的對稱加密密鑰，我們可以將CT′看作ElGamal密文).最后，云服務器將CT′和搜索到的密文數據一同發送給數據查詢用戶.

9) Decrypt(SKt,CT′)→Ke.解密算法由數據用戶執行，以用戶的私鑰SKt=(t,S,D,TK)和轉換密文CT′作為輸入，數據用戶計算：T0，得到封裝密鑰Ke，其中T0=C,T1=e(g,g)αst.最終，數據用戶用對稱加密密鑰Ke對密文數據文件進行解密得到明文數據.

搜索算法中部分數據的解密和關鍵字匹配計算：

e((uxih)-ziu-zi(ρ(i)-xi),grτ))ωit=

e(g,h)zirτe(g,u)ziAτrτe(g,v)-zir)ωit=

kw=e(C0,Qw)DT=

e(gs,H(w)wrtgα)e(g,w)rst=

e(g,g)αse(g,H(w)s)，

密文轉換的計算：

e(C0,D0)DT=e(gs,gαtwrt)e(g,w)rst=

e(g,g)αst.

在云服務器執行關鍵字搜索的過程中，算法Transformout對于每個密文只需要進行一次雙線性配對運算，而對于每個陷門值，Test算法則大致需要3|I|+1次線性配對操作.事實上，這里我們可以使用運算上的技巧來減少Test算法中配對操作的次數：

如此，云服務器執行搜索算法的計算過程中只需要進行4次配對計算即可.

5 應用場景的描述

本節將簡要描述在云計算環境中OO-CP-ABSE方案在移動設備上的應用，分為5個階段來描述：系統初始化階段、離線計算階段、數據上傳階段、數據檢索階段、數據下載階段.

1) 系統初始化階段.在這個階段，①由TA運行初始化算法Setup(λ,U)，得到系統公開參數PP和主密鑰MSK；②將公開參數公布，保留主密鑰；③數據用戶將屬性集合S發送給TA；④TA運行私鑰生成算法生成屬性私鑰SK，然后算法KeyGenout輸入SK，生成私鑰SKt(包含轉換密鑰TK)；⑤TA將私鑰SKt發送給數據用戶，具體流程如圖2所示:

Fig. 2 The high level description of system setup stage.圖2 初始化階段流程圖

2) 離線計算階段.在這個階段，數據擁有者(DO)對數據文件進行對稱加密，然后將對稱密鑰用ABE進行密鑰封裝.當DO的移動設備正在充電時，自動運行Offline.Encrypt算法，屬性基加密的預計算(對稱密鑰的封裝)將會在這個階段完成，DO通過運行算法Online.Encrypt去得到中間密文CT并將它預先存儲在數據擁有者的移動設備上，此時，ABE加密的大量計算工作被自動地完成了，所以可以大大地減少數據用戶端在線階段的計算量，進而為用戶的移動設備節省大量的電量消耗.

3) 數據上傳階段.在這個階段，主要完成ABE的加密后續工作并進行數據的上傳.在離線階段，完成了數據的對稱加密和會話密鑰的加密.當DO的移動設備在線時，運行算法：Online.Encrypt和Encrypt_Index分別完成在線ABE的加密過程以及關鍵字索引的加密過程，然后DO將加密數據文件、ABE密文和加密關鍵字索引集合發送到云端.

4) 數據檢索階段.在這個階段，數據用戶(DU)對他感興趣的數據文件進行搜索，首先DU執行算法Trapdoor去得到包含要搜索關鍵字的門限值，將它發送給云服務器，云服務器執行關鍵字搜索算法Search，搜索算法第1個階段的Test算法，驗證DU的屬性是否滿足ABE密文中的訪問策略，即驗證用戶是否是授權用戶，如果是，進行部分的解密計算，然后進行關鍵字的匹配，匹配成功，將繼續執行第2階段的Transofrmout算法，將匹配到關鍵字所對應的ABE密文進一步轉換，轉換為簡單的密文形式，但是整個過程中的部分解密運算并不會泄露有關明文的任何信息.最后云服務器將搜索到的加密數據文件以及ABE轉換密文CT′一同返還給數據用戶.

5) 數據下載階段.在這個階段，DU接收到云端返回的查詢結果并下載到移動設備端，然后DU運行解密算法去得到封裝密鑰Ke，對加密數據文件進行解密，最終DU得到數據文件的明文.

6 安全性分析

本節將對我們方案的安全性進行分析，方案滿足下述的安全性要求.

6.1 數據機密性

通過以下定理的證明，可以表明我們提出的方案具有數據機密性.

定理1. OO-CP-ABSE方案是安全的，當且僅當對于3.2節中的攻擊游戲，任何多項式時間的敵手有可忽略的優勢在上述游戲中獲勝.

證明. 如果存在多項式時間的敵手以不可忽略的優勢在本方案的攻擊游戲中獲勝，那么就可以構造出一個敵手以不可忽略的優勢在在線離線ABE[10]的攻擊游戲中獲勝.從一般ABE的構造來分析，OO-CP-ABSE方案與文獻[10]方案的不同之處在于本方案中加入了轉換密鑰算法和ABE密文的轉換算法，生成了2個密鑰.第1個是短的El Gamal類型的密鑰t，它是保密的；第2個稱作轉換密鑰TK，它可以與代理(云服務器)分享，也能夠對外公布.對于授權的用戶，云服務器驗證通過之后，利用轉換密鑰將ABE密文轉換成El Gamal密文形式，返還給用戶，用戶可以用私鑰t進行解密.轉換密鑰生成算法，在原有私鑰上加入了一個隨機數1t，本質上是對密鑰的一次盲化，方案的安全性得以加強；而密文轉換算法，其實是將ABE密文通過代理的形式轉換成了El Gamal形式的密文，雖然需要進行部分的解密操作，但是并不會泄露私鑰和明文的任何信息.在本方案的攻擊游戲中，與文獻[10]中OO-ABKEM的不同之處在于：詢問階段1，敵手私鑰的詢問，挑戰者會將轉換密鑰TK一同返還給敵手，因為轉換密鑰本來就是公開的，所以同OO-ABKEM的攻擊游戲相比較，假設的敵手能力并沒有增強，所以并不影響原有方案的安全性，我們可以通過在線離線ABE[10]的安全性，來推出OO-CP-ABSE方案的安全性，本文由于篇幅有限，具體的證明將會在以后的工作中展示出來，讀者也可以查閱文獻[9-10]，先了解在線離線ABE安全性的詳細證明，這里我們將不再給出.

證畢.

6.2 關鍵字隱私保密性

在OO-CP-ABSE方案中，由數據文件生成的關鍵字索引集合，在算法Encrypt_Index中進行加密，生成了安全關鍵字索引.首先是用Hash函數H對關鍵字進行處理；然后用Online.Encrypt算法中的秘密值s以及系統的公開參數PP對關鍵字進行加密，其中用到了一次配對的加密操作，這種構造方法類似于文獻[6]中加密關鍵字的構造，與關鍵字搜索算法密切相關.因此，分析表明，加密后的關鍵字索引，不會泄露任何有關關鍵字和數據文件的明文信息，所以，云端服務器不會從加密的關鍵字索引中得知任何有用的信息，所以方案是具有關鍵字隱私保密性的.

6.3 搜索的可控性

OO-CP-ABSE方案，將關鍵字搜索功能與ABE相結合，從而達到了對關鍵字搜索的權限控制，如果數據用戶進行關鍵字的搜索，首先要通過算法Test來驗證用戶的身份，云服務器執行Test算法，判斷用戶的屬性集合S是否滿足密文的訪問控制策略，如果不滿足則算法終止，否則云服務器才會執行關鍵字的搜索操作.因此，通過分析表明，方案具有搜索的可控性.

6.4 Trapdoor的隱私保密性

方案中的Trapdoor由Qw和TK組成，其中Qw=H(w)×D，算法首先用Hash函數H對關鍵字w進行處理，然后乘上D，將查詢關鍵字進行加密，D是私鑰的一部分，由算法KeyGenout輸出，通過對私鑰進行指數上的加密操作而生成，所以，D和TK都是安全的參數，不會泄露任何有關私鑰的信息.通過分析表明，本方案具有Trapdoor的隱私保密性.

7 性能分析

本節對方案的性能進行分析.首先，從方案算法構造的角度來分析我們方案的效率，然后給出與其他方案的效率對比，表明本方案在性能上的優勢.

在OO-CP-ABSE方案中，加密算法分為2個部分：在線階段和離線階段，大量的預加密工作可以在離線階段提前計算并將計算結果存儲在設備上，利用這個特點，可以使得當用戶的移動設備在充電或者不繁忙時，通過離線階段自動完成，而在線階段，通過簡單的運算就可以完成加密過程.在線離線技術，使得數據擁有者的在線計算代價最小化，從而節省了移動設備大量的電量消耗，而在其他大多數可搜索方案中沒有提出過.

在OO-CP-ABSE方案中，通過將復雜的計算外包給云服務器，使得方案的效率性進一步提高.因為云服務器的計算能力足夠強大，能夠快速地處理復雜的計算操作，我們將關鍵字搜索和ABE密文的轉換操作交給云端處理，并且云端不會知道任何有關明文的信息，因此，進一步減少了數據用戶端的計算代價.

上面分析表明，方案中在線加密和解密以及關鍵字搜索的過程，數據擁有者和數據用戶不需要做任何高代價的計算操作，因此本方案的效率很理想.

雙線性配對運算比其他的運算操作復雜得多.文獻[11]對一般運算的效率進行了實驗，在Samsung Galaxy S3的安卓操作系統上通過Pairing-Based Cryptograph (PBC)對各種運算操作進行效率的測試.實驗表明，運行雙線性配對操作的時間要比其他運算花費的時間長很多.因此，可以看出，配對運算是影響方案效率的主要因素，而且配對運算操作的次數會隨著數據加解密過程中用到屬性個數的增加而呈線性的增加，所以，在方案中減少配對運算的次數就顯得尤為重要，而OO-CP-ABSE方案的配對操作次數要比其他方案少很多.首先我們列出算法涉及到的所有計算符號，然后以表格的形式給出本方案與文獻[6-7]中方案的效率比較.H′表示{0,1}→P，F表示消息認證函數，P表示一個雙線性配對操作，n表示數據用戶屬性的個數，N[7]表示基于樹訪問結構中葉子節點的個數，l表示訪問控制矩陣M的行向量個數，|I|表示解密過程中用到的屬性個數，Δ表示在解密配對操作中特殊屬性的個數，E表示在群上的指數運算，ET表示在群T上的指數運算.表1給出了方案的安全關鍵字索引生成算法、查詢關鍵字生成算法和數據解密算法的漸進復雜度分析以及與其他方案的比較.從表1中可以看出，在OO-CP-ABSE方案中，陷門生成算法的復雜度減少為0；解密算法的復雜度減少為O(1).方案總的在線計算復雜度也比其他方案要小很多，分析表明，我們方案的效率高，數據用戶的在線計算量非常小.

表2給出了在線加密階段OO-CP-ABSE方案的漸進復雜度分析，這里，不考慮Hash函數計算和乘法計算的復雜度.從表2中可以看出，在線加密階段，數據擁有者也不需要做任何代價高的計算操作.

Table1 Comparison with the Schemes in Ref [6-7]

* Total online computation includes：Secure index,Trapdoor, Decryption and Online encryption.

Table 2 Computational Cost of Online Encryption on Data Owner Side

*tSKE.GandtSKE.Erepresent the key generation algorithm and the symmetric encryption algorithm of the symmetric encryption respectively.

總的分析表明，OO-CP-ABSE方案是高效的，在云計算環境中，適合在移動設備上的應用.

8 總 結

[1]Sahai A, Waters B. Fuzzy identity-based encryption[G] //LNCS 3494: Proc of EUROCRYPT’05. Berlin: Springer, 2005: 457-473

[2]Goyal V, Pandey O, Sahai A, et al. Attribute-based encryption for fine-grained access control of encrypted data [C] //Proc of the 13th ACM Conf on Computer and Communications Security. New York: ACM, 2006: 89-98

[3]Bethencourt J, Sahai A, Waters B. Ciphertext-policy attribute-based encryption[C] //Proc of IEEE Symp on Security and Privacy (SP’07). Piscataway, NJ: IEEE, 2007: 321-334

[4]Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword search[G] //LNCS 3027: Proc of EUROCRYPT’04. Berlin: Springer, 2004: 506-522

[5]Li J, Zhang L. Attribute-based keyword search and data access control in cloud[C] //Proc of the 10th IEEE Int Conf on Computational Intelligence and Security. Piscataway, NJ: IEEE, 2014: 382-386

[6]Wang C, Li W, Li Y, et al. A ciphertext-policy attribute-based encryption scheme supporting keyword search function[G] //LNCS 8300: Proc of the 5th Int Symp on Cyberspace Safety and Security. Berlin: Springer, 2013: 377-386

[7]Zheng Q, Xu S, Ateniese G. VABKS: verifiable attribute-based keyword search over outsourced encrypted data[C] //Proc of the 33rd IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 522-530

[8]Li Shuang, Xu Maozhi. Attribute-based public encryption with keywords search[J]. Chinese Journal of Computers, 2014, 37(5): 1017-1024 (in Chinese)(李雙, 徐茂智. 基于屬性的可搜索加密方案[J]. 計算機學報, 2014, 37(5): 1017-1024)

[9]Green M, Hohenberger S, Waters B. Outsourcing the decryption of ABE ciphertexts[C] //Proc of the USENIX Security Symp. Berkeley, CA: USENIX Association, 2011: 3-23

[10]Hohenberger S,Waters B. Online/offline attribute-based encryption [G] //LNCS 8383: Proc of Public-Key Cryptography. Berlin: Springer, 2014: 293-310

[11]Shao J, Lu R, Lin X. Fine-grained data sharing in cloud computing for mobile devices[C] //Proc of the 34th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2015: 2677-2685

[12]Rouselakis Y, Waters B. Practical constructions and new proof methods for large universe attribute-based encryption[C] //Proc of the 2013 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2013: 463-474

Chen Dongdong, born in 1990. Master candidate in School of Computer Science and Software Engineering, East China Normal University. His main research interests include cryptography and information security, in particular, public key encryption, attribute-based encryption.

Cao Zhenfu, born in 1962. Received his PhD degree in Harbin Institute of Technology. Currently distinguished professor and PhD supervisor in School of Computer Science and Software Engineering, East China Normal University. His main research interests include number theory, cryptography, trusted network and information security.

Dong Xiaolei, born in 1971. Received her PhD degree in Harbin Institute of Technology. Currently distinguished professor and PhD supervisor in School of Computer Science and Software Engineering, East China Normal University. Her main research interests include number theory, cryptography and trusted computing (dongxiaolei@sei.ecnu.edu.cn).

Chen Dongdong, Cao Zhenfu, and Dong Xiaolei

(ShanghaiKeyLaboratoryforTrustworthyComputing(SchoolofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity),Shanghai200062)

It is quite common for data owners to share the data via mobile phones in cloud computing. But because the cloud is not fully trusted, a series of privacy concerns emerge from it, and various schemes based on the attribute-based encryption have been proposed to these problems. However, most work either cannot support the keyword search function for the encrypted data, or bring a large of online computational cost in encryption and decryption phase. The efficiency of the data sharing and information query as well as the fined-grained of the data sharing will be affected by the most attribute-based encryption mechanism. To deal with these challenging concerns, we propose a new cryptographic primitive named onlineoffline ciphertext-policy attribute-based searchable encryption scheme (OO-CP-ABSE). By using the onlineoffline attribute-based encryption and the outsourcing decryption technique, we construct our scheme with minimum online computational cost on the data owner side and least decrypted computational cost on the data user side. Furthermore, we give the description of the application of OO-CP-ABSE in cloud computing for mobile devices. At last, we also present the efficiency of our scheme in comparison to other schemes and the security in terms of data confidentiality, keyword privacy, controlled searching, trapdoor privacy.

cloud computing; security and privacy; onlineoffline ciphertext-policy attribute-based encryption; keyword search; mobile device

2016-06-14；

2016-08-10

國家自然科學基金項目(61373154，61371083，61632012，61672239，61602180)；高等學校博士學科點專項科研基金項目(20130073130004)；上海市2016年度“科技創新行動計劃”高新技術領域項目(16511101400)；上海市自然科學基金項目(16ZR1409200)

曹珍富(zfcao@sei.ecnu.edu.cn)

TP309

This work was supported by the National Natural Science Foundation of China (61373154, 61371083, 61632012, 61672239, 61602180), the Specialized Research Fund for the Doctoral Program of Higher Education of China (20130073130004), the Shanghai High-Tech Field Project (16511101400), and the Natural Science Foundation of Shanghai (16ZR1409200).