基于区块链的公平可验证的多关键词密文排序检索

庞晓琼，王云婷，陈文俊，2，姜 攀，高亚楠

（1.中北大学 大数据学院，太原 030051；2.中国人民银行 太原中心支行，太原 030001）

0 引言

随着云计算的飞速发展，越来越多的用户将大量数据迁移到云平台，以节省本地存储成本；同时云平台也为远程存储和计算提供即时服务，方便用户随时随地进行数据访问和使用［1］。但由于用户失去了对数据的控制，如何保障数据隐私安全成为关键问题。为保护敏感数据的隐私性，数据需要在用户上传至云服务器（Cloud Service Provider，CSP）前进行加密处理［2］；然而数据加密使基于明文的关键词检索技术无法使用。可搜索加密技术［3］的提出不仅能实现对加密数据的检索，同时亦能保障数据隐私安全。

在可搜索加密技术中，通常假设CSP 是诚实且好奇的实体。然而在实际中，为获取服务费的同时节省计算资源，CSP 可能会不诚实地执行搜索操作并向用户发送不正确或不完整的搜索结果［4］。在先付费后使用的模式中，即使出现上述不诚实的情况，用户也必须先向CSP 支付服务费；而在先使用后付费的模式中，可能存在不诚实的用户收到正确的结果拒绝支付服务费的情况。此外，数据拥有者（Data Owner，DO）向CSP 提供的数据的价值也需要被考虑在交易中，即数据使用者（Data User，DU）进行交易时应向数据拥有者支付所提供数据的消息费［5］。为了解决以上公平问题，传统解决方案往往会依赖一个可信的第三方；但由于第三方没有能力直接验证检索结果的正确性和完整性，当发生交易纠纷时，第三方机构需要花费大量时间解决纠纷，公平支付无法直接保证，交易过程中产生的不诚实行为得不到惩罚。另一方面，第三方机构、CSP 及用户之间发生交互时，用户在第三方机构上的个人隐私信息也有被泄露的风险。

从以上分析可知，需要一种有效的方法来解决传统可搜索加密方案中的公平支付问题。随着比特币［6］的问世，区块链作为其底层技术能够为解决这一问题提供支持。区块链具有去中心化和不可篡改等特性，能够很好地与云计算结合；区块链上的智能合约［7］可以直接写入代码并自动执行，不受任何集中机构的控制。因此，区块链和智能合约适合在可搜索加密方案中执行验证操作并实现公平支付。

在区块链智能合约与可搜索加密方案相结合的进程中，人们利用区块链智能合约执行检索结果的验证和实现公平支付。此外，还有一些方案采用智能合约取代CSP 执行搜索操作，在执行过程中区块链智能合约需进行多笔事务交易，储存占用空间较多的索引以及执行复杂搜索操作，可扩展性低、费用高且时间耗费大；并且费用成本和时间成本会随着智能合约所执行操作的复杂性增加而增加。因此，有必要考虑在保证实现结果验证和公平支付的基础上，降低智能合约所执行操作的复杂性以降低时间与费用成本的开销，提高效率，同时拓展方案功能，对用户更友好。

此外，在实际应用中，仅支持单关键词检索的方案往往不能满足用户需求。例如，为了获得更精确的搜索结果，用户检索时一般会输入多个关键词，并希望返回与输入关键词最相关的前k个文档［8］。因此，有必要考虑在结合区块链技术保证实现结果验证和公平支付的基础上，设计一个检索功能更丰富的可搜索加密方案。

为降低实现结果验证和公平支付产生的时间和费用成本，本文方案将CSP 强大高效的检索能力与区块链智能合约自动执行合约内容的优势相结合，实现了对密文的排序检索、检索结果的验证以及数据拥有者、CSP 和数据使用者之间的公平支付。本文方案采用CSP 存储加密索引树和执行搜索操作，数据拥有者在生成加密索引树的同时，构建包含验证证明的查找表并将其存储在云端；在执行搜索操作时，CSP 通过验证令牌查找相应的验证证明，再将该验证证明发送给智能合约以辅助其完成检索结果的验证和公平支付，这种方式可有效降低智能合约执行操作的复杂性，节约费用和时间成本，提高验证效率；同时，为了解决关键词检索中功能过于局限的问题，本文方案将向量空间模型与词频逆文档频率（Term Frequency-Inverse Document Frequency，TF-IDF）结合，构建平衡二叉树的索引结构，在保证检索效率的基础上，支持多关键词检索的动态更新和检索结果的可排序，提升方案的用户友好性。

1 相关工作

可搜索加密技术是一种允许用户对密文数据进行检索的密码原语，利用云服务器的强大计算资源进行关键词检索，其核心思想在于使用户具有在密文域上进行关键词搜索的能力。2000 年，Song 等［3］首次提出了可搜索加密的思想，解决了在云平台上搜索加密数据的问题，随后云存储技术下的可搜索加密成为了研究热点。近几年，许多可搜索加密工作致力于丰富其功能，陆续提出了多关键词搜索［8-11］、动态加密搜索［12-15］、模糊关键词搜索［16-19］和可验证的加密搜索［20-23］等方案。这些方案通常假设云服务器会诚实地执行任务，然而云服务器往往并不是完全可信的，它可能为节省计算资源或者骗取服务费，在收到服务费后返回不正确或不完整的结果；同时，即使用户收到正确的搜索结果，如果用户声称搜索结果不正确，也可能恶意拒绝支付服务费。以上情况导致了服务-支付不公平现象，导致用户和云服务器之间互不信任。为解决上述问题，传统方案通常考虑由可信第三方机构进行监管与仲裁。

区块链自问世以来，受到了学术界和工业界的广泛关注，它能够在不引入第三方机构的情况下实现公平支付。因此，人们积极尝试将区块链与可搜索加密技术结合，以解决传统方案的问题。文献［24］提出一种基于云存储的可信赖关键词搜索方案，利用比特币区块链技术和哈希函数在没有第三方的情况下实现搜索费用的公平支付。该方案建立基于数字签名的安全索引，保证了用户端检索结果的正确性，同时也实现了服务器端对加密数据有效性的验证；但是该方案在用户端验证结果正确性的过程中需要进行大量签名验证计算，用户开销较大。文献［25］设计了一个基于比特币区块链的公平对称可搜索加密方案，通过区块链自动验证检索结果，保证了用户和云服务器之间交易的公平性；但是该方案每次需要执行6 笔交易才能获取检索结果，同时通过比特币脚本实现检索结果的验证，其交易周期过长从而导致时间成本较高。文献［24-25］方案均由云服务器执行检索操作，基于比特币区块链对检索结果进行验证以实现多方之间的公平支付；然而由于比特币智能合约并不是图灵完备的，其功能较为局限、交易过程复杂、交易周期长且效率不高。文献［26］在分布式存储网络中实现了支持动态高效的关键词检索，利用智能合约在以太坊区块链上记录加密搜索日志，并设计了一个协议来处理争议和发放佣金，以便在客户端与服务器之间进行公平搜索。该方案由分布式存储网络中的签约服务节点执行检索操作，将可搜索索引和检索结果的元数据作为证据锚定在区块链上，再由分布式存储网络中仲裁者分片上的仲裁节点检查检索结果的正确性并基于以太坊智能合约实现公平支付；当数据用户申请仲裁时，需要每个仲裁节点重新且独立地执行搜索算法，根据重新生成的搜索结果判断客户端发出的判断请求（即停止支付请求）是否有效，然后将这些单独的仲裁结果汇聚到仲裁智能合约中来作出最终决定；如果仲裁者分片中大于2/3 数量的节点接受判断结果，限时支付将被暂停；可以看出，该仲裁过程会浪费大量的计算资源。文献［27］提出了一个基于区块链的支持复杂逻辑表达式查询的可搜索加密方案，该方案利用以太坊智能合约保证了检索结果的正确性，能够在没有任何验证机制的情况下实现公平支付。文献［28］提出了一种基于区块链的支持细粒度访问控制的分布式存储系统，该系统使用以太坊智能合约实现了密文状态下的关键词搜索功能，解决了传统云存储系统中云服务器可能无法返回所有检索结果或返回错误结果的问题。文献［29］设计了一种基于区块链且支持验证的属性基搜索加密方案，该方案基于以太坊智能合约设计搜索合约与验证合约，在不需要本地额外验证的情况下实现了支持多关键词检索的公平支付。文献［27-29］方案均是由区块链存储加密索引和检索结果，并基于以太坊智能合约执行搜索操作以及实现公平支付；然而区块链的存储容量受到存储空间最小的节点的限制，复杂的加密索引需要分片处理后才能存储进区块链交易中，并且这些交易必须逐个上传，会消耗大量的时间；此外，智能合约执行操作时会消耗一定的费用，方案中由智能合约执行复杂性高的搜索操作和验证操作，执行时需要进行大量计算，亦会导致费用成本增加。因此文献［27-29］方案都存在可扩展性低、时间成本和费用成本高的问题。另外，文献［24-28］方案都仅支持单关键词检索，均未考虑对检索结果进行相关性排序，功能上不够灵活，用户友好性不高。

因此，本文提出了一种基于以太坊区块链的公平可验证的多关键词密文排序检索方案。利用云服务器高效的检索能力与以太坊智能合约自动执行的特点，由云服务器来存储加密索引树与查找表；同时执行搜索算法，可有效降低智能合约执行操作的复杂性，从而降低消耗的时间成本和费用成本；由以太坊智能合约实现结果的验证过程，不但保证检索结果的正确性和完整性，完成数据拥有者、云服务器和数据使用者之间的公平支付，而且可以有效减少费用开销并提高验证效率。此外，本文采用平衡二叉树为索引，在保证检索效率的基础上，实现了多关键词检索的动态更新以及检索结果可排序，提升了方案的灵活性和用户友好性。

2 预备知识

2.1 符号定义

DC={d1，d2，…，dm}，表示m个明文文档的集合。

C={c1，c2，…，cm}，表示存储在云服务器的密文文档集合。

DW={w1，w2，…，wn}，表示关键词字典。

Tr 为未加密的索引树，ETr 为对Tr 的加密形式。

Du为索引向量，它的维数等于字典DW的基数，u为索引树节点；Iu为Du的加密形式。

T 为查找表，W为查询关键词集，Q为查询关键词集W的查询向量，为Q的加密形式。

TD 为搜索令牌，token为验证令牌。

μVK为消息认证码，VK为验证密钥。

ek为文档加密密钥。

proof为搜索结果的验证证明。

FIDk(W)，Ck(W)，DCk(W)分别为按照相关性分数排序的前k个文档的标识符集合、密文文档集合和明文文档集合。

2.2 向量空间模型和相关性分数

向量空间模型与TF-IDF 规则广泛应用于明文信息检索，可有效支持多关键词排序检索。在TF-IDF 规则中，词频（Term Frequency，TF）是关键词在文档中出现的频率，逆文档频率（Inverse Document Frequency，IDF）是通过文档集合的总数除以包含该关键词的文档数量得到。在向量空间模型中，∀di∈DC，均能用一个|DW|× 1 维的文档索引向量Du表示，Du中每一位的值对应DW中相应关键词的归一化TF 值，若关键词在文档di中并未出现，则将Du对应位设置为0；用户搜索请求也能用一个|DW|× 1 维的查询向量Q表示，所查询关键词在Q的对应位为文档集合中查询关键词的归一化IDF 值，其他设置为0。通过计算向量Du和向量Q的内积可以量化文档di和查询之间的相关性。

以下是相关性评估函数中使用的符号：

2.3 未加密可搜索索引树构建

本文方案中的搜索索引树为平衡二叉树。给定文档集合DC={d1，d2，…，dm}，每个文档di对应于索引树中的一个叶子节点，如果有m个文档，则需要自下而上构造一个具有m个叶子节点的搜索索引树。将索引树节点u的数据结构定义为{ID，FID，Du，Prl，Prr}，其中：ID表示节点编号，Du表示n维向量，Prl和Prr分别表示指向u的左、右孩子的指针。对于文档di的叶子节点，FID表示文档di的标识符，Du表示文档di的索引向量。对于内部节点，Du的每一位则由其孩子节点中向量对应位的值计算得到，假设内部节点u的左右孩子节点分别为l和r，如果Dl[i]=0(i=1，2，…，n)且Dr[i]=0，则Du[i]=0；否则，Du[i]=1。内部节点中，FID设置为空。

通过BuildIndexTree(DC)算法构造索引树，算法如下所示。

算法1 BuildIndexTree(DC)。

1）对于文档合集中的每个文档di，生成对应的叶子节点，过程如下：

①为di生成一个唯一的标识符，并将这个标识符设置为这个叶子节点的FID。

②根据关键词字典DW={w1，w2，…，wn}生成索引向量Du，其中Du的维数为关键词字典的基数，每个维度Du[i]为文档di中wi的归一化的TF 值。

2）生成搜索索引树Tr，其叶子节点为上一步生成的m个节点，内部节点u的FID和Du的初始设置为空。

3）对于每个内部节点u，根据其左右孩子节点中向量对应位的值计算Du。

4）输出搜索索引树Tr。

在实际方案中，采用安全K近邻技术［30］加密上述可搜索索引树Tr 中的叶子节点向量Du和查询向量Q。

3 本文方案

3.1 方案框架

本文方案包括数据拥有者（DO）、数据使用者（DU）、云服务器（CSP）以及区块链和智能合约四个实体。

1）数据拥有者（DO）。

DO 生成密钥，授予搜索权限并通过安全信道传递用于检索的秘密信息给DU；加密明文文档、构建加密索引树和查找表，并存储到CSP；部署用于公平支付的FairPayment 智能合约以收取信息费；生成动态更新信息。

2）数据使用者（DU）。

DU 由DO 授予搜索权限，生成搜索和验证令牌并使用FairPayment 智能合约将搜索请求和令牌提交给CSP。若检索结果验证通过，则向CSP 支付服务费，向DO 支付消息费；否则不支付任何费用。

3）云服务器（CSP）。

CSP 为DO 存储密文文档、加密索引树和查找表；为DU提供搜索服务并收取服务费；向FairPayment 智能合约支付押金并上传检索结果和验证证明；根据接收到的信息更新存储内容。

4）区块链和智能合约。

区块链存储DU 上传至FairPayment 智能合约的搜索和验证令牌以及CSP 上传的检索结果和验证证明；FairPayment智能合约验证检索结果的正确性和完整性，实现预定义比例的费用公平支付，将检索结果返回给DU。

方案框架如图1 所示。

图1 本文方案框架Fig.1 Framework of proposed scheme

具体步骤如下：

步骤1 DO 生成安全密钥SK、文档加密密钥ek和验证密钥VK，然后从明文文档集合DC中提取关键词字典DW，生成加密索引树ETr 和查找表T。DO 利用ek对DC进行加密得到密文文档集合C，然后将ETr、T 和C外包给CSP。

步骤2 DO 部署用于公平支付的FairPayment 智能合约，并将验证密钥VK记录在用于公平支付的智能合约中。

步骤3 DO 记录智能合约地址和合约应用程序二进制接口（Application Binary Interface，ABI）。

步骤4 DU 向DO 请求搜索权限。

步骤6 DU 生成多关键词搜索令牌TD 和验证令牌token，并将其发送到区块链以触发智能合约。在请求之前，要求DU 在智能合约中存入足够的搜索费用（包括消息费和服务费）。

步骤7 如果DU 被验证为授权用户，并且存放了足够的搜索费用，则智能合约将自动在区块链广播TD 和token，CSP 将接收到它们。

步骤8 CSP 根据TD 和token分别对ETr 和T 执行检索操作，得到相应的检索结果和验证证明。CSP 支付一定的押金后，将检索结果和验证证明返回给智能合约进行验证。

步骤9 FairPayment 智能合约利用VK验证检索结果的正确性和完整性。如果验证通过，智能合约将自动使用DU的搜索费用向DO 支付信息费，向CSP 支付服务费（根据预定义的分配比例）并返回CSP 的押金；否则，DU 的搜索费用与CSP 的押金都将被支付给DU。

步骤10 步骤9 中的正确性和完整性验证通过后，智能合约将检索结果发送给DU。

步骤11 DU 从CSP 收到密文文档集合Ck(W)后，对加密文档进行解密。

步骤12 在实际应用中，DO 可以动态地添加、删除或修改文档，重新生成新的加密索引树ETr′、查找表T′和加密文档合集C′，以实现动态更新。

3.2 方案实现

本文方案包含8 个子算法（Setup，Enc，GenTrapdoor，Search，Verify，Decrypt，GenYpdatlnto，Update），具体过程如下：

1）Setup(1λ) →(SK，ek，VK)。

该算法由DO 执行。给定安全参数λ，定义伪随机函数消息认证码（Message Authentication Code，MAC）函数μVK：{0，1}λ×{0，1}*→{0，1}l，其中：fl是文档标识符的长度，l是标准MAC 函数的输出长度；密钥K1，K2，VK∈R{0，1}λ。DO 生成安全密钥SK={S，M1，M2，K1，K2}，其中：S是一个n维二进制的拆分指示向量；M1，M2是两个n×n阶可逆矩阵，用于加密拆分后的向量；n为关键词字典的基数。DO 生成用来加密文档集合的文档加密密钥ek∈REK，EK为对称密钥空间。上述过程如3.1 节步骤1 所示。

2）Enc(DC，DW，SK，ek，VK) →(ETr，T，C)。

该算法由DO 执行。给定一个明文文档集合DC={d1，d2，…，dm}，DO 首先扫描文档集合，提取出关键词字典DW={w1，w2，…，wn}，然后执行两个子算法GenIndex 和FileEnc 分别生成加密索引树ETr、查找表T 和密文文档集合C。

①GenIndex(DC，SK，VK) →(ETr，T)。

a）DO 使用算法BuildIndexTree(DC)构建未加密的索引树Tr。

b）构建加密索引树ETr。

c）构建查找表T。

DO 利用K1和VK构建包含验证证明的查找表T，T 是结构，其中key字段包含伪随机函数的输出，proof字段用于存储多关键词排序搜索结果的验证证明。

对每个查询关键词集W，利用关键词归一化后的TF 值和归一化后的IDF 值，计算相关性分数，得到按照相关性分数降序排序的结果ResultList(RScore，FID)，其中：RScore表示查询关键词集合W与文档的相关性分数，FID表示文档标识符。ResultList()根据RScore进行降序排序，包含查询关键词集W的文档的标识符集合被表示为FID(W)=，FID(W)中的FID按照RScore降序排序。

表1 查找表TTab.1 Lookup table T

②FileEnc(DC，ek) →C。

DO 利用ek对DC进行加密，得到密文文档集合C={c1，c2，…，cm}。

DO 将{ETr，T，C}外包给CSP。然后DO 在Ethereum 部署了一个FairPayment 智能合约，将验证密钥VK作为私有参数嵌入到合约之中（用Solidity 编码），其中VK只有DO 知道。合约负责注册授权用户，检查请求搜索服务的每个用户账户的有效性，记录和广播令牌以及验证来自CSP 的搜索结果，并且最终实现公平支付。DO 记录智能合约的地址和合约ABI。上述过程如3.1 节步骤1～3 所示。

3）GenTrapdoor(W，SK) →(TD，token)。

该算法由DU 执行。当用户账户第一次请求搜索服务时，应该首先向DO 请求搜索权限。如果请求被允许，DO 通过安全信道将授予DU。

①生成搜索令牌TD。

a）DU 根据其查询关键词集W和，生成n维查询向量Q。如果wi∈W，Q[i]存储wi的归一化IDF 值；否则，Q[i]被设置为0。

②生成验证令牌token。

DU 利用W和伪随机函数生成验证令牌token=

DU 将足够的搜索费用存入FairPayment 智能合约的存款池（与DU 的账户相关联），将TD 和token上传到合约，智能合约将自动在区块链广播TD 和token，CSP 将接收到它们。上述过程如3.1 节步骤4～7 所示。

4）Search(TD，ETr，T，token) →(FIDk(W)，proof)。

该算法由CSP 执行。FairPayment 智能合约收到token后，检查DU 是否为授权用户，如果DU 被授权，合约将通知CSP 执行以下检索操作。

①检索得到相应文档标识符集合FIDk(W)。

CSP 收到用户搜索令牌TD 后，对加密索引树ETr 进行检索。从树的根节点开始，当到达一个内部节点u时，对于TuW中的每一项如果至少存在一个at使得，则以相同步骤继续检索u的左右孩子。当检索到达某个叶子节点时，计算叶子节点中的Iu和的内积作为相关性分数。最后对相关性分数进行降序排序得到最相关的前k个文档标识符集合FIDk(W)。Iu和内积计算的具体过程如下：

②检索得到相应验证证明proof。

CSP 根据从智能合约收到的验证令牌token，在查找表T中查找到相应的proof，T[token]=proof。

CSP 检索过程见算法2。

算法2 Search（ETr 的根节点u，TD，T，token）。

CSP 向合约支付一定的押金，再发送FIDk(W)和proof向其求证。上述过程如3.1 节步骤8 所示。

5）Verify(VK，proof，FIDk(W)，token) →1/0。

该算法由FairPayment 智能合约执行，合约对CSP 的查询结果FIDk(W)的正确性和完整性进行验证。假设从CSP 接收的验证证明是proof，合约利用从DU 接收的token，计算proof′=μVK(token‖FIDk(W))并验证等式证明proof′=proof是否成立。如果等式成立，则认为CSP 返回的检索结果正确且完整，合约将按照预定义的分配比例将DU 的搜索费用从存款池中转移给DO 和CSP（分别作为消息费和服务费），将CSP 的押金返回，并将FIDk(W)发送给DU。否则，合约将会退回DU 的搜索费并将CSP 的押金转给DU 作为补偿。上述过程如3.1 节步骤9～10 所示。

FairPayment 智能合约验证检索结果并完成公平支付过程见算法Verify（）。其中，msg.sender表示消息或交易的发送方，msg.value表示交易的金额，deposit是DU 搜索费用金额，cspdeposit为CSP 押金金额。设定deposit=2cspdeposit。

算法3 Verify（proof，token，FIDk(W)，VK）。

该算法由DU 执行。DU 根据智能合约返回的FIDk(W)收到正确的密文文档集合Ck(W)后，利用ek解密Ck(W)，得到相应的明文文档集合DCk(W)，DCk(W)=Dec(ek，Ck(W))。上述过程如3.1 节步骤11 所示。

7）GenUpdatlnto(SK，ek，VK，P，updtype，doc) →(T′，EI′，Cdoc)。

该算法由DO 执行，当DO 插入或删除标识符为doc的文档ddoc时，需要更新加密索引树和查找表，生成更新信息{T′，EI′，Cdoc}发送给CSP，此过程如3.1 节步骤12 所示。在该算法中，updtype∈{Del，Ins}表示更新类型为删除或插入；P表示在更新期间需要修改的树节点组成的集合，一般为从更新的叶子节点到根节点路径上的所有节点。具体地：

①当updtype为Del 时，DO 查找文档标识符doc对应的叶子节点并将其删除，然后遵循索引树构造规则对P中节点的向量Du依次进行修改，生成新的节点集合P′。接着通过伪随机函数对P′中内部节点的向量Du加密，得到加密后的更新信息EI′，再生成更新后的查找表T′。DO 将{T′，EI′，null}提交给CSP。

②当updtype为Ins 时，DO 首先对文档ddoc进行加密得到Cdoc，并且生成一个新的叶子节点，然后依据平衡二叉树的插入规则，在不破坏搜索索引树平衡结构的情况下更新索引树，更新时必须保证原先的叶子节点仍为叶子节点。接着更新从新叶子节点到根节点路径上的节点得到P′。最后对新叶子节点和P′中内部节点的向量Du加密得到EI′，再生成更新后的查找表T′。DO 将{T′，EI′，Cdoc}提交给CSP。

在更新查找表T 时，无论updtype是Del 还是Ins，DO 能够根据文档ddoc中所包含的关键词，迅速定位到查找表T 中包含有这些关键词的key字段。如果updtype为Del，DO 首先判断相应proof字段中doc是否属于FIDk(W)，若doc∉FIDk(W)，则相应proof字段保持不变；若doc∈FIDk(W)，则需要重新计算相应的proof字段，生成更新后查找表T′。如果updtype为Ins，对于与文档ddoc相关的key字段所对应查询关键词集合W，DO 计算文档ddoc与这些W的相关性分数：若ddoc不属于最相关的前k个文档，则相应proof字段保持不变；若ddoc属于最相关的前k个文档，则得到新的FIDk(W)，DO 重新计算相应proof字段，生成更新后查找表T′。

8）Update(C，ETr，T′，EI′，updtype，Cdoc) →(ETr′，T′，C′)。

CSP 收到DO 的更新信息{T′，EI′，Cdoc}后，根据EI′中的节点编号ID在索引树ETr 中找到对应的路径，用EI′中的更新信息替换该路径中对应节点的信息，得到更新后的加密索引树ETr′与更新后的查找表T′。如果updtype为Del，则CSP从C中删除相应加密文档Cdoc；如果updtype为Ins，CSP 将Cdoc插入原有的C中，得到更新后的密文文档集合C′。

4 安全性分析

4.1 文档的隐私性

明文文档集合被发送到CSP 之前，DO 会对其进行加密处理，并且会在对DU 进行授权认证后，通过安全信道将密钥传递给已授权认证的DU。因此只有DO 和已授权认证的DU 才能得到明文文档，未授权认证的DU 和CSP 是无法对密文文档进行解密的；而且本文方案中对于文档的检索、更新和验证操作都是基于文档标识符的，不需要访问文档内容，因此文档隐私性得到了保证。

4.2 加密索引树、查找表和搜索令牌的机密性

生成加密索引树ETr 时，采用安全K近邻算法对未加密索引树Tr 的叶子节点的索引向量Du进行加密。由于该算法具有不确定性，即使对于拥有相同关键词集合的两个文档，其加密后得到的向量Iu也不相同；对于加密索引树中内部节点创建的哈希表φu，采用伪随机函数和将关键词及内部节点对应位置的向量进行加密隐藏，CSP 在未拥有伪随机函数密钥的情况下，不能推断出内部节点向量Du。构建查找表T 时，采用伪随机函数和MAC 函数μVK分别对查询关键词集W和文档标识符集合FIDk(W)加密，生成相应字段key和proof，在CSP 未拥有密钥K1和VK的情况下，不能推断出查询关键词集W和文档标识符集合FIDk(W)。

4.3 查询的无关联性

本文方案对查询向量Q采用二进制向量随机拆分进行不确定性加密，即使对前后两次相同的搜索请求，所生成的加密查询向量也是不同的，从这个角度考虑保证了查询的无关联性。然而，当搜索请求相同时，生成的TuW却是相同的，搜索执行时访问的节点和最终得出的加密文档也都是相同的；此外，相同的搜索请求即使被加密成了不同的向量，计算得到的相关性分数也是相同的。基于以上两点，仅在CSP能够关联相同搜索请求的情况下，在已知密文模型下会泄露检索模式或访问模式。

4.4 检索的公平性

本文方案中，DU 首先把搜索费用存入FairPayment 智能合约的存款池，CSP 在执行检索任务后，向合约支付一定的押金并返回相关检索结果，合约自动验证检索结果是否正确完整。若验证通过，合约按照预定义的分配比例将DU 支付的搜索费用从存款池中转移给DU 和CSP（分别作为消息费和服务费），将CSP 的押金返回，并将搜索结果发送给DU；否则，退回DU 的搜索费并将CSP 的押金转给DU 作为补偿。所以，CSP 为了获取服务费并且不被扣除押金，将会返回正确的检索结果；同时，DU 不能恶意拒绝支付费用，智能合约会根据预设的条件自动执行协议，保证了检索的公平与可信。

5 性能分析

本文方案使用Python 实现可搜索加密算法，其中伪随机函数采用HMAC-MD5 模拟，MAC 函数采用HMAC-SHA256。以太坊的仿真实验在以太坊虚拟机（Ethereum Virtual Machine，EVM）上进行，使用Solidity 语言构建了以太坊智能合约。计算机硬件配置为Inter Core i5 7300HQ@2.50 GHz 处理器、RAM 16 GB、SSD 512 GB、操作系统为Ubuntu 18.04LTS。

5.1 关键算法性能分析

DO 索引生成阶段GenIndex 算法的计算开销包括加密索引树的构建和查找表的构建，CSP 检索阶段Search 算法的计算开销包括加密索引树的检索和查找表的定位，以下对GenIndex 和Search 的计算开销进行仿真实验。实验中使用的数据集源自文献［31］，数据包含20 个类别，共9 804 篇文档，本文选用5 000 篇文档作为测试数据。

为观 察DO 执行GenIndex 以及CSP 执行Search 的计算开销与文档数量的关系，在实验1 中设置文档数量为500～5 000（步长500），实验结果如图2 所示。从图2（a）可以看出，GenIndex 的时间随着文档数量的增加基本呈线性增长，特别地，当测试文档数为500、5 000 时，GenIndex 的时间分别为221.655 s、2 012.544 s。需要说明的是，该项操作可在离线状态下执行，消耗的时间成本是可接受的。

如图2（b）所示，可以看出，Search 的时间随着文档数量的增加基本呈对数增长，在目前实验文档数下，Search 的时间均小于1 s，时间成本是可接受的。特别地，当测试文档数为500、5 000 时，Search 的时间分别为7.5 ms 和50.2 ms。

图2 GenIndex、Search的文档数量与计算开销的关系Fig.2 Relationships between computational cost and number of documents of GenIndex，Search

5.2 智能合约性能分析

以太坊区块链在以太坊虚拟机中实现智能合约，以太坊虚拟机中的每一步操作都会产生一定的消耗，用gas 来计算，每项操作的特定gas 消耗值被称为gas used，单位gas 的价格（用以太币计算）为gas price，实际的交易成本为二者的乘积，实验于2021 年7 月25 日进行，ETH 的价格是1 ether=2175 USD，gas price=1 Gwei，1 Gwei=109wei=10-9ether。

本文方案的智能合约部署在Ropsten 测试网络中，各个实体对应的账户、合约地址见表2。

表2 各实体对应的地址Tab.2 Address corresponding to each entity

实验测试了FairPayment 智能合约中各项功能的花费，结果如表3 所示。其中，DU 获取检索结果getSearchResults没有成本，这是因为getSearchResults 只执行读取操作获取结果。表3 结果表明本文方案能够以可接受的开销实现结果验证和公平支付。

表3 智能合约花费测试Tab.3 Smart contract cost test

5.3 功能比较

将现有的基于区块链的可搜索加密方案与本文方案分别从区块链技术、执行搜索算法的平台、是否在区块链上存储加密索引、是否支持访问控制、是否支持多关键词检索以及是否支持检索结果可排序6 个方面进行对比分析，对比结果如表4 所示。

从表4 可以看出，文献［24-25］方案都是由云服务器执行搜索算法，基于比特币实现公平支付；然而由于比特币智能合约不是图灵完备的，致使交易过程复杂以及交易周期长，即使并未在区块链上存储加密索引也导致区块链开销高。在基于以太坊的可搜索加密方案中，文献［26］方案由分布式存储网络中的签约服务节点执行搜索算法，由分布式存储网络中的仲裁节点检查结果的正确性，并基于以太坊智能合约实现公平支付；然而由区块链存储复杂且占用空间较多的索引导致区块链开销增加。文献［27-29］方案都是基于以太坊智能合约执行搜索算法以及实现公平支付；但是由于区块链存储复杂且占用空间较多的索引会消耗大量时间并且智能合约执行复杂的搜索算法亦会使费用成本增加，两者均导致区块链开销升高。本文方案由云服务器存储加密索引树和查找表，同时执行搜索算法，基于以太坊智能合约实现公平支付，有效降低智能合约执行操作的复杂性，从而降低区块链开销；此外，在访问控制、多关键词检索和检索结果可排序方面，仅本文方案同时支持此三项功能。综上分析，在以上功能方面，相较于对比方案，本文方案考虑较为全面。

表4 基于区块链的可搜索加密方案的功能对比分析Tab.4 Functional comparison and analysis of searchable encryption schemes based on blockchain

5.4 计算开销对比

将本文方案与相关对比方案在索引、搜索、验证方面的计算开销进行对比，结果如表5 所示。其中E0和E1分别表示两个不同乘法循环群上的指数运算，MM表示模乘运算，H 表示散列运算，F表示伪随机函数运算，V表示MAC函数运算，L表示构建每个内部节点的操作，X 表示n维向量间点积运算，E和D分别表示加密和解密操作，M表示取模运算。SIG表示签名算法，包含签名和验证2 个过程；“—”表示不参与此项操作。g表示条件表达式的记录条数，IA表示与门访问策略的下标，Y 表示树型访问策略的叶子节点个数，j表示返回密文文件个数，a表示满足条件表达式的文档标识符被分割成的份数，b表示数据使用者预测步数，t为W中的关键词数量，n为关键词字典DW的大小，Z为查找表中记录数量，θ为包含查询关键词的文档数量，现实场景中，θ远小于文档集合基数m。

表5 基于区块链的可搜索加密方案的计算开销对比分析Tab.5 Computational cost comparison and analysis of searchable encryption schemes based on blockchain

索引生成阶段，文献［24］方案需要在关键词字典和包含关键词的文档集合上进行1 次伪随机函数运算、1 次散列运算、1 次签名算法运算。文献［25］方案需要在关键词字典和包含关键词的文档集合上进行3 次伪随机函数运算、1 次加密操作、1 次散列运算。文献［26］方案需要在文档的ID 和添加标记集合上分别进行1 次散列运算，在明文文档合集上进行1 次加密操作，在关键词字典上进行1 次伪随机函数运算。文献［27］方案的数据拥有者需要进行a次耗时的模乘运算，还要进行2(a+1)g次伪随机函数运算。文献［28-29］方案的数据拥有者都需要进行耗时的指数和模乘运算，同时，文献［28］方案需要在每个关键词上进行2 次伪随机函数运算，文献［29］方案进行1 次伪随机函数运算。本文方案采用平衡二叉树作为索引，检索效率高，内部节点的构建需进行m-1 次，每个内部节点的加密需要对其向量中的每一位进行1 次对称加密运算，每个叶子节点向量由安全K近邻算法进行加密，需进行两次n×n矩阵与n维向量的乘法运算；构建一个与加密索引树相匹配的查找表，需要进行Z次伪随机函数运算和Z次MAC 函数运算。

搜索阶段，文献［26］方案对发布列表和文摘索引分别进行O(Z)次比较，再进行m次散列运算搜索。文献［27］方案需要进行b次耗时的模乘运算，还要进行2b次伪随机函数运算。文献［28-29］方案生成键值对的查找表作为索引，具有O(Z)的搜索效率。文献［26-29］方案均在区块链上存储加密索引和执行搜索算法，致使区块链开销高，既占用存储空间，效率也低。而文献［24-25］方案与本文方案都采用CSP进行搜索，CSP 存储密文文档和加密索引，能减小区块链开销，提高检索效率。本文方案对内部节点进行tθ(lbm-1)次解密运算，在最坏情况下，需做2θ次两个n维向量间的点积运算和θ次取模运算，根据DU 的token在查找表中定位相应的proof，需要进行O(Z)次比较操作。

验证结果的正确性阶段，文献［24］方案移除审计机构，但需要用户在本地进行m次散列运算和m次签名算法运算，随着文档数量的增加，验证时间增加。文献［25］方案仅需要进行4 次散列运算，但过程中需要涉及到比特币脚本上的6笔交易，验证时间长、效率低。文献［26］方案需要分布式存储平台中仲裁者分片上的每个仲裁节点对用户端获得的添加标记集合进行j次散列运算，再重新执行搜索操作进行m次散列运算以验证检索结果，计算开销大。文献［29］方案和本文方案采用智能合约进行搜索结果的验证，文献［29］方案需要进行j！次散列运算，本文方案仅需要进行1 次MAC 函数运算，判断MAC 函数运算后值是否正确，完成验证。

综上所述，相较于其他具有验证功能的对比方案，本文方案在验证阶段的计算开销是最低的。这是由于本文方案采用CSP 存储密文文档和加密索引、并执行搜索算法，而智能合约仅需执行验证和公平支付操作，使得其计算开销低；但是这也导致CSP 的存储开销和计算开销有所增加，但从搜索阶段计算开销的分析和Search 算法的实验结果可以看出，CSP 搜索阶段的计算开销也是可以接受的。

6 结语

本文提出了一种基于以太坊区块链的支持验证与公平支付的多关键词排序检索方案，实现了检索结果的验证、交易三方间的公平支付以及对密文的多关键词排序检索。为了实现检索结果的可验证与公平支付，同时降低时间和费用成本，方案设计由云服务器存储加密索引树和查找表、并执行搜索操作；由以太坊智能合约完成检索结果的验证与公平支付，有效降低了智能合约执行操作的复杂性，减少了时间和费用开销，提高了验证效率；此外，方案以平衡二叉树为索引，在保证检索效率的同时，实现了多关键词检索、检索结果可排序和动态更新功能，提升了方案的灵活性和用户友好性。最后对方案的安全性和性能进行了分析，并对方案进行了仿真实验。性能分析及实验结果表明本文方案具有可行性与实用性。功能对比结果表明，相较于现有的基于区块链的可搜索加密方案，本文方案在功能方面考虑更为全面。此外，本文方案的验证过程是针对所有检索结果进行的，有进一步优化的空间。未来研究针对特定交易的验证策略，以更好地满足用户需求，同时降低时间成本和费用成本。