选择性隐藏树型访问结构的CP-ABE方案

2020-07-17 07:35韩舒艳努尔买买提黑力力
计算机工程 2020年7期
关键词:敌手区分度密文

韩舒艳,努尔买买提·黑力力

(新疆大学 数学与系统科学学院,乌鲁木齐 830046)

0 概述

云存储作为一种网络在线存储模式,在提供数据存储便利的同时,其引发的数据安全问题也给数据所有者带来困扰。由于云存储数据存放在由第三方托管的多台虚拟服务器上,虚拟服务器可能向以进行商业欺骗和敲诈等活动谋取利益的未授权用户提供数据,因此数据所有者通常将数据加密后存储在云上,只有授权用户才能访问。Fuzzy-IBE[1]、KP-ABE[2]和密文策略属性基加密(Ciphertext Policy Attribute Based Encryption,CP-ABE)[3]是数据加密的常用方案。在CP-ABE方案中,由于数据所有者拥有访问控制主动权,能较好地解决云上安全存储问题,因此该方案适用于云服务器。

当前在多数CP-ABE方案[4-6]中,访问结构以明文形式嵌入到密文中,由于其可能含有敏感信息,因此需要被隐藏。文献[7]提出两种隐藏访问结构CP-ABE方案,通过具有多值属性的“与”门结构,实现保密消息和访问结构功能。文献[8]提出隐藏访问结构CP-ABE方案并证明该方案在标准模型下绝对安全。文献[9]在解密运算前提出匹配技术,减少不符合访问结构用户在解密过程中的开销。文献[7-9]均基于“与”门提出方案访问结构。文献[10]提出基于访问树的策略隐藏属性加密方案并论证该方案具有安全性。文献[11]提出表达能力较强的素数阶群中隐藏属性值CP-ABE方案且指出其安全类型为选择性安全。文献[12]提出素数阶群中部分隐藏树型访问结构的CP-ABE方案,该方案经验证完全安全。

本文在文献[11,13]的基础上,提出一种选择性隐藏树型访问结构的CP-ABE方案[14-16]。采用互信息(Mutual Information,MI)方法提取敏感属性,对含有原始属性集信息的部分属性进行隐藏,针对属性隐藏导致用户对自己解密能力无法提前判断的情形,利用以最少匹配代价判断解密能力的方法,使无解密能力的用户尽早放弃解密。

1 敏感属性提取

1.1 访问结构

本文使用的树型访问结构T内部节点支持“与”(AND)门、“或”(OR)门和“门限”(tofn)门。假设数据所有者ua的数据T中全体属性集为A={a1,a2,…,an}。访问数据的用户ut属性集表示为S′。ua制定T,利用互信息方法筛选出包含原始属性集A中绝大部分或者全部信息量的部分属性,隐藏部分属性,再将部分隐藏的T和密文一起分享到云服务器。ut根据未隐藏属性不能推测出加密信息。

隐藏部分属性的访问树如图1所示。假设有一份医疗数据为(住院号:005 AND医院:医院A)OR(2 of{医院:医院B;医生:心脏病专家;医院科室:心脏病内科}),如果不隐藏属性,则从T中可直接推测出医院A住院号为005的患者有心脏病。但是该患者不愿公开病情,因此医院在存储该患者信息时,选出并隐藏“心脏病专家”和“心内科”这两项包含较多敏感信息量的属性,然后分享到云端。访问者由隐藏部分属性的访问树不能推测出患者有心脏病,从而达到保护患者病史隐私目的。从信息熵角度,属性部分隐藏访问树与属性完全隐藏访问树的保密效果相同。

图1 隐藏部分属性的访问树

1.2 敏感属性提取算法

本文方案对T中属性进行选择性隐藏,选择哪些属性隐藏是重点考虑的问题。如果一个T中有n个属性,则选择性隐藏方案共有2n种,其中包括不隐藏全体属性和隐藏全体属性2种情形,本文着重考虑隐藏属性个数0

选择属性隐藏需要客观依据,本文借助特征提取方法选取需隐藏的属性。目前,常用特征提取方法主要包括互信息[17]、期望交叉熵、信息增益、词频法、文本证据权、几率比和卡方统计量等方法[18-20]。其中,互信息方法应用广泛[21-23],本文采用该方法来选择敏感属性。

本文属性提取过程从空集S开始,采用步进方式,每次选择1个属性。令:

(1)

(2)

第1次属性选择a1=al1,在只选择1个属性的情况下,a1=al1提供信息量最多。假设U为当前未被选择的属性集合,Sm-1为已选m-1个属性组成的集合,相对于U中其他属性,第m个属性am与整个属性集合A最大程度相关,同时与Sm-1中已选属性最小程度冗余。根据无监督最小冗余-最大相关标准(UmRMR),设:

(3)

其中,UmRMR(ai)表示为:

(4)

相关度表示为:

(5)

冗余度表示为:

Red(ai;at)=Rel(at)-Rel(at|ai)

(6)

条件相关度表示为:

(7)

其中,第m个属性选择为am=alm。在选择后续属性时,采用类似方式逐个进行选择。

定义1(敏感属性) 定义访问结构中属性ai为敏感属性,属性之间互信息存在以下关系式:

(8)

其中,k为数据所有者ua规定的阈值。如果属性之间互信息满足式(8),则敏感属性选取算法过程如下:

1)初始化:原始属性集A={a1,a2,…,an},设定初始候选集S=∅,Aδ为被选所有敏感属性组成的集合。

2)预先计算:对于∀ai,at∈A,计算信息熵H(ai)、互信息I(ai;at)、属性ai的相关度Rel(ai)和冗余度Red(ai;at)。

3)通过式(1)找到属性al1且U=Ual1,S={al1}。

4)根据式(3)找到属性alm且U=Ualm,S=S∪{alm}。

6)输出T中的Aδ。

经算法筛选出的敏感属性集合{a1,a2,…,ad}记为Aδ,其中am=alm,m=1,2,…,d(d

2 用户属性快速匹配

属性部分隐藏导致ut在解密前无法确定自己是否有解密能力,因此,在解密操作前,如果ut能提前判断自己没有解密能力,则其不再进行后续解密操作。本文结合访问树分析对用户属性进行快速匹配,以最少匹配代价判断自己的解密能力,使无解密能力的ut尽早放弃解密。

定义2(极小集) 满足T的最小属性集合为极小集,其特点包括:1)极小集交集非空;2)极小集交集为空集。

定义3(属性区分(Attribute Discrimination,AD)) 定义属性在给定的极小集中出现频次为属性区分度。

定义4(优先匹配次序) 给定的访问树T中,设∀a1,a2∈A,假设这两个属性对决定ut能否解密有必然关系,若AD(a1)>AD(a2),则优先匹配次序定义为a1≻a2,其中,AD(a1)和AD(a2)分别表示a1和a2的区分度。

优先匹配次序在T的属性匹配过程有以下性质:若ut使用优先匹配次序来匹配自己所拥有的属性,则其总匹配次数最少,即ut能够最早发现自己是否有继续解密的必要。

对该性质分析如下:

特别地,当t=n时,满足T的极小集S1={a1,a2,…,an}唯一。此时ut需将自身属性与S1中属性进行Hash值配对,且必须拥有S1中每个属性才能解密。

图2 极小集交集非空的访问树

2)若极小集交集为空集,对于极小集中没有隐藏的属性,ut通过目测部分了解自己是否满足T,但不一定完全了解自己能否满足T,这时ut解密能力由隐藏属性决定。若隐藏属性和公开属性的区分度相同,则为减少计算利用公开属性最大限度地排除部分极小集。若都是隐藏属性,则根据T节点特征与其Hash值,先找出区分度最大的属性以排除最多极小集,然后在剩余隐藏属性中找出区分度最大的属性,每次按照最大区分度方式寻找。将ut首先判断的属性假设为a1,理论上需要平均匹配(|S′|+1)/2次,若ut属性中没有a1,则直接排除有a1的极小集,由于极小集减少,因此ut是否有解密能力的不确定性也最大限度减少。而因为a1最先匹配,即所在的极小集最多,所以a1可在一次属性匹配过程中可最大限度地过滤掉不符合条件的极小集。若ut经Hash值计算判断自己属性中有a1,则将a3看成公开属性,余下极小集中最大区分度判断属性假设为a2,若没有a2,则ut在排除完没有a1极小集中再排除没有a2的极小集,其是否有解密能力的不确定性在前者基础上再次最大限度减少,从第2次匹配中可以看出,符合条件的极小集在进行下次匹配时其优先匹配次序将受到前一次匹配结果影响。以此类推,一直到ut确认自身有或没有解密能力。

极小集交集为空的访问树如图3所示。其中,极小集分别为S1={a1,a3,a4}、S2={a1,a3,a5}、S3={a1,a4,a5}、S4={a2,a3,a4}、S5={a2,a3,a5}、S6={a2,a4,a5}和S7={a6,a7},属性a3、a4、a5在极小集中出现4次,a1、a2出现2次,a6、a7出现1次,则优先匹配a3、a4、a5。假设其中隐藏属性是a1、a4、a7,若隐藏属性和公开属性的区分度相同,则为减少计算,利用公开属性最大限度地排除部分极小集,由于a3、a4、a5区分度相同,ut首先判断a3,若其属性中没有a3,则直接排除极小集S1、S2、S4、S5,ut是否有解密能力的不确定性减少57%;若ut经Hash值计算判断自己属性中有a3,则将a3看成公开属性。在余下的极小集中,a4、a5区分度相同,但a4隐藏,因此再判断a5,若ut属性中没有a5,则排除极小集S3、S6,ut是否有解密能力的不确定性在前者基础上又减少67%,然后判断用户属性中是否存在a6和a7,其中a6通过目测可得知。对于a7,ut理论上只需平均匹配(|S′|+1)/2次便可得知自己是否拥有此属性。若每次匹配次数最少,则整体匹配次数最少,即为最优匹配次序。采用优先匹配次序是为避免用户耗费时间进行无效计算。

图3 极小集交集为空的访问树

3 方案建立

3.1 相关定义

定义5(单调访问结构) 设{p1,p2,…,pn}是一个集合,访问结构A⊆2{p1,p2,…,pn}{∅}是一个非空子集合。对∀B,C,如果B∈A且B⊆C,则C∈A,那么A单调。

3.2 安全模型

以下通过挑战者和敌手之间交互性游戏建立策略部分隐藏CP-ABE方案的安全模型,该游戏流程如下:

1)初始化:挑战者运行初始化算法Setup(λ)生成公钥PK和主密钥MSK,并将公共参数发送给敌手。

2)阶段1:敌手适应性地向挑战者询问属性集A的密钥,可选定一些属性集γ1,γ2,…,γq进行密钥查询。挑战者运行算法KeyGen生成密钥SKut并发送给敌手,敌手可重复多次询问密钥。

3)挑战:敌手向挑战者提交2个等长的消息m0和m1,并访问树T0和T1(要求阶段1查询过的属性集γ1,γ2,…,γq均不满足T0和T1),挑战者抛掷1枚公平硬币b∈{0,1},计算c*=Encrypt(PK,mb,Tb),并将c*发送给敌手作为挑战密文。

4)阶段2:重复执行阶段1,但要求属性集γq+1,γq+2,…,γl不满足待挑战的访问树。

5)猜测:敌手输出对密文c*的一个猜测值b′∈{0,1}。如果b′=b,则称敌手赢得这个游戏。敌手在上述游戏中获胜的优势定义为:

(9)

定义8如果在任意多项式时间内,敌手赢得安全游戏的优势可忽略,那么该部分策略隐藏CP-ABE方案安全。

3.3 系统结构描述

数据分享系统结构如图4所示,具体如下:

1)密钥生成中心(Key Generation Center,KGC):对系统生成公共和秘密参数,假设KGC为半可信。KGC执行其他实体分配的合法任务,但其可能试图获取加密数据。

2)云服务器:提供数据存储和共享服务,实现部分解密。

3)数据所有者ua:拥有数据的用户将自己数据共享到云服务器。ua制定T,并利用MI算法筛选出T中敏感属性。在上传数据前根据T、KGC生成的公钥PKK和云服务器公钥PKS加密数据。

4)用户ut:访问数据的实体[24],KGC和云服务器根据用户属性生成用户密钥,若ut属性满足加密数据中的T,则其能够解密密文并获得数据M。

图4 数据分享系统结构

3.4 算法结构

本文在完全隐藏访问结构方案[25]的基础上,提出选择性隐藏树型访问结构CP-ABE方案,该方案由Setup、KeyGen、Encryption、Decrypt等4个算法组成。上述算法步骤具体如下:

1)Setup(λ)→(PKK,MKK),(PKS,MKS):该算法由KGC进行。算法输入安全参数λ,输出KGC公钥对PKK和密钥对MKK以及云服务器的公钥对PKS和密钥对MKS。

2)KeyGen(MKK,A)→SKut:KGC将MKK和属性集合A作为输入,为ut输出密钥SKut。

3)Encryption(M,T,PKK,PKS)→CT:ua使用PKK、PKS和T对数据M进行加密,并输出密文CT。

4)Decrypt(CT,SKut)→M:该算法由云服务器和ut来执行,以CT和SKut作为输入,ut对云服务器部分解密的CT′用自己密钥再次解密,并且输出明文M。

3.5 方案设计

3.5.1 系统初始化

KGC选择阶为素数p的循环群G0,g为G0的一个生成元。选择Hash函数H:{0,1}*→G0,H1:G1→{0,1}lb p,生成公共参数(G0,g,H,H1)。

3.5.2 密钥生成

SKut=(D=g(α+rt)/β,∀aj∈A,ai∈Aδ:Dj=

(10)

3.5.3 加密过程

(11)

为避免不必要的Hash配对,若ut花最小代价能判断出自己没有解密能力,则ut就不用去尝试参与后续解密过程,这样会减少ut与云服务器之间不必要的计算,从而降低时间成本。由于策略部分隐藏导致ut可能无法知道自己是否可以解密密文,针对因属性部分隐藏导致ut对数据解密能力无法提前判断的情况,本文提出以最少匹配代价判断自己解密能力的方法,使无解密能力的ut尽早放弃尝试解密。若此ut有解密能力,则继续后续解密操作。

3.5.4 解密过程

(12)

否则,有DecryptNode(CT,SKut,x)=⊥。

如果x为非叶子节点,则考虑递归情况,对于节点x所有孩子节点z,令Fz=DecryptNode(CT,SKut,z)。假设Sx为孩子节点z集合,使Fz≠⊥。该算法计算如下:

(13)

查询算法首先调用T根节点R上的函数。如果ut满足T,则云服务器运行DecryptNode(CT,SKut,R)=e(g,g)rtτs。

ut从云服务器得到密文CT′后,用自己密钥对密文进行解密。解密过程如式(14)所示,最终输出M。

(14)

4 方案分析

4.1 安全性分析

在CP-ABE方案中,秘密信息必须嵌入密文中而非密钥中。若攻击者想解密就必须恢复e(g,g)αs,则应使密文中Cx同用户密钥中Di相匹配,这样虽可获得e(g,g)αs值,但易被e(g,g)rs盲化。此外,当且仅当用户密钥满足密文中访问树时才能求出e(g,g)rs的值。用户合谋攻击无效,因为盲化每个用户密钥的盲因子均为随机。该方案的数据机密性、抗合谋、策略保密性与完全隐藏访问树方案[25]相同。

4.2 安全性证明

使用一般双线性群模型和随机预言机模型来论证CP-ABE方案,该方案的安全类型为选择明文攻击的不可区分性安全[26]。

定义9(一般双线性群模型) 考虑加法群Fp的2个随机编码ψ0和ψ1,即单射ψ0,ψ1:Fp→{0,1}m,其中m>3lbp。对于i=0,1,有Gi={ψi(x):x∈Fp}。于是得到G0和G1诱导群作用的预言,以及计算非退化双线性映射e:G0×G0→G1的预言。H为随机预言散列函数,G0为一般双线性群。

定理1如上述定义ψ0、ψ1、G0和G1。对于任何敌手,设q为从查询到哈希函数预言机、群G0和G1、双线性映射e以及与CP-ABE安全游戏交互中接收到的元素总数的一个边界。在CP-ABE安全游戏中,敌手优势为O(q2/p)。

以下介绍改进CP-ABE游戏模拟的符号。设g=ψ0(1)(用gx表示ψ0(x),e(g,g)y表示ψ1(y))。

在设置系统时,模拟者从Fp中随机选择α和β,并将其与0~p-1之间整数关联。如果β=0,事件发生的概率为1/p,则初始化中止。将公共参数h=gβ、e(g,g)α发送给敌手。

当敌手(或模拟者)要求对任意字符串i进行H评估时,从Fp中选择新随机值ti,模拟者提供gti作为对H(i)的响应。

当敌手提出挑战,发出两条消息M0,M1∈G1并访问树T时,模拟者执行以下操作:1)从Fp中选择一个随机的s;2)使用与T相关联的线性秘密共享方案为所有相关属性i构造s共享λi。根据秘密共享方案施加的线性条件,λi均由Fp中随机且一致地选择。特别地,对于某个l值,可通过均匀独立地选择l随机值μ1,μ2,…,μl来完全模拟λi′s选择,并让λi成为μk′s和s的固定公共线性组合。λi通常看作是上述独立随机变量的线性组合。

模拟者选择一个随机数θ∈Fp,并构造如下加密密文:

(15)

C=hs

(16)

在群G0或G1中均没有发生这种意外冲突。对于与不同有理函数η/ξ和η′/ξ′对应的同群中任何一对查询,只有当非零多项式ηξ′-ξη′计算结果为零时才会发生冲突。本文中ηξ′-ξη′总次数最多为5,此类冲突发生概率为O(1/p)。在联合约束下,任何此类冲突发生概率最多为O(q2/p)。因此,可以在不发生该冲突的情况下,保持质量概率为1-O(q2/p)。

由于θ仅以e(g,g)θ形式出现,而e(g,g)θ存在于G1中,因此v或v′在θ上唯一依赖性是具有γ′θ形式的相加项,其中γ′为常数。由此推断存在v-v′=γαs-γθ,其中γ≠0为常数。将查询v-v′+γθ=γαs添加到敌手查询中,且需证明敌手不能构造查询e(g,g)γαs。

(17)

为验证敌手查询多项式不是γαs形式,进行如下案例分析:

案例1存在某个j∈T,使得秘密共享集合Lj={λi′:∃i:(i,i′)∈T′j}不允许秘密s重建。如果存在j∈T,则sr(j)项将不会取消,因此敌手查询多项式不是γαs形式。

4.3 部分隐藏策略

4.4 性能分析

表1为3种同是树型访问结构但策略隐藏情况不同方案的对比情况。其中,L0和L1分别为群G0和群G1中元素长度,t为密文相关的属性个数,k为用户密钥相关的属性个数,e为双线性对,exp为群运算中的指数,|R|为满足T的用户属性个数,d为满足T的用户的感属性个数,d

表1 不同方案的性能对比

由于树型访问结构比LSSS矩阵更直观,策略可表达性更强,因此本文使用树型访问结构。由表1可以看出,完全公开访问树方案[3]的密钥长度和公钥长度较其他两种方案更短,但其数据安全性更低。与完全隐藏访问策略方案[24]相比,本文方案在加密和解密过程中指数运算和双线性对运算减少,在安全性相同情况下减少了计算量。在同是树型访问结构情况下,本文方案比完全公开访问结构方案安全性更高,比完全隐藏访问结构方案计算量更少。

5 结束语

本文从访问策略安全性和计算效率考虑,提出一种选择性隐藏树型访问结构CP-ABE方案,利用互信息方法进行属性提取,筛选和隐藏包含原始属性集信息的部分属性,采用以最少匹配代价判断解密能力的方法,使无解密能力用户尽早放弃尝试解密。分析结果表明,该方案与已有的完全隐藏方案具有相同保密效果,且有效减少加密和解密算法的计算量,较完全公开访问结构方案的策略安全性更高。下一步将研究更多样化和智能化的敏感属性提取算法,以减小算法计算量并提高CP-ABE方案的安全性。

猜你喜欢
敌手区分度密文
一种支持动态更新的可排名密文搜索方案
与“敌”共舞
基于模糊数学的通信网络密文信息差错恢复
密钥共享下跨用户密文数据去重挖掘方法*
浅谈试卷分析常用的几个参数及其应用
不带着怒气做任何事
图形推理测量指标相关性考察*
浅观一道题的“区分度”
一种基于密文分析的密码识别技术*
利用垂直平分线的定义巧解题