基于DFA访问结构的多授权机构ABE方案设计

蒋 琳，徐 颖，吴宇琳*，王 轩，方俊彬

(1.哈尔滨工业大学(深圳)计算机科学与技术学院，广东 深圳 518052；2.暨南大学 理工学院，广东 广州 510632)

0 引言

在大数据、云计算和物联网等信息技术的快速发展下，信息数据呈现爆炸式的增长。为了减轻用户的本地存储能力负担，越来越多的企业选择在云端存储海量数据。由于云服务器并不是完全可信的第三方，如何确保存储在云服务器中用户隐私数据的安全成为亟需解决的问题。密码学作为信息安全的基石，可以保证数据的完整性、机密性和不可否认性，是解决数据安全问题的关键技术。由于云服务提供平台不是可信第三方，因此现阶段普遍的做法是将数据加密之后再存储到云服务器上，传统的公钥加密体制通常是构建在一对一的数据安全上，无法满足加密数据共享中的一对多的场景。属性基加密(Attribute-based Encryption，ABE)作为公钥密码体制中的一员，能够实现细粒度的访问控制和一对多的加密模式，被广泛地应用于云计算环境中进行加密数据共享。

2005年，Sahai等人[1]提出了ABE的概念，首次将用户的身份信息转换为一系列的属性来控制加密数据的访问。ABE机制引入了属性集合和访问策略的概念，只有当属性满足访问策略时，用户才可以解开密文。2006年，Goyal等人[2]根据密钥/密文与策略的关系将ABE进一步地划分为密钥策略属性基加密(Key-Policy Attribute-based Encryption，KP-ABE)和密文策略属性基加密(Cipher-Policy Attribute-based Encryption，CP-ABE)两种类型。为了达到理想的灵活性，需要为ABE设计更具有表达性的访问结构，如访问树(Tree)[3]、线性秘密共享矩阵(LSSS)[4]和一般电路[5]等。传统的ABE系统大多都是单授权系统，需要一个完全可信的中央授权机构(Central Authority，CA)进行属性授权管理和密钥生成的工作。这也带来了用户隐私和单机器系统计算瓶颈的问题，对整个系统的安全十分不利，如果CA遭到恶意攻击造成密钥泄露更会导致严重的数据机密性问题。有学者针对多授权机构的ABE方案[6-7]进行研究，这些方案仍然需要CA帮助管理。为了解决这个问题，Lewko等人[8]提出了一个分散的多授权机构ABE系统，该系统任何一方都可以成为授权机构，且不需要CA进行属性管理和密钥分发。之后，又提出了许多不借助CA进行属性管理和密钥分发的方案[9-11]。上述方案大多数都是由传统的访问结构如LSSS，Tree作为控制策略，这些结构只能处理固定数量的属性变量，无法处理对任意数量的属性变量。2012年，Waters[12]提出了支持正则语言的ABE，在该使用确定性有限自动机(Deterministic Finite Automata，DFA)被用来作为访问结构生成解密密钥，以此识别任意长度的属性字符串，但是该方案依赖于q-type类型的动态假设且安全性只满足选择性安全。文献[13-15]对提升方案的安全性进行了详细研究。这些研究侧重单授权机构下自适应安全性的提升和简化安全性证明，存在密钥泄露的安全问题。

基于以上分析，本文提出了一种以DFA作为访问结构的多授权机构KP-ABE方案。通过使不同权限的授权机构管理相关密钥分发，解决了单授权机构下遭受攻击容易导致密钥泄露的问题。用户密钥由多个授权机构共同生成，并且和用户的身份标识绑定，所提方案能够抵抗非法用户及授权机构的共谋攻击。此外，该方案在系统建立后仍然可以动态增加授权机构，并且满足大属性集合的构造，增强了方案的可扩展性。最后，使用双系统加密技术[16-18]证明该方案在随机预言机模型下满足自适应安全。

1 相关知识

1.1 确定性有限自动机

1.2 合数阶双线性群

① 双线性：对于所有的g,h∈G,a,b∈Zn，有e(ga,hb)=e(g,h)ab。

② 非退化性：∃g∈G，使得e(g,g)≠1。

③ 可计算性：对于所有的g,h∈G，存在一个算法可以有效地计算e(g,h)。

④ 正交性：群的3个子群在双线性映射下满足“正交性”，即对于任意的g∈Gpi,h∈Gpj(i,j∈{1,2,3})，则有当i≠j的时候，e(g,h)为群GT的生成元，即e(g,h)=1。

1.3 困难问题假设

2 基于DFA的多授权机构ABE方案

2.1 方案系统模型

本文提出的基于DFA访问结构的多授权机构KP-ABE方案系统模型如图1所示。由5个实体构成：中央授权机构、普通授权机构、云服务器、数据拥有者和数据使用者。

图1 系统模型Fig.1 System Model

中央授权机构：负责建立系统全局公开参数，并为系统中的用户生成一个全局的唯一标识(gid)，为每个授权机构产生一个唯一标识(θ)。

授权机构：每个授权机构之间是相互独立的，负责生成自己的公私钥对，并根据用户的访问策略产生相对应的密钥。

云服务器：主要提供数据存取的服务。在该系统中，云服务器被设定为半诚实的实体，即它会正确地执行系统中合法用户的操作，同时也试图从接收的数据中获取信息。

数据拥有者：根据数据的属性值对该数据进行加密，并上传到云服务器上。

数据使用者：在该系统中，每个用户都拥有一个全局唯一的标识，并根据自己在不同机构上的访问策略可以获得对应的解密密钥。用户可以从云服务器上下载密文数据，当所有的访问策略满足加密数据的属性后，用户才能使用其密钥解密密文。

2.2 方案形式化定义

本文所提方案包括以下5个多项式时间算法，其形式化描述如下：

① GlobalSetup(λ)→GP：系统全局建立算法，由中央授权机构执行。算法输入安全参数λ，输出系统全局公共参数GP。

② AuthSetup(GP,θ)→(pkθ,skθ)：授权机构初始化算法，由每个授权机构执行。算法输入全局公开参数GP和授权机构的唯一标识θ，输出为该授权机构的公钥和私钥。

③ KeyGen(GP,ASKθ,θ,gid)→SKθ,gid：数据拥有者密钥生成算法，算法由授权机构执行。算法输入全局公开参数GP、属性机构的私钥ASKθ、用户访问自动机θ和用户身份标识gid，算法为gid标识的用户生成密钥SKθ,gid。

④ Encrypt(GP,{APKθ,ωθ}θ∈Auth,m)→CT：数据加密算法，由数据拥有者执行。算法输入全局公开参数GP、属性机构的公钥和属性字符串{APKθ,ωθ}θ∈Auth以及明文数据m，输出生成的密文数据CT。

⑤ Decrypt(GP,{SKθ,gid}θ∈Auth,CT)→m/⊥：数据解密算法，由数据使用者执行。算法输入全局公开参数GP、用户的组密钥{SKθ,gid}θ∈Auth和密文CT。如果密文的属性字符串满足标识为gid的用户的访问结构，则算法输出解密的明文数据m，否输出m/⊥。

2.3 方案安全模型

所提算法的安全性主要基于以下模型进行证明，此安全模型由挑战者和敌手之间的安全游戏进行描述。

系统建立：挑战者运行GlobalSetup和AuthSetup算法，生成全局公共参数和授权机构的公私钥对。令Auth*表示所有授权机构的集合，令Authc表示被腐蚀的授权机构的集合。对被腐化的授权机构，挑战者将其私钥和公共参数一并发送给敌手。

敌手查询请求阶段1：敌手向未被腐蚀的授权机构发送有限自动机θ以及身份标识gid进行密钥询问。挑战者运行KeyGen算法，产生解密秘钥SKθ,gid，并把它发送给敌手，这一过程可重复多项式有界次。

挑战阶段：敌手提交2个长度相等的消息M0，M1和待挑战的属性字符串{ωθ}θ∈Auth*。对每个授权机构θ∈Auth*/(Auth*∩Authc)，其ωθ不能被询问阶段1中的所有θ接受。然后挑战者投掷一枚硬币b，b取随机值0或者1，运行加密算法Encrypt(GP,{APKθ,ωθ}Auth*,Mb)生成密文CT*并返回给敌手。

询问阶段2：重复询问阶段1的过程，唯一的限制是对于θ∈Auth*/(Auth*∩Authc)的授权机构，其发送的θ不能接收ωθ。挑战者以阶段1中的方式进行回应，这一过程可重复多项式有界次。

猜测阶段：攻击者返回一个关于b的猜测b′。如果b′=b，则攻击者获胜。攻击者在游戏中的攻击优势为Adv=Pr[b′=b]-1/2。

定义：对于任意多项式时间内攻击者，如果在上述安全游戏中获得胜利的优势可以忽略，那么该方案是自适应CPA安全的。

2.4 方案具体构造

该方案包括以下5个多项式时间算法，具体构造如下：

③ KeyGen(GP,ASKθ,θ,gid)→SKθ,gid：由标识为θ的授权机构执行。假设身份标识为gid的用户在标识为θ授权机构下拥有的访问结构为θ=(Q,ZN,T,q0,qn-1)。令n表示状态机的状态个数即n=|Q|。对每个状态qx∈Q{qn-1}选取一个对应的随机数uθ,x∈ZN，有uθ=(uθ,0,uθ,1,…,uθ,n-1)，其中uθ,n-1=α，并计算得到令uskθ,1,0=H(gid)，令m表示自动机的转移函数的个数即m=|T|。对每一个转移函数T={(qxt,qyt,σt)|t∈[1,m]}，选择随机数rθ,t∈Zn，通过计算得到输出SKθ,gid=(uskθ,0,{uskθ,1,t}t∈[0,m],{uskθ,2,t,uskθ,3,t}t∈[1,m],θ)。

⑤ Decrypt(GP,{SKθ,gid}θ∈Auth,CT)→m/⊥：由数据使用者执行。对每个机构θ∈Auth进行下列计算：

3 方案正确性和安全性分析

3.1 正确性分析

对于所有授权机构θ∈Auth，如果数据使用者的与密钥相关联的自动机θ能够接受与密文相关联的ωθ，则有：

3.2 安全性分析

3.2.1 抗共谋安全性

在本文所提的系统中，用户的密钥与用户的身份标识gid相关联，在密文中，明文m与e(g1,g1)Γ相乘，所以必须借助Γ的值才能够恢复出明文数据。Γ使用加法秘密共享被拆分为多个共享值，并且使用e(g1,g1)αθsθ,0对不同机构的共享值进行加密，如果想要恢复这些共享值，用户的访问策略和属性字符串匹配才可以获得满足条件的SKθ,gid并最终解开密文。解密过程，当有2个身份标识gid和gid′的用户想要合谋解开密文的时，在双方的访问结构满足条件之后，解密的计算过程中产生式子e(g1,H(gid))∑θ∈Authδθ无法被约掉，也就无法得到正确的明文结果。因此本文提供的方案具有抗共谋安全性。

3.2.2 自适应选择明文安全

本方案的安全性证明类似于双系统加密证明技术。首先介绍半函数密文和半函数密钥，这些半功能密文和密钥仅用于安全性证明，不会在实际方案中出现。

①半功能密文：

②半功能密钥：

本文将通过一系列的混合游戏来证明所提方案的安全性，具体的定义如下：

GameReal：第一个游戏GameReal表示真实的安全游戏，即用户的密钥和挑战密文都是正常的。

Game0：在该游戏里，用户的密钥都是伪正常密钥，挑战密文是正常的密文。

Game1：该游戏与Game0的唯一区别是挑战密文是伪正常密文。

假设q为攻击者密钥查询的总次数，对于j∈[1,q]定义2种类型的游戏：

Game2,j,1：该游戏中，对前j-1个密钥请求，使用type2类型的半功能密钥；对于第j个密钥请求，使用type1类型的半功能密钥；其余的密钥请求使用正常密钥。挑战密文使用type1类型的半功能密文。

Game2,j,2：该游戏中，对前j个密钥请求，使用type2类型的半功能密钥；其余的密钥请求使用正常密钥。挑战密文使用type2类型的半功能密文。

Gamefinal：该游戏和Game2,q,2的唯一区别就是不使用mb来生成挑战密文，而是使用随机值生成挑战密文。

使用下面5个引理证明这些游戏是不可区分的。

引理1：假设存在一个攻击者能以的优势区分GameReal和Game0，则存在敌手能以接近的优势攻破假设1。

引理2：假设存在一个攻击者能以的优势区分Game0和Game1，则存在敌手能以接近的优势攻破假设1。

引理3：假设存在一个攻击者能以的优势区分Game2,j-1,2和Game2,j,1，则存在敌手能以接近的优势攻破假设2。

引理4：假设存在一个攻击者能以的优势区分Game2,j,1和Game2,j,2，则存在敌手能以接近的优势攻破假设3。

引理5：假设存在一个攻击者能以的优势区分Game2,q,2和Gamefinal，则存在敌手能以接近的优势攻破假设4。

定理1。如果假设1，2，3，4成立，则本文所提的方案在随机预言机模型下满足自适应安全。

证明。如果假设1，2，3，4成立，可以由先前的引理得到安全游戏GameReal和Gamefinal是不可区分的，在Gamefinal中，密文完全隐藏了b的信息，攻击者无法获取到任何有关b的信息，因此攻击者赢得Gamefinal的优势是可以忽略的，同样攻击者赢得GameReal的优势也是可以忽略的。所以，不存在一个多项式时间的敌手可以以不可忽略的优势攻破本文所提的方案。

4 性能分析与实验

4.1 性能分析

本文利用DFA作为访问结构，设计了一个多授权机构的KP-ABE方案，解决了单一授权机构的密钥滥用问题，提高了方案的安全性，并从访问结构、安全性、是否支持大属性集和共谋攻击等方面进行性能比较。

表1 性能比较Tab.1 Performance comparison

4.2 实验测试

为了验证本文所提方案的有效性，同时对方案的时间开销有更为直观的了解，接下来将给出方案的实验仿真结果。方案在开源代码库JPBC的基础上进行了仿真实现。由于所提方案基于合数阶群构造，故选取JPBC中的Type Al参数类型，设置群的阶为N=npq其中|n|=|p|=|q|=128 bit。实验运行的软件环境为Windows10 64位操作系统，Java版本为1.8。硬件环境为(英特尔)Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz(3 192 MHz)。群的所有实验仿真结果均取程序运行20次后的平均值。实验结果如下：

授权机构的初始化算法的开销为5E+P，其中E是指一次幂指数运算，P是指一次双线性配对操作，初始化算法时间复杂度与DFA中字符集字符的数量无关。授权机构初始化时间随DFA中字符集字符数量的关系如图2所示，随着字符集中字符数量的增加，授权机构初始化时间不会随之增长，满足大属性集合的性质。

图2 授权机构初始化算法时间开销Fig.2 Time cost of AuthSetup algorithm

方案在初始化、加密、密钥生成和解密4个算法消耗的计算时间如图3所示。假设用户的各个机构访问策略不变，同时用于加密的属性字符串长度依次增加。从图3可以看出，密钥生成算法和授权时间开销基本是固定的，原因在于该算法计算开销与属性字符串无关；而数据加密和数据解密时间开销与属性字符串长度成线性增长关系。

图3 方案的时间开销Fig.3 Time cost of the proposed scheme

5 结束语

本文对传统的基于DFA访问结构的ABE方案进行改进，提出了一种基于DFA访问结构的多授权ABE方案，解决了单授权机构下密钥泄露问题。所提方案不仅支持系统扩展性，还能够抵抗非法用户和授权机构的共谋攻击，增强了系统的安全性。此外，基于合数阶双线性群的子群判断假设问题，证明了方案在随机预言机模型下满足自适应安全，并通过仿真实验测试了所提方案的计算开销。本文所提的方案构建在计算开销比较大的合数阶双线性群，如何在计算效率更高的素数阶双线性群上构建基于DFA访问结构的自适应安全的多授权ABE方案是下一步要进行的工作。