基于OBDD访问结构的无配对CP-ABE方案

丁晟，曹进，李晖

（西安电子科技大学网络与信息安全学院，陕西 西安 710071）

1 引言

物联网作为传统互联网的延伸，旨在将现存的互联网与人们生活中的各种智能设备紧密结合，彻底打破数据孤岛，让数据流动起来。通过将数十亿的智能设备互联，物联网给予了智能电网、智慧城市、智能家居、智慧医疗等新模式更多的可能。然而，随着物联网设备之间的关系越来越紧密，如何保证数据在物联网中安全高效的共享成为一个相当棘手的问题。当物联网智能设备之间共享数据时，潜在的安全问题如数据泄露、数据完整性被破坏或未授权访问等都将严重影响数据在共享过程中的安全。

随着物联网设备数量的急剧增长，数据量规模也日趋庞大，单纯依靠设备自身存储和处理数据极易使其淹没在海量的数据之下。云计算作为互联网技术另一重要革新，其丰富的存储和计算资源可帮助物联网设备代理存储和处理数据。物联网设备可将本地存储的数据上传至云端，并可随时从云端下载数据，以节省本地存储资源。对于那些难以处理的数据，由于物联网设备自身计算资源有限，可以将数据提交给云端，利用云计算丰富的计算资源对数据进行必要的处理后，直接使用云计算返回的结果来进行下一步决策。

由于数据存储在云端，脱离了数据所有者的直接管控，其安全性将受到极大挑战。针对这一问题，普遍的解决方案是将数据加密，以密文形式存储在云端。基于属性的加密能同时实施数据加密和访问控制，有效保证了数据在共享过程中的安全。然而，直接将基于属性的加密应用到物联网设备上还存在一些问题，如其一直被诟病的效率问题。传统的基于属性加密的方案构造中都涉及双线性配对这一运算，经实验测试，一次双线性配对的计算开销大约是同一椭圆曲线下一次标量乘法运算的2～3倍[1]。因此，尽可能减少算法中双线性配对的计算次数，或者巧妙运用其他运算实现同样的算法功能，可在一定程度上提高基于属性加密的算法效率。

访问结构的设计也是基于属性加密中相当重要的一环。访问结构具有多种表现形式，例如线性秘密分享方案（LSSS,linear secret sharing scheme）[2]、与门[3]、门限[4]等。访问结构的优化可以提升密文策略属性基加密（CP-ABE,ciphertext-policy attribute-based encryption）系统的运行效率，可以提高访问策略的可表达能力，还能通过减少策略中冗余的属性来缩小密文长度。

本文基于有序二元决策图（OBDD,ordered binary decision diagram）访问结构，为物联网系统提出了一种新的无配对基于属性的加密方案，主要贡献如下。

1)为物联网系统提出了一种新的无配对基于属性的加密方案。该方案对传统CP-ABE进行了相关改进，利用椭圆曲线上较为轻量级的标量乘法代替复杂的双线性配对运算，有效降低了方案的计算开销。

2)基于OBDD技术优化了访问策略的数据结构，不仅支持任意关于属性的布尔表达式，还同时支持访问策略中属性的正负值。

2 相关研究

在过去的十年中，双线性配对的出现解决了许多之前在密码学领域无法解决的问题[5-7]。基于双线性配对，ABE被提出用于实现数据加密和访问控制的结合。Bethencourt等[4]提出了CP-ABE的具体构造，在他们的方案设计中，加密算法基于数据拥有者建立的访问树来加密消息。每个用户拥有一组代表其身份的属性以及每个属性对应的属性密钥。解密算法利用拉格朗日插值法来解密密文。Waters[2]基于LSSS访问结构提出了一个较为灵活的CP-ABE构造，并基于该构造提出了新的方案，改善了原有方案的不足。

2007 年，Cheung 等[3]提出了一种支持与门访问结构的CP-ABE 方案，该方案同时支持正负2种属性。Zhou等[8]提出了一种密文长度恒定的CP-ABE方案，密文长度不随系统中属性数量的变化而变化。该方案性能良好，但不支持非单调或析取范式的访问结构。Wang等[9]解决了CP-ABE 方案中的密钥托管问题，同时提高了属性的可表达性。Guo等[10]提出了一种密钥长度恒定的CP-ABE方案，该方案中解密密钥的数量独立于属性的数量。Li等[11]基于OBDD访问结构提出了一种新型的CP-ABE方案，该方案充分利用了OBDD访问结构丰富的表达性和计算上的高效性，但方案仍涉及双线性对的运算。尽管CP-ABE方案能有效保证云中数据的安全，并实施细粒度的访问控制，但方案中涉及大量双线性配对运算和模幂运算，计算开销过大这一问题严重限制了将其应用于物联网中的资源受限型的设备。

众所周知，基于配对的密码学协议的计算效率取决于配对运算的计算速度。针对这一问题，学者们进行了大量的研究[12-16]。为了优化椭圆曲线密码（ECC,elliptic curve cryptography）协议，Freeman等[17]分类列举了一些对于配对运算友好的椭圆曲线，并介绍了它们的具体构造以及相关的一些优化技术。Scott[18]分析了如何选择配对类型及椭圆曲线以提高ABE方案的计算效率。Rivain[19]详细讨论了如何在ECC方案中更快地计算标量乘法。

一种降低用户计算开销的方法是将复杂的运算外包给其他具有更强计算能力的实体。Chevallier-Mames等[20]在单不可信服务器模型下提出了一种将复杂的双线性配对计算外包的方案，但与Chen等[21]所提方案相比，计算开销仍较高。Chen等在双不可信服务器−单恶意实体模型下提出了一种新的计算外包算法，该算法计算效率更高，但其安全模型在实际应用中是不现实的。

一种较为直接的方法是将部分解密工作外包给云端。2011年，Green等[22]提出了一种解密外包的ABE 方案，属性私钥由两部分组成：El Gamal密钥和转换密钥。代理方可以利用转换密钥对密文进行部分解密，部分解密的结果为简单的El Gamal密文，用户只需再利用El Gamal 密钥进行简单运算即可完成解密。Li等[23]对这种方式进行了改进，使其同时支持对密钥分发和解密的外包。然而，这种计算外包方式只是将计算开销转移到了代理方或云服务器，对于整个系统来说，计算开销并没有得到有效降低。

为了从根本上优化ABE算法，本文利用其他更高效的算术运算代替复杂的双线性对运算。Odelu等[24]基于椭圆曲线密码学提出了一种密钥长度恒定的CP-ABE方案，但该方案只支持与门访问结构，限制了方案的灵活性。随后，他们基于RSA提出了一种新的密钥长度和密文长度均恒定的CP-ABE方案[25]。虽然该方案加密和解密的时间复杂度均为O(1)，但仍只支持与门访问结构。

3 基础知识

3.1 有序二元决策图

二元决策图（BDD）是一个有根、有向的非循环图，可用于高效的表示布尔函数。所有的布尔函数都可以转换为变量之间基本逻辑运算，例如AND、OR、NOT等的组合。

BDD由2种节点构成：决策节点和终端节点。每个决策节点会被标记为某一布尔变量，同时决策节点拥有2个子节点。当布尔变量获得赋值为1时，它的子节点被称为高节点；当获得赋值为0时，它的子节点被称为低节点。如果二元决策图中所有路径上的不同变量从根节点开始都以同样的次序出现，那么这种二元决策图被称为有序二元决策图（OBDD）。

举例来说，图1是用OBDD表示布尔函数f(x0,x1,x2,x3)=x0+x1x2+x1x3+x2x3。决策节点用圆圈表示，终端节点用方块表示。实线表示通向高节点的边，虚线表示通向低节点的边。布尔函数f(x0,x1,x2,x3)=x0+x1x2+x1x3+x2x3的值是通过从根节点开始沿着决策图中的某一路径向下，依次为每个决策节点中的变量赋值来得到的。函数f(x0=1,x1=1,x2=0,x3=0)的值可以从x0开始，沿实线向下移动到x1，再沿着实线移动到x2，最后连续沿着2条虚线移动到终端节点1。

图1 布尔函数f(x0,x1,x2,x3)=x0+x1x2+x1x3+x2x3的OBDD表示

3.1.1 生成OBDD访问结构

本节详细介绍如何将一个布尔表达式转换成对应的OBDD访问结构。

假设系统中定义了n种属性i，编号依次为i0,i1,…,in-1。访问策略包含系统中定义的所有属性。属性i的属性值为正，代表该访问策略要求满足策略的属性集里需含有属性i；属性i的属性值为负，代表满足策略的属性集里不需要含有属性i。基于布尔表达式的访问策略可表示为f(i0,i1,…,in-1)。

将OBDD中的所有节点进行编号，获得最终访问结构的表达式为

其中，ID是决策节点序号的集合；U是访问结构里出现的属性的集合；是一个元组(id,i,high,low)，id是当前节点的序号，i是当前节点内属性的序号，high代表1分支节点，low代表0分支节点，如图2所示。

3.1.2 判断是否满足访问结构

假设U是一个属性集，判断该属性集是否满足访问结构OBDD可按如下方式进行。

从根节点开始，对于具有属性i的决策节点，如果该属性i属于集合U，则代表该属性的属性值为1，判断过程将沿1分支节点向下；否则，判断将沿0分支节点向下。以上过程将重复执行直到抵达终端节点。如果终端节点为1，则表示属性集U满足该访问策略OBDD；如果终端节点为0，则表示属性集U不满足该访问策略OBDD。

图2 生成OBDD访问结构

3.2 CP-ABE框架

一个CP-ABE系统通常由5种算法组成，分别为系统初始化、授权机构设置、密钥生成、加密和解密，定义如下。

系统初始化 (k)→PP

系统设置算法将安全参数k作为输入，然后输出系统所需的全部公共参数PP。

授权机构设置 (PP)→PK,SK

基于第一步生成的公共参数PP，属性授权机构为自己和系统中的每一个属性生成公钥PK和私钥SK。

密钥生成(PP,i,GID,SK)→SKi,GID

密钥生成算法将公共参数、属性i、身份GID以及属性授权机构的SK作为输入，输出属性私钥SKi,GID，并将其发送给对应的用户。

加密 (PP,M,(A,ρ),{PKi })→CT

给定一消息M，访问矩阵(A,ρ)和访问策略中所有属性的公钥，加密算法输出密文CT。

解密(PP,CT,{SKi,GID})→M

如果某个用户拥有的一组属性满足密文的访问策略，解密算法可以成功恢复消息M，否则解密失败。

3.3 安全模型

本节给出无配对运算的CP-ABE方案的安全模型。该模型由以下描述的挑战者和敌手之间的游戏定义。

初始化

敌手首先选择一个挑战访问结构A，然后将其发送给挑战者。

设置

挑战者运行设置算法，为系统生成必要的全局参数，为每个属性生成公私钥对。然后挑战者将系统全局参数和属性公钥发送给敌手。

阶段1

攻击者可以自适应地查询任何属性私钥，唯一的限制是相查询的属性集不能满足挑战访问结构A。

挑战阶段

敌手选择2条等长的消息M0和M1，并将它们发送给挑战者。然后挑战者掷一枚随机硬币β∈{0,1}，并在访问结构A下对消息Mβ加密，然后发送给敌手。

阶段2

敌手可以继续查询属性私钥，唯一的限制条件与阶段1相同。

猜测

敌手对β输出猜测结果β′。敌手在这场游戏中的优势被定义为

定义1如果任何多项式时间敌手赢得这个安全游戏的优势是可以被忽略的，则所提方案被认为是选择性CPA安全的。

3.4 DDH假设

椭圆曲线上的判定性Diffie-Hellman（DDH,decisional Diffie-Hellman）假设的定义描述如下。

挑战者选择一个素数阶r的循环群P。令G是循环群P的一个生成元，a和b是从Zr中随机选择的。如果挑战者给攻击者一个元组(G,aG,bG)，那么攻击者在多项式时间内区分元素abG∈P和随机元素R∈P是困难的。算法β解决P中DDH假设的优势定义为ε，当

定义2如果多项式时间算法解决DDH困难问题的优势是可忽略的，那么DDH假设是成立的。

4 方案构造

本节将给出为物联网中高效安全数据共享所设计的基于OBDD访问结构的无配对CP-ABE的具体构造。由于双线性配对一直被认为是基于属性加密方案设计中计算开销最大的运算，因此本文选择用椭圆曲线上相对轻量级的标量乘法来代替复杂的双线性配对运算，以提高方案在加密和解密阶段的计算效率。此外，采用基于OBDD的访问结构来提高访问策略的表达能力，该类型访问结构既同时支持属性的正负值，也支持任何布尔运算。所提方案由以下5种算法组成。

1)系统初始化

令GF(p)为一阶为p的有限域。E是定义在GF(p)上的一条椭圆曲线。G是椭圆曲线E上一阶为r的元素。G生成了一个E的循环子群，其中椭圆曲线离散对数问题是困难的。

2)授权机构设置

3)密钥生成

假设用户拥有一属性集U。对于系统中定义的每一个属性i，如果i∈U，那么对于该用户来说该属性取正值，对应的属性私钥为ki；否则，该属性取负值，对应的属性私钥为。若为拥有属性集U的用户生成密钥，属性授权机构可计算其中，表示ki或

4)加密

首先，将明文消息映射到椭圆曲线E上的一点M。数据拥有者设置的访问结构为

令有效路径(root→1)的数量为V，其中每条有效路径为{Pj,j∈[0,v-1]}。数据所有者随机选择s∈Zr，并计算

整个密文为{OBDD,C,,j∈[0,V-1]}。

5)解密

若要解密密文CT，数据使用者拥有的属性集必须满足数据拥有者制定的访问策略。具体的解密步骤可以通过以下递归算法实现。

步骤1寻找编号为2的节点，即根节点，并将其定义为当前节点。

步骤2提取当前节点中包含的信息对于属性i：如果，则算法转到步骤3继续执行；如果表示NOTi），则算法转到步骤4继续执行。

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

①如果1分支节点是终端节点0，则终止递归算法并返回解密失败。

② 如果1分支节点是终端节点1，则算法转到步骤5继续执行。

③如果1分支节点是非终端节点，则将其定义为当前节点，算法转到步骤2继续执行。

步骤4搜索当前节点的0分支节点。

①如果0分支节点是终端节点0，则终止递归算法并返回解密失败。

② 如果0分支节点是终端节点1，则算法转到步骤5继续执行。

③如果0分支节点是非终端节点，则将其定义为当前节点，算法转到步骤2继续执行。

步骤5如若数据使用者拥有的属性集满足某一条有效路径Pj，那么为了恢复出明文M可以计算

最后，数据使用者可以将M映射回明文消息。

5 安全性分析

5.1 安全证明

本节将证明所提方案在DDH假设下是选择性CPA安全的。

定义3如果存在一个多项式时间的敌手A可以一个不可忽略的优势ε>0来破解提出的方案，那么存在一个多项式时间算法B可以的优势来区分DDH元组和随机元组。

令G为E的一个阶为r的生成元，β是集合{0,1}中的随机元素，R是E中一随机元素。DDH挑战者C首先随机选择a,b∈Zr。如果β=0，则令Z=abG；否则令Z=R。挑战者C将元组(G,aG,bG,Z)提交给模拟器B。然后B在下面的游戏中代替C扮演挑战者的角色。

系统初始化

A首先向B提交一个挑战访问结构

设置

为了给敌手A生成系统中的每个属性i的属性公钥，B随机选择。令ikaG为正属性i的公钥，为负属性i的公钥。因为是随机选择的，所以公共参数实际上也是随机的。

阶段1

A自适应地将属性集提交给B以求获得相应的属性私钥。唯一限制条件是敌手无法查询任何可用于成功解密密文的属性私钥。换句话说，属性集U不能是A的任何有效路径。

挑战

A在随机选择2条等长消息M0,M1∈E，并将它们提交给B。然后B掷一枚随机硬币β∈{0,1}，并根据访问结构A加密Mβ。令C=bG,B将挑战密文返回给敌手A。

阶段2

与阶段1相同。敌手A可以提交其他属性私钥查询，只要不违反与阶段1相同的限制条件。

猜测

A输出对β的猜测β′。如果β′=β，B输出0表示Z=abG；否则，B输出1表示Z=R。

如果Z=R，则对敌手A而言是完全随机的。从而有

因此，B破解DDH问题的优势为

5.2 共谋攻击

对于CP-ABE来说，共谋攻击是方案设计时需要考虑的最重要的安全问题之一。由于ABE旨在授予属性集满足访问结构的用户访问权限，因此不具备访问资格的用户不应能够恢复出明文，即使他们彼此串通。换句话说，他们不能通过组合或计算他们自己的属性私钥来获得可用于成功解密密文的密钥。在本文的方案中，每个用户的密钥是其属性集中每个属性值对应的的总和。假设有n个属性，编号依次为{0,1,2,…,n-1}，每个属性对应的密钥为（当属性值为正时，属性私钥为；否则，）。总共有2n个可能的密钥，分别为

实际上，这2n个属性私钥形成了一个拥有2n个变量的线性方程组，分别为

该线性方程组的系数矩阵为

很明显，系数矩阵的秩小于变量的数量。因此，这种线性方程组具有无限多个解。换句话说，对于那些不合格的数据用户，他们无法通过使用自己的密钥计算获得有关的确切值的任何有价值的信息。因此，本文方案可以有效抵抗共谋攻击。

6 性能分析

本节将所提方案与其他方案在性能表现方面进行了对比，包括加解密计算开销、密钥生成计算开销、密文长度和密钥长度。在分析计算开销时，着重统计了方案中涉及的一些主要的运算，如群元素的幂运算、双线性对运算、标量乘法。为了便于理解，将分析中用到的符号在表1进行简要说明。

表1 符号示例

为了证明双线性配对运算比标量乘法计算开销大，表2中对比了在本文的实验环境中2种运算的计算开销。实验环境为一台搭载Intel的Pentium G620 CPU，2.60 GHz和2 GB RAM机器，该机器运行Ubuntu Linux 16.04LTS 系统。方案基于PBC库（版本0.5.14），选择了512 bit有限域上的一条超奇异曲线上160 bit的椭圆曲线群，来实现80 bit的安全性。实验结果是30轮实验的平均值。从表2可见，一次双线性配对运算的计算开销大约是一次标量乘法的2～3倍。

表2 各种运算计算开销对比

从表3中可以清楚地看到，所提方案在多个方面均优于其他方案。密钥生成和解密的时间复杂度均为O(1)，且由于所提方案的密钥生成阶段仅涉及模加运算，因此其密钥生成阶段的计算开销几乎可以忽略不计，而较文献[3]方案和文献[4]方案更为高效的文献[11]方案仍需要进行2次群元素的幂乘运算。解密过程仅需要一次标量乘法，虽然在时间复杂度上与文献[11]方案一样均为O(1)，但文献[11]方案仍需要进行双线性配对运算。此外，所提方案中属性授权机构为用户分发的密钥长度是固定的，而非正比于属性的数量，且较文献[11]方案来说，密钥长度仅为文献[11]方案的一半。加密过程的计算开销以及密文长度均正比于OBDD访问结构中有效路径的个数，而非访问结构中属性的个数，这显然有效降低了方案的计算和存储开销，尤其是当V较小时。

表3 性能对比

7 结束语

为了保证物联网数据安全高效的共享，本文应用CP-ABE技术来对数据进行安全的加密，同时实施细粒度的访问控制。基于OBDD 的访问结构提出了一种新型的无配对CP-ABE方案。利用椭圆曲线密码技术，将原本CP-ABE方案构造中复杂的双线性配对运算替换为轻量级的标量乘法，从而降低了方案的计算开销。同时方案采用OBDD访问结构，该类型访问结构不仅能表示任何关于属性的布尔表达式，还同时支持访问策略中属性的正负值。安全性和性能分析结果表明，所提方案在DDH假设下满足选择性选择明文安全，且方案的计算效率能满足物联网的实际应用需求。