分布式环境下基于倒排索引的可搜索加密研究

Research on Searchable Encryption Based on Inverted Index in Distributed Environment

摘要: 目的：大数据、云计算技术和分布式技术给人们带来便捷，但是将个人数据加密并上传到云端服务器存储带来了个人隐私泄漏的问题。可搜索加密技术实现了安全高效地检索密文。方法：本文基于Spark计算框架，提出了分布式可搜索加密方案。使用高效的伪随机标签和文档标签通过Spark集群的RDD操作分布式生成倒排索引结构，利用Spark集群的性能优势进行检索，并结合提出的验证算法，进一步提高了分布式可搜索加密方案在半诚实且好奇的威胁模型下的安全性。结果：我们在不同节点数量下考察集群大小对存储性能和对计算效率影响，实验表明集群环境可以有效缓解单机存储的压力，并提升加解密、索引构造和验证的效率。结论：验证了分布式环境下基于倒排索引的可搜索加密的优越性。

Abstract: Purposes: Big data, cloud computing technology and distributed technology bring convenience to people, but encrypting and uploading personal data to the cloud server storage brings about the problem of personal privacy leakage. Searchable encryption technology enables secure and efficient retrieval of ciphertext. Methods: Based on Spark computing framework, this paper proposes a dis-tributed searchable encryption scheme. The efficient pseudo-random tags and document tags are used to generate the inverted index structure through the RDD operation of the Spark cluster, and the performance advantages of the Spark cluster are used for retrieval. Combined with the pro-posed verification algorithm, the security of the distributed searchable encryption scheme under the semi honest and curious threat model is further improved. Finding: We investigate the impact of cluster size on storage performance and computing efficiency under different node numbers. Ex-periments show that the cluster environment can effectively relieve the pressure of stand-alone storage, and improve the efficiency of encryption and decryption, index construction and verifica-tion. Conclusions: The advantages of searchable encryption based on inverted index in distributed environment are verified.

1. 引言

随着信息技术蓬勃发展，海量数据催生了云计算和云存储业务的发展。为了对云端数据进行高效地传输和使用，可搜索加密这一研究方向应运而生。Song等人最早于2000年提出可搜索加密问题，并提出了解决方案 [1] ，但是该方案陷门的生成过程是固定的，因此又易于遭受统计攻击。基于其提出的方案，后来的研究也确定了在可搜索加密方向的研究需求，即数据、搜索算法、查询算法的效率以及安全性。基于Song等人的研究，Curtmola等给出更高要求的安全定义，以更高效的算法实现可搜索加密 [2] ，提出了规范化的对称可搜索加密的安全目标。文章提出采用Hash结构存储关键字和文件标志符之间的映射关系，在这种结构基础之上提出了SSE-1密文检索方案，提升了文件的检索效率，但是新增及删除文件时重新构造索引时间开销较大。Wang [3] 采用倒排索引结构提出了隐藏密文检索的概率陷门生成算法，提升了搜索次数限制，但存在对手发起关键字猜测攻击的风险。为了管理云储存的加密数据，并高效地检索。钟晗等人通过建立高维关键词的词嵌入，增加语义距离扩展关键词集的方式建立安全索引，并用伪随机函数对私钥和关键词进行安全保护 [4] 。Varri [5] 等人提出了一种在云存储中基于密文策略属性的可搜索加密，是无量子攻击的。Fan [6] 等人改进了数据挖掘算法Apriori，提出了一种支持多关键字子集检索的可搜索加密方案。Varadharajan等人 [7] 通过并行处理大量数据来最大程度地减少加密所需的时间。Gu等人 [8] 扩展了数据存储方式，通过属性加密为分布式数据存储提供精确的访问控制。Zheng等人 [9] 建立了一个基于Lucene架构与Hadoop架构相结合的配电网大数据中心全文检索系统，是Hadoop在检索系统应用的重要体现。Duan等人 [10] 结合互联网搜索中涉及的海量数据的并行化方法和可行性，提出了利用MapReduce进行网页倒排索引并行处理，但是没有将算法应用到密文搜索且MapReduce存在IO开销和资源消耗较大的问题。吴志强等人 [11] 给出了一种并行可拆分式倒排索引结构，可适用于分布式环境。Liang [12] 等人设计了一种基于加密云文件的动态多关键字搜索加密方案，支持关键词的更新，提高了方案的实用性。Govindharaj等人 [13] 提出一种预先分类的数据检索框架，使用MapReduce对数据集并行处理，从而方便检索。MapReduce操作之间必须落盘，导致网络IO开销和资源消耗较大。随着技术发展，基于内存的Spark技术出现并广泛应用，越来越多的国内外企业开始转向Spark进行数据分析处理工作，目前Spark在可搜索加密研究方面得到部分学者使用。罗王平等人 [14] 针对传统属性加密算法效率低的问题，提出了基于Spark构造快速加密和共享算法，降低了加密计算的时间成本。

针对云环境下的可搜索加密，本文从陷门安全性、检索结果验证、分布式计算方面研究并设计了安全可靠的可搜索加密方案。对于文献 [2] 的索引构造开销问题，我们在可信服务器端构造索引，索引文件生成过程中使用伪随机标签和文档标识符等结构实现相关信息的加密操作，并利用Spark集群加速构造索引解决了文献 [10] 中MapReduce存在的问题，然后对索引文件和明文文档加密处理后上传云服务器，同时可以将检索操作交给集群处理，提升检索效率。加密算法选择AES，可以避免文献 [3] 存在的一些安全问题。本文的主要贡献包括：1) 提出了一种基于Spark集群构造的倒排索引结构，以支持高效的分布式索引构造和密文检索功能；2) 基于消息验证码设计一种验证算法；3) 从索引构造时间、空间效率和检索时间等角度，与文献 [2] 和 [3] 在不同集群节点数量下对比实验，验证了本文提出的可搜索加密方案的优越性。

2. 可搜索加密

可搜索加密可描述为以下过程：将数据文档集处理上传到云端私有Spark集群中，其中每个文档都被抽取为含有n个关键词的集合 $W=\left\{w_1,w_2,w_3,\cdots ,w_n\right\}$ ，将文档集加密并构造可靠的安全索引块。构造过程中，利用倒排索引结构，使用伪随机标签与每个关键词文档对关联，并将伪随机标签添加到文档集中，构成可供检索的索引结构。私有集群完成任务后，将安全索引和密文文档上传到公有Spark服务器集群，服务器提供给授权的数据使用者文档检索服务。当数据使用者查询某一关键词时，查询服务器根据陷门函数构造查询令牌，通过安全索引查询密文文档，验证成功后用户可查看明文文档集。整体方案的结构如图1所示。

Figure 1. Solution architecture

图1. 方案结构

2.1. 数据预处理及加解密模块

数据预处理模块用来完成关键词词典的构建。该模块首先读取原始文档内容，然后将读取的内容分词并过滤停用词，保留其他关键词，以此获得所有关键词集合。大数据场景下的可搜索加密，我们选择AES算法，该算法在保证数据安全的同时还能够顾及加解密操作的效率。此外，加解密部分将可变输入长度的伪随机函数和对称加密方案作为组件。定义函数可变长度伪随机函数F，以密钥 $K\in {\left\{0,1\right\}}^{\lambda }$ ， $x\in {\left\{0,1\right\}}^{\text{*}}$ 为输入，输出 ${\left\{0,1\right\}}^{\lambda }$ 字符串。在敌手攻击游戏中，敌手选择索引j并输入 $x\in {\left\{0,1\right\}}^{\text{*}}$ ，对于真随机函数PRFReal，存储在数组T[j]处的密钥产生输出。在伪随机函数PRFRand中，敌手的响应从关键字字典的条目中返回，每个关键字在被使用时会初始化为一个随机值。

定理1. 对于所有有效敌手A，若以下表达式

$Ad{v}_{F,A}^{prf}\left(\lambda \right)=\mathrm{Pr}\left[PRFRea{l}_F^A\left(\lambda \right)=1\right]-\mathrm{Pr}\left[PRFRan{d}_F^A\left(\lambda \right)=1\right]$ (1)

是可忽略的，则称函数F为可变输入长度的伪随机函数。

2.2. 分布式倒排索引生成模块

分布式倒排索引技术可以满足海量文档的检索效率需求。我们提取文档中的关键词，即每个文档会对应多个文档ID，而这些文档中必定都包含所需的关键词，由此得到的倒排索引结构如图2所示。

Figure 2. Inverted index structure

图2. 倒排索引结构

对于明文倒排索引结构的安全缺陷和文献 [2] 频繁加解密操作，我们在索引文件生成过程中使用伪随机标签和文档标识符等结构实现相关信息的加密操作，利用Spark集群的计算能力提高了索引构造和加解密操作效率。

首先数据拥有者获取密钥 $K\stackrel{R}{\leftarrow }{\left\{0,1\right\}}^{\lambda }$ ，针对每个关键词，使用伪随机函数F将字符附加到K上，生成两个新的密钥K₁和K₂，确保使用不同的密钥加密单词和文档记录。遍历整个文档数据集时，使用伪随机函数和密钥K₁生成单词标签 $l\leftarrow F\left(K_1,c\right)$ ，使用密钥K₂生成密文文档 $d\leftarrow Enc\left(K_2,id\right)$ ，将每个单独的标签l与文档id对 $\left(l,d\right)$ 添加到索引集合 中，此集合作为索引用于密文检索。索引可以通过Spark使用RDD操作构造。

2.3. 检索模块

索引构建时，每个文档和关键词组合使用伪随机函数F和私钥K产生的标签是对应确定的。因此，在搜索阶段若给定相同的私钥K和伪随机函数F，则可以重新产生相同的标签。根据这一特点，检索集群使用相同的私钥，按产生索引相同的方式构造陷门，就能够通过密文索引查找到相对应的文档标签。首先，输入密钥K和查询关键词w；然后使用伪随机函数F，根据K分别生成用于文档解密密钥K₁、关键词解密密钥K₂和验证消息密钥K_M。搜索服务器计算匹配加密伪随机标签，检索完成后验证结果。如果验证通过，则使用K₂解密随机标签得明文文档集。检索具体算法过程如算法1所示。密文数据库EDB为一字典，其中包含有 $N={\displaystyle {\sum }_{w\in W}\left|DB\left(w\right)\right|}$ 个文档标识符/密文关键词对。由于每个处理器都可以独立运行计算 $F\left(K_1,c\right)$ ，所以应用到Spark中可以分布式检索计算相应的密文。检索完成后，公有Spark服务器将检索结果密文文档集 $ED{B}_Q$ ，检索密文文档关联加密索引 $EInde{x}_Q$ ，文档集验证消息 $Ma{c}_{EQ}$ ，检索密文文档关联加密索引验证消息 $Ma{c}_{EIQ}$ 发送给数据使用者。将接受到的内容在本地进行验证消息 $Ma{c^{\prime }}_{EQ}$ 、 $Ma{c^{\prime }}_{EIQ}$ 计算比对。若验证通过则将检索结果解密，否则结束。

2.4. 验证模块

为了保证数据使用者获得的数据完整性，我们设计了验证模块，即检索结果文档集存在于明文文档数据集中，并且返回的密文文档集无遗漏或改变。输入待验证消息M和消息验证密钥MK，跟据公式 $HMAC\left(MK,M\right)=H\left(MK\oplus OP|H\left(MK\oplus IP|M\right)\right)$ 计算消息验证值 $ma{c}_M=Mac\left(M\right)$ ，根据不同情景分别在服务器和客户端进行，令第二次计算出的消息摘要为 $ma{c^{\prime }}_M=Ma{c}^{\prime }\left(M^{\prime }\right)$ ，若前后消息一致，则输出1，否则输出0。在索引构造阶段，当数据拥有者OD构造完成索引后，使用验证算法对安全索引I计算消息验证值 $ma{c}_I=Mac\left(I\right)$ 。为了验证密文文档 $C=\left\{c_1,c_2,\cdots ,c_3,\cdots ,c_n\right\}$ 的完整性，在完成对文档加密后，还要根据文档加密标识符 $SID=\left\{si{d}_1,si{d}_2,\cdots ,si{d}_i,\cdots ,si{d}_n\right\}$ 对文档进行计算消息验证值 $ma{c}_c{}_i=Mac\left(c_i\left|\right|si{d}_i\right)$ 。在搜索阶段，不仅返回密文文档 $C_Q$ ，基于验证需求，还要返回所有感兴趣的检索关键词W对应的密文索引 $I_Q$ ，以及 $ma{c}_{I_Q}$ 和 $ma{c}_{c_i}$ 。验证时，数据使用者使用验证密钥MK计算返回待验证的密文索引 ${I^{\prime }}_Q$ 的消息验证值 $ma{c}_{{I^{\prime }}_Q}=Mac\left({I^{\prime }}_Q\right)$ ，若 $ma{c}_{{I^{\prime }}_Q}=ma{c}_{I_Q}$ ，则证明返回的密文索引没有被篡改。随后数据使用者使用验证无误的安全索引，根据陷门TD在本地进行检索，若对于每个查询关键词，都可以在本地查找到密文文档集，且文档集和服务器返回文档集相同，则证明检索结果无误，使用验证密钥计算密文文档的验证消息 $ma{c}_{{c^{\prime }}_i}=Mac\left({c^{\prime }}_i\left|\right|si{d^{\prime }}_i\right)$ ，若有 $ma{c}_{{c^{\prime }}_i}=ma{c}_{ci}$ 分别成立，则证明返回的密文文档集无遗漏或改变。

3. 实验设计

3.1. 实验环境

硬件环境：本文仿真实验部署在3节点的Spark集群上，其中包含一个主节点，2个从节点。服务器的配置参数如下所示：2.3 GHz主频2核CPU，8G内存，512 G硬盘空间。软件环境：本文实验全部在Linux环境下运行，源代码采用IDEA开发，编程语言为Java、Scala。运行中的每个节点均安装部署JDK1.8。实验集群配置如表1所示。

Table 1. Software configuration of Spark cluster

表1. Spark集群软件配置

3.2. 性能分析

为了验证提出的分布式可搜索加密算法，我们对文档数量，检索关键词个数，分区数量，节点个数和返回文档数量等角度进行分析。实验采用的数据集来自Wikipedia，共有约20,000个文档。

明文到密文空间大小变化是体现索引构建性能的重要指标。从图3可知，密文文档大小会随着明文文档大小变化成比例增大，并且随着节点个数的变化几乎在各节点均匀分布。因此，分布式存储形式能够有效缓解单机情况下节点存储能力不足的问题。

Figure 3. Specifies the relationship between ciphertext document size and data set size

图3. 明密文文档大小随数据集规模变化关系

为了验证算法的索引构造空间效率，在文档大小在20~180 MB范围内时将该算法与文献 [2] 中的密文索引大小情况进行了比较，实验结果如图4所示。文献 [2] 方案占用空间更多，这主要是因为文献 [2] 在构造密文索引时，会首先生成明文索引，然后对明文索引中的数据和指针进行加密。而我们通过构造伪随机标签的形式存储索引，未使用指针加密，因此空间性能较好。此外，在多节点情况下索引文件分布式存储在集群上，单机情况下相较于文献 [2] 更加节约空间。因此基于Spark实现的密文倒排索引结构具有良好的空间性能。

密文索引构造所需的时间是对算法进行衡量的标准之一，从图5可知，文献 [3] 包含公钥配对和求幂以及乘法计算等操作，所以索引构造效率较低。在初始文档数量较少时，文献 [2] 方案索引构造效率较高。在文档数量到达6000左右时，表现出分布式计算的优势，所以随着文档数据集的不断增大，本方案索引构造的时间开销表现优于文献 [2] 方案。资源相同资源下，基于Spark的分布式可搜索加密能够有效的提高索引构造效率。

Figure 4. The size of an index relative to document size

图4. 索引大小随文档大小的变化关系

Figure 5. The construction time of ciphertext indexvaries with the number of documents

图5. 密文索引构造时间随文档数量的变化关系

实验检索时间随检索返回文档数量的变化情况如图6所示，当返回相同数量文档时，分布式方案的检索时间远小于文献 [2] 。因为文献 [2] 方案中构造的倒排索引指针要经过加密处理，进行相关数据检索时需要先进行指针解密。随着文档数量逐渐增加，分布式方案所需的检索时间增长更为平缓。在检索返回文档数量小于500时，文献 [3] 方案和分布式可搜索加密方案检索耗时接近，但随着检索规模变大，分布式计算优势会逐渐显现出来。此外，由于采用本地验证方式，故实际通信开销较小，检索效率优于文献 [3] 。综合以上实验结果，分布式可搜索方案更加适用于大数据环境。

Figure 6. The relationship between retrieval time and the number of documents returned from retrieval

图6. 密检索时间随检索返回文档数量的变化关系

为了保证数据的完整性，我们根据验证模块分别计算查询关键词返回的文档与验证文档的MAC值。在固定文档数量为5000，抽取关键词个数为500~3000并且搜索关键词个数 $t=5$ 时，对公有Spark服务器返回得的 $ED{B}_Q$ (检索结果密文文档集)， $EInde{x}_Q$ (检索密文文档关联加密索引)， $Ma{c}_{EQ}$ (文档集验证消息)， $Ma{c}_{EIQ}$ (检索密文文档关联加密索引验证消息)在本地进行验证，并计算比产生的 $Ma{c^{\prime }}_{EQ}$ 、 $Ma{c^{\prime }}_{EIQ}$ 。结果显示检索返回和本地验证的MAC完全相同，即返回结果正确且无遗漏。

3.3. 安全性分析

考虑到要保证信息在传输过程中的有效性和完整性，本文提出的方案主要建立在“半诚实且好奇”的公有云服务器威胁模型基础上，并将服务器与潜在攻击对象视为威胁。这一威胁模型不同于以往的可搜索加密方案，其通常采用“诚实且好奇”的服务器威胁模型。在这一威胁模型下，检索过程可能会产生信息失真，就要求可搜索加密方案能够验证返回的检索结果，另一方面对于密文文档和陷门等信息也要验证其完整性、真实性。下面我们首先给出正确性和可靠性的定理。

定理2. 正确性：对于一个可验证可搜索加密方案，若方案满足 $\forall \left(SK,MK,DK\right)\leftarrow KeyGen\left(1^{\lambda }\right)$ ，对于 $\forall D_i\in D\left(1\le i\le n\right),\forall w\in W$ ，有：

$\left(Search\left(TD,I\right)\to \left(C_Q,I_Q,ma{c}_{I_Q},ma{c}_c{}_i\right)\right)\wedge \left(Verify\left(M,MK\right)\to \left(0,1\right)\wedge DecFile\left(C_Q,SK\right)=D_Q\right)=1$ (2)

则称该验证方案为正确的。其中i为常数，n为文档个数。

定理3. 可靠性：对于一个可验证的可搜索加密方案，面对一个多项时间内的敌手 $\mathbb{A}$ ，当用户提交关键词检索陷门 $T{D}^{\prime }$ 后，敌手 $\mathbb{A}$ 产生一个伪造检索结果 ${C^{\prime }}_Q$ ，并生成对应的 ${I^{\prime }}_Q$ ， $ma{c}_{{I^{\prime }}_Q}$ ， $ma{c}_{{c^{\prime }}_i}$ 返还给用户，而服务器运行产生的正确结果为 $\left(C_Q,I_Q,ma{c}_{I_Q},ma{c}_{c_i}\right)\leftarrow Search\left(TD,I\right)$ ，若

$\mathrm{Pr}\left[Ad{v}_{\mathbb{A}}\left(\lambda \right)=1\right]\le negl\left(\lambda \right)$ (3)

即使用敌手伪造信息来进行验证，获得结果 $1\leftarrow Verify\left(M,MK\right)$ 成立的概率可以忽略，称该验证方案可靠。

下面我们采取选择关键字攻击(indistinguishability of SCF-PEKS against chosen keyword attack, IND-SCF-CKA)游戏来证明关键字的不可区分性，在抗选择关键字攻击等安全性依赖于判定性子群假设和DBDH假设前提下 [15] ，假设当前有敌手A和模拟者B，我们建立两者相互攻击模型，安全参数设为 $\lambda$ 。

Game1：假设A为内部攻击者(服务器)。

1) Setup：运行初始化算法 $GlobalSetup\left(\lambda \right)$ 生成系统参数GP，三个密钥生成算法得到用户密钥中心、服务器、接受者的公私钥对： $\left(p{k}_K,s{k}_K\right)$ ， $\left(p{k}_S,s{k}_S\right)$ 和 $s{k}_R$ ，随后模拟者B将 $\left(p{k}_S,s{k}_S\right)$ 和 $p{k}_K$ 发送给敌手A。

2) Queryphase1：对任意关键词w，敌手A向B询问关键字陷门，B运行陷门生成算法 $T_w=Trapdoor\left(GP,s{k}_R,w\right)$ ，并将结果返回给敌手A。

3) Challenge：A向B发送挑战关键词对 $\left(w_0,w_1\right)$ ，并且 $w_0,w_1$ 都不能出现在Queryphase1中，B随机选取 $b\in \left(0,1\right)$ ，计算 $C^{*}=SCF-PEKS\left(GP,p{k}_S,p{k}_K,w_b\right)$ 作为挑战密文发给A。

4) Queryphase2：敌手A在不选择 $w_0$ 和 $w_1$ 的前提下，继续对关键词进行陷门询问。

5) Guess：A输出猜测 $b^{\prime }$ ，若 $b^{\prime }=b$ ，则敌手A获得胜利，否则A失败。

A攻破Game1的优势为：

$Ad{v}_A^{Game1}\left(\lambda \right)=\left|\mathrm{Pr}\left[A\left(b^{\prime }=b\right)\right]-\frac{1}{2}\right|.$ (4)

Game2：假设A为外部攻击者，攻击游戏过程如下。

1) Setup：和Game1类似，通过 $GlobalSetup\left(\lambda \right)$ 算法获得系统参数gp，并通过密钥生成算法得到三个公私钥对 $\left(p{k}_K,s{k}_K\right)$ ， $\left(p{k}_S,s{k}_S\right)$ 和 $s{k}_R$ ，最后模拟者B将 $p{k}_S$ 和 $p{k}_K$ 发送给敌手A。

2) Queryphase1：A自适应的选择接收者的密钥 $x\in Z_N^{*}$ ，在密钥生成中心生成用户密钥，得到 $s{k}_R$ 。

3) Challenge：敌手A发送关键词对 $\left(w_0,w_1\right)$ ，B随机选取 $b\in \left(0,1\right)$ ，计算 $C^{*}=SCF-PEKS\left(GP,p{k}_S,p{k}_K,w_b\right)$ 作为挑战密文发给A。

4) Guess：A输出猜测 $b^{\prime }$ ，若等于b则敌手A获得胜利，否则A失败。

A攻破Game2的优势为：

$Ad{v}_A^{Game2}\left(\lambda \right)=\left|\mathrm{Pr}\left[A\left(b^{\prime }=b\right)\right]-\frac{1}{2}\right|.$ (5)

上述两个攻击游戏中，如果 $Ad{v}_A^{Game1}$ 和 $Ad{v}_A^{Game2}$ 之于安全参数 $\lambda$ ，则称该方案是IND-SCF-CKA安全的。

假设1 敌手的随机询问 $w_i\left(i=1,2,\cdots ,q\right)$ 每次都是不同的，且给定的 $R_3$ 可以完美的随机化陷门。

假设2 密钥注册中心不是敌手，那么其肯定忠诚且安全。

引理1 若DBDH假设为困难的，那么可以忽略对任意多项式时间算法的敌手A能够区分关键字陷门的优势。

证明：假设存在一个多项式时间算法内的外部敌手对本文方案进行攻击，和游戏挑战者B。攻击游戏过程为：挑战者B设置一个阶为 $p^{\prime }$ 的群 $G^{\prime },{G^{\prime }}_T$ 和双线性映射 $e:G^{\prime }\times G^{\prime }\to {G^{\prime }}_T$ ，其中 $G^{\prime },{G^{\prime }}_T$ 分别为群 $G,G_T$ 的素数阶子群。向挑战者输出参数 $\left(g_1,g_1^a,g_1^b,g_1^c,T\right)$ ，挑战者的目标为区分T是否等于 $e{\left(g_1,g_1\right)}^{abc}$ 。

敌手和挑战者的攻击游戏如下：

1) Setup：输入安全参数 $\lambda$ ，选择一个抗碰撞单向hash函数 $H:{\left\{0,1\right\}}^{*}\to Z_N$ ，双线性映射的参数有 $\left(N,G,G_T,e\right)$ ，关键字空间为 $K{S}_w={\left\{0,1\right\}}^{*}$ ，全局参数为 $GP=\left\{N,G,G_T,e,H,K{S}_w\right\}$ ，运行密钥生成算法可得 $p{k}_s=\left\{u^{\frac{\beta }{\alpha }}=Q\right\}$ ， $s{k}_s=\alpha$ ， $s{k}_R=\left\{x,R\right\}$ ， $s{k}_K=\beta$ ， $p{k}_K=\left\{g_1,u,X,Y\right\}$ ，挑战者B将 $p{k}_S$ ， $s{k}_S$ ， $p{k}_K$ ， $s{k}_R$ 发送给敌手A。

2) Queryphase：敌手A向随机预言机发送关键词 $w_i$ 并询问其陷门，预言机获得 $p{k}_K$ ， $s{k}_R$ ， $s{k}_K$ ，然后随机选择 $R_3\in G_{p_3}$ ，计算 $T_2=T_1^n{Y}^{H\left(w^{\prime }\right)}{R}_3$ ，将计算出的陷门 $T_{w_i}=\left[T_1,T_2\right]$ 返回到敌手A。

3) Challenge：敌手A多次询问预言机后，随机选取未经过查询的关键词 $\left(w_0,w_1\right)$ 发送给挑战者B，挑战者将随机选取 $b\in \left\{0,1\right\}$ 并设置挑战关键词 $w^{*}=w_b$ ，计算 $T_1=R^{\frac{1}{x}}$ ， $n=H\left(e{\left(T_1,u\right)}^{\beta }\right)$ ，随机选择 $R_3\in G_{p_3}$ ，计算 $T_2=T_1^n{Y}^{H\left(w^{*}\right)}{R}_3$ ，将关键词陷门 $T_w^{*}=\left[T_1,T_2\right]$ 发送给敌手A。

4) Guess：敌手A在获取陷门后进行猜测，输出猜测 $b^{\prime }$ 。若 $b^{\prime }=b$ ，则有 $t=H\left(e{\left(T_1,Q\right)}^{\alpha }\right)=H\left(e{\left(g_1,g_1\right)}^{abc}\right)$ ， $T=e{\left(g_1,g_1\right)}^{abc}$ ，则 $T_w^{*}$ 为合法的输出，返回“Yes”；否则T为 $G_T$ 中的随机元素，返回“No”。

如果敌手A可以区分关键词陷门，那么挑战者B就可以攻破DBDH假设。综上所述本方案中的关键词陷门具有不可区分性，可抵抗外部关键字猜测攻击，也能够抵抗选择关键字攻击，满足IND-SCF-CKA安全。

上文证明了加密方案可以抵抗外部关键字猜测攻击和选择关键字攻击，我们接着通过分析不同情况下敌手攻击来验证本文可搜索加密的安全性。假设敌手的攻击方式主要为唯密文攻击，则敌手能够获得本文方案下的加密索引文件和密文文档集合，我们使用的加密算法AES是完全公开的，在以上条件下，本方案的加密索引和密文文档的安全性通过密钥保护。由于AES加密算法为成熟安全的对称加密算法，因此，敌手在不知道密钥的情况下难以破解密文文档和密文索引的内容。在仅有加密文档和加密索引的情况下，敌手可以通过分析密文词频获取密文与明文的对应关系从而进行推测。但是本文使用伪随机标签将关键词和文档标识符的信息进一步隐藏，因此密文索引中只包含伪随机标签相关信息。伪随机标签的使用在一定程度上避免了文档词频统计攻击。在对倒排索引加密时，每个倒排索引关键词对应的密钥都随机生成，各个倒排索引之间关联性较弱，很大程度上可以避免敌手攻击。

在敌手已获得部分明文信息条件下，敌手可以对获得的信息构造加密索引并和本文方案中的密文索引进行比较。但是在密文倒排索引中，敌手无法获取各文档在索引中所处位置，难以通过对安全索引进行对比获取明文信息。综合以上考虑分析，基于Spark的可搜索加密方案是安全可靠的。

4. 结语

本文提出一种基于Spark的分布式可搜索加密方案，提高了大数据场景下单机存储性能和计算性能。另外通过伪随机标签和文档与关键词标签等技术，构造出轻量化方案。结合提出的验证算法，增强检索结果的正确性和完整性。实验对比本文方案与文献 [2] 和文献 [3] 方案不同分布式节点个数下的密文索引空间性能，结果显示本文方案随着分布式节点的不断增多，单机空间消耗减少，具有良好的空间性能。此外，通过索引构造的不同时间开销对比，表明该方案在索引构造过程消耗的时间远小于其余两种方案。而且在关键词检索方面，本文方案的时间效率仍优于文献 [2] 和文献 [3] 方案。验证结果证明检索能够正确完整的返回目标文档，查全率与查准率满足方案目标。综上，设计的基于Spark的分布式可搜索加密方案更适用于大数据环境下的可搜索加密需求。

在当下可搜索加密研究场景下，一对多、多对多模式已十分常见，分布式集群的计算能力可以处理海量数据，如何让这些数据同时给多名授权用户提供支持，充分发挥集群力量，是云环境下可搜索加密应用场景的探索方向。