自适应安全的带关键字搜索的外包属性基加密方案

郭丽峰，王倩丽

（1.山西大学计算机与信息技术学院，太原 030006；2.山西大学大数据科学与产业研究院，太原 030006）

0 引言

近年来，政府对云计算产业发展的高度重视使得其产业规模迅速增长。作为云计算中一种典型的应用场景，云存储的应用领域从政府到民生，并逐渐向全行业延伸拓展。但由于云存储服务提供商是不可信的，可能存在数据篡改、数据泄露等安全隐患。因此，用户选择将数据以密文形式存储在云上。但大部分加密体制提供了一对一的数据共享方式，不适用于云存储中一对多的数据共享要求。随后，文献［1］提出了属性基加密方案，该方案提供了一种一对多的细粒度访问控制方式，并逐渐成为云存储环境中最具发展前景的加密体制。

文献［1］于2005 年提出了一种模糊的基于身份的加密方案，该方案将身份标识看作一串描述性属性，匹配加密用户与解密用户的身份标识，若匹配结果满足预先设定的阈值，用户可以解密获得明文。为了提高访问策略的灵活性，文献［2］提出了密钥策略的属性基加密（Key-Policy Attribute-based Encryption，KP-ABE），文献［3］提出了密文策略的属性基加密（Ciphertext-Policy Attribute-based Encryption，CP-ABE），KP-ABE的特性是访问策略和密钥相关联，属性集合和密文相关联；CP-ABE 的特性是访问策略和密文相关联，属性集合和密钥关联。文献［4］在标准模型下证明了该方案的安全性，文献［5］利用双系统技术证明了所提的属性基加密方案是自适应安全的。属性基加密方案提供了一对多的细粒度访问控制方式，但云存储环境中数据种类繁多，用户可以利用关键字搜索方案快速地检索所需消息，文献［6］提出了一种带关键字搜索的公钥加密（Public Encryption with Keyword Search，PEKS）方案，该方案由云服务器在不知道关键字的前提下对关键字索引和陷门进行匹配，实现数据检索功能。关键字可搜索方案的提出，提高了用户在云存储环境中查找数据的效率，文献［7-11］进一步改善了关键字搜索的公钥加密体制。为了实现带关键字搜索的细粒度访问控制，文献［12］将关键字搜索集成到属性基加密中，并将解密阶段的计算降低到常量级。文献［13］提出了一种访问策略为布尔公式的通用的KP-ABE方案，且该方案支持布尔公式作为搜索条件。文献［14］利用CP-ABE 和关键字搜索方案提出了一种应用在局域网上的细粒度的密文数据的搜索方案，所提的方案可以同时为资源受限的用户提供关键字搜索和轻量级访问。

由于属性基加密采用了双线性对运算，给用户带来大量的本地计算成本。文献［15］首次提出了外包属性基加密（Outsourced Attribute-based Encryption，OABE）方案，该方案利用服务器完成一次密文的转换，将解密阶段的计算外包给云服务器以降低用户的本地计算成本。在不影响带关键字搜索的细粒度访问控制的前提下，文献［16］提出了一种在线/离线密文策略属性基关键字可搜索加密方案，该方案采用预计算方法降低加密用户的本地计算成本，并且由云服务器完成关键字匹配以及部分解密的工作，使得解密用户的本地计算成本降低到常量级，但该方案必须保证密钥生成机构是完全可信的。文献［17］提出了一种适用于物联网的带平等测试的关键字可搜索的属性基加密方案，该方案将密钥生成、加密和解密阶段的计算完全外包给服务器，同时利用平等测试验证不同的访问策略下密文是否包含相同的明文，从而减少用户需要解密的次数，但该方案中包含的参数较多，计算较为繁琐。文献［18］提出了一种多授权机构的带关键字搜索的密文策略的属性基加密，该方案利用离线加密和外包解密技术以降低用户的本地计算成本，且该方案支持对恶意权威机构的追踪，但该方案是面向小属性集合的，当增加新的属性时需要更新整个系统。同时，现有的带关键字搜索的外包属性基加密方案大部分是在素数阶群下的选择模型中证明的安全性。

基于上述问题，本文提出了一种自适应安全的带关键字搜索的外包属性基加密（Outsourced Attribute-Based Encryption with Keyword Search，OABE-KS）方案。该方案利用关键字搜索技术提高用户在云服务器中检索数据的效率，最后利用云服务器降低加解密用户的本地计算成本到常量级。本文的具体工作如下：

1）面向大属性集合增强了系统的灵活性。系统需要添加属性时，无需对整个系统进行更新，只需要在密钥生成阶段添加对应的属性即可。

2）降低加解密用户的本地计算负担。由云服务器辅助用户完成加/解密，将用户本地计算成本降低到常量级，使得方案更适用于计算资源有限的移动设备。

3）解密用户无需为外包解密计算转换密钥。由于权威机构是利用用户公钥为用户生成密钥，从而可以在保证信息安全的前提下将全部的解密密钥发送给云服务器用于外包解密。

4）提高用户检索数据的效率。在外包属性基加密的基础上，利用云服务器的公私钥实现了免安全信道传输的关键字搜索功能。

5）在标准模型下利用双系统技术证明了该方案是完全安全的。

1 预备知识

1.1 合数阶双线性群

合数阶双线性群最早由文献［19］提出。令G表示群算法生成器，输入安全参数λ，得到双线性群的描述(N，G，GT，e)。其中N=p1p2p3是三个互不相同的素数的乘积，G，GT是N阶乘法循环群，e：G×G→GT是一个映射，有：

1）双线性性：∀g，h∈G，a，b∈ZN，有e(ga，hb)=e(g，h)ab。

2）非退化性：∃g∈G，使e(g，g)在GT中的阶为N。

3）可计算性：∀g，h∈G，可以有效地计算e(g，h)。

1.2 访问结构

令参与方集合表示为P={P1，P2，…，Pn}。对于∀B，C，如果B∈A，且B⊆C，有C∈A，则称集合是单调的。一个（单调的）访问结构A是{P1，P2，…，Pn}的一个非空（单调的）子集，即。在A中的集合称为授权集，不在A中的集合称为非授权集。

1.3 线性秘密共享方案

在参与方集合P上的秘密共享方案∏是线性的，如果以下条件成立：

1）每个参与方的份额构成群Zp上的一个向量；

2）在∏上存在一个份额生成矩阵M。对于所有的j=1，2，…，l，函数ρ将M的第j行映射到一个参与方ρ(j)。考虑一个列向量v=(s，v2，v3，…，vn)用于共享秘密值s∈Zp，其中v2，v3，…，vn∈Zp是随机选择的，则λ=Mv是方案∏上秘密共享值s的有效份额的向量，其中，λj=(Mv)j表示参与方ρ(j)的份额。

线性重构性：∏是访问结构A对应的线性秘密共享方案。S是一个授权集，定义I={i：ρ(i)∈S}。如果{λi}是秘密s的有效份额，那么可以在多项式时间内找到一组常数，使得=s成立。

1.4 复杂性假设

假设1 通用子群判定假设。令G表示群生成器，且Z0，Z1，…，Zk表示集合{1，2，3}的非空子集，其中，每个Zi(i≥2) 满 足Z0∩Zi≠∅≠Z1∩Zi或 者Z0∩Zi=∅=Z1∩Zi。定义如下分布：

对于一系列固定的集合Z0，Z1，…，Zk，定义敌手A攻破以上假设的优势为：

如果对于任意的PPT 敌手A以及任意恰当的子集系列Z0，Z1，…，Zk，(λ)是可忽略的，则称G满足以上假设。

假设2 给定群生成器G，定义如下分布：

定义敌手A攻破以上假设的优势为：

如果对于所有的PPT 敌手，(λ)是可忽略的，则称G满足以上假设。

2 带关键字搜索的外包属性基加密方案

2.1 系统模型

本文提出了一种带关键字搜索的外包属性基加密（OABE-KS）方案，系统结构如图1所示，该方案包含6个实体：权威机构（AUThority，AUT）、外包加密服务器（Encryption Server Provider，ESP）、数据拥有者（Data Owner，DO）、云服务商（Cloud Server Provider，CSP）、数据使用者（Data User，DU）和外包解密服务器（Decryption Server Provider，DSP）。

图1 带关键字搜索的外包属性基加密方案的系统结构Fig.1 System structure of outsourced attribute-based encryption scheme with keyword search

其中，权威机构（AUT）为系统生成公共参数，同时为数据使用者验证云服务器外包计算的正确性；数据拥有者（DO）在两个不可合谋的服务器ESP 的协助下完成加密，并将密文上传到云服务器；数据使用者（DU）为所需关键字生成陷门并将其传送给云服务器；云服务器（CSP）通过匹配陷门和关键字索引，将匹配成功的密文返回给数据使用者；解密服务器（DSP）为数据使用者完成部分解密，降低数据使用者的计算负担。

2.2 方案描述

本文的方案OABE-KS 是基于文献［5］的合数阶群下的方案构造的，该方案包含以下12个多项式算法：

Setup(1λ) →(mpk，msk)：系统初始化算法由AUT 执行。输入安全参数λ，输出系统公共参数mpk和系统主密钥msk。

SetupU(mpk) →(pku，sku)：数据使用者公私钥生成算法由DU 执行。输入系统公共参数mpk，输出数据使用者的公私钥对(pku，sku)。

SetupC(mpk) →(pkc，skc)：云服务器公私钥生成算法由CSP执行。输入系统公共参数mpk，输出云服务器的公私钥对(pkc，skc)。

KeyGen(msk，S，mpk，pku) →sk：用户解密密钥生成算法由AUT 执行。输入系统主密钥msk，系统公共参数mpk，用户属性集合S，用户公钥pku，为数据使用者生成解密密钥sk。

Secret_Destribute(1λ) →(s1，s2)：辅助服务器ESP的秘密值生成算法由DO执行。该算法为两个ESP输出秘密值s1，s2。

Part_EncryptESPi(mpk，(Μ，ρ)) →cti：外包加密算法由ESP1和ESP2分别执行。该算法输入系统公共参数mpk和数据拥有者设置的访问结构(M，ρ)，为其生成两部分密文ct1，ct2。

Encrypt((Μ，ρ)，mpk，ct1，ct2，w，pkc，m) →CT：最终加密算法由DO 执行。该算法输入两部分密文ct1，ct2，系统公共参数mpk，关键字w，云服务器公钥pkc以及明文消息m，输出包含关键字索引的密文CT。

Trapdoor(mpk，sk，sku，w') →Tw'：陷门生成算法由DU 执行。该算法输入系统公共参数mpk，数据使用者的解密密钥sk，数据使用者私钥sku以及数据使用者想查询的关键字w'，最后生成陷门Tw'。

Test(Tw'，index，skc) →CT⊥：匹配算法由CSP 执行。该算法输入陷门Tw'，关键字索引index和云服务器私钥skc，对关键字索引和陷门进行匹配，若匹配成功，云服务器返回相应的密文CT；否则，返回终止符⊥。

Decryptout(CT，mpk，sk) →C：外包解密算法由DSP 执行。该算法输入密文CT，系统公开参数mpk，数据使用者解密密钥sk，计算得到外包解密结果C。

Decrypt(C，sku，CT) →m⊥：解密算法由DU 执行。该算法输入外包解密结果C，数据使用者私钥sku和密文CT，调用审计算法Audit，若Audit输出为1，DU 可以执行解密得到明文消息m；否则，输出终止符⊥。

Audit(C，msk，C1)→10：审计算法由AUT执行。该算法输入外包解密结果C，系统主密钥msk，密文C1，若验证云服务器解密结果正确，则返回1；否则，返回0。

2.3 安全性定义

本节定义了在假设1 和假设2 下OABE-KS 方案中外包属性基加密的完全安全性以及带关键字搜索的安全性。

2.3.1 外包CP-ABE的完全安全

本节给出了OABE-KS方案中外包CP-ABE 的完全安全的定义。这个安全性通过一个挑战算法B和一个敌手A的游戏来描述。游戏过程如下：

1）Setup：算法B 运行Setup，得到系统公共参数mpk，并将mpk发送给敌手A；同时B 生成数据使用者的公私钥(pku，sku)和云服务器的公私钥(pkc，skc)。

2）Phase 1：敌手A提交属性集合S1，S2，…，以及用户公钥pku进行解密密钥查询，算法B 运行KeyGen 得到sk并将其返回给A。

3）Challenge：敌手A提交2 个等长的消息key0、key1和一个访问结构(M*，ρ*)，注意，Phase 1 中查询的属性集合S1，S2，…，均不满足访问结构(M*，ρ*)。算法B 随机选择b∈{0，1}，并在访问结构(M*，ρ*)下加密keyb，得到密文CT，并将其发送给敌手A。

4）Phase 2：同Phase 1，要求查询的属性集合，…，SQ不满足挑战访问结构(M*，ρ*)。

5）Guess：敌手A输出猜测b'。

在外包属性基加密（OABE）这个游戏中，敌手A的优势是：

定义1一个外包CP-ABE 方案是完全安全的，如果任意多项式时间的敌手A在以上的安全游戏中的优势是可忽略的。

2.3.2 关键字可搜索方案的选择关键字攻击

本节给出了标准模型下外部攻击者进行选择关键字攻击（Chose Keyword Attack，CKA）的安全性分析。攻击者A和挑战算法B之间的交互游戏过程如下：

1）Setup：算法B 执行Setup 得到公开参数mpk和主密钥msk，生成数据使用者和云服务器的公私钥对，并发送公开参数给敌手A。

2）Phase 1：敌手A向算法B进行密钥查询和陷门查询。

3）Challenge：敌手A提交要挑战的关键字w0，w1，算法B随机选择关键字wb∈{w0，w1}，生成关键字索引index，并将其返回给敌手A。

4）Phase 2：同Phase 1，但敌手查询的关键字满足如下条件(w≠w0)∧(w≠w1)。

5）Guess：敌手输出猜测b'。

在以上游戏中，敌手A的优势为：

定义2如果敌手在以上游戏中优势是可忽略的，则称该方案可抗选择关键字攻击。

3 本文方案构造与安全性证明

3.1 方案构造

本文的方案OABE-KS 是基于文献［5］提出的合数阶群下的方案提出的，具体过程如下：

3.2 安全性证明

定理1如果假设1 和假设2 成立，则方案是完全安全的。

证明 本文方案在文献［5］的属性基加密方案的基础上，实现了外包加密以及外包解密，并增加了关键字可搜索功能，加快用户在云存储服务器中检索数据的速度，但其中外包属性基加密方案的安全性证明和文献［5］的相同，因此，此处不再对外包属性基加密方案的安全性证明过程进行赘述。

定理2如果假设1 和假设2 成立，则该方案对外部攻击者是选择关键字安全的。

本文的安全性证明过程是通过一系列游戏的混合论证完成的。令Gamereal表示之前安全性定义中的真实游戏。为描述接下来的游戏，引入了半功能密钥和半功能关键字索引。令g2表示子群Gp2中的固定生成元。

1）半功能密钥：为属性集合S生成半功能密钥，首先运行正常的密钥生成算法KeyGen 得到K0，K1，K2，{Ki，1，Ki，2}i∈[1，k]。然后随机选择W∈，按如下形式构成半功能密钥为：

2）半功能关键字索引：为关键字w生成半功能关键字索引，首先调用通过调用Encrypt 算法生成正常关键字索引index=(I1，I2，I3，C2)。其中，yc为云服务器私钥，H(w)为关键字的哈希值，随机选择a'，s'∈ZN，有：

用Q表示敌手A进行密钥查询的总次数。定义游戏如下：

Gamereal表示真实的安全游戏。对于k∈[0，Q]，在Gamek中，挑战阶段生成的关键字索引以及前k次查询得到的密钥是半功能的，其余是正常的密钥。Gamefinal中返回给敌手A是随机关键字的半功能索引，其余返回信息和GameQ一致。

混合论证按从Gamereal到Game0，到Game1，再到GameQ，最后到Gamefinal。在GameQ中，返回给敌手A的挑战密文和A查询得到的密钥都是半功能的。最后，转换到Gamefinal，此时证明方案在选择关键字攻击下是安全的，因为敌手A在Gamefinal中的优势是0。

引理1如果假设1成立，则没有概率多项式时间敌手能以不可忽略的优势区分Gamereal和Game0。

证明 假设有一个概率多项式时间敌手A能以不可忽略的优势区分Gamereal和Game0，因此可以创建一个概率多项式时间挑战算法B 以集合Z0={1}，Z1={1，2}，Z2={1}，Z3={3}打破假设1。输入g1，g3，T给算法B，其中g1是的生成元，g3是的生成元，T是或者中的随机元素，根据输入，算法B与敌手A模拟Gamereal和Game0。

2）Query 1：敌手A向算法B 提交要查询的属性集合S1，S2，…，，算法B运行密钥生成算法Keygen得到对应的正常的密钥，具体过程如下：

a）密钥查询：B 初始化一个空集合D和一个空列表T。A提交属性集合S进行密钥查询时，B 令集合D=D∪S，同时调用密钥生成算法KeyGen 为属性集合S生成解密密钥sk，将(S，sk)存入列表T中，并返回(S，sk)给敌手A。

b）陷门查询：A针对属性集合S和关键字w进行陷门查询时，若T中有(S，sk)，则取出sk，利用数据使用者私钥sku和关键字哈希值H(w)生成陷门Tw，将陷门返回给敌手A。

若T∈，则第k次查询得到的是正常密钥，表示B 很好地模拟了Gamek-1；若T∈，则是一个半功能密钥，B模拟了Gamek。若敌手A可以区分出游戏中第k次查询得到的陷门是半功能的还是正常的，B可以利用敌手A区分Gamek-1和Gamek的优势去攻破假设1。

引理3如果假设2成立，则没有概率多项式时间敌手能以不可忽略的优势区分GameQ和Gamefinal。

4）Query 2：同Query 1，限制敌手A查询的属性集合不满足Challenge阶段挑战的访问结构(M*，ρ*)。

5）Guess：敌手A输出猜测b'。

若T=e(g1，g1)αs，所得结果是关键字wb的半功能关键字索引，则算法B 很好地模拟了GameQ；若T是GT中的一个随机元素，所得结果是随机关键字wR的半功能关键字索引，B模拟了Gamefinal。因此，若敌手A可以不可忽略的优势区分T，那么B可以利用A的优势攻破假设2。

4 实验结果与性能分析

4.1 理论分析

本节在理论上将本文方案与文献［8］方案、文献［16］方案、文献［17］方案、文献［18］方案、文献［5］方案进行性能对比。文献［8］方案是合数阶群下的关键字可搜索方案，文献［16-18］方案是带关键字搜索的外包属性基加密，通过与文献［5］方案的对比体现出本文方案的优势。各方案实现的功能以及各方案的安全性对比如表1 所示，理论上各个方案在不同阶段的计算成本对比结果如表2所示。

由表1 的对比可以看出，本文方案是面向大属性集合的，同时支持外包加密和外包解密，最后在标准模型下利用双系统技术证明本文方案是完全安全的，而在同类型的带关键字搜索属性基加密的方案中，文献［16］方案、文献［17］方案与文献［18］方案是在选择模型下证明了方案的安全性，文献［18］方案和文献［5］方案是面向小属性集合的。

表1 不同方案的功能及安全性对比Tab.1 Function and security comparison of different schemes

表2 对系统初始化的计算成本、加密用户和解密用户的本地计算成本，以及云服务器完成关键字匹配的计算成本进行对比。其中，|U|表示系统属性集合的大小，|l|表示访问矩阵M的行数，|S|表示用户属性集合的大小，P表示群GT上的双线性对运算，EG，分别表示群G，GT上的模幂运算。

表2 不同方案的性能对比Tab.2 Performance comparison of different schemes

4.2 结果分析

方案效率对比所采用的实验环境是Windows 10 操作系统，Intel Core i7-7700 CPU @3.60 GHz 的处理器，以及16 GB的内存。其中，对合数阶群采用Type A1 的椭圆曲线，对素数阶群采用Type A 的椭圆曲线，用到的群的阶数均采用256位，最后，所采用的运行时间是100 次结果的平均值，以保证运行结果的准确性。但需注意的是合数阶群下的运算速度比素数阶群下的运算速度慢，因此，在效率图中与理论分析阶段可能有所差别。

系统初始化建立阶段的运行时间如图2 所示，加密用户本地的运行时间如图3 所示，云服务器执行关键字匹配时间如图4所示，解密用户本地的运行时间如图5所示。需注意的是，这里均是按单关键字进行实现的。同时，由图5 可知，合数阶群的运行时间多于素数阶群，对于同样的计算量EGT，在实现的过程中仍会有不同的运行时间。从图2 可以看出，对于系统属性为小属性集的文献［5］方案和文献［18］方案，系统初始化建立的时间会随着属性数量的增加而增加；在图3～5中未表示出文献［5］方案的性能，是因为文献［5］方案中各阶段计算量太大，会导致无法看出其他方案的差异；文献［8］方案为合数阶群下的带关键字搜索，该方案不含属性这一概念，因此只对比云服务器匹配关键字的时间，在图4中呈现。

图2 不同方案的系统初始化建立时间Fig.2 Time of system initialization and setup for different schemes

图3 不同方案的加密用户本地运行时间Fig.3 Local running time of encryption user for different schemes

图4 不同方案的云服务器搜索时间Fig.4 Search time of cloud server for different schemes

图5 不同方案的解密用户本地运行时间Fig.5 Local running time of decryption user for different schemes

对以上结果综合分析可以发现，本文的方案在系统初始化、用户加解密以及云服务器匹配关键字的时间上均为常量级，不会随着属性数量的增加而增加。此外，本文方案在标准模型下利用双系统技术证明了所提方案是完全安全的。

5 结语

针对云服务器中数据繁琐以及云存储服务提供商不可信的问题，本文提出了一种自适应安全的带关键字搜索的外包属性基加密方案，即在降低加解密用户本地计算成本到常量级的基础上，利用关键字搜索提高云服务器检索数据的效率，最后利用双系统技术证明了所提方案是自适应安全的。同时，本文实现了外包解密的正确性验证。接下来的工作中，可以利用密码协议，如比特承诺、零知识证明等，实现方案中主密钥对权威机构的保密性。