在线/离线密文策略属性基可搜索加密

陈冬冬 曹珍富 董晓蕾

(上海市高可信计算重点实验室(华东师范大学计算机科学与软件工程学院) 上海 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).