云存储中支持属性撤销的多关键词可搜索加密方案

黄保华，黄丕荣，赵伟宏，彭 丽

（广西大学计算机与电子信息学院，南宁 530004）

0 概述

随着互联网技术的快速发展，用户对数据处理和数据存储的需求日益增加。为满足高效的数据处理能力和海量数据存储的需求，选择将个人或企业的数据外包给云存储服务器是当前流行的做法，但是当用户将数据存储在云端时，服务器并非完全可信，有可能工作在半可信或者恶意的模型下。半可信模型是指服务器试图通过与用户的交互获取敏感信息，恶意模型是指服务器除了会试图获取用户信息，还有可能破坏协议的执行或者破坏数据的完整性和正确性。在这种数据外包的背景下，不可避免地会带来数据的隐私性和安全性等方面的问题。

为防止非授权用户访问数据进行非法操作，在外包数据之前，可以先对其进行加密，最后以密文的形式交由云服务器进行存储管理。但这样会限制外包数据的可用性，加密后的数据不能再根据原来的明文索引进行检索，传统的明文检索方案不再可行。因此，在对密文数据进行检索的同时保证关键词隐私，成为当前亟待解决的问题，可搜索加密技术应运而生。

本文将密文策略基于属性加密与关键词搜索相结合，提出一种支持属性撤销的多关键词可搜索加密方案。该方案支持连接关键词搜索，可提供灵活的多关键词搜索功能。针对可能存在的访问策略动态变化问题，能够对过期非授权用户进行属性撤销操作，使其更接近于真实场景需求。相对于效率较低的树形访问结构，本文采用具有强表达能力的线性秘密共享方案作为访问结构。

1 相关工作

可搜索加密代表性的方案是SONG等［1］在2000年提出的线性扫描算法，由于此方案每进行一次检索都要扫描单篇文档的关键词集合，检索效率较低，并且容易暴露关键词在文档中的位置信息，因此易受到关键词统计攻击。其搜索开销与文档数、关键词总数成正比，当文档数和关键词总数特别大时，该方案在实际应用中的搜索效率较低。此后学术界有很多研究人员从功能性、安全性、搜索效率等方面对可搜索加密方案进行改进。KAMAR 等［2］提出支持文档动态更新和密态索引动态构建的密文检索方案，该方案在更新用户数据时，不需要重构索引，通过扩展倒排索引，设计一个关键词搜索字典，以此来达到次线性的搜索时间。CURMOLA 等［3］分别在自适应的非自适应模型下设计具有高安全性和高效率的对称加密关键词搜索方案。

2005 年，SAHAI 等［4］提出一种基于属性的加密方案。在该方案中，用户的密文和密钥可以使用一组属性来标识，如用户的性别、年龄、工作等信息可以视为一组属性。只有解密者拥有的属性符合嵌入密文的属性组时，解密者才能正确解密密文。2008年，WATERS等［5］用线性秘密共享（Linear Secret-Sharing Scheme，LSSS）矩阵表示密文的访问控制结构，相比树形的访问控制结构，LSSS 在拥有相同性能和功能情况下有更好的表达能力，该基于属性的加密方案具有高效和可证明安全的特点。由于加密文件的访问策略是动态变化的，用户属性也是动态变化的，为应对这种属性动态变化的需求，文献［6-8］提出一种支持用户属性自动撤销基于属性加密的解决方案。由于基于属性加密的加解密算法计算量大，对于移动设备等计算力受限的设备来说是沉重的计算负担，也会加快设备电池的消耗，为平衡设备的计算量和加密方案的安全性之间关系，文献［9］提出将复杂计算外包给第三方服务器的基于属性加密方案，能在一定程度上减轻轻量型设备的计算负担。以上的方案仅提供了数据加解密功能，并没有实现加密数据的搜索和共享功能，将基于属性加密运用在关键词搜索中是其应用场景之一。

传统的可搜索加密方案没有考虑到用户的搜索权限，不能对加密的文件进行细粒度的访问控制，并且由于运用对称加密技术，仅适用于一对多场景且存在泄露密钥的风险。结合基于属性加密技术，可搜索加密方案能够在实现关键词搜索的同时，又能够实现加密文件的细粒度访问控制。曹素珍等［10］借助区块链技术防篡改、去中心化的优势，将密态索引存储于区块链，加密数据存储于云服务器，构造一个可验证基于属性的多关键词搜索方案，系统的密钥可安全地在公开信道传输。MICHALAS 等［11］将对称可搜索加密与基于属性加密技术相结合，构造一个混合加密的可搜索加密方案，该方案既具有对称可搜索加密方案高效检索的特点，又能对用户进行访问控制。YIN 等［12］提出密文策略基于属性（CPABE）的可搜索加密方案，由于该方案只能进行单关键词搜索，因此会使服务器返回的搜索结果包含大量不相关的内容而浪费网络带宽，或者因为进行多轮搜索而增加通信开销。宋衍等［13］提出一种基于属性加密的支持关键词任意连接的搜索方案，该方案使用多项式方程实现对非结构化数据的多关键词连接搜索，但不支持用户的属性撤销。陈燕俐等［14］提出一个密文策略基于属性加密的关键词搜索方案，该方案支持用户属性撤销但不支持多关键词检索，且属性撤销时需要同时更新用户密钥和密文信息。

针对移动设备计算力有限的情况，文献［15-17］引入加解密离线/在线的思想，离线阶段提前进行了大部分的计算工作，有效减轻了客户端的计算负担，但是这些方案都不支持属性的撤销。SUN 等［18］提出可验证性的基于属性的密文检索方案，该方案支持用户属性撤销，在多对多场景下授权机构能对服务器返回的结果进行验证，但该方案存储开销较大且计算效率不高。孙瑾等［19］提出结果可验证的多关键词搜索加密方案，但该方案的访问结构使用的是效率较低的树形结构。邓志辉等［20］提出基于双线性对的可搜索加密方案，该方案能够抵抗外部关键词猜测攻击，但是该方案不能支持用户的访问控制，也缺少实验进行论证。

2 预备知识

2.1 双线性映射及困难性假设

定义1（双线性映射）G、GT表示阶为素数p的乘法循环群，g∈G满足下述要求，则其为有效的双线性映射。

1）双线性：∀h1,h2∈G,a,b∈Zp,=e(h1,h2)ab。

2）非退化性：e(h1,h2)≠1。

3）可计算性：∀h1,h2∈G，存在多项式时间计算e(h1,h2)。

定义2（q-DPBDHE 假设）令G、GT表示阶为素数p的乘法循环群，g∈G为生成元，e：G×G→GT为有效的双线性映射，随机选取a,s∈Zp,T∈GT。给定元组：

q-DPBDHE 假设是指不存在多项式时间的算法以不可忽略的优势判定是否成立，其中T为GT中随机元素，q-DPBDHE假设最早在文献［21］给出定义和安全性证明。

2.2 访问结构

定义3（访问结构）令P={P1,P2,…,Pn}为用户集合，访问结构A⊆2P是集合2P的一个非空子集。如果对于任意集合B和C，B∈A且B⊆C，有C⊆A，那么称A是单调的访问结构。访问结构A中的集合称为授权集合，否则称为非授权集合。

2.3 线性秘密共享方案

若一组参与方P上的线性秘密共享方案Π 满足下述条件，那么它是线性的。

1）每个参与方的线性共享份构成一个Zp上的向量。

2）对于秘密共享方案Π，存在一个秘密共享份生成矩阵Ml×n，函数ρ：{1,2,…,l}→Pi将Ml×n中的第i行映射到参与方的集合中。令s∈Zp表示待共享的秘密值，随机选取组成向量v=(s,r2,…,rn)。MvT表示秘密值s的l个共享份，其中λi=(MvT)i表示第i个共享份，将λi分配给参与方ρ(i)。

秘密共享方案满足线性重构性质：令Π 表示一个线性秘密共享方案，S为其一个授权集，集合I定义为I：{i：ρ(i)∈S}⊆{1,2,…,l}，存在多 项式时 间算法计算{ωi∈Zp}i∈I，使对Π 上的有效共享份成立。

2.4 系统模型

系统中包括云服务器（Cloud Server，CS）、授权机构（Authorized Authority，AA）、数据拥有者（Data Owner，DO）、数据使用者（Data User，DU）4 类实体。

1）CS：储存加密的文件并提供关键词的搜索服务。根据授权机构的重加密密钥，对加密的索引进行重加密，以此达到更新访问权限的目的。同文献［14］的方案，假定云服务器诚实且好奇，即云服务器会诚实地执行用户提交的任务，但是可能会通过用户提交的数据推断出额外的信息。

2）AA：负责系统建立、用户密钥生成、根据访问策略更新重加密密钥、撤销用户属性等工作，AA 是可信的第三方机构。

3）DO：首先将文件加密，从该文件中提取m个关键词，根据这些关键词使用下文的索引生成算法生成索引，然后使用对称加密算法将文件加密，最后将密态文件和索引一起放至CS 存储，提供CS 原始数据以进行搜索操作。

4）DU：根据需求向CS 发起关键词搜索请求，并获得相应的检索结果。

本文方案的工作流程如图1 所示。

图1 本文方案工作流程Fig.1 Working procedure of the proposed scheme

2.5 算法描述

一个支持用户属性撤销的多关键词搜索方案由以下6 个算法组成：

1）Setup(1λ,U)→(PK,MSK)。为系统建立算法，由AA 运行，输入安全参数λ和系统总体属性集合U，输出公钥PK 和主密钥MSK。

2）KeyGen(PK,MSK,S)→SK。算法输 入公钥PK、主密钥和用户属性集S，输出用户的个人私钥SK。

3）Index(PK,MSK,D,(M,ρ))→INDEX。算法输入公钥PK、用户主密钥MSK、文档集合D和访问结构(M,ρ)，输出加密索引INDEX。

4）Trapdoor(PK,SK,SKW)→TD。算法输入公钥PK、用户私钥SK 和查询关键词集合SKW，输出查询陷门TD。

5）ReEnc(INDEX,RK)→INDEX'。算法输入加密索引INDEX 和重加密密钥RK，输出重加密索引INDEX'。

6）Search(INDEX',TD)→SR。算法输入重加密索引INDEX'和查询陷门TD，输出搜索结果SR。

2.6 安全模型

本文通过敌手A 和挑战者C 之间的交互式攻击游戏，给出本文方案的选择关键词攻击下不可区分性（IND-CKA）安全模型。

初始化敌手A 提交待挑战的访问结构(M*,ρ*)给挑战者C。

系统建立挑战者C 运行系统建立算法，将生成的公钥PK 和系统重加密密钥RK 发送给敌手A。

阶段1敌手A 发起以下询问。密钥询问：敌手A 选取属性集合S={S1,S2,…,Sn}，其中S不满足访问结构(M*,ρ*)，挑战者C根据A提交的S运行密钥生成算法，将生成的密钥SK 发送给敌手A。陷门询问：敌手A 向挑战者C 询问关键词集合SKW 的陷门，C 将SKW 添加到关键词列表LSKW中，C 生成SKW的陷门返回给A。

挑战A 选择2 个待挑战的关键词集合KW0、KW1，将其发送给C，要求LSKW中没有(KW0KW1)∪(KW1KW0)中的任何关键词子集。C 随机选择β∈{0,1}，生成挑战索引indexKWβ。

阶段2A 重复阶段1 发起的询问。要求在密钥询问过程中，S不满足访问结构(M*,ρ*)，在陷门询问过程中，不能询问(KW0KW1)∪(KW1KW0)中任何关键词子集的陷门。

猜测A 输出对β的猜测β'，如果β=β'，则A 赢下这个游戏，A 在游戏中获胜的优势被定义为

定义4如果任何多项式时间的A 以可以忽略的优势赢得以下安全游戏，则本文提出的基于属性加密支持用户属性撤销的多关键词搜索方案是IND-CKA 安全的。

3 方案构造

3.1 本文方案具体构造

本文方案使用的部分符号描述如表1 所示。

表1 符号定义Table 1 Notations definition

本文方案具体构造如下：

1）Setup(1λ,U)→(PK,MSK)。该算法 输入安 全参数λ，设G是阶数为素数p的循环群，g为其生成元，e：G×G→GT表示一个双线性映射。首先AA 随机选取α,a,b∈作为用户的主密钥MSK。U是系统的全体属性集合，对于i∈U，AA 随机选取fi,di∈，随后计算出RK。算法输出公共参数PK、主密钥MSK 和重加密密钥RK，如式（1）所示：

2）KeyGen(PK,MSK,S)→SK。该算法为用户的秘钥生成算法，由AA 运行。算法输入公共参数PK、主密钥MSK 和用户的属性集合S。AA 随机选取t∈，然后计算出K=gα gat和L=gt。对于x∈S，计算Kx=。算法输出用户私钥SK={K,L,Kx}，如式（2）所示：

3）Index(PK,MSK,D,(M,ρ))→INDEX。该算法为索引的生成算法，由DO 运行。输入公共参数PK、主密钥MSK、文件集合D=(d1,d2,…,dp)以及访问结构 (M,ρ)。Ml×n为秘密生成矩阵，函数ρ：{1,2,…,l}→Pi将矩阵Ml×n中的第i行映射到参与方的集合中。DO 随机选取向量v=(s,y2,…,yn)∈Zp，其中s为秘密分享值。对于i∈[1,l]，计 算λi=v.Mi。对于j∈[1,n]，DO 提取每个文件dj的m个关键词，假设单个文件的关键词集合KW={KW1,KW2,…,KWm}，构 造m级多项 式 ：f(x)=d(x-H(KW1))(x-H(KW2))…(x-H(KWm))+s=am xm+am-1xm-1+…+a1x1+a0，aj对应为m级多项式的系数。DO 随机选取r1,r2,…,rl∈Zp，为每个 文件构 造索引 项indexk={(Ml×n,ρ),C,C',{Ci,Di|i∈[1,U]},{Ej|j∈[0,m]}}，如 式（3）所 示。算法输出加密索引INDEX={indexk|k∈[1,p]}。

4）Trapdoor(PK,SK,SKW)→TD。该阶段为数据使用者的查询阶段，H：{0,1}*→G是一个抗碰撞的哈希函数。假设待查询的关键词集合为：SKW={SKW1,SKW2,…,SKWm'}（m'为查询 关键词的数量）。数据使用者分别计算K'和Fi|m'i=0，算法输出关键词的搜索陷门TD=(K',{Fi}m'i=0)，如式（4）所示：

5）ReEnc(INDEX,RK)→INDEX'。该阶段为授权机构根据数据使用者的属性对索引的重加密阶段。对于访问结构(Ml×n,ρ)，i∈[1,l]，如果ρ(i)∈S，则授权机构根据重加密密钥RK 计算如果ρ(i)∉S，那么Di=D'i。算法输出INDEX'={index'k|k∈[1,p]}。

6）Search(INDEX',TD)→SR。该阶段为云服务器的搜索阶段，在接收到数据使用者的搜索陷门TD后，云服务器首先检查数据使用者的属性集合S是否满足数据拥有者制定的访问结构(Ml×n,ρ)，满足时继续执行以下操作，否则返回⊥。

（1）令I={I：ρ(i)∈S}表示满足访问结构的最小属性集合，云服务器按照式（5）分别计算T1、T2、T3，其中

（2）验证等式T2=T1T3是否成立，若成立，则所检索的文件包含用户查询的关键词，若不成立，则该文件不是用户检索的文件。

3.2 方案正确性

本节从以下2 个方面对方案的正确性进行论述：只有当用户的属性集满足数据拥有者构造索引时所嵌入索引的访问策略，则云服务器检索行为才会继续，否则停止检索协议；只有当数据使用者选取的多个关键词都在数据拥有者设置的关键词集合内，才会返回正确的检索结果，否则返回⊥。

1）访问控制。根据线性共享方案的线性重构性质，若检索用户的属性集合满足嵌入密态索引INDEX的访问策略，秘密值s能由有效的共享份λi重构，即成立，否则秘密值s不能由共享份恢复。T1的值计算如下：

2）关键词检索。根据索引构造的多项式f(x)=d(x-H(KW1))(x-H(KW2))…(x-H(KWm))+s。若 数据使用者选取的关键词SKW={SKW1,SKW2,…,SKWm'}都在数据拥有者设置的关键词集合KW={KW1,KW2,…,KWm}内，则多项式f(x)的值才为s。T3的值计算如下：

从以上推导的结果可知：T1=e(g,g)ats，T3=e(g,g)αse(g,g)bs，所以T1T3=e(g,g)αse(g,g)atse(g,g)bs。

故本方案是正确的。

4 安全性分析与证明

本文方案实现属性撤销的步骤如下：

1）授权中心将撤销的用户属性θ∈S发送给云服务器。

2）根据撤销信息，云服务器更新用户的属性集合。

3）当用户对存储在云服务器上的文件进行关键词搜索时，云服务器会根据用户属性集合运用重加密算法对索引进行重加密，最后再对重加密的索引进行搜索。

下文证明提出的方案满足陷门不可伪造性和关键词隐私性。

陷门不可伪造性：当攻击者要伪造陷门TD 时，需要构造出K'和Fi这2 个陷门的组成部分，要正确构造出K'需要获取用户的私钥，或者通过已有陷门推断出用户私钥b的值，但是在离散对数困难问题的假设下，攻击者无法求解出b的值。

索引隐私性：如果q-DBDHE 假设成立，并且挑战矩阵M*的大小为l*×n*，其中l*×n*≤q，则该方案满足选择模型下的IND-CKA 安全性。

证明假设本文方案在IND-CKA 安全游戏中是不安全的，那么存在一个多项式时间敌手A 能以不可忽略的优势赢得安全游戏，从而本文方案能构造出一个多项式时间的仿真器S 利用A 攻破q-DBDHE假设。

初始化仿真器S 接收q-DBDHE 挑战向量y和T，敌手A 将待挑战的访问结构(M*,ρ*)和x*提交给仿真器S，其中M*有l*行n*列，存在i使得ρ*(i)=x*。

系统建立 仿真器S 由以下步骤生成公共参数PK，仿真器S 随机选 取α'∈Zp，令α=α'+aq+1，则。对于属性1≤x≤U，S 随机选取值zx，令X表示使得ρ*(i)=x所有i的集合，若ρ*(i)=x，仿真器S计算否则仿真器S 将公开参数PK=(g,e(g,g)α,ga,F1,F2,…,FU)发送给敌手。

阶段1（密钥询问）敌手A 提交属性集，其中该属性集不满足访问结构M*。首先S 随机选取r,rk1,…,rkU∈Zp，w=(w1,w2,…,wn*)∈Zp，其 中w1=-1，对于所有使得ρ(i)∈S的i的集合，有令t为t=r+w1aq+w2aq-1+…+wn*aq-n*+1，有L=然后仿真器S计算K=如果不存在i使得ρ*(i)=x，则否则 存在i使得ρ*(i)=x，设X为使ρ*(i)=x成立的所有i的集合，计算：

陷门询问：根据A 提交的属性集，假设查询的关键词集合SKW={SKW1,SKW2,…,SKWm'}。S随后执行陷门生成算法Trapdoor，计算K'=K.gb，将生成的陷门TD=发送给A，将关键词集合SKW 添加到列表LSKW中。

阶段2阶段2 与阶段1 相同。但当A 提交的属性集合满足(M*,ρ*)时，A 查询的关键词集合不能是集合的子集。

猜测A 输出β'表示对随机数β的猜测。根据敌手的猜测，如果β'=β，仿真器回答T=e(g,g)aq+1s，此时索引是有效索引，否则仿真器回答T为群GT中的一个随机元素T∈GT，当T为群中的一个随机元素，关键词对应的索引是保密的，有

因此，当多项式敌手以不可忽略的优势ε攻破方案的IND-CKA 时，则存在仿真器的优势 攻破q-DBDHE 假设。

5 方案分析

5.1 功能比较

表2 选取一些具有代表性的基于属性的可搜索加密方案进行对比。从表2 可以看出，对比方案中的文献［12，18-19］均不能同时满足表中列出的3 个功能性要求，即不能同时满足属性撤销、支持多关键词查询和撤销用户属性时不需要更新用户密钥等要求。本文方案能同时满足以上3 个功能性要求且采用表达能力强的LSSS 作为访问结构，所以从功能性方面来比较，本文方案更占优势，使得本文方案更适于实际应用。

表2 不同方案的功能对比Table 2 Function comparison of different schemes

5.2 存储开销比较

为便于比较，下文定义一些用于存储开销的符号：|G|表示在群G中元素的比特长度；|Zp|表示在域Zp中元素的比特长度；|S|表示系统中用户拥有的属性个数；|N|表示系统中总的属性数量；m表示数据拥有者提取的关键词数量；t为用户提交的关键词数量。表3 给出了存储开销对比，从表3 可以看出，本文方案在涉及客户端操作的陷门生成算法的存储开销是对比方案中最小的，其能有效减轻通信带宽。

表3 不同方案存储开销对比Table 3 Comparison of storage overhead of different schemes

5.3 计算开销比较

群G和域Zp中的指数运算和配对运算比乘法运算和哈更加耗时，所以，以下的分析比较只考虑指数运算E和配对运算P。从表4 可以看出，基本上所有方案算法的计算开销与系统的属性数量或者与用户的属性数量成线性关系，但当t≪|S|或者t≪|N|时，也就是在系统属性数量和用户属性数量固定的条件下，当用户提交的关键词数量小于这两者数量时，本文方案的陷门生成算法的计算效率更高。

表4 不同方案的计算开销对比Table 4 Comparison of calculation overhead of different schemes

5.4 实验仿真

本文实验的硬件条件为：Intel Core i3-2348M 2.3 GHz @ CPU，4 GB RAM。操作系统为64 bit Ubuntu 18.04.3 LTS。实验基于Charm 架构，选取SS512 椭圆曲线。本文选取系统总体属性数量和用户属性数量为|N|=|S|∈[10,60]。

图2（a）～图2（c）分别描述了系统建立、密钥生成和陷门生成的时间开销。如图2（a）所示，通过对比3 个方案可以看出，文献［12］方案中系统建立算法的计算开销为2E+P，是一个常数，而其他2 个方案的开销随着系统属性个数N的增加而增长，本文方案的系统建立算法在对比方案中处于中等水平。如图2（b）所示，3 个方案密钥生成算法的时间代价都与系统属性数量成线性增长关系，但是本文方案的时间开销增长最慢，所以对于密钥生成算法而言，本文方案效率是最高的。图2（c）描述了陷门生成算法，本文方案的陷门生成只与用户提交的关键词数量相关。在给定关键词数量t=20 时，本文方案陷门生成的时间开销是一个常数，在t

图2 不同方案时间开销对比Fig.2 Comparison of time overhead of different schemes

6 结束语

本文提出一个基于属性的可搜索加密方案。采用LSSS 作为访问结构，提供多关键词搜索和用户属性撤销的功能，适用于云存储中数据的搜索与共享，并从陷门不可伪造性和关键词隐私性两方面对本文方案进行安全性分析，从存储开销和计算开销两方面与现有方案进行对比。理论分析和实验结果表明，该方案具有安全、高效、灵活等特点。但是本文方案并不支持用户对搜索结果的正确性进行验证，并且不能隐藏同为敏感信息的访问策略，因此设计结果可验证、隐藏访问策略、可动态更新的基于属性加密的关键词搜索方案将是下一步的工作。