基于KP-ABE算法的云存储可验证安全删除方案

朱怡晓 赵 奎

(四川大学网络空间安全学院 四川 成都 610065)

0 引 言

云计算连接了大规模的存储和计算资源,吸引大量数据外包到云服务器进行存储和共享[1]。在不同文献提出的各种模型中,云服务器被定义为好奇但会诚实执行程序的不完全受信任的实体[2]。由于数据外包存储会造成数据所有者和数据管理权分离,当用户想删除云端数据时,云服务器可能为了潜在利益不按用户要求彻底销毁数据[3],如仅使数据对用户不可见而数据本身仍保留在存储介质中,从而能够回收这些数据进行进一步的挖掘和分析或转卖给第三方,这大大增加了隐私泄露的风险[4]。如何实现数据确定性删除是云存储不可忽视但受关注相对较少的一个问题。

确定性删除旨在使被删除数据不可恢复[5]。从数据管理角度看,云服务器在执行删除时可能仅是移除一些索引或链接,并没有真正清除存储介质上的数据,这就使得数据可能被恢复而导致信息泄露。因此实际应用中,基于密码学的删除方式被广泛采纳,通过使数据密文不可解密达到删除数据的目的[6]。虽然密码学删除能够一次快速删除大量数据,但文件的加密形式让内容共享变得不便[7],基于属性的加密算法能够实现细粒度访问控制和一对多文件共享,近年来在云计算中被广泛应用[8]。Tiplea等[9]提出一种基于双线性映射的单调布尔电路密钥策略属性基加密方案,该方案基于秘密共享和双线性映射,构造了包含与门、或门和扇出门访问结构,实现了细粒度的安全访问控制,并证明了其在标准模型中的选择性安全性。

针对云环境下数据的确定性删除问题,国内外研究者先后提出了多种方案，而大部分方案仅通过返回“成功”或“失败”等结果告知用户删除操作的执行情况, 因此用户无法追踪验证,只能无条件相信该结果[10]。Xue等[11]提出基于属性基加密的可验证安全删除方案,半可信云服务器利用Merkle Hash Tree(MHT)在执行删除后产生一个数据删除证据,数据拥有者也通过构建新的MHT验证该证据的有效性,从而验证数据是否被确定性删除。但该删除方案仅支持较简单的访问策略,其对应于用户私钥的访问结构由简单的与门表示,缺乏对灵活的访问控制策略的支持。

为实现支持灵活访问策略的细粒度访问控制、确定性删除、删除结果可验证,本文在文献[9]和文献[11]的基础上,基于KP-ABE算法提出一种云存储可验证安全删除方案。使用属性集合描述关联加密数据,引入支持与门、或门和(k,n)阈值门的布尔电路构造用户私钥中的访问结构,通过撤销访问数据所必需的属性使数据无法访问从而确定性地删除数据,并利用多分支路径树实现删除的可验证性。

1 背景知识

1.1 基于属性的加密

基于属性的加密(Attribute-based Encryption, ABE)是在非对称密码学和基于身份的加密算法的基础上发展起来的一种非对称加密方案[12],将一系列属性和访问控制策略嵌入密文和用户私钥,只有当属性集合满足相应访问规则时才能成功解密。

根据访问策略部署方式,属性基加密可分为密钥策略属性基加密(KP-ABE)[13]和密文策略属性基加密(CP-ABE)[14]。在KP-ABE算法中,使用属性集合关联标记密文,访问策略被部署于用户私钥,算法由以下四个概率多项式时间算法元组构成。

初始化Setup(s)：输入安全参数s,输出公共参数PP和主密钥MSK。

加密Encryption(R,A,PP)：输入待加密数据R、密文描述属性集A和公共参数PP,输出R对应密文E。

密钥生成KeyGenerate(AS,MSK)：输入访问结构AS和主密钥MSK,输出用户私钥SK。

解密Decryption(E,SK)：输入密文E和用户私钥SK,若E对应的属性集合A满足SK对应的访问结构AS,则解密密文,输出明文信息R。

1.2 双线性映射

G1和G2为两个阶为素数p的乘法循环群,Zp为相应的数域，g为G1的生成元。若映射e：G1×G1→G2是双线性映射,则其具备下列三个特性[15]。

双线性(Bilinear)：对任意x,y∈G1;a,b∈Zp,存在e(xa,yb)=e(x,y)ab；

可计算性(Computable)：对任意x,y∈G1,始终存在有效算法e以计算e(x,y)；

非退化性(Non-Degenerate)：e(g,g)是群G2的生成元,且e(g,g)≠1。

1.3 DBDH假设

决策性双线性Diffie-Hellman假设[16]定义为：给定阶为素数p的乘法循环群G1,随机选择生成元g(G1,对于任意的元素a,b,c,z∈Zp,给定一个五元组(g,ga,gb,gc,e(g,g)abc),不存在算法能够在概率多项式时间内以不可忽略的优势区分e(g,g)abc和e(g,g)z。

1.4 布尔电路

布尔电路由线路和节点组成,其中每个叶节点对应一个属性取值真值(True或False),内部节点由与门、或门和非门3种逻辑门组成,任意节点的输出只能作为一个上层节点的输入[17]。本文将讨论支持与门、或门和阈值门的单调布尔电路。其中(k,n)阈值门表示仅当n个输入中至少有k个输入被计算为真时,其输出才为真。与门和或门可分别表示为(2,2)和(1,2)阈值门。

1.5 Shamir秘密共享算法

Shamir秘密共享算法[18]将秘密S分为n个子秘密,任意k个子秘密都可以恢复出S,而任意少于k个的子秘密无法恢复S。

加密过程中,取随机数a1,a2,…,ak-1,令a0=S,构造多项式f(x)=a0+a1x+…+ak-1xk-1,取n个数x1,x2,…,xn代入多项式得到f(x1),f(x2)…,f(xn)。解密时,任取k个数据(x1,f(x1)),(x2,f(x2)),…,(xk,f(xk)),使用拉格朗日插值多项式计算出唯一的原k-1阶多项式,从而恢复出秘密S。

1.6 多分支路径树

多分支路径树(Large Branching Tree, LBT)是基于哈希值的多叉树,每个节点有多个兄弟节点但仅有一个父节点,其中叶节点值为数据块哈希值,而内部节点值则是其所有子节点值的哈希值[19]。在叶节点数量相等情况下,多分支路径树的深度远小于MHT。

图1展示了9个数据块集合的多分支路径树。每个数据块元素Ei都具有完整性辅助认证集合,由该元素在到达根节点的路径上的所有兄弟节点值组成,如E2的完整性辅助认证集合为{h1,h3,h11,h12}。根据元素Ei及其完整性辅助认证集合能够计算出LBT根值。假设验证方知道原数据的LBT根值R,当需要验证某元素完整性时,从证明方获得对应的辅助认证集合并计算得到树根值R’,检查R’是否等于R即可检查该元素是否被证明方未改变地存储。因此,多分支路径树被广泛应用于完整性验证。

图1 多分支路径树示例

2 基于KP-ABE的可验证删除方案

2.1 方案模型

为实现云存储中数据的细粒度访问控制、确定性删除和可验证,提出基于KP-ABE的可验证安全删除方案。方案涉及以下四种角色。

1) 数据拥有者：文件的创建者。将数据上传至云服务器前,数据拥有者先对数据进行加密,并希望在发出删除指令后数据得到确定性删除,即此前所有授权访问的用户均不能再获取数据相应信息。

2) 用户：云服务器存储数据的访问者。不同用户拥有不同私钥,决定该用户是否被数据拥有者授权访问指定文件。

3) 半可信云服务器：具备强大的存储资源和计算能力的实体。同时,云服务器不完全受信任,可能由于潜在利益对存储的数据进行窥探或不按数据拥有者要求确定性地删除数据。

4) 可信授权方：可信任的用户私钥和重加密密钥的派发中心。

数据拥有者在将数据上传至云服务器前,首先使用对称加密算法AES加密该数据,然后使用一系列属性标记加密AES密钥,再将数据密文和密钥密文一起上传到云服务器。可信授权方根据访问结构为数据拥有者和其他用户派发私钥,满足访问条件的用户可正确解密密钥密文,再通过解密所得AES密钥解密数据密文。当想要删除云服务器上的数据时,数据拥有者向可信授权方发送删除请求,并获得重加密密钥。随后数据拥有者将该重加密密钥转发至云服务器,通知云服务器执行删除操作。完成删除后,云服务器向数据拥有者返回能够用于验证删除被正确执行的证据。

方案模型如图2所示。

图2 方案模型

2.2 具体构造

在方案构建中,为属性集合引入一个关键属性akey,默认情况下密文属性集合和授权用户访问结构中都含有该属性并且取值为真。用户访问结构最终输出门为与门,akey作为该门的一个输入。通过更改关键属性的取值,密文将不再被包括数据拥有者在内所有用户的私钥正确解密,从而达到数据删除的目的。为实现删除可验证,数据拥有者和云服务器可基于密文组件创建多分支路径树并获取根值,重加密密文后云服务器将新的根值作为删除证据发送给数据拥有者进行验证。方案整体流程为初始化、加密、生成密钥、解密、请求删除、生成重加密密钥、执行删除、验证删除结果。

2.2.1初始化

可信授权方选择两个素数阶p的乘法循环群G1和G2,双线性映射e：G1×G1→G2,g为G1的生成元。n为属性个数,随机选择y∈Zp,ti∈Zp,计算Y=e(g,g)y,Ti=gti，其中i∈[1,n]。输出公共参数PP=(e,g,Y, {Ti}),保留主密钥MSK=(y, {ti})。数据拥有者选择随机数r∈Zp,计算v=gr,生成签名公私钥对(sk,pk)。

2.2.2加 密

输入明文R,数据拥有者使用AES算法加密数据,输出加密后的数据密文Rk,其中k为AES密钥。基于公共参数PP,关键属性akey取值为真的密文属性集A以及AES密钥k,数据拥有者选择随机数s∈Zp,计算C1=k·Ys,C2=gs,C3={∀ai∈A,Xi=Tis},输出密文C=(A,C1,C2,C3),将数据密文Rk和密钥密文C上传至云服务器。

加密后,使用哈希函数对C3中元素进行压缩,将获得的有序集{H(Xi)}作为叶子节点构建多分支路径树,数据拥有者保存树根值Root并使用私钥sk对Root进行签名得到sk(Root)。同时,为数据选择唯一名称Dname,记录C3中关键属性对应的密文元素Xk、Xk对应哈希值在叶节点中的索引index，以及Xk在多分支路径树中的完整性辅助认证集合IAAS。为该外包数据生成标签L=(H(Dname‖Xk‖index))r,上传(Dname,index,IAAS,L,sk(Root))至云服务器。

2.2.3生成密钥

输入主密钥MSK和用户访问结构电路Circuit,可信授权方自顶向下进行遍历。由于与门和或门均可表示为阈值门,因此基于Shamir秘密共享算法,以y为根秘密沿布尔电路向下构造其子秘密,生成电路连线wirei和元素集合的映射S,输出相应密钥D给用户：

S=Share(y,Circuit)={〈wirei,elements〉}

式中：elements表示数域Zp中的元素；inputwirei表示第i个属性值节点对应的输入线路；n为电路总输入数。Share(y,Circuit)描述如下。

1) 标记访问结构中所有逻辑门为未访问状态,即令F={unvisited,∀gate∈Circuit}。

2) 将y赋值给映射S中访问结构最终输出线o对应的元素数组,即S(o)={y}。

3) 自顶向下遍历电路。若当前(k,n)阈值门的状态F(gate)==unvisited,那么将其更新为visited。该阈值门连接输出线w和n个输入线w1,w2,…,wn,对i∈{1,2，…,|S(w)|},选择随机数a1,a2,…,ak-1∈Zp,构造秘密共享多项式p(x)=S(w)[i]+a1·x+a2·x2+…+ak-1·xk-1。然后对j∈{1,2,…,n},S(wj).add(p(j))。

2.2.4解 密

用户从云服务器获取数据密文Rk和密钥密文C,基于公共参数PP及用户密钥D,创建叶节点编号与元素数组的映射VA及电路连线wirei与元素数组的映射R。对i∈{1,2,…,n}和j∈{1,2,…,|S(wirei)|},若属性i∈A,执行：

遍历所有叶节点后,执行秘密重建：

R=Reconstruct(Circuit,VA,gs)

Reconstruct(Circuit,VA,gs)过程描述如下：

1) 令F={unvisited, ∀gate∈Circuit}。

2) 对于i∈{1,2,…,n},R(inputwirei)=VA(i)。

3) 自底向上遍历电路。若当前(k,n)阈值门的状态F(gate)==unvisited,那么将其更新为visited。该阈值门连接输出线w和n个输入线w1,w2,…,wn,判定|R(w1)|=|R(w2)|=…=|R(wn)|并定义length=|R(w1)|,对i∈{1,2,…,length},执行下列操作。

(1) 从R(w1)[i],R(w2)[i],…,R(wn)[i]中随机选择k个值Bi1,Bi2,…,Bik,使得∀j∈{1,2,…,k}都有Bij!=null成立,其中i1,i2,…,ik代表值非空的gate编号。如果本次取值为i的循环中没有足够非空值,则用下一个i继续。

(2) 对所有j∈{1,2,…,k},计算：

(3)w为输出线路,计算：

(4)R(w).add(Rw)。

若密文属性集合满足该访问结构,通过重建过程能够得到R(o)[1]=e(g,g)y·s。根据密文和重建结果,可解密AES密钥k=C1/R(o)[1],最终通过k解密数据密文Rk。

2.2.5请求删除

当想要删除云服务器上的数据时,数据拥有者分别向可信授权方和云服务器发送删除请求{Dname,akey},请求可信授权方修改密文属性集中关键属性取值为假。云服务器接收请求后,将文件Dname中对应关键属性akey的相关信息{Xk,IAAS,L,index,sk(Root)}返回给数据拥有者。

通过验证e(g,L)=e(v,H(Dname‖Xk‖index))是否成立,数据拥有者可判定云服务器发送的Xk是否为akey对应的正确密文元素。若成立,则数据拥有者使用Xk和云服务器发送的IAAS计算LBT树根值R1,若sk(Root)=sk(R1),则证明该IAAS是正确有效的。

2.2.6生成重加密密钥

基于删除请求和主密钥MSK,可信授权方找到{ti}中对应于关键属性的值tkey,选择随机数tkey’,计算rk=tkey’/tkey,返回{Dname,akey,rk}给数据拥有者。接收重加密密钥后,数据拥有者将该信息转发给云服务器。

2.2.7执行删除

基于密钥密文C和重加密密钥,云服务器计算Xk’=Xkrk,并替换原始密文中的Xk为Xk’,输出更新后的密文C’=(A’,C1,C2,C3’)。同时,云服务器计算H(Xk’),更新原LBT获取新的树根值Rnew,将其作为删除证据返回给数据拥有者。

2.2.8验证删除结果

为验证云服务器是否诚实执行删除操作,数据拥有者使用rk对Xk进行重加密得到Xnew。接收到云服务器发送的删除证据Rnew后,数据拥有者使用Xnew和此前云服务器发送的IAAS生成树根Rverify。若Rnew=Rverify,则证明云服务器确实删除了该数据。

3 安全性分析

定理1若DBDH假设成立,那么不存在敌手能够在多项式时间内在基于属性的选择性模型下成功对方案进行选择明文攻击。

本文安全模型中考虑两种攻击者：攻击者A1旨在破坏密文的机密性；攻击者A2旨在破坏删除过程中生成的重加密密钥的机密性。通过反证法假设攻击者能以优势ε在CPA游戏中胜出,那么存在模拟者B能以不可忽略的优势ε/2解决DBDH问题实例。

给定模拟者DBDH问题实例如下：选择两个素数p阶乘法循环群G1和G2以及双线性映射e,g为群G1的生成元,随机选择a,b,c,z∈Zp；通过掷硬币结果v决定Zv的值,若v=0则Zv=e(g,g)abc,否则Zv=e(g,g)z。

初始化：攻击者A(A1,A2)选择要挑战的非空属性集合ω并发送给模拟者B。

设置：对于集合U中的属性ai,模拟者B分别选择一个与之对应的随机数ri∈Zp,然后设置ti如下：若ai∈ω,ti=ri, 否则ti=bri。B将公共参数(e,g,Y,{Ti})发送给A,其中Ti=gti,Y=e(ga,gb)=e(g,g)ab。

阶段1：攻击者进行如下询问。

密钥询问：攻击者提交访问结构C给模拟者B以获得相应密钥,B针对两种攻击者分别进行应答：

1) 对A1,默认其选择的属性集合ω不满足访问结构C,B执行FakeShare过程将ga作为根秘密进行共享生成私钥,同时B提供基于秘密gb的密钥。从A1角度看,密钥生成流程与原方案相同,若同时通过一组授权属性和该解密密钥, Reconstruct过程应返回e(g,g)abc。

采用符号Cw(A1)表示A1对访问结构C中电路连线w进行评估时的取值,对A1提交的访问结构C,总是满足Cw(A1)=0。FakeShare(ga,C)过程描述如下。

(1) 令F={unvisited, ∀gate∈C}。

(2) 创建映射S,令S(o)={ga},o为电路C输出线路。

(3) 自顶向下遍历电路。若当前(k,n)阈值门状态F(gate)==unvisited,那么更新为visited。该阈值门连接输出线w和n和输入线w1,w2,…,wn,对i∈{1,2,…,|S(w)|},判断执行：

若Cw(A1)=1,选择随机数a1,a2,…,ak-1∈Zp,构造多项式p(x)=S(w)[i]+a1·x+…+ak-1·xk-1。对j∈{1,2,…,n},执行：

若Cw(A1)=0,选择随机数a1,a2,…,ak-1∈Zp,构造多项式p(x)=gS(w)[i]+a1·x+…+ak-1·xk-1。对j∈{1,2,…,n},执行：

S=FakeShare(ga,C),私钥D={Di},Di取值如下：

2) 对A2,默认它能对任何访问结构C进行私钥询问,包括其选择的属性集合满足的访问结构。通过Share过程对秘密y=ab进行共享,得到S=Share(y,C)及有效密钥D={Di}={gbS(i, j)/ri|j∈[1, |S(i)|]}。

重加密密钥询问：A2发送一个删除请求{Dname,akey},B随机选择rkey’,生成重加密密钥rk=rkey’/rkey,然后将{Dname,akey,rk}返回给A2。

删除执行询问：A2将信息{Dname,akey,rk}提交给模拟者B,B替换原始密文中关键属性对应的密文组件,输出重加密后的密文CT’。

挑战：攻击者A(A1,A2)选择两条长度相等的明文m0和m1并发送给模拟者B,B随机选择u({0, 1}和Zv({Z0,Z1}以使用Zv来加密mu。

对A1,返回密文CT=(ω,mu·Zv,gs, {Xi=Tic=gcri}i∈ω)。

对A2,B先执行重加密操作撤销关键属性akey,为其随机选择ti’,令tkey=ti’,返回密文CT=(ω’,mu·Zv,gs,{Xi=Tic=gcri}i∈ω’)。

阶段2：攻击者A(A1,A2)进行同阶段1的额外询问,B返回相应结果。

猜测：A输出猜测结果u’,若u’=u,B输出v’=0；否则B输出v’=1。已知A在CPA游戏中胜出的优势为ε,B的优势计算如下：

式中：P(v=0)=P(v=1)=1/2。当v=0时Zv=e(g,g)abc,CT是与属性集合ω相关的有效密文,因此有：

当v=1时Zv=e(g,g)z,C1是来自G2的一个随机元素,即密文CT与攻击者选择的属性集合ω无关,故有：

综上可得B在DBDH游戏中的优势为ε/2,故方案是选择明文安全的。

4 性能分析

为验证方案有效性并评估其性能,在Windows 7系统64位计算机上进行相关实验,具体配置为Intel(R) Core(TM) i7-7700 @3.60 GHz处理器,8 GB RAM。方案基于Java语言并通过调用Java Pairing Based Cryptography(jPBC)库进行实现,下面从加密解密、生成用户私钥及删除验证阶段评估方案效率,实验结果均取10次实验的平均值。

选择1 MB大小的文件,首先增加密文属性集合中属性个数以观察在各个阶段的时间开销。固定用户访问结构布尔电路中逻辑门个数,使密文描述属性集合元素个数从3开始递增至15。

图3给出了用户加解密时间开销。可以发现加密时间随属性个数增加大致呈线性增加趋势,同时由于解密阶段也与密文属性集合大小相关,因此解密时间也随属性个数增加增大。本文方案在文献[13]的基础上提高了访问结构的灵活性,当属性个数为15时,加密和解密时间开销分别为138 ms和88 ms,低于方案文献[13],且对于用户是可接受的。

图3 加密及解密时间开销

图4给出了生成用户私钥和删除验证的时间开销。由于用户私钥所关联的访问结构与属性个数相关,因此随着属性个数增多,生成用户私钥的时间开销增大,当属性个数增至15时,该阶段时间开销为137 ms。在删除验证阶段,数据拥有者需要执行双线性对运算,进行重加密和LBT的重构,并对比云服务器作为删除证据发送的LBT树根值和验证阶段产生的树根值。如图4所示,删除验证过程中数据拥有者的时间开销约为44 ms,且与密文属性集合元素个数无关。

图4 生成用户私钥及删除验证时间开销

图5显示了固定密文属性集合中属性个数为15,递增用户访问结构中逻辑门个数从1至14时生成用户私钥的时间开销变化。由于用户访问结构中的与门和或门均可用(k,n)阈值门进行表示,且一个阈值门与其等价的若干阈值门在生成插值多项式时的计算量相当,因此在生成用户私钥阶段,与访问结构中逻辑门个数无关,可信授权方的时间开销约为139 ms。

图5 访问结构逻辑门数-生成用户私钥时间开销

为分析构建LBT的时间开销,固定密文属性个数为15,给出树的构建时间与其出度的关系如图6所示。出度为2时,表示结构为二叉树,对应于文献[13]中使用的MHT。本文方案中树的出度大于2,可以看到LBT的构建时间比MHT的构建时间大大减少,同时随着出度的增加逐渐减小,能够减轻数据拥有者和云服务器的计算负担。

图6 多分支路径树构建时间开销

5 结 语

本文针对云存储中数据确定性删除问题,提出一种新的可验证安全删除方案。基于KP-ABE算法,通过撤销访问密文必需的关键属性和构建多分支路径树实现外包数据的安全删除和删除结果可验证,同时引入含(k,n)阈值门的单调布尔电路支持灵活的访问控制策略。安全性分析证明在基于属性的选择性模型下,该方案能够抵御选择明文攻击。进一步实验结果表明该方案能以可接受的时间开销实现加解密及删除验证,证明了其有效性和实用性。未来可针对数据多副本关联删除、批量数据可验证性删除方面展开进一步研究。