支持灵活访问控制的多关键字搜索加密方案

闫玺玺，赵 强，汤永利，李莹莹，李静然

(河南理工大学 计算机科学与技术学院，河南 焦作 454003)

目前，云服务已经成为数据外包和共享的一个普遍和经济的平台，大多数用户(包括企业用户和个人用户)都使用云服务对数据进行存储和管理。但是当数据迁移到云服务器后，用户会失去对数据的直接控制。为了保护数据的安全，在外包之前对数据进行加密以确保数据的隐私。然而，通过加密的形式外包数据，如何有效地访问数据成为了新的难题，从而催生了可搜索加密。文献[1]首次提出可搜索加密概念，将文件划分为单词并逐个加密，在检索时单词与密文进行扫描对比，查看密文中是否包含要查询的关键字，但随着文件数量的增加，服务器的计算开销也会增大。为了解决与密文进行比对的问题，文献[2]通过布隆过滤器将加密之后的关键字映射为比特到索引表中，搜索时只需将陷门同样也映射成比特与索引表匹配即可。之后，可搜索加密方案对于检索方式的研究得到飞速的发展。文献[3]实现了多关键字查询，并通过双关键字索引结构提高了搜索效率。文献[4]采用潜在狄利克雷分布(Latent Dirichlet Allocation，LDA)模型实现了基于语义的多关键字搜索，改进了TF-IDF(Term Frequency-Inverse Document Frequency)模型中忽略了关键字与文档之间的语义关联的缺点。文献[5]实现了模糊关键字搜索，解决了精确搜索中无法接受关键字具有轻微拼写错误和格式不一致的问题。

检索方式的多样性使检索效率和精确率都得到了提升，但仍然无法避免在检索过程中陷门与所有加密索引进行对比。文献[6]通过提取关键字，根据关键字的相似性将相似文档聚类在一起，列出簇中所有的关键字，并通过安全散列算法计算得到关键字的哈希值发送给数据拥有者。在检索时，比较簇索引的哈希值和陷门哈希值‘0’的位置来找到匹配的簇。该方案解决了检索文件时陷门与所有索引比较时开销过大的问题，但是它忽略了关键字在文档中的比重和每个簇的主题分布。文献[7]使用k均值聚类(k-means clustering，k-means)算法对文档进行聚类，通过计算其他文档与质心的欧氏距离来进行聚类，提高了相同簇中文档的相似性。文献[8]首次提出使用潜在狄利克雷分布模型和k均值算法来解决隐私保护问题。

在实际应用场景中，可搜索加密机制需要为用户提供相应的搜索权限，以使不同的用户可以访问不同的文件。最基本的解决方案是数据所有者使用不同的密钥加密不同的文件。之后，数据所有者给每个用户授权搜索的所有文件的加密/解密密钥，显然这个方法是繁琐且低效的。文献[9-10]提出了一个基于属性的可搜索加密的方案，将私钥、密文与属性和访问结构相关联，陷门由用户私钥生成。在检索过程中，当文档的关键字索引和访问结构与陷门中的关键字和属性同时满足时，用户才可以从云服务器中获得密文并解密。为了进一步提升效率，采用对称加密的思想对文件和索引进行加密。文献[11]添加了一个对称密钥进行加密。用户在执行查询操作时，需要先解密对称密钥才能生成陷门。在上述两种方案中，密钥的大小取决于数据拥有者的访问控制策略中涉及的属性总数。文献[12]通过赋予授权证书来控制用户的搜索权限，每当新用户加入时，会为该用户提供一个具有关键字列表的授权证书并结合联合查询使用户只能对授权证书上的关键字进行查询。但是该方案采用了布尔查询，每次检索返回所有匹配的文档，可返回的文档中有很多是用户不需要的，且是无序的。由于下载了许多不必要的文件，且需要从检索的结果中删除不相关的文件，会导致通信成本的增加。文献[13]采用广播加密的方式，为每组用户提供可访问的加密文件，并允许用户在被授权访问的文件的子集内进行搜索关键字，但该方案不支持多关键字搜索。

为了满足云环境下数据共享时灵活的访问控制需求，且提高搜索效率，笔者提出了一种具有访问控制功能的高效可搜索加密方案。主要贡献如下：(1)为了减少搜索时间和保证搜索的精确率，使用k均值聚类算法将文档集分为若干个簇，并结合文献[8]中的文档主题提取技术为每个簇生成主题，计算每个关键字的权重以及关键字在该主题的分布概率，对每个主题用关键字集合进行表示，减小搜索集的大小，从而提高搜索效率。(2)采用广播加密体制在加密阶段为每组用户提供相应的访问权限，进而缩短每个用户的密钥长度，达到常数大小。(3)构造多关键字搜索方案，对索引隐私、文件隐私和标识符隐私进行保护，减少搜索操作中陷门与索引的对比次数。与其他方案进行对比表明，这种方案同时支持灵活的访问控制、多关键字搜索以及多客户端设置，并通过实验表明该方案在保证搜索精确率的情况下对搜索效率进行了优化。

1 预备知识

1.1 判定线性假设

1.3 广播加密的概念模型

广播加密方案的概念模型一般由以下4部分构成。

(1) 系统建立Setup(λ，n)：将安全参数λ和接收广播消息用户的最大数量n作为输入，输出系统主密钥K0和系统公钥集合K1，其中K0被私钥生成中心秘密保存。

(2) 私钥提取Extract(K1，K0，di)：将公钥K1、主密钥K0和用户身份di作为输入，输出用户对应的私钥Yi。

(4) 广播解密Decrypt(S，d，Yi，hk，K1)：将密文头(hk，S)、公钥K1、接收方身份d及其私钥Yi作为输入。如果d∈S，则输出会话密钥K2。当接收方要对密文主体Ck解密时，使用上述获得的会话密钥K2对Ck进行解密，输出消息明文M。

2 算法与安全模型定义

2.1 系统模型

该方案基于主题提取和聚类来减少搜索外包加密数据所需的比较次数，通过广播加密控制数据用户的访问权限。模型包含3个实体，分别是数据拥有者、用户和云服务器。

2.2 算法定义

Setup(n，λ)：算法将用户数量n和安全参数λ作为输入，输出(K1，{Y1，…，Yn})。K1是系统公钥集合，Yi是用户i的私钥。

Enc(K1，Wt，Sk，Mk，I(wi))：数据拥有者将文件Mk、簇的标识符Wt、公钥K1、用户集合Sk和关键字集合I(wi)作为输入，输出标识符密文Ck、文件密文C′k和加密关键字索引I′(wi)，上传到云服务器。

Trap(Yi，search query)：用户将私钥Yi和搜索查询作为输入，输出用户i对于搜索查询的陷门ti，W，发送给云服务器。

Test(K1，Sk，ti，W，Ck)：云服务器将标识符密文Ck、陷门ti，W、用户集合Sk、公钥K1作为输入，输出β∈{0，1}。如果i∈Sk且陷门中的关键字集合所对应的簇属于Ck，则输出β=1；否则，输出β=0。

Search(ti，W，I′(wi))：当β=1时，云服务器执行搜索算法，将相关性得分最高的前k个加密文件返回给用户；当β=0时，则返回⊥。

Dec(K1，Yi，C′k，Sk)：用户接收到加密文件，将公钥K1、私钥Yi和文件密文C′k作为输入，输出明文Mk。

2.3 安全模型

定义1(索引隐私) 如果敌手得到了一些加密的关键字索引和相关的私钥，敌手无法在多项式时间内学习到关于关键词的任何信息，则称满足索引隐私。

定义2(文件隐私) 通过挑战者C和敌手A之间的游戏，为本方案中的文件隐私定义静态语义安全。

初始化：A接收参数(n，λ)并且选择想要挑战的用户集合S0，明文消息M0，M1。

设置：C运行Setup(n，λ)算法获得公钥K1，然后将公钥K1发送给A。

问询：A自适应地发出对用户j∉S0的私钥查询。C将用户j的私钥Yj发送给A。

挑战：C选择一个随机数b∈{0，1}，运行加密算法Enc(S0，K1，Mb)获得密文C′，并将密文发送给A。

猜测：A要输出一个猜测b′∈{0，1}。当b=b′时，宣布敌手在游戏中获胜。

文件隐私游戏如果对所有攻击|Pr[b=b′]-1/2|≤Nnegl(λ，n)，则满足选择明文攻击(Chosen-Plaintext Attack，CPA)安全。

定义3(标识符隐私) 在本方案中，通过敌手A和挑战者C之间的游戏来定义标识符隐私的静态语义安全。敌手A和挑战者C将参数(n，λ)作为输入。

初始化：A接收安全参数λ，并输出希望挑战的用户集合S0和簇对应的标识符W0，W1。

设置：C运行Setup(n，λ)算法去获得公钥K1和一组私钥Y1，…，Yn，然后将公钥K1发送给A。

问询：A自适应地发出查询q1，…，qλ，其中qk是对用户i和关键字集合W的陷门查询。A进行陷门问询时，当且仅当i∉S0，且询问的关键字集合所对应簇的标识符Wk满足Wk≠Wb，b∈{0，1} 。对陷门查询，挑战者C运行陷门生成算法Trap(Yi，search query)→ti，Wt，获取ti，Wt发送给A。

猜测：C选择一个随机数b∈{0，1}，运行加密算法Enc(K1，Wb，S0)，输出(C0，S0)，其中Wb是簇的标识符。A要输出一个猜测b′∈{0，1}，当b=b′时，宣布敌手在游戏中获胜。

如果不存在多项式时间内A以不可忽略的优势区分不同簇下加密的标识符密文，则本方案满足标识符隐私。

3 方案构造

(1) 密钥生成

(1)

通过安全信道将私钥发送给用户i，私钥Yi=(di，1，…，di，14，u，v)。

(2) 语义聚类

聚类用于在创建索引之前将文档分为不同的簇。对文档进行聚类应减少每个簇的文档数量，以提高搜索过程的效率。为了执行聚类，数据拥有者将所有文档收集到一个数据集F={f1，f2，…，fA}中。然后，数据拥有者在F上应用k均值算法，生成k个簇，即L={l1，l2，…，lk}。lt是一组相似文档的集合，其中t=1，2，…，k。这意味着同一簇中的所有文档应尽可能地相似，并且不同簇中的文档应与所有其他簇中的文档尽可能不相似。

k均值算法作为划分式聚类算法，对于大部分数据都有较强的适用性。算法相对可伸缩，且计算简单、高效；空间复杂度较低，为线性复杂度。相对于同为划分式聚类算法的Single-Pass增量聚类算法，其对数据输入时的顺序十分敏感；基于层次的聚类算法相较于k均值算法，时间复杂度较高。文献[8]中的实验表明，k均值算法的搜索效率要高于层次聚类算法的；基于密度的聚类算法鲁棒性很强，但是结果的精度与参数设置关系密切，实用性不强。

具体流程如下：① 随机选择k个文档作为质心。② 计算各个文档到各个质心的欧氏距离。③ 将文档分配到距其最近的簇中。④ 分配完成后重新计算各类的质心，观察聚类是否收敛。若收敛，则完成聚类算法；否则，继续执行②至④步。

(3) 提取聚类主题和簇索引

主题建模是从文档集合中生成关键字。采用潜在狄利克雷分布算法为L={l1，l2，…，lk}中的每个簇生成关键字，这些关键字将作为每个簇的索引。

使用潜在狄利克雷分布算法进行文本收集的主题建模分4个步骤执行：① 从带有参数β的狄利克雷分布中选择多项式θt作为每个主题t的主题分布，其中β为每个主题词分布上的狄利克雷参数；② 对于每个文档f，从带有参数α的狄利克雷分布中选择一个多项式文档分布θd，其中α为每个文档主题分布上的狄利克雷参数；③ 为文档中的每个单词w选择来自θd的主题t；④ 从θt中选择一个单词w来代表文本文档的主题。生成主题的概率为

(2)

其中，K是主题的数量，θp是文档f的主题分布，β是在每个主题词分布上的狄利克雷参数，N是文档集中关键字的总数量，α是每个文档主题分布上的狄利克雷参数，ti是文档中第i个单词的主题，θ是文档的主体分布，wi是文档第i个关键字，φ是一个主题的单词分布。经过潜在狄利克雷分布算法处理后，每个簇会有该簇的关键字列表来表示该簇内文档的主要信息。定义该关键字列表为Wt={w1，w2，…，wk}，1≤t≤k，并将该关键字列表作为该簇的索引。

(4) 生成关键字索引

聚类结束后，数据拥有者使用潜在狄利克雷分布算法为每个簇创建一个索引，然后为每个簇内的文档创建关键字索引。本方案构造关键字索引时使用文献[14]中提出的索引技术，用排名功能来计算匹配文件与给定搜索请求的相关性得分。评估相关性分数使用的统计测量方法是TF-IDF规则。关键字索引创建步骤如下：

① 数据拥有者从文档集合F={f1，f2，…，fA}中对每个文档fi提取出对应的关键词集合wj={w1，w2，…，wm}，数据拥有者建立关键字索引I(wj)=d(fij)，1≤i≤p，1≤j≤m。

③ 将关键字的相关性得分添加到索引中，即I(wj)=(d(fij)‖(sij))。

(5) 加密阶段

(3)

(6) 陷门生成

Trap(ski，search query)→ti，Wt，用户i选取r，r′∈Zp计算(tr，1，tr，2，…，tr，5)。

(4)

(7) 权限控制

Test(K1，Sk，ti，Wt，Ck)→β，云服务器接收到陷门之后，检查下面的等式是否成立：

(5)

其中，T=e(hk，3，tr，3)e(hk，2，tr，2)e(hk，4，tr，3)。当该用户属于用户集合Sk中，且陷门中的簇标识符Wt与Ck中的簇标识符Wt相同时，等式成立，返回测试值β=1；否则，返回β=0。验证过程如下：

同理，可得

(8) 排名搜索

(9) 解密阶段

4 方案分析

4.1 安全性分析

定理1基于定义1，本方案满足索引的隐私保护。

综上所述，这种方法抵抗选择密文攻击是安全的。基于对关键字的加密方法及其对内部和外部敌手攻击的安全强度，以及选择密文攻击，本方案满足索引的隐私保护。

定理2主要构造在判定性-BDHE假设下具有文件隐私性。

初始化：A接收参数(n，λ)并且向C发送选择挑战的用户集合S0，明文消息M0，M1。

声明：当Z=e(g，v)时(即C的输入是从PBDHE采样的-BDHE元组中的)，μ=0。此外因此对A才是一个有效的挑战，如同在真实攻击中一样。另一方面，当Z是群G1中的一个随机元素(即C的输入是从RBDHE采样的)时，和只是G1中的随机独立元素。

猜测：A输出对于b的猜测b′。如果b=b′，则C输出μ′=0，表示Z=e(g，v)；否则，输出μ′=1，表示Z是群G1一个随机元素。

当(g，v，yg，α，，Z)是来自RBDHE的采样时，A不能获得Mb的有效密文，A只能纯粹猜测b的值，因此而当b≠b′时，C输出μ′=1，所以

当(g，v，yg，α，，Z)是来自PBDHE的采样时，A可以获得Mb的有效密文。由前面的假设可知，A攻破本方案的优势(即区分密文)是ε，因此而当b=b′时，C输出μ′=0，所以

综上所述，C攻破定性-BDHE假设的优势为

Adv-BDHE=

定理2证明完毕。

定理3(标识符隐私)本方案的主要构造在决策线性假设下具有标识符隐私性。

证明 敌手A对于簇关键字索引W0，W1，获得标识符密文Cb，输出猜测b′。若b=b′，则A挑战成功(用Succ来表示该事件)，挑战者C利用A来攻击判定线性假设。挑战者C接收一个决策线性实例g，gz1，gz2，gz1z3，gz2z4，Z，Z为gz3+z4或者是G中的一个随机元素，两者的概率是相等的。为了方便起见，将其改写为g，gz1，gz2，gz1z3，V，gt，gt=Z。游戏流程如下。

初始化：敌手A向挑战者C发送希望挑战的用户集合S0和簇对应的关键字索引W0，W1。

设置：挑战者选取随机元素α，γ，ζ，a2，b2和b←R{0，1}，使用与决策线性实例中相同的g，设置g1，…，gn，gn+2，…，g2n，υ，其中gi=gαi，υ=gγ，h0，1=g-Wb+，h1，1=g，h0，2=gz2(-Wb)g，h1，2=gz2。挑战者C设置

问询1：对(S，W)进行加密问询，其中W≠Wb。挑战者C选取，1，2计算出hk，1，…，hk，7发送给敌手A，计算方式如式(3)所示。

问询2：对(i，W)进行陷门问询，敌手A进行陷门问询时当且仅当i∉S0，且询问的关键字集合所对应簇的关键字索引Wk满足Wk≠Wb。挑战者C选取ρi1，ρ′i1，ρi2，ρ′i2，r，r′计算出陷门中的(tr，1，tr，2，…，tr，5)发送给敌手A，计算方式如式(4)所示。

挑战：挑战者C以簇对应的关键字索引Wb和集合S0作为响应。假设t1=z3，挑战者C随机选取t2∈Zp，输出密文。

猜测：令Γ0为事件敌手A输出一个字节b′来猜测标识符密文Cb是属于哪个索引的加密结果，如果b′=b，则输出为1；否则，输出为0。当输出为1时，挑战者C猜测B=gz2(t-z3)，Z=gt；当输出为0时，挑战者C猜测B独立于z1，z2，t，t1，t2时，Z是随机的。

分析：令D表示B=gz2(t-z3)，Z=gt；令R表示B独立于z1，z2，t，t1，t2时，Z是随机的。

再证明Pr[C(Γ0)=1|D]=Pr[S]，S表示成功。因为事件D发生时，B=gz2(t-z3)，Z=gt(z1，z2，t，t1，t2是随机选取的)，所以C输出1当且仅当成功。

Pr[C(Γ0)=1=0]=Pr[D]Pr[C(Γ0)=1=0|D]+Pr[R]Pr[C(Γ0)=1=0|R]=

即如果A能以某个不可忽略的优势ε区分不同簇索引下加密的标识符密文，则C可以以相同的优势攻破判定线性假设。

4.2 功能对比

将文中的功能特征与文献[8，13]中的方案进行对比，如表1所示。文献[8]中的方案支持多关键词搜索，使用了排名关键词搜索，并且通过减少陷门与索引的比较次数提高效率，但是文献[8]不具备访问控制功能和多客户端设置。文献[13]中的方案通过广播加密的方式，实现了多客户端设置，并在加密过程中将关键字一起加密实现访问控制，但是文献[13]中的方案只支持单关键词查询，而且每次查询需要将陷门与所有索引进行对比。

从功能方面来看，笔者提出的方案在实现访问控制和多客户端的前提下，改进了文献[13]中单关键词搜索的权限，并通过聚类后的优势减少了陷门与索引的对比次数。

表1 功能对比

4.3 计算开销分析

将文中的方案与文献[8，13]中的方案从计算开销方面进行分析比较。在方案对比中，E表示模指数运算，P表示双线性对计算，M表示群中模乘运算，X表示异或运算，H代表哈希运算，n代表文档数量，j表示用户数量，t表示陷门中的关键字个数。计算开销如表2所示。

由于文献[8]中的方案没有细粒度访问控制功能，所以无验证阶段并且不需要进行配对操作。文献[13]中的方案为单关键字可搜索加密方案，因此生成陷门的计算开销与关键字个数无关。笔者提出方案的主要优势是对文献[13]中的方案进行了功能性的扩展，并在搜索阶段减少搜索集的大小来提高搜索效率。搜索效率的提高将在节4.4中进行阐述。

表2 计算开销对比

4.4 实验分析

(1) 数据集和评估环境

数据集(https：//archive.ics.uci.edu/ml/datasets/NSF+Research+Award+Abstracts+1990-2003) 包含描述1990年至2003年NSF基础研究奖项的129 000个摘要，选择了3 000个摘要作为实验数据，并提取了226个不同的关键字。实验硬件环境为Intel Core i5-9300H，2.4 GHz，处理器内核数为4，内存为8 GB DDR4；软件环境是Windows 10 64位操作系统和PyCharm开发平台。本次实验的主要内容是计算聚类操作后返回正确文档的精确率以及对同一个可搜索加密方案进行聚类操作和未进行聚类操作的搜索时间对比。

在k均值算法中的聚类数目会影响搜索精度和搜索效率。聚类数目越小，每个簇的文档数量就会增加，搜索精度就越高，但搜索效率会下降；聚类数目越大，每个簇的文档数量就会减少，搜索精度就越低，但搜索效率会提升。因此，聚类数目的选取变得至关重要。为了保证每个簇中有一定的文档数量，将聚类数目的区间设置在5～20之间，并采用肘部法则，按照递增的顺序尝试不同的聚类数目，选取拐点作为聚类数目。经过实验测试，选择11为聚类数目。

(2) 搜索精度

表3 搜索精确率

(3) 搜索时间评估

将本方案对文档集使用聚类算法和不使用聚类算法两种情况的搜索时间进行对比，根据查询关键字个数(q)、文档数(m)和返回的文档数(k)评估和分析了搜索时间(Δt)。图1显示了CSP基于授权用户从陷门搜索文档所需的时间，搜索时间包括获取陷门中的关键字集合，并根据该关键字集合选择相似性分数最高的簇中，计算该关键字集合在每个文档中的分数。搜索时间随着查询关键字个数的增加而增加。如果对文档集不使用聚类算法，虽然不用计算关键字集合和簇索引的相似性分数，但由于是在整个文档集上进行搜索，当查询关键字个数为10时，搜索时间约为39.89 ms；当查询关键字个数为50时，搜索时间约为50.82 ms。当使用聚类算法后，搜索效率提高了约6倍，搜索时间分别约为5.53 ms和9.08 ms。

在图2中，设定文档总数为1 000，1 500，2 000，2 500，3 000。当未进行聚类操作时，可以发现文档总数越多，搜索时间就越长，且远高于聚类后的搜索时间。当文档总数为1 500时，搜索时间约为10.5 ms；当文档总数为2 500时，搜索时间约为18.92 ms。在进行聚类后，在簇中文档数量相似的情况下来计算搜索时间。此次选择的簇中文件数量约为80。当簇中文档数量相似时，搜索时间分别约为1.18 ms，1.3 ms，1.19 ms，1.23 ms，1.26 ms。

图1 基于查询关键字个数的搜索时间

图2 基于文档总数的搜索时间

在图3中显示出搜索时间会随着簇中文档数量的增加而增加。当簇中文档数量为107时，搜索时间约为1.56 ms；当簇中文档数量为244时，搜索时间约为3.55 ms；当簇中文档数量为392时，搜索时间约为5.6 ms。

图2和图3显示出聚类后的搜索时间受到每个簇中文档数量的影响，而不会受到文档总数的影响，因此搜索时间不会因为文档总数的增多而增加。

图4显示出搜索时间会随着返回的文档数量的增加而增加，且基于相同的返回文档数量，进行聚类操作后的搜索时间要优于未进行聚类操作的搜索时间。随着返回文档数量的增加，两者的搜索时间相差越大。当未进行聚类时，若返回文档数量为50，则搜索时间约为20.72 ms；若返回文档数量为150，则搜索时间约为 36.23 ms；若返回文档数量为300，则搜索时间约为55.75 ms。当进行聚类后，选取簇中文档数量为363的簇，若返回文档数量为50，则搜索效率提高了约4倍；若返回文档数量为150，则搜索效率提高了约5倍；若返回文档数量为300，则搜索效率提高了6倍。

图3 基于簇中最大文档数的搜索时间

图4 基于返回的文档数量的搜索时间

综上所述，笔者提出的方案在功能方面更加全面，实现了访问控制功能、多关键字搜索以及多客户端的设置。在搜索效率方面，对文档集采用聚类方法，根据查询关键字个数、文档数和返回的文档数，评估和分析了搜索时间。结果表明，在保持了搜索文档的精确率前提下(精确率平均约为91.67%)，大大提高了搜索效率，并使得搜索时间与文档总数无关。

5 结束语

笔者提出的方案在可搜索加密方案的基础上，对明文消息进行聚类，并对每个簇进行主题和摘要提取。通过陷门中的关键字集合来选择在相关度最高的簇中进行搜索，以减少陷门与索引的对比次数。此外，对加密数据进行排序的多关键字搜索减少了文件检索阶段的通信开销，从而以最小的误报为用户提供了最相关的文件。同时，将每个簇的摘要加入加密过程中，分发给用户对于簇的权限控制。笔者提出的方案保证了用户都只拥有常数大小的私钥，网络带宽使用和服务器的存储开销不取决于被授权访问文件的用户数量。

未来将对聚类算法进行改进，以支持云环境中更高效的动态数据操作和对大型加密数据的排名多关键字搜索。另外，希望能高效地更新用户集(从预定义的授权集中添加或删除用户)。