支持多用户场景的区块链可搜索加密新方案*

周 让，杨 可，汪小芬，曹 晟，张晓均，张小松，4

1.成都理工大学 计算机与网络安全学院，成都610059

2.电子科技大学 网络空间安全研究中心，计算机科学与工程学院，成都611731

3.西南石油大学 计算机科学学院，成都610500

4.鹏城实验室 网络空间安全研究中心，深圳518055

1 引言

随着互联网和云计算的飞速发展，大量与生活生产相关的数据被采集和利用，使得数据规模呈现爆发式增长，与之相伴的是数据存储需求的大幅增加.为了有效应对这个需求，更多的组织和个人选择将数据外包到第三方云存储平台进行存储，以降低存储开销.而数据的外包存储，增大了数据泄露的风险.为了降低数据泄露风险，研究人员引入数据加密来保障数据的机密性，从而实现数据的安全外包存储.进一步地，数据要产生价值，还需要被有效利用，就需要为具体的数据分析提供精准的数据，如何在加密数据中精准定位所需数据就成了一个亟需解决的问题.为了解决这个问题，研究人员引入可搜索加密技术[1-4].而可搜索加密又主要分为非对称可搜索加密[5]和对称可搜索加密[6].

在非对称可搜索加密中，数据发送者使用数据拥有者的公钥来加密数据文件并生成搜索标签，将其发送给云服务器，数据拥有者使用自身私钥生成的搜索令牌，并将其发送给云服务器进行搜索匹配.Boneh等人[5]首先提出了第一个基于公钥体制的可搜索加密方案，在该方案中，任何数据发送者都可以向云服务器发送加密数据，但只有数据拥有者才能生成取回对应数据的搜索陷门.而这个方案并不安全.文献[7]指出文献[5] 的方案存在由于关键字空间远小于密钥空间导致的离线关键字猜测攻击.针对这个问题，文献[8] 和文献[9] 分别提出改进方案，其中文献[8] 通过引入概率陷门的生成方法，并结合不经意传输的使用来实现对外部恶意敌手关键字猜测攻击的抵抗，而文献[9] 通过引入救援服务器的方式来实现对内部敌手发起的关键字猜测攻击.尽管公钥可搜索加密在密钥分配管理和安全性上有更好的优势，但其无法避免计算开销较大的问题.

与非对称可搜索加密相对应的是对称可搜索加密，其普遍具备更高的搜索效率.第一个对称可搜索加密方案由Song 等人[2]提出，该方案允许客户端使用对称密码体制进行数据文件的加密和解密，同时服务器的搜索时间和文档的数量呈线性正相关.接着，文献[10] 通过安全索引增强Song 等人方案的安全性.而文献[6] 使用关键字来生成安全倒排索引的标签，极大地提升了搜索效率.此后，研究人员将目光转向实际应用中的动态更新问题，并由Kamara[4]提出了首个动态对称可搜索加密方案，其实现了对文件动态更新的支持.

然而，文献[11] 指出，在少量泄漏发生的情况下也将使敌手有能力推断出数据中隐藏的敏感信息，换而言之，如果敌手获得了部分数据拥有者的文件内容或者文件内的关键字，敌手就可以从泄漏函数中推断出客户端所进行的查询.进一步地，文献[12] 提出文件注入攻击，这种攻击仅用少量的注入文件就可以获取完整的客户端查询，使得动态可搜索加密方案的安全性遭受威胁.为了应对这类攻击，文献[13，14] 引入前向隐私安全，且文献[14] 使用陷门置换更新存储在客户端状态的方式来实现前向隐私.为了进一步提升更新算法效率，文献[15] 提出了一种基于I/O 的前向隐私对称可搜索加密方案，在该方案中，客户端每次执行完搜索后都会对存储在本地的更新密钥进行更新迭代，使得服务器无法从已知的密钥或状态来预测未来的密钥或状态，从而实现前向隐私.接着，云服务器作为服务实体，遭受到各种网络攻击而导致其所存储的数据易被篡改，使得返回数据不完整或错误.因此，还需要对返回的搜索结果进行完整性验证，以确保返回数据完整有效.为实现这个目标，研究人员提出了具有验证功能的对称可搜索加密方案.文献[16] 构建了第一个基于特征树可验证对称可搜索加密方案，但该方案不支持动态更新操作.随后，文献[17] 利用可验证的哈希表构建了一个新的可验证对称可搜索加密方案，其能支持文件的动态更新.为了进一步提升更新效率，文献[18] 提出了一种基于增量哈希的可验证数据结构来实现对所搜索返回数据的有效验证.尽管基于云存储的可搜索加密方案能通过对返回数据的验证来实现对搜索结果的验证，但其往往以额外的计算步骤来生成验证证据，从而完成验证，使得搜索需要消耗更多的时间成本才能完成.

为了降低这个时间开销，区块链存储被引入到可搜索加密的研究中，借用区块链本身所具有的不可篡改特性，来实现对返回数据完整性的验证.文献[19] 中提出了一种基于比特币的对称可搜索加密方案，将加密数据和加密反向索引嵌入到交易脚本中实现搜索标签记录，但该搜索方法执行效率较低.文献[20] 也通过区块链实现了对用户数据搜索的支持，但该方案没有考虑到实际搜索中的动态更新需求.为了满足动态更新需求，文献[21] 支持用户通过智能合约对加密数据进行搜索和动态更新操作，并利用打包技术来降低交易汽油费，但该方案不支持前向隐私安全.文献[22，23] 将区块链作为一个记录搜索请求和搜索结果的公开账本，提出了具有双重验证机制的对称可搜索加密方案.文献[24] 将区块链作为第三方可信监督实体来实现搜索结果返回验证，但该方案并不能抵抗关键字注入攻击，也没有考虑搜索陷门的安全性.

已有方案虽然实现了区块链可搜索加密，但都只能支持单用户场景，而不适用于多用户场景.基于此，研究人员提出了一系列面向多用户场景的区块链可搜索加密方案[25-27].文献[25] 将方案部署在比特币平台上，但需要通过在用户和云服务器上构建一系列辅助实现搜索的参量才能有效完成搜索请求的生成，其灵活性较差.另一方面，文献[26，27] 通过构建非对称密码算法来实现对多用户场景的支持，但其搜索匹配部分执行开销较大，在区块链上难以有效执行.并且，这些已有方案均未关注搜索陷门的伪造问题.尽管现有方案能支持多用户场景的区块链可搜索加密，但仍存在搜索陷门被伪造、搜索执行效率较低等问题.因此，提出一个能同时支持多用户场景和搜索陷门防伪造的区块链可搜索加密方案势在必行.

本文从区块链数据存储和搜索的实际应用需求出发，提出了一个支持多用户场景的区块链可搜索加密新方案，以解决区块链环境下多用户的数据搜索、搜索陷门安全性和搜索效率等问题.首先，通过将同态异或加密函数加入密钥生成，来实现对多用户搜索权限的控制，以满足多用户场景下的区块链数据搜索;其次，通过对搜索陷门进行签名，来实现对搜索陷门的验证，确保所发起的搜索是合法的，以增强搜索陷门安全性;接着，利用缓存命中的方法，在智能合约中加入搜索结果存储列表，来降低二次搜索的匹配开销，进一步提升搜索效率.评估分析表明，所提方案的搜索执行效率更高.而仿真模拟结果表明，本文所提出的方案在本地测试网络和Goerlic 测试网络上均能有效执行，具有较强的实用性.

2 预备知识

2.1 安全性假设

2.1.1 计算性Diffie-Hellman 困难问题(CDH)

定理1计算性Diffie-Hellman 困难问题(CDH): 在群G上，已知g，ga，gb G，其中g为群G的生成元，a，，计算gab G是困难的.

2.1.2 伪随机函数

伪随机函数(pseudorandom function，PRF) 作为一个由确定性算法生成的数学函数，主要用于构建安全的密码原语和安全的加密协议，其能在给定密钥的情况下使得所生成的输出具备随机性.

定理 2假设 key←KeyGen(λ) 是通过标准的密钥生成算法生成的随机密钥，随机函数R:{0，1}λ ←{0，1}l，函数F:{0，1}λ ←key×{0，1}l，若对于任意概率多项式敌手都有

若negl(λ) 是一个可忽略的概率多项式函数，则F是一个伪随机函数.

2.2 同态异或函数

同态异或函数是一种带有加密性质的伪随机函数，该函数具有以下性质:

其中，ki和kj表示具有相同位长的随机密钥.该函数中fki(x1) 和fkj(x2) 输出的随机结果进行异或运算，其结果与输入值异或绑定后使用两个随机密钥ki和kj异或后运算产生的随机输出结果相等.为了实现上述性质，该函数利用了一个安全的Fisher-Yates 排列算法[28]来产生均匀随机分布的输出.

2.3 对称可搜索加密

对称可搜索加密主要利用相应对称密码体制和相关密码原语实现对存储在不可信环境中存储的加密数据的搜索和查询，其目标是保护搜索过程中的数据隐私.其定义如下:

· 初始化算法(σ，key，EDB)←SetUp(DB，λ): 初始化算法通过输入待加密数据文档DB、安全参数λ，得到输出加密后的数据文档EDB，客户端将加密数据文档EDB 上传给第三方云服务器，将对称加密密钥key 和状态σ秘密保存在本地;

· 搜索协议(σ′，ST;R，EDB′)←Search(key，w，σ;EDB，ST): 搜索协议通过交互的方式运行在客户端和云服务器之间.客户端使用本地秘密保存的对称加密密钥key 和待搜索的关键字w运行搜索令牌生成算法得到相应的搜索令牌ST 和状态σ′;云服务器接收该客户端的搜索令牌ST，输入加密数据文档EDB 来执行搜索操作.搜索匹配结束后，云服务器向客户端返回对应的搜索结果R并更新云服务器上的加密数据文档EDB′;

· 更新协议(σ′，EDB;EDB′)←Update(key，σ，DB;EDB): 更新协议交互式的运行在客户端和云服务器之间，客户端使用对称加密密钥key，运行对称加密算法对数据文档DB 进行加密得到加密后的数据文档EDB，同时输出更新后的状态σ′;客户端将加密数据文档EDB 发送给第三方云服务器进行存储，保存更新状态σ′;云服务器更新加密数据文档EDB′.

2.4 区块链和智能合约

区块链是一个由固定长度的块组成的链状分布式数据库，其中加密哈希函数和区块之间的共识机制保证了区块之间链接的安全性，且每个连接到链上的区块由网络中的所有节点参与维护和验证，使得区块链具有去中心化、透明性和不变性的特征[29].智能合约是一种部署在区块链上的计算机程序，其中交易双方的协议条款被直接编码到代码中，依靠设定好的用户输入或协议条件在受到监督的状态下自动触发执行[30].因此，智能合约能够可靠地执行交易，且所有交易都满足可追溯和不可篡改的特性.

3 系统架构

3.1 系统概述

系统构架如图1 所示，包括四个参与实体: 数据拥有者、用户、区块链和智能合约、IPFS 分布式数据库.数据拥有者: 被认为是一个完全诚实的实体，其行为不会对系统造成威胁.其负责方案流程中密钥的生成和分发，智能合约的部署，数据的加密上传以及搜索令牌的签名、生成和发送.用户: 负责向数据拥有者提出搜索请求.区块链和智能合约: 区块链负责加密索引的存储，智能合约负责签名验证和搜索匹配.IPFS 分布式数据库: 负责加密文件数据的存储.系统的工作流程如下: 数据拥有者通过安全信道分发密钥给所有注册用户保证系统的密钥传输安全性;使用对称加密密钥和IPFS 分布式数据库对相关数据进行加密操作和存储操作保证文件的机密性;将加密文件索引上传到智能合约，由智能合约写入区块链来避免数据的单点故障问题;授权用户利用授权密钥生成关键字授权搜索令牌，并将其发送给数据拥有者;数据拥有者为该用户的搜索令牌进行签名，同时将公钥信息与该签名一并发送给智能合约，该公钥不仅用于签名验证，还将作为搜索令牌的一部分参与搜索匹配;智能合约首先验证数据拥有者发送的搜索令牌，确认其不是伪造的;然后在存储的字典中进行搜索结果的搜索匹配测试，并将匹配测试的结果存储到智能合约上该关键字对应的结果列表中;智能合约将对应的搜索结果给用户;用户用得到的搜索结果集合向IPFS 分布式数据库发起返回文件获取请求，得到对应的加密文档.

图1 系统构架Figure 1 System structure

3.2 系统模型

本文所提出支持多用户场景下的区块链动态对称可搜索加密系统模型主要由以下四个部分组成:

· 初始化(PG，key，E;Dict)←SetUp(λ): 数据拥有者运行初始化算法，在区块链上部署智能合约;数据拥有者输入安全参数λ，输出公钥参数PG、对称加密密钥key 和空字典E，其中key 被数据拥有者秘密保存，字典E被用于存储待加密关键字的相关状态;智能合约初始化加密索引空字典Dict，用于存储数据拥有者发送的加密数据.

· 更新(EDB，ρ′;Dict′)←Update(key，w，ind，op，ρ;Dict): 数据拥有者和区块链上智能合约运行更新协议，数据拥有者输入对称加密密钥key 和待更新的关键字文档对(w，ind)、操作符opadd，del}以及客户端状态ρ，输出更新后的加密数据文档EDB 以及更新后的数据拥有者的状态ρ′.区块链上智能合约接收数据拥有者发送的加密数据文档EDB，更新加密索引字典Dict 得到Dict′.

· 搜索(STu;ST;ρ;IR;Dict′)←Search(，w;E;ρ，key;Dict): 搜索协议主要运行在数据拥有者，授权用户和智能合约之间，具体流程如下: 授权用户使用数据拥有者颁发的授权密钥和待搜索关键字w生成用户搜索令牌STu，并将其发送给数据拥有者;数据拥有者接收用户搜索令牌，输入本地秘密存储的关键字状态字典E、数据拥有者的状态ρ以及对称加密密钥key，输出用于匹配的搜索令牌ST，再将其发送给智能合约，并更新本地的状态得到ρ′;智能合约收到该搜索令牌后，对加密索引字典Dict 进行搜索，得到索引结果集合IR，同时更新该加密索引字典得到Dict′，并将搜索得到的索引结果集合IR 返回给搜索用户;该索引搜索结果集合用于向IPFS 分布式数据库发起对应的加密文件返回请求.

3.3 安全威胁模型及安全性需求

针对支持多用户场景的可搜索加密方案，其主要存在以下三方面的安全性需求: 给定泄露函数下的自适应语义安全、给定泄露函数下的前向隐私安全和搜索陷门的不可伪造性.接下来，将通过引入概率多项式敌手A和挑战者C以及模拟器S的游戏来对安全威胁模型进行形式化的定义.

3.3.1 给定泄露函数下的自适应语义安全

假设动态对称可搜索加密方案为Φ(SetUp，Control，Update，Search)，方案的泄露函数为L(LSetUp，LControl，LUpdate，LSearch).通过引入泄露函数和两个概率多项式游戏，形式化语义安全描述如下:

· RealA(λ): 挑战者C运行初始化算法SetUp，得到系统参数PG 以及对称加密密钥key;随后，C执行Update 算法，将加密后的数据文档EDB 返回给敌手A;上述阶段完成后，A自适应地选择查询qi，C判断查询的类型;如果查询是一个用户权限控制查询，则C运行用户权限控制算法Control，从A处接收权限控制查询qi、用户列表User 和操作符op，生成新的用户列表User′并返回给敌手A，其中opadduser，deluser};如果查询是一个搜索查询，则C运行搜索算法Search，从A处接收搜索查询qi、状态ρ，在加密数据文档EDBi中进行文件匹配，输出匹配结果Result，搜索后的数据文档以及新状态ρ′;如果查询是一个更新查询，C运行更新算法Update，C从A处接收更新查询qi、状态ρ，并更新加密数据文档EDBi，输出更新后的数据文档和新状态ρ′;自适应查询完成后，A输出一个真实游戏返回的比特0，1}.

· IdealA(λ):S利用泄露函数LSetUp生成系统参数PG 并返回给敌手A;随后，S利用泄露函数LUpdate生成加密数据文档EDB;A自适应地选择查询qi，S判断查询的类型;如果查询是一个权限控制查询，则S运行LControl模拟更新后的用户列表User′并将其返回给敌手A;如果查询是一个搜索查询，则S运行LSearch泄露函数模拟搜索结果并返回给A，同时输出搜索后的数据文档以及新状态ρ′;如果查询是一个更新查询，S利用泄露函数LUpdate模拟更新后的数据文档和新状态ρ′;自适应查询完成后，A输出一个模拟游戏返回的比特b′0，1}.

定理3对于任何概率多项式敌手A来说，如果存在一个模拟器S满足

则方案Φ是L-自适应安全的对称可搜索加密方案，其中概率多项式函数negl(λ) 是可以忽略的.

3.3.2 前向隐私安全

为防止动态可搜索加密方案中的文件遭受注入攻击[12]，研究人员提出了前向隐私安全的需求，来确保服务器在新添加的文件时，该文件的更新令牌无法与客户端之前的搜索令牌建立链接.而在更新操作完成后，服务器也将无法泄露所更新关键字的任何信息.由此，达到给定泄露函数L下的前向隐私安全，其安全威胁模型描述如下:

定理4如果一个具有L-自适应安全的动态可搜索加密方案Φ具有前向隐私安全性，则该方案需要满足更新查询qi(indi，wi，opi) 的泄露函数为LUpdate(qi)(i，opi，indi).

3.3.3 搜索陷门的不可伪造性

为增强多用户管理，防止搜索陷门中的关键字信息泄露，需要通过对数据拥有者发送的搜索陷门进行签名，来实现数据拥有者搜索陷门的不可伪造性，其安全威胁模型描述如下:

· SetUp: 假设SP 为系统参数，模拟器S执行密钥生成算法生成密钥对(PK，SK)，将公钥PK 发送给敌手A，S存储私钥SK 用于回应A的签名查询.

· Query: 敌手A自适应地选择消息mi进行签名查询，对于A提交的消息mi，模拟器S运行签名算法，计算δmi并发送给A.

· Forgery: 敌手A返回一个关于某个消息m*的伪造签名，其中，该签名不仅要是消息m*的合法签名，还要满足消息m*在Query 阶段没有被询问过.

若敌手A能够在此安全威胁模型下成功伪造签名，则视为敌手A取得了该攻击游戏的胜利.敌手胜利的概率ε是概率多项式敌手A在此安全威胁模型下成功伪造签名的可能性.

定理5如果敌手A无法在时间t内进行q次签名询问后，以概率ε赢得上述游戏，则该签名方案在EU-CMA 安全模型下是(t，q，ε) 安全的.

4 方案构建

4.1 方案具体构建

本文所提方案主要由初始化、用户权限控制、更新和搜索四个部分组成，通过在区块链上额外设置一个存储搜索结果的字典来提高本方案的二次搜索效率，以更加有效地实现搜索和更新操作;同时，还利用了文档打包技术来减少存储过程中发送的交易量，以减少区块链上的存储代价.

如算法1 所示，在系统初始化中，数据拥有者通过安全参数λ计算系统公钥参数PG(G，g，e) 以及对称加密密钥key;智能合约初始化两个字典，Dict 和DictI，其中Dict 用于存储加密索引，DictI是一个基于搜索令牌的字典，其键值对为搜索令牌和该搜索令牌下的结果集合.

如算法2 所示，用户权限控制协议主要包括添加用户和撤销用户功能;具体而言，在添加用户时，数据拥有者为各个申请注册的用户随机生成授权密钥keyci和随机秘密字符串ri(line 3—4)，其中keycikey⊕ri;在删除用户时，数据拥有者从用户列表中删除用户和该用户对应的随机值ri.

更新协议主要运行在数据拥有者和智能合约之间.如算法3 所示，数据拥有者使用同态异或加密函数fkey生成该关键字的更新状态tw，并将tw 秘密保存在本地(line 3);随后，数据拥有者使用状态tw 取出待搜索关键字w下的状态值ϱ(st，α，c)，其中(st，α) 是数据拥有者利用系统公钥参数PG 生成的公私钥对(line 3—7);同时，数据拥有者还对所有文档标识符进行打包处理以减少存储过程中的交易量(line 10).当所有数据文档DB(w) 被完全加密后，数据拥有者将所有加密文档分成n块，并嵌入到交易中发送给智能合约.因此，一个交易中含有的(w，ind) 对数目为n×P;最终，智能合约接收数据拥有者发送的数据后，将加密标签和加密文档存储在字典Dict 中.

搜索协议是一个三方运行协议，运行在授权用户、数据拥有者和智能合约之间，如算法4 所示.首先，授权用户利用同态异或函数f和随机字符串S生成授权搜索令牌ST.其中，随机生成的字符串S和待查询的关键字w通过异或操作绑定后作为同态异或函数f的输入，授权密钥被作为同态异或函数f的密钥(line 1—3);随后，数据拥有者利用同态异或函数的性质计算关键字搜索状态tw，其中fkey(w)(line 4—6);数据拥有者依据搜索状态tw 从本地存储的字典E取出该令牌对应的的状态(st，c，α).数据拥有者使用私钥α对令牌(c，tw) 进行签名，同时更新该关键字w下的公私钥(st，α).上述操作意味着数据拥有者每进行一个搜索查询，搜索状态就发生一次改变.接着，数据拥有者将计算后的(kw，tw，c，σ) 作为搜索令牌发送给智能合约，其中，tw 是待搜索关键字w的公钥st，c是该关键字下的文档索引ind 的数目;智能合约接收搜索令牌后，首先验证签名的合法性.如果签名验证通过，智能合约使用搜索令牌tw 查找反向索引结果字典DictI，并将结果加入结果集合Result.最后，智能合约计算加密标签，在字典Dict 中进行文件匹配，将匹配后的结果加入字典DictI和结果集合Result 中，并将结果集合Result 返回给用户(line 21—29).

4.2 方案安全性分析

4.2.1 给定泄露函数下的自适应语义安全分析

为了证明本方案能满足给定泄露函数下的自适应语义安全，就需要证明本方案满足定理3，这里设计了一系列不可区分混合游戏的模拟，其具体模拟过程如下.

证明:假设Game0为本方案的真实方案，故游戏Game0中不做任何改变，因此Game0和真实方案是不可区分的:

模拟游戏Game1中使用伪随机函数HF 代替方案中的同态异或函数f;在数据拥有者的更新阶段、搜索询问生成阶段中，对同态函数f的每次输入都被模拟器S1模拟成对伪随机函数HF 的输入，在伪随机函数HF 中，同态异或函数f的密钥被嵌入伪随机函数HF 的输入中;敌手A发起询问后，S1通过随机函数HF 运算得到一个随机值;同样地，为了避免失败模拟，S1将在Game1中设置一个Bad1变量表示模拟终止的情况，这种情况主要出现在A构建不同的值向伪随机函数HF 发起询问时，HF 返回相同值的情形.且只有在这种情形下，游戏Game1才会终止，敌手才能区分Game1和真实游戏.总而言之，游戏Game1除了将同态异或函数替换成伪随机函数之外，同Game0毫无差别.由于A不能区分一个同态异或函数f和一个伪随机函数HF，所以Game1和Game0是不可区分的.对于游戏Game1来说有一个模拟器S1满足:

模拟游戏Game2将生成授权搜索令牌tw 中的同态异或函数f建模为一个黑盒函数FF，模拟器S2无法知道黑盒函数运行的具体细节和相关密钥.同态异或的性质导致了在授权令牌生成阶段，该函数的输出总是和更新阶段中本地更新令牌一一对应.为了保证模拟正常进行，Game2设置FF(r ⊕s)HF(⊕w ⊕S)⊕HF(key⊕w).因此，当S2输入一个固定的值时，总是能够得到一个固定的输出值.在此轮游戏中，Game2除了在搜索算法的数据拥有者搜索令牌生成阶段中将同态异或函数替换成黑盒函数FF 之外，同Game1毫无区别.通过一个标准的论证，模拟器S2满足:

在模拟游戏Game3中，哈希函数H1和H2被替换为随机预言机HH1和HH2.同样地，模拟器S3使用变量Bad2表示随机预言机HH1和HH2在输入值不同的情况下，输出值相同的情况.且只有在这种情况下，Game3才会终止.确切来说，在Game3中，加密数据不是通过哈希函数来生成相应掩码，而是通过A对随机预言机H1和H2的询问得到任意的随机值来模拟生成的.当H1和H2的输出发生碰撞时，Game3被终止，A能够区分出Game3和真实游戏.通过上述论证，在模拟游戏Game3中，除了标签的生成形式不同之外，Game3和Game2是不可区分的.因此，对于游戏Game3，有:

模拟游戏Game4使用六个字典TW、L、T1、ST、LW、T2匹配在Game1、Game2和Game3游戏中产生的随机数;同时模拟器S4初始化一个关键字计数器sw来该记录搜索协议中，待搜索关键字w的搜索次数;在初始化阶段，关键字计数器sw被初始化为0.在搜索协议中，关键字w每被搜索一次，计数器sw就增加一次;相较于Game3来说，Game4只使用了字典来记录随机值的生成，而其他方面没有做任何改动.因此，在敌手A的角度看来，Game4和Game3是无法区分的.对于模拟器S4来说，有:

同游戏Game4不同的是，Ideal 中的模拟器S将关键字w匹配|w|.具体而言，在搜索过程中，模拟器S将关键字w映射到只泄露了关键字的长度信息.除了泄露函数外，模拟器不需要输入任何其他的信息.

综上，在模拟游戏和真实游戏中，对于任意敌手A来说，如果存在一个概率多项式模拟器S满足:

则方案Φ是L-自适应安全的对称可搜索加密方案.因此，定理3 得证，所提出的方案Φ能满足给定泄露函数下的自适应安全.

4.2.2 给定泄露函数下的前向隐私安全分析

证明:通过对方案给定泄露函数下自适应安全的安全性分析，可以得到方案Φ的泄露函数L为LSetUp(λ)，LControl(λ，|User|)，LUpdate(w，ind，op)，LSearch其中，|User| 指注册用户的数量.在给定泄露函数L下，该方案前向隐私安全性分析和文献[17] 类似，这里不再赘述.因此，定理4 得证，所提出的方案能满足给定泄露函数下的前向隐私安全.

4.2.3 搜索陷门的不可伪造性安全分析:

在本文所提方案中，数据拥有者搜索陷门的不可伪造性是依靠签名的不可伪造性来实现的.因此，证明搜索陷门的不可伪造性即是证明搜索陷门签名的不可伪造性.

假设哈希函数H是一个随机预言机，如果CDH 问题是困难的，则关于搜索令牌的签名方案在EUCMA 下安全模型下是可证明安全的.换而言之，若存在一个敌手A可以在EU-CMA 的安全模型下以(t，qH，ε) 破坏搜索陷门的签名，则存在一个模拟器S能够解决CDH 问题，其中t代表模拟器运行的最大时间，qH代表敌手进行哈希询问的次数，ε表示概率多项式敌手A在EU-CMA 安全模型下破坏搜索陷门签名的概率.

证明:假设(g，ga，gb) 是系统参数PG 的一个实例，模拟器S将控制随机预言机H按照以下的描述进行工作.

SetUp:设置系统参数为PG，H是一个随机预言机，公钥st(h1ga)，S设置私钥αca.

H-Query:在敌手A对随机预言机进行Hash 询问之前，S随机选择一个整数[1，qH]，其中qH指的是A对随机预言机的查询次数，于此同时，S使用Hash 列表回应A的查询.若Hash 列表中没有记录A的查询，则S从ZP中选择一个随机数si，同时按照以下的方式设置H(mi):

Query:A进行对消息mi进行签名询问，如果说消息mi是在Hash 列表中的第i-th 询问，则模拟停止，否则S设置H(mi).同时S模拟签名为.根据签名的结构定义，这个签名是一个有效的签名，有:

不可区分性:此轮模拟游戏主要在初始化阶段以及A进行Hash 询问阶段使用了随机数，本轮模拟中使用的随机数如下:

其中，a，b以及si都是从ZP中随机选择的，且各个随机数之间相互独立.因此，在此轮模拟游戏和真实游戏之间具有不可区分性.

成功模拟的概率:如果敌手A能够成功伪造签名，需要满足以下条件: (1) 消息m*没有被询问过;(2) 敌手A对消息m*进行签名伪造时，满足签名结构;(3) 消息m*是在Hash 列表中第i-th 个消息;因此，成功模拟并发起有效攻击的概率是

综上所述，敌手A解决CDH 的概率为，其中，qH是敌手A对模拟器S上随机预言机进行Hash询问的次数.而这个概率是可以忽略的，即敌手不能成功伪造签名.因此，定理5 得证，本文所提方案满足搜索陷门签名不可伪造.

5 方案功能及效率分析

5.1 同现有方案的功能和安全性对比

表1 从对用户场景的支持和安全性两方面出发，对本文所提方案与现有区块链对称可搜索加密方案进行了对比分析.分析结果表明，本文所提方案能更好地扩展到多用户场景，并满足形式化的语义安全性，使其在功能和安全性上均优于现有方案.

表1 方案对比Table 1 Comparison among different schemes

5.2 同现有方案的效率比较

表2 从标签生成、搜索令牌产生、第一次搜索时间、第二次搜索时间、更新复杂度和更新时间等方面出发，对本文所提方案与一些现有区块链对称可搜索加密方案进行了效率对比分析.分析结果表明，经过两次搜索过后，本文方案的搜索时间将降低至常数级别.进一步分析，形成该结果的主要原因为搜索结果存储字典的引入，使得本文所提方案在二次搜索上展现出较强的搜索效率.此外，为了实现搜索令牌的不可伪造性以增强方案的安全性，本方案在生成搜索令牌时多进行了一次签名操作，使其计算量增大，但该签名操作是由计算能力较强的数据拥有者端来执行，因此，本文所提方案计算生成搜索令牌的代价是可以容忍的.

表2 效率对比Table 2 Performance comparison

5.3 仿真评估

5.3.1 仿真环境及方案实现概述

仿真所用设备为英特尔酷睿i9-12900k，64 GB 内存的服务器，用于实例化系统中的数据拥有者;在测试数据集方面主要选用安然电子邮件数据集[31]，其是一个包含大约50 万封的来自约150 位用户的电子邮件集合，而仿真模拟所采用的数据测试集为该电子邮件数据集的四个子集.

仿真采用了混合编程的方式，在数据预处理、数据拥有者端和客户端实现、以太坊智能合约实现三个不同的部分分别使用了Python、Java 和solidity，并利用web3js 和javascript 来完成中间层交互.

具体而言，通过对所选用的数据测试集进行数据预处理以获得相对应的(w，ind) 对，其中w表示数据库中的关键字，ind 指的是包括该关键字的文档索引，而每个测试文件仅包含一个加密的(w，id) 对，EDB size 表示加密文档集总和所需要的存储空间，数据集处理结果的详细描述如表3;而算法的具体实现过程中，选用了Keccak256 和HMAC-SHA256 来实现伪随机函数PRF 和随机预言机;接着，为了保证智能合约能正确验证方案的签名，数据拥有者端的签名算法使用了基于椭圆曲线的算法签名ECDSA.此外，为了满足数据集初始化过程的存储需求，减少数据拥有者发送的交易数量，打包参数P被设置成8.进一步地，本仿真将数据库分成了n块，每个块中最多包含40 个文档条目.而当数据拥有者在初始化文档发送交易时，每个交易至多包含320 个文档条目.

表3 加密数据集处理结果Table 3 Properties of encrypted data set

为了更加准确地评估本文所提方案，仿真实现主要考虑了理想环境和真实环境下的智能合约仿真模拟: 第一个为理想环境的模拟，主要通过使用Ganache 在本地部署模拟网络的方式实现;第二个为真实环境模拟，主要通过使用以太网Goerli 测试网络的方式实现，来使得运行环境更加靠近真实环境.进一步地，方案执行效率主要通过加密文件大小、时间、存储开销以及交易数量的具体执行参数来进行评估.

5.3.2 本地模拟性能评估

本地模拟网络环境下，仿真初始化了十个测试账户，每个交易的gas 数量上限为6721 975，每个gas的费用被设置为20 000 000 000 wei，同时将出块时间设置为0.在智能合约部署阶段，分别对不同数据集在初始化时间、交易数目和交易存储开销三个方面进行了测试，分别记录测试结果并将其在表4 中列出.通过对仿真结果进行分析可以发现，交易数量和表3 所显示的加密文档存储空间呈线性正相关，随着加密文档存储数量及交易数量的增加，其所需要的时间和所消耗的存储开销都将增大.

表4 本地测试网络存储开销Table 4 Storage overhead on local test network

在方案更新的过程中，为更加准确地描述更新开销，实验设定每有一个需要更新的(w，ind) 对都会对应完成一个新的交易，这使得交易数量较大，造成仿真的更新效率较低.图2 记录了在测试网络上更新文档所需要的时间和存储开销.通过对仿真结果进行分析可以发现，更新时间和更新开销与更新的交易数呈线性正相关，随着更新进行的交易数越多，更新时间与更新开销会同步进行增长.在搜索效率评估方面，为了使得结论更有效，以10 次搜索匹配测试的平均值作为测试结果，执行结果如图3.进一步地，通过对执行结果进行分析可以发现，在本文所提方案中，匹配文档的数量变化对搜索效率的影响基本可以忽略不计.

图2 本地测试网络更新时间Figure 2 Update time of local test network

图3 本地测试网络搜索匹配时间Figure 3 Search time of local test network

5.3.3 测试网络模拟性能评估

仿真模拟上传了1500 个文件到测试网络进行测试，这1500 个(w，id) 对被分别打包为5 个交易进行发送.图4 记录了本方案的交易区块号以及进行交易所花费的ETH，对结果进行分析可以发现，所提方案主要的开销来自于对加密文件在测试网络区块链上的存储.同时，因为实际测试网络中，区块出块难度是动态调整的，导致存储到每一个块的实际开销会不同，从而造成结果的上下波动.本方案在Goerli 测试网络上进行搜索所需要的时间如图5，其中搜索时间为从拥有者发送搜索陷门，到智能合约在区块链上进行匹配，将搜索结果打包生成交易发送到区块上，经过一个块确认后的整体时间.对运行结果的变化趋势进行分析可以发现，方案的搜索时间大致呈现出随产生交易数量的增加而上升的结果.

图4 Goerli 网络更新开销Figure 4 Update cost of Goerli network

图5 Goerli 网络搜索匹配时间Figure 5 Search time of Goerli network

比较特别的是，在交易数相同的情况下，匹配文档数量为100 和200 的时间开销基本相近，说明此时搜索时间开销主要受搜索结果打包存区块的时间影响，即主要受出块速度影响.同时，匹配文档数量为100 和200 时，搜索时间呈现出的少许下降，其主要原因是在实际测试网络中，区块交易的记录会受到实际出块速度的影响，即挖矿难度的影响，而区块链的实际挖矿难度是会动态调整的，从而使得搜索所需要的时间也随之受到影响而呈现出动态波动.同理，可以解释在交易数相同的情况下，400 个匹配文档到500个匹配文档的搜索时间变化.此外，当匹配文档数量为300 个时，其计算开销会明显高于100 个和200 个时，这是因为此时在区块链上实际进行搜索所用的时间变长，超过了一次出块所需要的时间，使得搜索结果打包存区块的时间开销对搜索结果的影响降低，从而造成搜索时间明显增长.综上所述，造成搜索时间变化的因素分别为产生交易数量和搜索匹配文档数量，其中前者对搜索时间的影响更大.

6 结论

本文提出了一种支持多用户场景的可搜索加密方案，实现了多用户搜索权限控制功能、搜索询问防伪造和二次搜索效率提升.然后，将本方案部署到本地测试网络和Georli 测试网络，对所提方案进行了模拟执行，结果表明，所提方案能有效执行.