支持非单调访问结构的可验证搜索属性加密方案

林素青，张书华

（1.天津财经大学理工学院，天津 300222；2.天津财经大学管理可计算建模协同创新中心，天津 300222）

0 引言

随着云存储服务的快速发展，越来越多的用户为减轻本地存储负担而选择将数据外包至云端存储，为确保敏感信息安全，数据通常会在外包之前进行加密，于是，针对加密存储数据的高效搜索和共享成为难题。密文关键字搜索技术能帮助用户安全快速且有选择地从云存储中检索感兴趣的数据。但是，多数可搜索加密方案［1-3］不支持细粒度搜索访问，而属性加密却能为实现密文细粒度搜索提供技术支持。属性加密［4-7］能根据用户属性实现细粒度访问权限设置，将属性加密与密文关键字搜索技术相结合，可构造支持密文关键字细粒度搜索的属性加密方案［8-11］，但多数方案仅支持单调访问结构。Chaudhari 等［12］基于非单调访问结构，即“与”门访问结构，设计支持隐私保护的细粒度搜索访问机制，无需透露用户访问权限即可执行搜索过程，并证明方案在随机预言机模型中具有自适应安全性；随后，Mamta 等［13］利用支持AND、OR、NOT 等所有布尔运算的简化有序二元决策图构造支持非单调通用树型（General Tree）访问结构的关键字搜索方案，且保持私钥和搜索令牌的长度恒定；Mamta 等［14］基于密文策略属性加密框架，设计支持“与”门访问结构的关键字搜索方案，具有恒定的私钥和密文长度。然而，以上三类方案均不支持数据共享功能。Ge 等［15］提出了一种基于密文策略属性加密的关键字搜索方案，同时支持基于属性的关键字搜索和数据共享，且关键字在共享阶段可更新；但是，该方案的解密计算量随着属性个数的增加呈线性增长趋势，且包含双线性对运算，这极大限制了方案在资源受限环境中的应用。由于细粒度密文搜索的计算负担较重，通常不适用于电池寿命或内存等资源有限的场景；然而，随着移动云计算的出现，移动设备已成为大多数人必不可少的计算工具，因此，解密计算复杂度高的属性基关键字搜索方案已无法满足移动设备或者弱终端用户的需求。为减轻终端用户的计算负担，可将解密过程中高度复杂的运算外包给云服务器，同时确保不泄露密钥或明文信息，即实现外包解密。现有诸多属性加密方案［16-21］均支持外包解密，且多数建立在经典的属性加密方案基础之上。将支持外包解密的属性加密方案与密文关键字搜索技术相结合，可构造支持外包解密的关键字搜索方案。Cui 等［22］和Xu 等［23］分别提出了支持在线/离线加密和外包解密的关键字搜索方案，降低终端用户在线加密和解密成本，并证明方案具有数据和关键字的不可区分安全性；但以上方案仅支持单调访问结构，且未对服务器的搜索结果进行有效检验，而执行搜索过程的第三方服务器是不可信任的，存在恶意操作的可能，假如因此而导致搜索结果不正确，将在实际应用中造成不可预估的后果。

本文基于属性加密提出支持非单调访问结构的密文关键字搜索方案，分别根据属性集和访问策略所含属性构造对应多项式，并以多项式是否满足整除性质确定属性集与访问策略之间的匹配关系，从而实现密文细粒度搜索访问权限的设置。该方案同时具备密文细粒度搜索和数据共享功能，并支持外包解密操作，即将解密过程中复杂度高的计算交由云服务器处理，简化最终密文形式，以满足弱终端用户搜索访问的需求。此外，借鉴文献［18，20］方案中关于外包解密验证机制的设计思路，通过在密文中增加绑定密文和关键字的承诺值实现对云服务器搜索结果的正确性检验。可以证明本文方案在随机预言机模型中关于选择密文攻击具有选择性的不可区分安全性（INDistinguishability under Chosen Ciphertext Attack，IND-CCA），即选择IND-CCA 安全性；关于选择关键字攻击也具有选择性的不可区分安全性（INDistinguishability under Chosen Keyword Attack，INDCKA），即选择IND-CKA 安全性。

1 预备知识

1.1 双线性映射

设G1、G2、GT均为素数p阶乘法群，其中G1、G2是椭圆曲线上的循环群，e：G1×G2→GT是满足以下条件的双线性映射：

1）双线性性：对于任意g∈G1，h∈G2，a，b∈Zp，有e(ga，hb)=e(g，h)ab。

2）非退化性：若g、h分别是G1、G2的生成元，则e(g，h)是GT的生成元。

3）可计算性：对于任意g∈G1，h∈G2，存在一个有效算法计算e(g，h)。

1.2 扩展多指数序列判定Diffie-Hellman假设

扩展多指数序列判定Diffie-Hellman（augmented Multi-Sequence of Exponents Decisional Diffie-Hellman，aMSE-DDH）假设对应的(q1，q2，n)-aMSE-DDH 问题［24］描述如下：

设G1、G2、GT均为素数p阶群，e：G1×G2→GT是双线性映射，g0、h0分别是群G1、G2的生成元。令φ(x)和ψ(x)分别为q1和q2次互素多项式。给定：

其中：α，γ∈Zp；T∈GT。解决(q1，q2，n)-aMSE-DDH 问题就是判定T等于e(g0，h0)γφ(α)或等于GT中的随机元素。

定义1aMSE-DDH 假设。如果任意t-多项式时间敌手，至多以ε的优势解 决(q1，q2，n)-aMSE-DDH问题，则称(q1，q2，n)-aMSE-DDH 问题是(t，ε)困难的。

1.3 访问结构

设U={A1，A2，…，An}为系统属性集，S⊆U表示与用户相关联的属性集合，P⊆U表示与密文相关联的“与”门访问策略。下面分别用n比特二进制串表示U中各属性Ai是否归属S或P，并给出属性集S满足访问策略P的定义。

2 可搜索属性加密方案

2.1 系统模型

本文方案的系统模型如图1 所示，执行算法的实体包括可信授权机构（Trusted Authority，TA）、云服务器（Cloud Service Provider，CSP）、数据属主（Data Owner，DO）和用户（Data User，DU）。

图1 系统模型Fig.1 System model

1）可信授权机构（TA）负责选定安全参数，生成系统公共参数PP和私钥，并向各实体发布PP。当用户（DU）提交关键字Wu的搜索请求时，将自身属性集S发送给TA，TA 根据用户属性特征生成对应的搜索陷门TPS并发送给云服务器（CSP），同时将数据恢复密钥RKS发送给用户。

2）数据属主（DO）负责对数据和关键字进行加密。通过设计恰当的访问策略P，利用属性加密方法生成密文CTP，实现密文搜索的细粒度权限设置，并将密文上传至云服务器（CSP）。

3）云服务器（CSP）负责密文关键字搜索和外包解密。CSP 用搜索陷门TPS执行细粒度搜索算法，该算法包括关键字搜索和外包解密两个阶段。当用户属性满足密文关联的访问策略时，执行第一阶段的关键字搜索，检验用户提交的关键字与密文关键字是否匹配；若匹配成功，则执行第二阶段的外包解密，即在不泄露密钥或明文信息的前提下，有效处理解密过程中计算复杂度高的部分，并将简化密文CT'P发送给终端用户。

4）用户（DU）负责对搜索结果进行正确性检验并解密。收到简化密文CT'P之后，用户（DU）用数据恢复密钥RKS执行自带验证的解密算法，对搜索结果进行正确性检验，若检验通过，则可获得明文数据。

2.2 具体方案

本方案包括系统建立算法、陷门生成算法、加密算法、密文搜索算法和自带验证的解密算法等。各算法具体描述如下：

1）Setup（λ，U）：系统建立算法。输入安全参数λ和属性空间U，TA 首先选取素数p(p∈Θ(2λ))阶乘法循环群G1、G2和GT，其中g∈G1，h∈G2分别为G1、G2的生成元；接着定义双线性映射e：G1×G2→GT，计算e(g，h) ∈GT；然后，随机选取w1，w2∈G2，α∈，计算{gi=，hi=，i=1，2，…，n}，并选取抗碰 撞Hash函数H0，H1，H3，H4：{0，1}*→，H2：GT→{0，1}3λ。最 终，TA 输出系统 公共参数PP=(G1，G2，GT，p，e，e(g，h)，h，w1，w2，H0，H1，H2，H3，H4，{gi，hi}1≤i≤n)，保存主私钥MSK=(g，α)。

2）Trap_KeyG（PP，MSK，Wu，S）：陷门生成算法。输入系统公共参数PP，主私钥MSK，搜索关键字Wu，以及用户属性集合S。设BS=a1a2…an，TA 首先在Zp[x]中定义多项式函数：

并计算：

3）Encrypt（PP，M，Wm，P）：加密算法。输入系统公共参数PP，明文数据M及其关键字Wm，以及访问策略P⊆U(|P|≠0)，其中|P|表示P所含属性个数。设BP=b1b2…bn，其中至少存在一个bi=1，数据属主在Zp[x]中定义n-|P|次多项式函数：

则必有n-|P|≤n-1。设n-|P|+1 次多项式函数：

其中fi表示xi的系数。

4）Search_Trans（PP，CTP，TPS）：密文搜索算法。输入系统公共参数PP，密文CTP，用户搜索陷门TPS；其中，搜索陷门对应属性集二进制表示为BS=a1a2…an，密文对应访问策略二进制表示为BP=b1b2…bn。若存在i∈{1，2，…，n}，使得ai＜bi，则属性集S不满足访问策略P，服务器CSP 输出错误标识符⊥；否则，对于所有i∈{1，2，…，n}，均有ai≥bi。服务器CSP 计算ci=ai-bi（i=1，2，…，n），并在Zp[x]中定义多项式函数：

不难验证，F(x)关于未知量x至多n-|P|次，设

其中Fi∈Zp(i=0，1，…，n-|P|)，则

CSP 计算：

令CT'P=(C'，C3，C4)，CSP 输出简化密文CT'P。

方案正确性说明：若Wu=Wm，则

3 安全性分析

下面将证明所提方案在aMSE-DDH 假设下关于明文数据具有选择IND-CCA 安全性，关于搜索关键字具有选择IND-CKA 安全性。

定理1设H0，H1，H3，H4：{0，1}*→，H2：GT→{0，1}3λ为随机预言机，如果aMSE-DDH 假设成立，则所提方案具有选择IND-CCA 安全性。

学科实践活动的开发实施需要基于学科核心知识的功能价值，设计需要指向解决真实问题的主题学科实践活动，依托参观、调研、制作、实验等形式开展。

证明 假设存在敌手A 能在多项式时间内以不可忽略的优势ε攻破方案的选择IND-CCA 安全性，则可构造算法B以不可忽略的优势ε'在多项式时间内解决(q1，q2，n)-aMSEDDH 问题。

1）初始化阶段。A 发布挑战的访问策略P*(P*⊆U且|P*|≠0)，设其对应 二进制表示为BP*=b1b2…bn，则至少存在一个bi=1。随后，B 定义：

其中φ(x)和ψ(x)分别为|P*|次和n-|P*|次多项式函数。令q1=|P*|，q2=n-|P*|，则1 ≤q1≤n，0 ≤q2≤n-1。B 将φ(x)和ψ(x)发送给挑战者之后，得到(q1，q2，n)-aMSE-DDH问题的挑战实例：

在素数p阶双线性群(G1，G2，GT，p，e）中，给定：

B 随机选取w1，w2∈G2，再选取抗碰撞Hash函数H0，H1，H3，H4：{0，1}*→，H2：GT→{0，1}3λ，输出系统公共参数：

PP=(G1，G2，GT，p，e，e(g，h)，w1，w2，H0，H1，H2，H3，H4，{gi，hi}1≤i≤n)

3）第一次询问阶段。敌手A 提交多项式次下列询问：

a）H0询问：已知访问策略P*对应二进制表示为=b1b2…bn。若收到关于i∈[1，n]的询问，当bi=0 时，B 输出ψ(x)=0 的一个新根；当bi=1 时，B 输出φ(x)=0 的一个新根。

b）H1询问：若收到关于的询问，B 随机选取N∈，并作为H1值输出。

c）H2询问：若收到关于的询问，B 随机选取R∈{0，1}3λ，并作为值输出。

d）H3询问：若收到关于(M‖Wm)的询问，B 随机选取Q1∈，并作为H3(M‖Wm)值输出。

e）H4询问：若收到关于σ的询问，B 随机选取Q2∈，并作为H4(σ)值输出。

②搜索陷门询问：敌手A 提交关于属性集S和关键字Wu的搜索陷门询问，其中，S不满足访问策略P*。B 随机选取θ1，θ2∈，设：

并令：

由fφ(x，S)至少为1 次多项式函数可知，f1(x)、f31(x)和f32(x)分别为至多q1次和q1-1 次多项式函数，f2(x)、f41(x)和f42(x)分别为至多q2+1 次和q2次多项式函数且1 ≤q2+1 ≤n，于是可设：

B 隐含设定：

并计算：

③密钥询问：敌手A 提交关于属性集S和关键字Wu的密钥询问，B 维护列表LT，查询(S，Wu，TPS，RKS)是否已存在于列表中，若存在，则令SKS=(TPS，RKS)，并输出SKS；否则，输出错误标识符⊥。

④解密询问：敌手A 提交关于Encrypt（PP，M，Wm，P）所得密文的解密询问，B 维护列表LD，查询关于(P，M，Wm)对应密文的解密询问是否已经存在于列表中，若存在(P，M，Wm，σ，N，R，Q1，Q2)，则表示密文由随机数σ参与生成，B 输出M；否则，输出错误标识符⊥。此处假设合法密文通过解密询问都将得到正确答复。因为只要敌手执行合法的加密过程，就必须提交关于H0、H1、H2、H3、H4的Hash 询问，而其中的H4询问是关于加密过程所需随机数σ的询问。因此，上述假设是合理的。

5）第二次询问阶段。如同第一次询问阶段，敌手A 提交多项式次关于Hash 值、密钥、搜索陷门和解密的询问，其中，询问相关属性集S均不满足访问策略P*，且不能提交关于挑战密文的解密询问。B 按照第一次询问阶段的步骤，给出相应答复。

6）猜测阶段。敌手A 输出β'∈{0，1}。若关于T的H2询问出现在列表LH2中，则B 输出1，推断T=e(g0，h0)γφ(α)；否则，B 输出0，推断T为GT中随机元素。

定理2设H0，H1，H3，H4：{0，1}*→，H2：GT→{0，1}3λ为随机预言机，如果aMSE-DDH 假设成立，则所提方案具有选择IND-CKA 安全性。

说明 定理2 的证明过程，除了在两次询问阶段无密钥询问和解密询问，以及挑战密文不同之外，其余阶段均与定理1 证明过程中的相应描述相同。

4 性能分析

本文基于非单调访问结构，构造支持密文关键字搜索可验证的属性加密方案。下面将通过与文献中同类方案的功能和安全性，以及计算量作对比，分别从理论和实验两方面对所提方案的性能进行分析。

4.1 功能和安全性对比

本节对比分析所提方案与现有属性基密文关键字搜索方案在功能和安全性方面的优劣：功能方面主要考察数据共享、外包解密和搜索可验证等；安全性方面主要考察明文数据安全和关键字安全。

根据功能和安全性指标，将本文方案与文献［12-15，23］方案作对比分析。如表1 所示，文献［12-14］方案均支持非单调访问结构，且文献［12］方案具有选择策略的IND-CKA安全性，但三类方案均不支持数据共享、外包解密和搜索验证等功能，而本文所提方案能同时实现密文关键字细粒度搜索和加密数据共享，且支持外包解密和搜索可验证。文献［15，23］方案均支持基于线性秘密共享体制（Linear Secret Sharing Scheme，LSSS）的访问结构，且文献［15］方案关于数据能达到选择IND-CCA 安全性，文献［23］方案具备数据共享和外包解密的功能，但两类方案均未能提供对搜索结果的有效检验。相比而言，本文方案支持AND 访问结构，能同时实现对密文的细粒度搜索、密文数据共享和外包解密；借助服务器，最大限度地减轻终端用户的解密负担，且无需依赖交互即可实现方案的搜索可验证功能，从而能对第三方服务器的搜索结果和外包解密结果进行有效检验。安全性方面，本文方案能达到关于明文数据的选择IND-CCA 安全性和关于关键字的选择IND-CKA 安全性，即本文方案在增加搜索可验证和外包解密两项功能的同时，达到甚至超过文献同类方案的数据安全性级别，且仍能保持密文关键字的不可区分安全性。

表1 几种方案的功能和安全性对比Tab.1 Comparison of function and security among several schemes

4.2 计算量对比

将所提方案与文献同类方案的计算量进行对比分析，主要考察由数据属主执行的加密算法，用户参与的解密密钥和陷门生成算法，以及终端用户执行的解密算法等。

如表2 所示，关注方案的加密算法、陷门生成算法，以及解密算法中模指数运算和双线性对运算次数，其中，TE、TP分别表示模指数、双线性对运算次数，n、n1、m、m1、|P|、|V|分别表示属性空间中属性数、用户属性集所含属性数、线性秘密共享矩阵行数、解密时所用矩阵行数、访问策略中所含属性个数、从根节点到终端节点的所有合法路径数。与文献［12-14］方案相比，本文方案在增加数据共享功能的情况下，仍保持相对较小的计算量；与文献［15］方案相比，本文方案的各算法计算量均相对较低，且解密算法仅需要3 次模指数运算，计算量不随属性个数的增加而增加；与文献［23］方案相比，本文方案的加密计算量较小，但解密算法多1 次模指数运算，文献［23］方案基于单调访问结构LSSS 构建而成，同时支持密文关键字搜索和外包解密，但不具备密文搜索可验证功能。

表2 几种方案的计算量对比Tab.2 Computational amount comparison among several schemes

为进一步比较效率，本文基于开源代码库Charm［25］，利用224 位MNT 椭圆曲线进行仿真实验，在配置为1.19 GHz Intel Core i5-1035G1 CPU 和16 GB RAM 的笔记本电脑上，运行64 位Ubuntu 18.04，用Python 3.8 编程实现方案的5 个算法。通过设置属性数为20 至200，分别计算系统建立算法、陷门生成算法、加密算法、密文搜索算法和解密算法的平均运行时间，这些时间值通过固定属性数，执行算法10 次并取平均值得到。实验结果如表3 所示。

表3 各算法的平均运行时间 单位：sTab.3 Average running time of each algorithm unit：s

将上述算法的平均运行时间用图形直观呈现，如图2 所示。实验结果表明：所提方案的系统建立时间、陷门生成时间、加密时间和密文搜索时间均随着属性个数的增加呈线性增长趋势，其中搜索时间相对较短，增长速度相对较慢，当属性数达到200 时，密文搜索时间大约0.7 s。终端解密时间与属性个数无关，始终保持在12.9 ms 左右。

图2 各算法的时间消耗Fig.2 Time consumption of each algorithm

5 结语

本文基于非单调访问结构，提出支持细粒度密文关键字搜索和数据共享的属性加密方案，增加密文搜索可验证的功能，检验云服务器是否诚实可靠地执行搜索算法。同时，为减轻终端用户的解密负担，在算法中增加外包解密操作，借助云服务器的计算能力预先处理解密过程中高度复杂的计算，终端授权用户仅需3 次模指数运算即可获得明文。可以证明所提方案在随机预言机模型中关于明文数据和关键字均具有选择性的不可区分安全性。理论分析和实验结果表明，本文方案与文献同类方案相比，在增加密文搜索可验证和外包解密两项功能的同时，保持拥有与文献同类方案同等级别的安全性和相当甚至更高的计算效率。