支持复杂访问策略的属性基加密方案*

许城洲,李 陆,张文涛

(1.中国航天系统科学与工程研究院,北京 100037;2.中国航天科技集团有限公司,北京 100048)

1 引言

云存储作为一种将存储资源放在云上供人存取的新型存储方案,以其较低的成本、更好的备份和便捷的访问等优势受到了许多用户的青睐。然而云服务器并不是完全可靠的,云服务商也爆出了许多安全事故,导致用户担忧云服务的安全性[1]。为了实现数据在云环境中的安全存储,用户可以将数据加密后上传至云端服务器。云存储中有许多云服务器,他们通常分别发布和处理不同的信息,为用户提供服务。传统的公钥加密和身份基加密IBE(Identity-Based Encryption)[2,3]无法满足云存储模式下的访问控制需求,属性基加密ABE(Attribute-Based Encryption)[4-6]特别是密文策略属性基加密CP-ABE(Ciphertext-Policy ABE)[7],可以让用户为数据设置独特的访问策略,并实现“一对多”的访问模式和细粒度的访问控制,让用户更安全高效地享受新型网络服务[8]。

访问结构是ABE体制中的重要组成部分,会直接影响ABE方案的表达能力。本文中“复杂访问策略”是指访问策略中包含“与门”“或门”,也可能包含“非门”,且同一个属性可以在访问策略中以任何状态(“需要”“不需要”“无所谓”)重复出现。Annane等[9]基于与门访问结构,构造属性基加密方案,该方案需要所有属性参与,无法防止无关属性干扰,且无法支持复杂访问策略。Zhang等[10]基于树形访问结构构造属性基加密方案,加强了对访问策略的支持。Cheung等[11]提出基于与门的CP-ABE方案,为每个属性设置“需要”“不需要”和“无所谓”3种状态的特征值,避免了系统中无关属性的干扰。Waters[12]提出了基于线性秘密分享方案LSSS(Linear Secret Sharing Scheme)访问结构的CP-ABE方案。Balu等[13]提出了基于分布矩阵的CP-ABE方案。这些方案可以成功表示一些访问策略,但是每个属性只能在访问结构中出现一次。Li等[14]基于有序二元决策图OBDD(Ordered Binary Decision Diagram)访问结构提出新型CP-ABE方案,充分利用了OBDD的高效性和高表达性,可以高效地表达带有“与门”“或门”和“非门”的任意布尔函数的复杂访问策略,但是OBDD访问结构中有效路径包含所有属性,无关属性干扰会导致访问结构中冗余有效路径较多。

属性基加密广泛使用的双线性配对运算计算开销较大,限制了属性基密码体制的应用。实验结果表明,双线性配对运算的计算开销大约是椭圆曲线标量乘法的2～3倍[15],是群元素幂运算的3～5倍[16]。Odelu等[17]首次指出双线性配对运算计算开销过大,并基于椭圆曲线密码、多项式函数和布尔运算实现属性基加密方案,其加密和解密时间复杂度为O(n)。随后,他们基于RSA属性认证和布尔运算提出新的CP-ABE方案[16],其加密和解密时间复杂度降为O(1)。然而这2个方案均只支持与门访问策略。丁晟等[18]基于OBDD访问结构和椭圆曲线密码构造无双线性配对的CP-ABE方案,支持包含“与”“或”“非”组合的访问策略,但是仍然受OBDD性能的影响。研究人员尝试将部分计算外包给云服务器,从而降低本地的计算开销。Green等[19]提出了支持解密运算外包的ABE方案。Li等[20]提出支持密钥生成和解密运算外包的ABE方案,还增加了对返回结果的正确性验证。赵志远等[21]提出了一种可验证的完全外包CP-ABE方案,将密钥生成、加密和解密计算都外包给云服务器,降低了用户本地计算开销。Wang等[22]将计算任务外包给半可信第三方,降低本地计算开销且本地计算开销是固定的。Das等[23]使用椭圆曲线构建属性基加密方案,并将方案中的计算部分外包给服务器,进一步降低了本地计算开销。

本文基于简化有序二元决策图ROBDD(Reduced Ordered Binary Decision Diagram)访问结构,构建支持复杂访问策略的CP-ABE方案。该方案充分利用了ROBDD访问结构的高效性和高表达性。相较于OBDD访问结构,ROBDD不受系统中无关属性干扰,节点和有效路径更少,降低了加密计算开销和密文存储开销。该方案使用群元素幂运算和布尔运算替代双线性配对运算,降低了运算开销。该方案通过布尔函数组合访问结构中有效路径特征值,当用户获得任一有效路径,通过布尔函数运算可得密文解密参数,从而对密文解密,密文不用额外存储有效路径特征值,降低了密文的存储开销。

2 相关知识

2.1 简化有序二元决策图

有序二元决策图OBDD是一个有根节点、非叶子节点和叶子节点的有向非循环图,可以高效表达带有“与门”“或门”和“非门”的布尔函数。如果OBDD中节点的2个分支均指向同一子节点,则去除该节点,将该节点的父节点直接指向其子节点,同时,合并结构中2个分支子节点分别相同的节点。经过以上简化后的决策图称为ROBDD。ROBDD有OBDD同等的表达能力,且ROBDD中节点数量和有效路径数量更少,可以降低相应的计算开销和存储开销。

Figure 1 Boolean functions expressed with OBDD

Figure 2 Boolean functions expressed with ROBDD

将ROBDD中的节点依次编号,最终生成的访问结构为:ROBDD={Nodeid|id∈ID}。其中,ID是节点编号的集合;Nodeid是一个元组(id,pi,high,low),id是当前节点的编号,pi是标记该节点属性的属性特征值,high是当前节点的高分支子节点,low是当前节点的低分支子节点。

2.2 安全模型

本节给出所提CP-ABE方案的安全模型。该安全模型定义为攻击者和挑战者之间的交互性游戏,是选择明文攻击CPA(Chosen Plaintext Attack)下的不可区分性IND(INDistinguishability)游戏。通过安全模型,证明本文CP-ABE方案是IND-CPA安全的。具体描述如下:

(1)初始化:攻击者输出一个挑战访问结构T并发送给挑战者。

(2)系统建立:挑战者运行设置算法,为每个属性生成属性公私钥对,生成系统参数(MSK,MPK)并将MPK发送给攻击者。

(3)查询阶段1:攻击者向挑战者查询属性Pi的属性私钥,唯一的限制条件是攻击者查询的属性集不能满足访问结构T。

(4)挑战:攻击者选择2个等长的数据(M0,M1)并发送给挑战者,挑战者抛掷一枚硬币c∈{0,1},根据访问结构T对数据Mc进行加密得到密文CT并发送给攻击者。

(5)查询阶段2:攻击者可以继续向挑战者询问属性Pi的属性私钥,限制条件依然是攻击者查询的属性构成的属性集不能满足访问结构T。

(6)猜测:攻击者输出对c的猜测结果c′,如果c=c′则攻击者赢得该游戏。

攻击者在该游戏中的优势定义为:ε=Pr[c=c′]-1/2。

定理1如果在任何多项式时间内,攻击者的优势可以被忽略,则该CP-ABE方案被认为是IND-CPA安全的。

2.3 困难假设

设G是阶为素数r的循环群,g是循环群G的生成元,Zr是模r的简化剩余系,a和b是Zr中的随机元素,R是G中的一个随机元素。DDH(Decisional Diffie-Hellman)假设定义如下:给定元组(g,ga,gb,gab)和(g,ga,gb,R),在任意多项式时间内算法B解决循环群G中的DDH假设的优势如式(1)所示:

ε=|Pr[A(g,ga,gb,Z=gab)=0]-

Pr[A(g,ga,gb,Z=R)=0]|

(1)

定理2若对于任何多项式时间算法解决DDH困难问题的优势ε是可以忽略的,DDH假设成立。

3 支持复杂访问策略的属性基加密方案描述

3.1 系统模型

系统模型由5个部分构成,如图3所示。

Figure 3 System model

(1)属性授权机构AA(Attribute Authority):系统管理员角色,负责初始化系统,为系统选择加解密方式,生成系统公共参数和私有参数,为系统中用户生成用户私钥,将用户公钥发送给解密服务器DSP(Decryption Service Provider),为数据拥有者提供系统公钥。AA是完全可信的。

(2)云端服务器CSS(Cloud Storage Server):存储数据拥有者DO(Data Owner)上传的加密数据,并向用户提供下载服务。CSS是半可信的。

(3)解密服务器:在数据使用者DU(Data User)对密文进行解密时分摊计算量较大的属性集认证部分,并返回用户半解密密文。

(4)数据拥有者:为数据设置访问策略,生成相应的访问结构,并对数据进行加密,将加密后的密文上传至CSS。

(5)数据使用者:从CSS下载密文,向DSP提交处理过的属性集私钥,得到半解密密文,当DU的属性集满足访问策略时,可对数据进行后续解密,否则解密失败。

3.2 方案框架

完整的属性基加密方案通常由5个部分组成:系统建立、密钥生成、加密、属性集认证和解密。各个部分定义如下:

(1)系统建立:AA根据系统属性集生成系统参数MSK和MPK。

(2)密钥生成:AA为用户分配属性集Uid,生成用户唯一身份标识uid和用户密钥,将参数发送给用户。

(3)加密:数据拥有者DO设定访问策略ST并生成访问结构,使用加密算法对数据M进行加密,生成密文CT,并将密文上传至CSS。

(4)属性集认证:数据使用者DU将自己部分的密钥和密文上传至DSP,DSP进行属性认证并将属性认证结果返回给DU。

(5)解密:若DSP返回的认证结果表明DU的属性集满足访问策略,DU可以对DSP返回的计算结果进行下一步解密计算并恢复数据M,否则解密失败。

3.3 方案定义

本节将给出本文方案各个部分的具体构造,其中相关参数在表1中说明。

Table 1 Parameters explanation

本文方案各部分具体定义如下:

(1)系统建立。

属性授权机构AA选择2个不相等的大素数p,q,计算N=pq,系统属性全集为={P1,P2,…,Pn},用户的属性集为Uid,为系统中每个属性Pi随机选择满足gcd(pi,φ(N))=1的素数pi,计算满足piqi≡1(modφ(N))的值qi。选择满足2

(2)密钥生成。

AA为每个用户分配唯一身份标识uid,随机选择满足gcd(auid,φ(N))=1的素数auid,计算满足auidbuid≡1(modφ(N))的值buid,根据用户的属性集Uid计算用户密钥(buid,{auidqimodφ(N)|Pi∈Uid})。

(3)加密。

数据拥有者DO设置访问策略ST,根据ST生成ROBDD访问结构,选择随机值s,计算gsmodN,ROBDD决策节点结构为(id,gspi+smodN,high,low),gspi+s为节点对应属性Pi标记值。ROBDD中的有效路径为{PTi,i∈[1,BN]},BN为有效路径数量。计算式(2):

(2)

生成加密密文CT=(gs,Cm,Dm,Sm,ROBDD),DO将密文上传至CSS。

(4)属性集认证。

DU将{auidqi|Pi∈Uid}上传至DSP,DSP通过以下递归过程进行属性集认证:

步骤1将ROBDD的根节点作为当前节点,提取当前节点值gspi+s。

步骤2计算:

(gspi+s)auidqimodN=gsauid+sauidqimodN

(3)

如果Pi∈Uid,转到步骤3;否则,转到步骤4。

步骤3搜索当前节点的high分支节点。

①如果high分支节点是终端节点0,过程结束,并返回属性集认证失败。

②如果high分支节点是终端节点1,DU属性集对应有效路径为PT,计算式(4):

(4)

其中,k为路径PT中节点数量,过程结束,并返回属性集认证成功和(QT,k)。

③如果high分支节点为非终端节点,则将该节点定义为当前节点,提取当前节点值gspi+s,转到步骤2。

步骤4搜索当前节点low分支节点:

①如果low分支节点是终端节点0,过程结束,并返回属性集认证失败。

②如果low分支节点是终端节点1,DU属性集对应有效路径为PT,计算式(5):

(5)

其中,k为路径PT中节点数量,过程结束,并返回属性集认证成功和(QT,k)。

③ 如果low分支节点为非终端节点,则将该节点定义为当前节点,提取当前节点值gspi+s,转到步骤2。

(5)解密密文。

DU的属性集认证成功会从CSS处返回(QT,k),DU计算式(6)和式(7):

(6)

M′=Cm&H2(K′i)|Dm&～H2(K′i)

(7)

DU通过计算Sm=H1(gs,M′)验证是否解密成功。如果解密成功,则输出明文M。

4 安全性分析

4.1 抗串谋攻击

串谋攻击是属性基加密方案中需要面临的重要安全挑战。一个完整的属性基加密方案需要具备抗串谋攻击的特性,即数个属性集不满足访问条件的用户无法通过相互交换自身信息来满足访问条件,从而对密文进行解密。

在本文方案中,N是系统公共参数,由大整数因子分解困难问题可得φ(N)不可由N在多项式时间内计算的得到。用户密钥中auid,buid和qi均是在模φ(N)下运算,且auid,qi,φ(N)和{ki}均未知,通过用户密钥构建的n+1阶等式(见式(8))中未知数的数量为2n+2,参数有无限多个解。通过多个用户密钥构建n阶等式(见式(9))中未知数的数量为2n+2,参数也有无限多个解。综上,用户无法在多项式时间内通过自己密钥获得qi的确切值,因此本文方案可以抗串谋攻击。

(8)

(9)

4.2 安全证明

本节证明本文方案在DDH假设下是IND-CPA安全的。

证明若攻击者A可以以一个不可忽略的优势ε>0在多项式时间内破解本文方案,那么存在一个算法B可以在多项式时间内以不可忽略的优势ε/2解决DDH问题。

设G是阶为素数r的循环群,g是群G的生成元,a和b是Zr中随机元素,R是G中的一个随机元素。挑战者B抛掷一枚硬币c∈{0,1},当c=0时,四元组为(g,ga,gb,gab);当c=1时,四元组为(g,ga,gb,R)。

(1)初始化。

A首先设置挑战访问策略,根据访问策略生成ROBDD访问结构T。

(2)系统建立。

B选择2个不相等的大素数p,q,计算N=pq,为系统中每一个属性选择满足gcd(pi,φ(N))=1的不同素数{pi,i∈[1,n]},然后计算满足piqi≡1(modφ(N))的值qi,选择2个单向的抵抗哈希碰撞的哈希函数H1:{0,1}*→{0,1}lN和H2:{0,1}*→{0,1}lM,其中lN为N的长度,lM为M的长度。系统公钥如式(10)所示:

MPK={N,g,gp1,gp2,…,gpn,gaq1,gaq2,…,gaqn}

(10)

系统私钥如式(11)所示:

MPK={φ(N),q1,q2,…,qn}

(11)

B将公钥分发给A。

(3)查询阶段1。

A向B查询属性Ai的属性私钥qi,唯一的限制条件是A查询的属性集不能满足访问结构T。

(4)挑战。

A随机选择2个等长的数据M0和M1,并将它们提交给B。B随机选择数c∈{0,1}后根据访问结构T对数据Mc进行加密。计算式(12)生成加密密文CT=(gb,Cm,Dm,Sm,ROBDD),B将密文返回给A。

(12)

(5)查询阶段2。

重复查询阶段1,限制条件与阶段1的相同。

(6)猜测

A提交一个对c的猜测值c′。如果c=c′,则Z=gab;如果c≠c′,则Z=R。

如果c=c′,则A猜测正确,表明Mc′为真正的密文。在这种情况下,攻击者拥有的优势为ε,可以计算得到Pr[c=c′|Z=gab]=1/2+ε;如果c≠c′,此时Z=R,对于A而言是完全随机的,从而有Pr[c=c′|Z=R]=1/2。

B破解DDH问题的优势如式(13)所示:

Pr[α′=α|α=0]Pr[α=0]+

(13)

若攻击者可以在一个概率多项式时间内以一个不可忽略的优势赢得游戏,则可以以优势ε/2解决DDH问题。因此,攻击者不存在以不可忽略的优势打破本文方案,本文方案是IND-CPA安全的。

□

5 性能分析

本节将本文方案与文献[12,14,15,18]中的方案在功能和性能2个方面进行分析比较。设G,GT是循环群,群G和GT中有双线性映射e:G×G→GT。方案中双线性配对运算、群元素幂运算等计算开销较大,因此忽略其他计算开销较小的运算,如哈希运算、布尔运算等。表1中列举了进行方案性能对比时所用到的符号和说明。

表2从方案的主要功能进行对比分析,从中可知所有方案均支持复杂访问策略。文献[12,14,18]中的方案均不支持解密外包,解密阶段计算均由本地承担。本文方案采用ROBDD访问结构,文献[12,15]中方案采用LSSS访问结构,均不需要系统所有属性参与,可防止无关属性干扰。文献[14,18]中方案采用OBDD访问结构,访问结构中包含系统所有属性,无关属性干扰会导致系统计算和存储开销较大。本文方案通过布尔函数整合解密参数,密文定长且密文存储开销较低,其余方案未整合解密参数,密文长度随访问策略变化而变化,且密文存储开销较高。文献[14,15]均采用双线性配对运算,文献[18]中方案采用轻量级椭圆曲线标量乘法,本文方案采用计算开销更低的群元素幂运算,降低了方案的整体计算开销。本文方案通过设置冗余参数实现解密结果可验证。

Table 2 Function comparison

表3从方案计算代价进行对比分析。加密阶段本文计算开销与有效路径数量相关,由于本文方案访问结构为ROBDD,有效路径比文献[14,18]方案的少,方案加密计算开销更低。文献[12,15]方案使用LSSS访问结构,需要进行矩阵运算和其他参数运算,加密开销较高。密钥生成阶段本文方案仅需要普通的乘法,计算开销可以忽略不计。解密阶段本文方案仅需要轻量级群元素幂运算,计算开销较低且固定。文献[12,14]中方案需要进行双线性配对运算,计算开销较高。本文方案通过布尔函数整合解密参数,密文长度较小且定长。

Table 3 Comparison of computing overhead

6 仿真实验

本文对表2中部分方案进行了仿真实验,实验运行环境为Intel®CoreTMi5-8259UCPU@3.2GHz,8GB内存,MacOSBigSur11.3操作系统。仿真程序采用Python(版本3.8),基于PyPBC库(版本0.2)、PyEDA库(版本0.28.0)和PyCharm开发环境编写。本文方案对访问结构、运算方式和解密参数等进行优化,支持复杂访问策略并可防止无关属性干扰。因此,仿真实验中访问策略为复杂访问策略,实验过程中访问策略和系统属性集如式(14)所示:

(14)

由图4可知,文献[14,18]方案中访问策略的变化和系统属性集属性数量的增加使访问结构中有效路径数量接近幂次增加,本文方案加密时间线性增加;当访问策略不变时,系统属性集中的属性增加时,文献[14,18]方案的加密时间接近幂次增加,本文方案加密时间不再增加。用户计算有效路径特征值时,涉及的群元素幂运算和标量乘法计算开销较大,对方案加密时间产生了影响。ROBDD可以避免无关属性干扰,降低了访问结构中的有效路径,因此本文方案的加密时间比文献[14,18]方案的加密时间更短。文献[14,18]方案的密文需要存储有效路径特征值,密文大小与访问结构中有效路径数量成正比。由图5可知,文献[14,18]方案的密文大小接近幂次增加,本文方案密文大小不变。本文方案密文中的初始参数数量比文献[14,18]方案中的初始参数多,但是本文方案将解密参数整合使密文长度不受有效路径数量影响,且增加了密文解密验证功能,因此本文方案性能更高。

Figure 4 Comparison of encryption time between schemes from reference[14,18]and this paper’s scheme

Figure 5 Comparison of ciphertext size between schemes from reference[14,18]and this paper’s scheme

文献[12,15]方案中采用LSSS访问结构,不支持访问策略中同一个属性多次出现。基于同等的实验环境,本节将本文方案与文献[12,15]方案进行对比分析。对比分析时,访问策略仅包含“与”“或”门,同一个属性在访问策略中仅出现一次。

图6和图7分别从方案的加密时间和解密时间进行对比分析。由图6可知,本文方案在仅包含“与”“或”门的访问策略时,加密时间整体短于文献[12,15]中方案的,由于本文方案需要计算ROBDD中有效路径特征值和访问结构中节点特征值,文献[12,15]中方案需要生成LSSS矩阵向量特征值和随机因子,因此方案的加密时间随着访问策略中属性数量增加而增长,本文方案与文献[12,15]中方案增长效率接近。由图7可知,由于本文方案将计算开销较大的属性集认证运算外包给解密服务器,用户本地承担的计算开销较低且固定,本文方案的解密时间不随着访问策略中属性数量的增长出现明显的增长;文献[12,15]中方案均采用LSSS访问结构,用户本地需计算满足解LSSS矩阵的参数,并进行相关参数配对运算,本地计算开销较大,且方案解密时间随着访问策略中属性数量增加而明显增加。文献[12]中方案包含较多双线性配对运算,方案解密计算开销较高;文献[15]中方案采用轻量级椭圆曲线标量乘法,方案解密计算开销低于文献[12]的。

Figure 6 Comparison of encryption time between schemes from reference[12,15]and this paper’s scheme

Figure 7 Comparison of decryption time between schemes from reference[12,15]and this paper’s scheme

图8从方案的密文大小进行对比分析。由图8可知,本文方案采用布尔函数参数整合结构整合解密参数,密文存储开销较低且固定;文献[12,15]中方案,均需要存储LSSS矩阵生成的相关参数,密文存储开销较大,且文献[12,15]中方案随着访问策略中属性数量增加,密文存储开销明显增加。

Figure 8 Comparison of ciphertext size between schemes from reference[12,15]and this paper’s scheme

综上,本文方案相对于其他方案有更高的加解密效率和更低的存储开销。

7 结束语

本文基于ROBDD构建一个支持复杂访问策略并能够防止无关属性干扰的属性基加密方案,充分发挥了ROBDD的高效性和高表达性。使用群元素幂运算和布尔运算替代双线性配对运算,降低了方案的计算开销。通过布尔函数整合多个有效路径对应的有效路径特征值,拥有任一有效路径特征值的用户通过布尔函数计算可得到密文解密参数,密文中不用额外存储有效路径特征值,解密时也不需要进行解密参数配对,降低了密文存储开销。本文方案将属性认证外包给解密服务器,降低了本地运算开销。最后在安全模型下证明了本文方案在DDH假设下是IND-CPA安全的。性能分析和仿真分析均表明本文方案更具有优势。