当前，移动互联、万物互联以及数字化转型所带动的海量数据流量致使人们对存储的需求呈现爆发式增长. 伴随海量数据所增长的储存和处理需求直接拉动云环境下外包数据存储市场高增. 然而，在人们享受云存储带来的便利的同时，数据安全性的问题随之而来. 为了防止云服务提供商和黑客未经授权访问用户的外包数据，用户可以将敏感和隐私数据进行加密再外包至云服务器. 然而，传统加密方法会改变数据的原始特征，云服务器无法对密文进行搜索和处理，严重影响外包数据的可用性. 为了解决上述问题，研究者们提出了可搜索加密技术——在保障用户安全方便地使用外包数据存储服务的同时，使云服务器端能够在不解密数据的前提下对密文进行搜索，从而保证了外包数据的机密性与可用性. 近年来，可搜索加密技术得到了广泛且深入的研究，但仍面临许多挑战.

首先是动态更新方面. 现实场景中，企业及个人用户外包数据很少是一成不变的，经常需要频繁定期更新. 已有可搜索加密方案中利用前向索引构造的方案^[1]支持直接文件更新，动态性较好，易于实际开发应用，但是前向索引结构泄露了和明文相关的信息，容易被敌手进行统计攻击，而且搜索效率不尽如人意. 倒排索引结构是实现关键字到文件映射关系的最佳方式，能够实现高效搜索^[2]，然而，倒排索引动态更新过程较为复杂，添加或删除文件时必须对索引中的所有条目进行线性扫描. 现有基于倒排索引的可搜索加密方案的动态更新过程大多需要额外更新结构进行辅助，这些更新结构通常过于复杂，导致更新效率非常低，并且只能允许有限的更新操作. 除此之外，已有的动态更新方法在更新过程中往往会向服务器泄露较多信息，例如关于更新关键字的关联信息等，即敌手可将更新的文件与之前的历史搜索结果建立联系，进而使方案无法抵抗文件注入攻击.

其次，为了更好地提高用户的搜索体验，可搜索加密一个重要的研究方向是提高搜索语句表达性，例如支持多关键字布尔搜索^[3]. 严格意义上的布尔搜索是指利用布尔逻辑运算符连接各个搜索关键字，然后由计算机进行相应逻辑运算，以找出所需信息的方法. 布尔搜索在所有搜索功能中使用面最广、使用频率最高. 但是，布尔搜索不仅需要云服务器进行关键字密文搜索，还需要对搜索结果进行布尔运算，过程中更容易由于节点崩溃或外部攻击而返回不正确的布尔搜索结果. 因此为了应对上述问题，亟需引入搜索结果验证机制来保证搜索结果的正确性. 一些可搜索加密方案通过数据认证技术，如MAC认证结构^[4]、Merkle哈希树^[5]和布隆滤波器^[6]等，实现对搜索结果的验证. 然而上述验证方法仅能验证搜索语句表达性较差的搜索请求，甚至单一关键字搜索请求. 对于多关键词布尔搜索，目前的验证方法主要使用基于数据持有性证明技术中随机抽取的思想来实现^[7]，面临误差较大以及结果验证计算负载较大等缺陷，不能适应实际广泛的应用场景.

最近几年，随着加密货币和去中心化应用的流行，区块链技术受到了各行业极大的关注. 区块链数据存储成为构建分布式存储平台的关键技术. 例如Bigchain DB^[8]和Bluzelle^[9]，其通过共识协议确保数据存储的一致性和不可篡改性，为解决上述这些问题提供了可能. 近年来，很多方法将密码学加密技术与区块链结构相融合，一定程度上实现了链上数据的隐私保护^[10-11]. 一些可搜索加密方案以智能合约代替传统的可信第三方来提供搜索公平性的保证^[12-14]. 然而，上述方案中安全索引仍然部署于服务器端，而且受制于区块链固有的分叉问题导致方案的可用性受到了影响，并未发挥出区块链数据存储固有的防篡改和增量更新性等优势.

本文针对上述问题展开研究，提出基于区块链索引的可验证布尔搜索加密方案VBSE-BI.方案将可搜索加密中的安全索引结构与区块链数据存储进行深度融合，限制服务器由于单点故障原因对索引结构进行破坏，实现索引的存储机密性、动态更新性以及搜索正确性. 同时方案在支持对多关键字布尔搜索的同时，保证了布尔搜索结果的不可伪造性. 本文主要工作如下：

1）提出基于区块链存储结构的增量链式安全索引构造方法. 首先构建“关键字-文件”链式索引结构，将索引拆分为数据块的形式存储在区块链结构的交易信息中，利用指针进行链接，并引入同态加密机制代替标准加密方法来加密索引信息，在不解密索引的情况下实现高效搜索. 此方法以区块链的不可篡改性来提供搜索正确性和可靠性，并且避免了构建辅助更新索引结构导致的索引存储及更新开销大的问题.

2）提出针对布尔搜索结果的完整性验证方法. 针对服务器端布尔运算完整性验证需求，给出VBSE-BI的搜索结果不可伪造性定义，基于双线性映射累加器和扩展欧几里德算法设计面向布尔搜索的完整性证明以及验证方法，并且，基于双线性q阶强Diffie-Hellman假设，对该方法的不可伪造性进行了严格的安全性证明.

3）对VBSE-BI方案每个算法和协议进行详细构建，并从存储开销、计算开销以及通信开销3个维度对比分析方案性能；对VBSE-BI方案进行了编程实现，并通过对算法的性能测试来分析方案在实际应用中的性能表现. 性能分析结果显示，本方案降低了服务器端存储以及搜索开销的同时，降低了用户计算复杂度，满足实际云环境下资源受限本地设备的应用需求.

1.   相关工作

近几年，学者们对可搜索加密方案的各方面问题进行了深入的研究. 针对可搜索加密的动态更新问题，2012年，Kamara等人^[2]提出了基于正反双链表结构的动态可搜索加密方案，但是在更新文件的时候会造成较大信息泄露，无法抵抗文件注入攻击. 为了降低更新泄露，Hahn等人^[15]中提出一种新的动态可搜索加密方案，主要思想是根据用户的搜索历史构造前向索引和倒排索引2个索引结构，云服务器不会得到除了搜索令牌之外的任何用户信息，但是该方案仅在文件数据庞大而关键字数目不多的场景下具有高的搜索效率.2016年，Bost^[1]构造了一个满足向前安全性的动态可搜索加密方案，向前安全性保证了更新文件时敌手无法将其关键字信息与之前的搜索历史进行匹配.2018年，Zuo等人^[16]基于二进制树和同态加密算法构建了2个动态可搜索加密方案，并支持范围查询，第1个方案拥有前向安全，第2个方案拥有前向安全和部分后向安全，但对加密文档的数量有限制.

在搜索结果的可验证性方面，2013年，Chai等人^[17]首先提出并研究了支持搜索结果验证可搜索加密问题. 2015年，Wang等人^[18]提出了一种在混合云中支持容错性和可验证性的可搜索加密方案，通过基于字典的索引构建方法，生成模糊关键字字典，实现搜索结果的动态排序和可验证性. Kurosawa等人^[19]利用RSA累加器生成搜索标签，从而实现搜索结果的验证并支持对文件的动态更新. 2015年，Ameri等人^[20]利用布隆过滤器和多层级访问控制略构造了一种通用的多层级可验证关键字搜索方案. 2017年，Jiang等人^[21]基于特殊倒排索引结构QSet、二进制矢量以及MAC函数设计了支持多关键字排序的可验证可搜索加密方案. 2018年，Wang等人^[22]基于OXT的连接关键词检索方法，采用聚合器和采样检测技术提出了公开可验证的连接关键词检索方案. 已有的支持搜索结果验证的方案或多或少会牺牲搜索性能. 2020年，闫玺玺等人^[23]提出了一种可验证属性基搜索加密方案，方案结合区块链技术解决半诚实且好奇的云服务器模型下返回搜索结果不正确的问题. 2021年，Najafi等人^[24]针对实际应用场景中对多关键字可搜索加密的需求，提出多关键字动态可搜索加密及搜索结果完整性验证方法. 2024年，Xie等人^[25]提出了一种新的可验证中文多关键字模糊排序可搜索加密方案，使用认证标签和概率陷门提高安全性、准确性和效率，解决了现有模糊关键词搜索方法的存储和计算资源消耗问题.

基于上述研究现状可以看出，现有的支持验证的可搜索加密方法中，数据拥有者端通常需要存储庞大的辅助结构，导致本地存储负载较大，而且大多可验证算法包含复杂的通信与计算代价，在实际应用中具有局限性. 考虑到资源受限的移动设备数量急剧增加，用户端的结果验证代价应尽可能小，否则将没有实用价值. 因此，提高搜索语句的表达性并且降低用户验证代价是可验证可搜索加密中亟待解决的关键问题.

2.   VBSE-BI模型

VBSE-BI方案主要考虑2类实体：用户U和云服务器S.方案模型架构如图1所示. 用户U通过对本地文件集合进行信息提取来构建搜索索引，将索引利用密码学算法进行结构化加密，生成安全链式索引，并将链式索引拆分为交易值的形式存储于区块链索引中，根据对应的交易地址以及附加辅助验证元素生成以关键字为键的查找表，将查找表同样利用密码学算法进行结构化加密，生成密态查找表发送给云服务器S.区块链的增量存储特性使得索引能够满足文件的动态更新需求，即用户U可以随时添加或删除文件，并同时更新索引和查找表结构. 随后，用户发起生成布尔搜索请求，利用密码学工具将布尔表达式中的关键字信息进行加密，生成搜索令牌并发送给云服务器S.云服务器S在收到搜索令牌后，在密态查找表中定位到区块链索引中的搜索关键字对应的链式索引交易地址，进而在区块链安全索引中进行搜索并对搜索结果进行布尔运算. 随后，云服务器S将搜索结果以及对于布尔搜索结果正确性的证明返回给用户U. 用户U在收到搜索结果和相关的证明之后，在本地验证搜索结果的正确性，验证通过则可判定云服务器S正确执行了布尔搜索请求. 值得说明的是，区块链只负责存储链式索引结构，而真实的数据以加密的形式存储在云服务器S中.

图  1  VBSE-BI 模型架构

Figure  1.  VBSE-BI model architecture

下载: 全尺寸图片 幻灯片

2.1   符号描述

本节列出了论文中涉及的符号及其对应的含义，如表1所示.

表  1  符号描述

Table  1.  Symbols Description

符号	含义
${1^k}$	安全参数
$f$	文件集合
${f_{{w_i}}}$	包含关键字${w_i}$的文件集合
BC	区块链索引
T	密态查找表
$\phi ({\mathcal{W}})$	关键字${\mathcal{W}}$布尔表达式
${R_{\phi ({\mathcal{W}})}}$	搜索结果
${\mathcal{L}}$	泄露函数
$\pi$	证据
$\tau$	搜索/更新令牌
F，G，P	伪随机函数
${K_1}$，${K_2}$，${K_3}$	伪随机函数F，G，P的密钥
$K$	用户密钥
${L_w} = ({N_1}, … ,{N_{\# {{\mathbf{f}}_w}}})$	BC中关键字$w$对应的虚拟链表
$addr(N)$	节点N在BC中的地址
$acc({f_{{w_i}}})$	${f_{{w_i}}}$的双线性累加值
I/U/D	交/并/差集
flag	添加/删除标志

下载: 导出CSV 

| 显示表格

2.2   形式化定义

定义1. VBSE-BI方案主要由5个多项式时间算法和协议组成，即KeyGen，Setup，Search，Verify，Update，具体描述如下：

1）$(K,PP) \leftarrow KeyGen{\text{(}}{{\text{1}}^k}{\text{)}}$. 密钥生成算法，由用户U执行. 输入安全参数${{\text{1}}^k}$，输出密钥$K$和公共参数PP.

2）$(T,BC) \leftarrow Setup{\text{(}}K,f{\text{)}}$. 初始化算法，由用户U执行. 输入密钥$K$，文件集合$f$，输出区块链索引BC以及密态查找表T.

3）$({R_{\phi ({\mathcal{W}})}},\pi ; \bot ) \leftarrow Search(U(K,\phi ({\mathcal{W}}));S(T,BC))$. 搜索协议，由用户U和云服务器S交互执行. 用于搜索文件. 用户输入密钥$K$、布尔表达式$\phi (\mathcal{W})$，云服务器S输入密态查找表T和区块链索引BC，输出布尔搜索结果${R_{\phi ({\mathcal{W}})}}$以及正确性证明$\pi$.

4）$b \leftarrow Verify(K,{R_{\phi ({\mathcal{W}})}},\pi )$. 验证算法，由用户U执行. 输入密钥$K$、搜索结果${R_{\phi ({\mathcal{W}})}}$以及证明$\pi$，输出输入1或者0表示接受或拒绝.

5）$( \bot ;(T',BC')) \leftarrow Update{\text{(}}U(K,f);S(T,BC{\text{)}})$. 更新协议，由用户U和云服务器S交互执行. 用户输入密钥$K$、更新文件$f$，云服务器输入密态查找表T和区块链索引BC，输出更新后的区块链索引$BC'$以及密态查找表$T'$.

定义2. VBSE-BI正确性.VBSE-BI方案的正确性包括搜索正确性以及更新正确性：

1）搜索正确性. 对于所有的安全参数k、所有的由$KeyGen({1^k})$生成的$K$、所有的文件$f$以及所有由$Setup{\text{(}}K,f{\text{)}}$输出的(T, BC)和$Update{\text{(}}U(K,f);S(T,BC{\text{)}})$即任意顺序的更新操作，用户U与云服务器S交互执行的搜索协议$Search(U(K,f);S(T,BC))$总会得到正确的结果${R_{\phi ({\mathcal{W}})}}$. 即用户端的验证算法$Verify(K,{R_{\phi ({\mathcal{W}})}},\pi )$输出为1.

2）更新正确性. 用户U利用更新协议$Update(U(K, f); S(T,BC))$与云服务器S交互添加或删除包含关键字信息的文件$f$时，协议执行后服务器端的更新的密态查找表$T'$和区块链索引$BC'$会正确添加或删除文件$f$的相关信息，且二者仍然保持一致性且完整性.

2.3   安全性定义

在VBSE-BI方案的威胁模型中，假设云服务器为恶意敌手，即可能伪造搜索结果的布尔运算过程. 在这种威胁存在的情况下，VBSE-BI方案应该满足以下安全性定义：

定义3. 动态IND-CKA2安全性. 设$\mathcal{A}$为敌手，$\mathcal{S}im$为模拟器，${\mathcal{L}_1}$，${\mathcal{L}_2}$，${\mathcal{L}_3}$分别为初始化、搜索、更新文件阶段的泄露函数. 定义如下2个实验：

1）$Rea{l_{\mathcal{A}}}({1^k})$. 为敌手$\mathcal{A}$和挑战者$\mathcal{C}$之间的交互式实验，使用真实的方案算法. 在该实验中，挑战者$\mathcal{C}$运行$KeyGen{\text{(}}{{\text{1}}^k}{\text{)}}$生成密钥$K$和公共参数PP. 敌手$\mathcal{A}$输出文件集合$f$给挑战者$\mathcal{C}$，挑战者$\mathcal{C}$运行初始化算法$Setup{\text{(}}K,f{\text{)}}$，输出$(T,BC)$给敌手. 敌手$\mathcal{A}$可以向挑战者发起多项式次自适应质询${\{ \phi ({\mathcal{W}_i}),{f_i}\} _{1 \leqslant i \leqslant q}}$. 对于每次质询$\left\{ {\phi ({\mathcal{W}_i}),{f_i}} \right\}$，挑战者$\mathcal{C}$为敌手$\mathcal{A}$生成搜索令牌${\tau _{s,i}}$. 或者更新令牌${\tau _{u,i}}$. 由于$\mathcal{A}$是自适应敌手，所以其每次质询的结果都可以作为输入来产生下一次质询. 在所有$q$次质询结束后，敌手$\mathcal{A}$输出一个比特值$b$作为该实验的输出.

2）$Idea{l_{{\mathcal{A}},{\mathcal{S}}}}({1^k})$. 为敌手$\mathcal{A}$和模拟器$\mathcal{S}im$之间的交互式实验. 敌手$\mathcal{A}$输出索引结构$\delta$. 根据泄露函数${\mathcal{L}_1}$，模拟器$\mathcal{S}im$生成模拟的$(\widetilde T,\widetilde {BC})$并发送给敌手$\mathcal{A}$. 敌手$\mathcal{A}$可以向模拟器$\mathcal{S}im$发起多项式次自适应质询$\{ \phi ({\mathcal{W}_i}), {\delta _{{f_i}}}\} _{1 \leqslant i \leqslant q}$. 对于每次质询$(\phi ({\mathcal{W}_i}),{\delta _{{f_i}}})$，模拟器可以访问泄露函数${\mathcal{L}_2}$和${\mathcal{L}_3}$其中之一，并返回给敌手对应的模拟搜索令牌${\tilde \tau _{\mathcal{S}}}$. 最终，敌手$\mathcal{A}$返回一个比特值$b$作为该实验的输出.

VBSE-BI方案满足动态IND-CKA2安全性，当且仅当对于所有满足概率多项式时间计算能力的敌手$\mathcal{A}$，存在多项式时间计算能力的模拟器$\mathcal{S}im$，使得

其中$negl({1^k})$为以${1^k}$为输入的可忽略函数.

定义4. 不可伪造性. 设$\mathcal{A}$为一个有状态的敌手，$\mathcal{C}$为挑战者，${\mathcal{L}_1}$，${\mathcal{L}_2}$，${\mathcal{L}_3}$分别为初始化、搜索、更新文件阶段的泄露函数. 考虑游戏$Forg{e_{\mathcal{A}}}({1^k})$中，敌手$\mathcal{A}$输出文件集合$f$给挑战者$\mathcal{C}$，挑战者$\mathcal{C}$运行初始化算法$(T,BC) \leftarrow Setup{\text{(}}K,f{\text{)}}$，输出区块链索引BC以及密态查找表T给敌手. 敌手$\mathcal{A}$可以向挑战者发起多项式次自适应质询${[\left\{ {\phi ({\mathcal{W}_i}),{f_i}} \right\}]_q}$. 在所有$q$次质询结束后，敌手输出包含一组关键字的布尔表达式$\phi (\mathcal{W})$、一个针对该表达式的错误搜索结果${\widetilde R_{\phi ({\mathcal{W}})}}$和针对这一错误结果的证明$\pi$. 如果证明可以通过验证算法的验证，即$Verify(K,{\widetilde R_{\phi ({\mathcal{W}})}},\pi ) = 1$，那么实验输出1，否则输出0.

VBSE-BI方案满足不可伪造性，当且仅当对于所有满足多项式时间计算能力的敌手$\mathcal{A}$，使得：$Pr{\text{[}}Forg{e_{\mathcal{A}}}({1^k}) = 1] \leqslant negl({1^k})$，其中$negl({1^k})$为以${1^k}$为输入的可忽略函数.

3.   VBSE-BI方案

本节给出VBSE-BI方案的设计思路与具体构建方法. 首先通过构建基于区块链数据存储的增量安全索引结构来实现对密文的搜索以及高效更新，然后设计布尔搜索结果完整性验证方法来实现布尔搜索结果的完整性验证；最后根据设计思路完成方案中每个算法和协议的详细构建.

3.1   设计思路

3.1.1   基于区块链的安全索引构建方法

VBSE-BI的主要搜索结构包含存储于区块链结构中的增量链式安全索引(简称区块链索引BC)以及存储于云服务器的密态查找表T. 令F，G，P为3个伪随机函数，用户U随机选择3个长度k 比特的比特串${K_1}$，${K_2}$，${K_3}$作为伪随机函数F，G，P的密钥. 用户首先在文件集合$f = ({f_1},{f_2}, … ,{f_{\# f}})$中提取到关键字信息${\mathcal{W}} = ({w_1},{w_2}, … ,{w_{\# {\mathcal{W}}}})$，构建以关键字为引导的进行组织的$\# {\mathcal{W}}$条虚拟链表$({L_1},{L_2}, … ,{L_{\# {\mathcal{W}}}})$，每个链表都由$\# {f_w}$个节点$({N_1},{N_2}, … ,{N_{\# {f_w}}})$构成，每个节点都存储一个唯一的“文件/关键字”对，所有链表共同构成链式索引结构. 随后，用户将链式索引结构以数据条目的形式上传到区块链中，每个节点存储在BC中的一条交易中. 为了能够将区块链索引中一条虚拟链表中的不同节点进行连接，在每个节点${N_i}$内额外添加指针信息$addr({N_{i - 1}})$，指向链表内上一个节点${N_{i - 1}}$的交易地址，从而实现整条链表的高效定位与查找. 定义节点${N_i}$的结构为${N_i} = \langle {f_i},addr({N_{i - 1}}),flag\rangle$，其中${f_i}$为文件的唯一标识， $addr({N_{i - 1}})$表示链表内上一个节点${N_{i - 1}}$的交易地址，$flag$为增删标识位. 链表${L_w}$中的所有节点都使用${P_{{K_3}}}(w)$进行异或加密从而对索引的真实索引信息进行隐私保护，其中${K_3}$为伪随机函数$P$的密钥. 除此之外，用户构建查找表T，包含了系统中的所有关键字信息，对于每个关键字$w$，查找表T中的对应元素以${F_{{K_1}}}(w)$为键，以指向指向区块链索引中链表${L_w}$的末节点地址$addr\left( {{N_{\# {f_w}}}} \right)$为值，其中${K_1}$为伪随机函数$F$的密钥，$addr\left( {{N_{\# {f_w}}}} \right)$使用${G_{{K_2}}}(w)$进行异或加密，其中${K_2}$是伪随机函数$G$的密钥.

搜索关键字${w_i} \in {\mathcal{W}}$包含的文件时，服务器S使用${F_{{K_1}}}({w_i})$作为键来在密态查找表T中定位到到密态地址，使用${G_{{K_2}}}({w_i})$来解密得到${L_{{w_i}}}$的末节点地址明文，并链接到区块链索引BC中的相关交易，最后使用${P_{{K_3}}}({w_i})$来解密交易信息，获得文件标识和前一个节点的地址信息，进而在区块链索引BC中提取到链表${L_w}_{_i}$中所有节点$\left( {{N_1},{N_2}, … ,{N_{\# {f_{{w_i}}}}}} \right)$的信息，得到针对关键字${w_i}$的文件标识符集合${f_{{w_i}}}$.

图2为索引结构示意图. 为了更好地说明方案的索引结构间的关系和搜索过程，图2中索引结构均以明文形式阐述. 在区块链结构中，一定数量的新数据条目作为交易的形式封装到一个新的块中，块头包含当前链的最后一个块的哈希值、随机数、交易的Merkle哈希根以及时间戳等信息，块体包含了所有的交易信息，即存储索引BC. 例如，对于关键字${w_2}$，在查找表中键${w_2}$对应的值为402，即指向了区块链中地址为402的交易. 地址为402的交易信息中存储了一个指向地址为101的交易的指针，地址为101的交易中存储的指针指向了地址0，然后结束遍历. 通过对关键字${w_2}$的虚拟链表的遍历，所有包含关键字${w_2}$的文件都可以被找到. 上述过程实现搜索正确性的思想是，由于区块链结构对网络中的所有对等点都是可审计的，一旦挖掘出一个块并达成一致意见，就不再在该块中进一步执行修改操作. 因此区块链索引凭借着安全不可篡改的特性， 能防止已经确认的交易记录被更改，能够保证每个得到有效性验证的区块数据和交易记录中的节点信息的完整性，因此其保证了索引存储以及搜索的正确性.

图  2  BC 索引结构示意图

Figure  2.  Schematic diagram of BC index structure

下载: 全尺寸图片 幻灯片

3.1.2   布尔搜索完整性验证方法

为了搜索针对关键字集合${\mathcal{W}} = \{ {w_1},{w_2}, … ,{w_n}\}$的某个布尔表达式$\phi (\mathcal{W})$，服务器S需要通过查找表对每个关键字${w_i} \in \mathcal{W}$在区块链中定位链表${L_{{w_i}}}$的末节点${N_{\# {f_{{w_i}}}}}$的地址$addr\left( {{N_{\# {f_{{w_i}}}}}} \right)$，并分别在区块链索引中进行搜索，得到结果$R{\text{ = }}\left( {{f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_{_{{\text{\# }}{\mathcal{W}}}}}}}} \right)$后进行针对布尔表达式$\phi (\mathcal{W})$的运算. 根据类型不同，布尔运算正确性满足如下性质：

1）交集. 如果$I = \{ {f_1},{f_2}, … ,{f_m}\}$为${f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_n}}}$正确交集，当且仅当下列2个条件成立：①子集条件. 作为集合的交集，集合$I$一定为每一个集合${f_{{w_i}}}$的子集，即$\left( {I \subseteq {f_{{w_1}}}} \right) \cap … \cap \left( {I \subseteq {f_{{w_n}}}} \right)$；② 完备性条件. 集合$I$必须包含集合${f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_n}}}$的所有共同关键字，即$\left( {{f_{{w_1}}} - I} \right) \cap … \cap \left( {{f_{{w_n}}} - I} \right) = {f_{{w_m}}}$.

2）并集. 直观上，$U = \{ {f_1},{f_2}, … ,{f_m}\}$为${f_{{w_1}}},$${f_{{w_2}}}, … ,$${f_{{w_m}}}$正确并集，当且仅当下列2个条件成立：①成员条件. 作为集合的并集，集合$U$中的任何文件一定包含于某个集合${f_{{w_i}}}$，即$\forall {f_k} \in U,\exists i \in \left\{ {1,2, … ,n} \right\}:{f_k} \in {f_{{w_n}}}$；②超集条件. 任何集合${f_{{w_i}}}$一定是集合$U$的子集，即$\left( {U \supseteq {f_{{w_1}}}} \right) \wedge \left( {U \supseteq {f_{{w_2}}}} \right) \wedge … \wedge \left( {U \supseteq {f_{{w_n}}}} \right)$.

3）差集. 给定集合$D$和2个集合${f_{{w_i}}},{f_{{w_j}}}$，$D$为${f_{{w_i}}},{f_{{w_j}}}$正确差集当且仅当差集条件成立：集合$D$中的文件包含所有包含关键字${w_i}$但不包含关键字${w_j}$中的文件，即$D = {f_{{w_i}}} - {f_{{w_j}}} \Leftrightarrow {f_{{w_i}}} - \left( {{f_{{w_i}}} - D} \right) = {f_{{w_i}}} \cap {f_{{w_j}}}$. 如果${I_{{w_i} \wedge {w_j}}}$为集合${f_{{w_i}}}$和${f_{{w_j}}}$的交集，即${I_{{w_i} \wedge {w_j}}} = {f_{{w_i}}} \cap {f_{{w_j}}}$，则集合$D$和${I_{{w_i} \wedge {w_j}}}$的并集与集合${f_{{w_i}}}$相等：$D \cup {I_{{w_i} \wedge {w_j}}} = {f_{{w_i}}}$. 因此，证明$D = {f_{{w_i}}} - {f_{{w_j}}}$等价于证明${f_{{w_i}}} = D \cup {I_{{w_i} \wedge {w_j}}}$，即证明${f_{{w_i}}}$为$D$和${I_{{w_i} \wedge {w_j}}}$的并集.

本文设计融合双线性映射累加器和扩展欧几里德算法的集合运算正确性证明方法.

具体来讲，为了证明并集搜索结果I的子集条件，对于所有$w \in {\mathcal{W}}$，首先用户分别为${f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_n}}}$计算累加值$acc({f_{{w_i}}})$，然后便可以为每一个集合${f_{{w_i}}}$生成对应的子集包含证据$(I,{{\mathcal{W}}_{ I,{f_{{w_i}}}}})$. 用户利用$acc({f_{{w_i}}})$和$(I,{{\mathcal{W}}_{ I,{f_{{w_i}}}}})$验证集合$I$和集合${S_i}$之间的子集包含关系了. 除此之外，若集合$I$是完备的，当且仅当存在多项式${q_1}(s),{q_2}(s), … ,{q_n}(s)$，使得${q_1}(s){P_1}(s) + {q_2}(s){P_2}(s) + … + {q_n}(s){P_n}(s) = 1$，其中

因此假设$I$并不是完备的集合，那么在多项式${P_1}(s),{P_2}(s), … ,{P_n}(s)$中至少存在一个公因式. 在这种情况下，便不存在多项式${q_1}(s),{q_2}(s), … ,{q_n}(s)$使得${q_1}(s){P_1}(s) + {q_2}(s){P_2}(s) + … + {q_n}(s){P_n}(s) = 1$. 因此如果能找到符合要求的${q_1}(s),{q_2}(s), … ,{q_n}(s)$，那么就说明${P_1}(s),{P_2}(s), … ,{P_n}(s)$中一定不存在公因式.

为了证明并集搜索结果U的成员条件，需要为集合U中的每个文件${f_j}$生成针对文件集合${f_{{w_i}}}$的成员证据${\mathcal{M}_{j,i}}$. 验证时，验证成员条件通过验证下列等式是否成立：$e\left( {{{\mathcal{M}}_{j,i}},{g^{{f_j}}}{g^s}} \right) = e\left( {acc\left( {{f_{{w_i}}}} \right),g} \right)$. 需要注意的是，对于集合$U$中的每个文件${f_j}$，只有当对于每个集合${f_{{w_i}}}$上述等式都不成立时，才表示元素${f_j}$不属于任意集合${f_{{w_i}}}$，此时认为验证失败. 证明超集条件时，需要为${f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_n}}}$构造超集证据：对于$1 \leqslant i \leqslant n$，计算

令$\mathcal{S} = {\{ {\mathcal{S}_i}\} _{1 \leqslant i \leqslant n}} = {\{ {g^{{P_i}}}\} _{1 \leqslant i \leqslant n}}$为超集证据. 验证时，通过验证下列等式是否成立，验证

其中${S_i}$为超集证据$S$中元素. 如果所有的验证过程都通过，那么就可以认为$U$是正确的，即的确是由${f_{{w_1}}},{f_{{w_2}}}, … ,{f_{{w_n}}}$通过并集运算得到的结果. 由于差集证明方法可规约为并集证明，因此不再过多赘述.

3.1.3   安全索引的动态更新机制

用户U可以随时在方案中添加或删除包含${{\mathcal{W}}_f} = ({w_1},{w_2}, … ,{w_n})$关键字的文件$f$. 对于${{\mathcal{W}}_f}$中的任意关键字${w_i}$，首先用户U和服务器S交互获取密态查找表T中与${w_i}$对应的链表${L_{{w_i}}}$的末节点${N_{\# {f_{{w_i}}}}}$在区块链索引BC中的交易地址$addr{\text{(}}{N_{\# {f_{{w_i}}}}})$以及相关累加值$acc({f_{{w_i}}})$，并且利用此地址$addr({N_{\# {f_{{w_i}}}}})$更新链表${L_{{w_i}}}$——增加文件$f$对应的新的末节点$N_{\# {f_{{w_i}}}}^{'}$. 之后用户将$N_{\# {f_{{w_i}}}}^{'}$作为交易的形式更新到区块链索引BC中，得到$N_{\# {f_{{w_i}}}}^{'}$的交易地址$addr(N_{\# {f_{{w_i}}}}^{'})$. 除此之外，用户需要利用原有${f_{{w_i}}}$对应的累加值$acc({f_{{w_i}}})$和更新的文件$f$计算新的累加值$acc({f_{{w_i}}})'$. 最后用户将$addr(N_{\# {f_{{w_i}}}}^{'})$以及累加值$acc({f_{{w_i}}})'$更新到查找表中${w_i}$键对应的值中，至此完成安全索引结构的更新. 由于区块链结构为增量数据结构，且具有防篡改性，因此无法修改或删除已有交易值信息，针对上述情况，将添加和删除文件过程均利用添加节点至区块链来进行，通过在每个节点内区分标flag标志位的值来区分添加和删除操作，$flag{\text{ = 1}}$则表示$f$为增加的文件，$flag{\text{ = 0}}$则表示$f$为删除的文件. 上述动态更新过程中服务器S可以在无需对查找表进行解密的情况下，使用用户发送的更新令牌中的密文信息直接对密态查找表直接进行更新.

3.2   详细算法及协议

令$F:{\{ 0,1\} ^k} \times {\{ 0,1\} ^*} \to {\{ 0,1\} ^k}$，$G:{\{ 0,1\} ^k} \times {\{ 0,1\} ^*} \to$${\{ 0,1\} ^*}$，$P:{\{ 0,1\} ^k} \times {\{ 0,1\} ^*} \to {\{ 0,1\} ^k}$ 为3个固定长度伪随机函数，${\sum _{BC}}(Init,Put,Get)$为区块链数据存储结构，具体的算法及协议描述如下：

3.2.1   密钥生成算法

$(K,PP) \leftarrow KeyGen{\text{(}}{{\text{1}}^k}{\text{)}}$：进行用户端密钥的生成. 主要步骤如下：

1）随机选择3个长度为$k$比特的比特串${K_1},{K_2},{K_3}$.

2）选择双线性配对的参数$(p,G,{\mathcal{G}},e,g)$.

3）选择$s \in \mathbb{Z}_p^*$作为一个随机的秘密陷门.

4）计算$(g,{g^s},{g^{{s^2}}}, … {g^{{s^q}}})$作为公开参数.

5）输出密钥$K = ({K_1},{K_2},{K_3},s)$，并输出公开参数$PP = (g,{g^s},{g^{{s^2}}}, … ,{g^{{s^q}}})$.

3.2.2   初始化算法

$(T,BC) \leftarrow Setup{\text{(}}K,f{\text{)}}$：用户U初始化索引结构. 主要步骤如下：

1）初始化长度为$\# {\mathcal{W}}$的查找表T.

2）调用${\sum }_{BC}{}_{·}Init\text{(}k\text{)}$算法，输入安全参数$k$，初始化区块链索引$BC$.

3）对于每个关键字$w \in {\mathcal{W}}$：

① 构建一个由$\# {f_w}$个节点$({N_1},{N_2} … ,{N_{\# {f_w}}})$构成的链表$L$，节点的结构定义为

其中${f_i}$为文件标识，$addr({N_{i - 1}})$表示节点${N_{i - 1}}$的交易地址，$addr({N_1}) = \bot$，$flag$为增删标识位；

② 对于链表${L_w}$的所有节点$({N_1},{N_2}, … ,{N_{\# {f_w}}})$，依次调用${\sum }_{BC}{}_{·}Put\text{(}{N}_{i}\text{)}$算法，将节点${N_i}$作为交易值封装进区块链索引BC的区块上并获取交易地址$addr({N_i})$，最终返回$addr({N_{\# {f_w}}})$.

4）对于每个关键字$w \in {\mathcal{W}}$：

① 计算${f_w}$的累加值，即

② 输出区块链索引BC和密态查找表T共同作为安全索引结构，即

3.2.3   搜索协议

$({R_{\phi ({\mathcal{W}})}},\pi ; \bot ) \leftarrow Search(U(K,\phi ({\mathcal{W}}));S(T,BC))$：用户U和云服务器S交互执行针对关键字集合$\mathcal{W} = \{ {w_1}, … ,{w_n}\}$的布尔表达式$\phi (\mathcal{W})$的搜索过程，服务器针对搜索结果生成相应布尔运算证明. 主要步骤如下：

1）用户U.

① 针对每个搜索关键字$w_i \in \mathcal{W}$：生成搜索令牌${\tau _i} = ({\tau _{i,1}},{\tau _{i,2}},{\tau _{i,3}}) = ({F_{{K_1}}}({w_i}),{G_{{K_2}}}({w_i}),{P_{{K_3}}}({w_i}))$.

② 发送搜索令牌${\tau _s} = (\phi (\mathcal{W}),{\{ {\tau _i}\} _{i \in \mathcal{W}}})$给服务器S.

2）服务器S.

对于每个关键字${w_i} \in \mathcal{W}$，执行以下步骤：

① 使用${\tau _{i,1}}$作为键检索密态查找表T中的值${\theta _1} \leftarrow T[{\tau _{i,1}}]$.

② 计算链表头节点在索引BC中的交易地址${\alpha _1} \leftarrow {\theta _1} \oplus {\tau _{i,2}}$.

③ 在BC中获取地址$addr({N_{\# {f_{{w_i}}}}})$的交易值$t{x}_{1}\leftarrow$${\sum }_{BC}{}_{·}Get\left(add{r}_{{N}_{\#{f}_{w}}}\right)$.

④ 计算${a_1}||{a_2}||{a_3} \leftarrow t{x_1} \oplus {\tau _{i,3}}$.

⑤ 如果${a_3} = 1$，则更新${R_{{w_i}}} \leftarrow {R_{{w_i}}} \cup \left\{ {{a_1}} \right\}$，如果${a_3} = 0$，则更新${R_{{w_i}}} \leftarrow {R_{{w_i}}}/\left\{ {{a_1}} \right\}$.

⑥ 如果${a_2} \ne \bot$，则重复过程③④，继续查找BC中地址为${a_2}$的交易值，直到${a_2} = \bot$. 对于所有关键字 ${w_i} \in \mathcal{W}$搜索完毕后，得到搜索结果$R = ( {R_{{w_1}}},{R_{{w_2}}}, … , {R_{{w_{_{\# {\mathcal{W}}}}}}} )$.

对于布尔表达式$\phi (\mathcal{W})$，云服务器S进行如下步骤完整集合运算的证明：

1）交集证明.

步骤1. 计算交集${R_I} = {R_{{w_1}}} \cap {R_{{w_2}}} \cap … \cap {R_{{w_n}}}$，其中${R_I} = \{ {f_1},{f_2}, … ,{f_m}\}$.

步骤2. 对于每个集合${R_{{w_i}}}$，$1 \leqslant i \leqslant n$，执行如下：

①计算多项式${P_i} = \prod\limits_{f \in {R_{{w_i}}} - {R_I}} {\left( {s + f} \right)}$.

②计算集合${R_I}$对于${R_{{w_i}}}$的子集包含证据${{\mathcal{I}}_{{R_I},{R_{{w_i}}}}} = {g^{{P_i}}}$.

③计算子集证据${\mathcal{I}} = \{ {{\mathcal{I}}_i}\} = {\{ {{\mathcal{I}}_{I,{f_{{w_i}}}}}\} _{1 \leqslant i \leqslant n}}$.

④使用公开参数$(g,{g^s}, … ,{g^{{s^q}}})$来计算${g^{{P_i}}}$的值.

⑤给定$\{ {P_1},{P_2}, … ,{P_n}\}$，使用扩展欧几里德算法找到多项式$\{ {q_1},{q_2}, … ,{q_n}\}$，满足${q_1}{P_1} + {q_2}{P_2} + … + {q_n}{P_n} = 1$. 整合${\mathcal{C}} = \{ {g^{{q_1}}},{g^{{q_2}}}, … ,{g^{{q_n}}}\}$为完备性证据.

步骤3. 整合交集证据${\pi _I} = \{ {\mathcal{I}},{\mathcal{C}}\}$.

2）并集证明.

步骤1. 计算并集${R_U} = {R_{{w_1}}} \cup {R_{{w_2}}} \cup … \cup {R_{{w_n}}}$，其中${R_U} = \{ {f_1},{f_2}, … ,{f_m}\}$.

步骤2. 对于每个集合${R_{{w_i}}}$，$1 \leqslant i \leqslant n$，执行如下：

①对于${R_U}$中每个文件${f_k}$，计算多项式

②使用公开参数$(g,{g^s}, … ,{g^{{s^q}}})$计算${\mathcal{M}_{k,i}} = {g^{{F_{k,i}}}}$.

步骤3. 计算多项式${P_i} = \prod\limits_{f \in {R_U} - {R_i}} {(s + f)}$.

步骤4. 计算成员证据$\mathcal{M}{ = }{\{ {\mathcal{M}_{i,j}}\} _{1 \leqslant i \leqslant n,1 \leqslant k \leqslant m}}$，超集证据$\mathcal{S} = {\{ {\mathcal{S}_i}\} _{1 \leqslant i \leqslant n}} = {\{ {g^{{P_i}}}\} _{1 \leqslant i \leqslant n}}$.

步骤5. 整合并集证据${\pi _U} = \{ {\mathcal{M}},{\mathcal{S}}\}$.

3）差集证明.

设差集搜索令牌${\tau _s} = (\mathcal{D}({w_i},{w_j}),{\tau _i},{\tau _j})$ ，计算差集${R_D} = {R_{{w_i}}} - {R_{{w_j}}}$，其中${R_D} = \{ {f_1},{f_2}, … ,{f_m}\}$. 之后服务器按照如下方式计算证据${\pi _D} = \{ {\mathcal{M}},{\mathcal{S}}\}$以完成证明：

步骤1. 对于${R_D}$中每个文件${f_k}$，$1 \leqslant k \leqslant m$：

①计算多项式

${F_1} = \prod\limits_{f \in {R_D} - {f_k}} {(f + s)}$，${F_{2,1}} = \prod\limits_{f \in {R_{{w_i}}} - {f_{_k}}} {(f + s)}$，以及${F_{2,2}} = \prod\limits_{f \in {R_{{w_j}}} - {f_{_k}}} {(f + s)}$.

②使用公开参数$(g,{g^s}, … ,{g^{{s^q}}})$来计算

其中${\mathcal{M}}_1=g^{F_1}$，${\mathcal{M}}_2=g^{F_{2,1}}$，${\mathcal{M}}_3=g^{F_{2,2}}$.

步骤2. 计算交集${I_{{w_i} \wedge {w_j}}} = {R_{{w_i}}} \cap {R_{{w_j}}}$.

步骤3. 计算$acc({I_{{w_i} \wedge {w_j}}}) = {g^{\prod\limits_{f \in {I_{{w_i} \wedge {w_j}}}} {(f + s)} }}$.

步骤4. 对于集合${R_D}$和${I_{{w_i} \wedge {w_j}}}$，计算

步骤5. 计算超集证据：

步骤6. 整合差集证据${\pi _D} = \{ {\mathcal{M}},{\mathcal{S}}\}$.

随后，云服务器S将搜索结果集合${R_{\phi ({\mathcal{W}})}}$和针对该集合的证明$\pi$返回给用户U.

3.2.4   验证算法

$b \leftarrow Verify(K,{R_{\phi ({\mathcal{W}})}},\pi )$：用户U验证布尔搜索结果的完整性. 主要步骤如下：

1）交集验证.

步骤1. 对于${\tau _s}$中的每个${\tau _i}$，$1 \leqslant i \leqslant n$，使用${\theta _2}$通过以下等式来验证子集条件：

其中$({f_1},{f_2}, … ,{f_m})$为交集中的元素，${\mathcal{S}_i} = {g^{{P_i}}}$为子集证据$\mathcal{S}$中元素.

步骤2. 通过以下等式来验证完备性条件：

其中${\mathcal{S}_i}{\text{ = }}{g^{{P_i}}}$为子集证据$\mathcal{S}$中元素，${\mathcal{C}_i} = {g^{{q_i}}}$为完备性证据$\mathcal{C}$中对应元素.

步骤3. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.

2）并集验证.

步骤1. 对于每个文件${f_k} \in U$，$1 \leqslant k \leqslant m$，使用${\theta _2}$通过以下等式来验证验证成员条件：

其中${\mathcal{M}_{k,i}}{\text{ = }}{g^{{F_{k,i}}}}$为$\mathcal{M}$中的元素.

步骤2. 对于每个集合${R_{{w_i}}},1 \leqslant i \leqslant n$，通过以下等式来验证超集条件：

其中${\mathcal{S}_i}$为超集证据$\mathcal{S}$中元素.

只有${R_U}$中的存在文件对于任意集合${f_{{w_i}}}$的成员条件均不成立时，认为验证失败.

步骤3. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.

3）差集验证.

步骤1. 对于每个文件标识${f_k} \in {R_{{w_i}}},1 \leqslant k \leqslant m$，通过以下等式来验证成员条件：

其中$({\mathcal{M}_1},{\mathcal{M}_2},{\mathcal{M}_3}) = ({g^{{F_1}}},{g^{{F_{2,1}}}},{g^{{F_{2,2}}}})$为成员证据$\mathcal{M}$中的元素.

步骤2. 对于集合$R$和${I_{{w_i} \wedge {w_j}}}$，通过以下等式来验证超集条件：

其中$({\mathcal{S}_1},{\mathcal{S}_2},{\mathcal{S}_3},{\mathcal{S}_4}) = ({g^{{P_1}}},{g^{{P_2}}},{g^{{P_3}}},{g^{{P_4}}})$为超集证据$\mathcal{S}$中元素.

步骤3. 当步骤1中成员条件3个等式都不成立时，判定验证失败. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.

3.2.5   更新协议

$( \bot ;T';BC') \leftarrow Update{\text{(}}U(K,f);S(T);BC)$：用于用户U添加或删除包含${{\mathcal{W}}_f} = ({w_1},{w_2}, … ,{w_d})$关键字的文件$f$时索引结构的更新. 主要步骤如下：

用户U计算$({F_{{k_F}}}({w_1}),{F_{{k_F}}}({w_2}), … ,{F_{{k_F}}}({w_d}))$发送至服务器S.

服务器S对于每一个$t_u^j$，在查找表中获取$T{\text{[}}t_u^j{\text{]}}$，将$({\theta _1},{\theta _2}, … ,{\theta _d})$按序发送回用户U.

1）用户U对于每一个${\theta _i}$，执行以下步骤：

步骤1. 计算$add{r_{{N_{\# {f_{{w_i}}} - 1}}}} = {\theta _i} \oplus {G_{{k_G}}}({w_i})$.

步骤2. 如添加文件，计算

如删除文件，计算

步骤3. 调用${\sum }_{BC}{}_{·}Put\left({N}_{\#{f}_{{w}_{i}}}\right)$，将${N_{\# {f_{{w_i}}}}}$作为交易值封装进区块链索引BC的区块上并获取交易地址$addr\left( {{N_{\# {f_{{w_i}}}}}} \right)$.

步骤4. 计算更新后${f_{{w_i}}}$对应的相关累加值

步骤5. 计算$\tau _i^2 \leftarrow {G_{{K_G}}}({w_i}) \oplus addr\left( {{N_{\# {f_{{w_i}}}}}} \right)$.

步骤6. 如果为添加操作，计算$\tau _i^3 \leftarrow {\theta _2}^{s + f}$.如果为删除操作，计算$\tau _{u,i}^3 \leftarrow {\theta _2}^{1/\left( {s + f} \right)}$.

步骤7. 计算${\tau _i} = \left( {\tau _i^1,\tau _i^2,\tau _i^3} \right)$.

步骤8. 对于所有${\theta _i}$执行完步骤1～6后，将${\tau _u} = \left( {{\tau _1},{\tau _2}, … ,{\tau _d}} \right)$作为更新令牌发送给服务器.

2）服务器S对于每个$\tau _i^{}$，执行以下步骤：

步骤1. 获取$({\theta _1},{\theta _2}) \leftarrow T[{\tau _{i,1}}]$.

步骤2. 使用$\tau _{u,i}^2$对${\theta _1}$进行更新$\theta _1^\prime \leftarrow \tau _{u,i}^1$.

步骤3. 使用$\tau _{u,i}^3$对${\theta _2}$进行更新$\theta _2^\prime \leftarrow \tau _{u,i}^3$.

步骤4. 更新查找表T：$({\theta _1}^\prime ,{\theta _2}^\prime ) \leftarrow T[{\tau _{i,1}}]$.

步骤5. 输出更新后的索引结构$T\prime ;BC\prime$.

4.   安全性分析

4.1   动态IND-CKA2安全性

首先定义3个泄露函数${L_1}(T,I)$，${{\mathcal{L}}_2}(f,\phi ({\mathcal{W}}))$，${\mathcal{L}_3}(f)$来描述初始化、搜索和更新文件执行期间向服务器泄露的信息. 接下来的定理表明，给定以上泄露函数的情况下，VBSE-BI方案在随机预言模型下满足动态自适应CKA安全性.

定理1. 若$F$,$G$,$P$为伪随机函数，则VBSE-BI方案在随机预言模型下针对自适应选择关键字攻击是$({\mathcal{L}_1},{\mathcal{L}_2},{\mathcal{L}_3})$安全的，即满足动态IND-CKA2安全性.

证明. 在$Idea{l_{{\mathcal{A}},{\mathcal{S}}}}(k)$中，通过${\mathcal{L}_1}$的信息，模拟器可以确定可以获知查找表T的大小$\# T$、字典大小集合$\# {\mathcal{W}}$以及集合${[id(w)]_{w \in {\mathcal{W}}}}$. 随后，它可以使用随机值来构建搜索结构，并输出作为模拟值$(\widetilde T,\widetilde {BC})$. 由于真实索引是使用伪随机函数$F$,$G$,$P$产生的，而模拟索引是由随机比特填充的，因此，如果函数$F$,$G$,$P$的伪随机性成立，则对于所有PPT敌手$\mathcal{A}$，无法在多项式时间内区分真实索引和模拟索引.

为了响应敌手的质询，模拟器需要使用${\mathcal{L}_2}$和${\mathcal{L}_3}$来构建模拟搜索令牌和更新令牌，使其与真实令牌是无法区分的. 具体来说，泄露函数${{\mathcal{L}}_2}(\delta ,f,\phi ({\mathcal{W}}))$向服务器泄露了所有关键字$w \in \mathcal{W}$的标识$id(w)$，以及每个关键字标识$id(w)$和包含关键字$w$的文件标识之间的关联. 因为${\tilde \tau _s} = ({\tilde \tau _1},{\tilde \tau _2}, … ,{\tilde \tau _n})$，${\tilde \tau _i} = ( \gamma ( {id({w_i})} )$，$T\left[ {\gamma \left( {id({w_i})} \right)} \right] \oplus iT\left( {id({w_i})} \right),{K_{id({w_i})}} )$，而${\tilde \tau _s} = ({\tilde \tau _1},{\tilde \tau _2}, … ,{\tilde \tau _n})$，${\tau _i} = ({F_{{K_1}}}({w_i}),{G_{{K_2}}}({w_i}),$ ${P_{{K_3}}}({w_i}))$，根据函数$F$,$G$,$P$的伪随机性，对于所有概率多项式计算能力敌手$A$，不能区分搜索令牌和模拟搜索令牌${\tau _s}$和${\tilde \tau _s}$. 同理，泄露函数${L_3}(f)$泄露了更新协议中更新文件所包含的关键字的标识符集合. ${\left[ {id(w)} \right]_{w \in {{\mathcal{W}}_f}}}$. 以及关键字$w$是否是一个新的关键字${\left[ {apprs(w)} \right]_{w \in {{\mathcal{W}}_f}}}$，其中$apprs(w)$为一个1 b的标志位，值为1表示关键字$w$已经存在于索引中；值为0表示$w$是一个新关键字. 因此，基于函数$F$,$G$,$P$的伪随机性，敌手同样不能区分更新令牌${\tau _u}$和模拟更新令牌.

综上所述，对于所有PPT敌手$\mathcal{A}$来说，实验$Rea{l_{\mathcal{A}}}(k)$与$Idea{l_{{\mathcal{A}},{\mathcal{S}}}}(k)$的输出是一致的，除了以可忽略的概率$negl(k)$，即

因此，VBSE-BI方案在在随机预言模型下满足动态IND-CKA2安全性. 证毕.

4.2   不可伪造性

VBSE-BI方案的不可伪造性指对于所有概率多项式计算能力敌手$\mathcal{A}$，针对伪造的布尔搜索结果，无法生成正确有效的证据.

定理2. 如果双线性$q$-SDH假设成立，那么VBSE-BI方案满足不可伪造性.

证明. 如果存在一个概率多项式计算能力敌手$\mathcal{A}$使得实验$Forg{e_{\mathcal{A}}}({1^k})$的输出为1，那么就存在一个模拟器$Sim$，有能力攻破双线性$q$-SDH假设. 证明主要针对交集布尔搜索场景的不可伪造性，并集以及差集证明方法与交集不可伪造性证明方法过程类似，不再赘述.

假设$\mathcal{A}$在执行针对集合$\mathcal{W}$的搜索算法${\text{Search}}$后，输出一个文件标识符集合${\widetilde R_{\phi ({\mathcal{W}})}} \ne {R_{\phi ({\mathcal{W}})}}$和一个有效的证明$\pi$. 这意味着该证明$\pi$通过了验证算法${\text{Verify}}$中的所有验证，即敌手$\mathcal{A}$成功的进行了伪造. 证明$\pi = \left\{ {\mathcal{S},\mathcal{C}} \right\}$中的伪造可以分为伪造$\mathcal{S}$和伪造$\mathcal{C}$这2种情况. 通过以下分析，我们能够得出，模拟器$\mathcal{S}im$能够通过伪造$\mathcal{S}$和伪造$\mathcal{C}$来攻破双线性$q$-SDH假设.

给定模拟器$\mathcal{S}im$双线性$q$-SDH实例：$(p,G,{\mathcal{G}},e,g)$以及一个$(q + 1)$元组$(g,{g^s}, … ,{g^{{s^q}}})$，模拟器$\mathcal{S}im$和敌手$\mathcal{A}$在实验$Ver{i_{\mathcal{A}}}({1^k})$中交互.

首先，由于模拟器$\mathcal{S}im$不知道给定实例中的$s$值，他需要对实验$Ver{i_{\mathcal{A}}}({1^k})$进行修改，重新构造和$s$值相关的算法：

1）KeyGen算法中，模拟器$\mathcal{S}im$在不知情$s$的情况下直接使用$(g,{g^s},{g^{{s^2}}}, … ,{g^{{s^q}}})$作为公开参数并发送给敌手$\mathcal{A}$.

2）Setup算法中，模拟器$\mathcal{S}im$利用$(g,{g^s},{g^{{s^2}}}, … ,{g^{{s^q}}})$计算$acc({f_{{w_i}}}) = {g^{\prod\limits_{f \in {f_w}} {\left( {s + f} \right)} }}$. 为了模拟更新令牌，模拟器$\mathcal{S}im$需要构造一个额外辅助结构$\mathcal{N}$，为每个$acc({f_{{w_i}}})$存储一个多项式${n_w} = \prod\limits_{f \in {f_w}} {\left( {s + f} \right)}$.

3）Update协议中，模拟器$\mathcal{S}im$不能直接生成更新令牌${\tau _u}$，首先找到结构$\mathcal{N}$中与${\theta _{i,2}}$相等的多项式${n_i}$，然后利用$(g,{g^s},{g^{{s^2}}}, … ,{g^{{s^q}}})$计算${g^{{n_i}(s + f)}}$，生成新的${\theta _2} = {g^{{n_i}(s + f)}}$.

模拟器$\mathcal{S}im$将和$s$值相关的数值通过上述方式计算，然而由于修改的实验中算法的输出和实验$Ver{i_{\mathcal{A}}}({1^k})$算法的输出是不可区分的，所以在敌手$\mathcal{A}$的视角中，新计算的数值仍然有效. 那么如果敌手$\mathcal{A}$赢得了游戏，那么意味着敌手$\mathcal{A}$攻破了双线性$q$-SDH假设，即成功伪造了伪造子集证据$\mathcal{S}$或者成功伪造了完备性证据$\mathcal{C}$.

1）伪造子集证据$\mathcal{S}$：敌手输出错误的搜索结果$I' = \{ {f_1},{f_2}, … ,{f_m}\}$和伪造的子集证据${\mathcal{S}_i} = \stackrel{\frown}{g}^{{P_i}}$. 令${S_i} = \{ {f_1}, {f_2}, … ,{f_q}\}$为包含关键字${w_i}$的文件标识符集合，如果$I' \not\subset {S_i}$，那么一定存在某个$1 \leqslant j \leqslant m$，使得${f_j} \notin {S_i}$. 通过验证意味着

因为${f_j} \notin {S_i}$，因此$(s + {f_j})$并不能整除$(s + {f_1}) (s + {f_2}) … (s + {f_q})$. 所以存在一个次为$q - 1$的多项式$Q(s)$和一个常数$c \ne 0$，使得$(s + {f_1})(s + {f_2}) … (s + {f_q}) = Q(s)(s + {f_j}) + c$. 因此

经过变形后，最终可以得到

这说明模拟器$\mathcal{S}im$可以借在多项式时间内解决双线性$q$-SDH问题的一个实例. 这违反了双线性$q$-SDH假设.

2）伪造完备性证据$\mathcal{C}$：这种情况下，敌手输出错误的交集搜索${\widetilde R_{\phi ({\mathcal{W}})}}$ = $\{ {f_1},{f_2}, … ,{f_m}\}$和一个完备性证据$\stackrel{\frown}{\cal C}$. 因为${\widetilde R_{\phi ({\mathcal{W}})}}$是$R$的真子集，那么多项式${P_1},{P_2}, … ,{P_n}$至少存在一个公因式. 令$(s + f)$为${P_1},{P_2}, … ,{P_n}$的一个公因式，其中$f \notin I'$. 通过验证算法意味着$\prod\limits_{i = 1}^m {e( {\cal S},\stackrel{\frown}{\cal C} )} = e\left( {g,g} \right)$成立. 通过计算${g^{{{P'}_i}}} = {({g^{{P_i}}})^{1/(s + f)}}$，将$(s + f)$从每个${P_i}$中提取出来，即

因此模拟器$\mathcal{S}im$可以很容易的计算$e{\left( {g,g} \right)^{1/(s + f)}} = \prod\limits_{i = 1}^n {e\left( {{g^{{{P'}_i}}},{g^{{q_i}}}} \right)}$，从而找到双线性$q$-SDH问题的一个实例的解，这同样违反了双线性$q$-SDH假设.

综上所述，如果敌手可以伪造出一个有效的证据，那么就存在一个模拟器$\mathcal{S}im$，可以攻破哈希函数${H_3}$的抗碰撞性和双线性$q$-SDH假设的至少一个. 因此，对于所有概率多项式计算能力敌手$\mathcal{A}$来说，赢得实验$Ver{i_{\mathcal{A}}}({1^k})$概率为：

其中$negl({1^k})$是一个以安全参数${1^k}$为输入的可忽略函数. 因此VBSE-BI方案具有不可伪造性.

5.   性能分析与实验

本节主要分析提出VBSE-BI方案的性能，. 首先从理论层面对方案的各个阶段的性能进行综合对比评估，之后通过设计实验方案的原型系统，来对不同阶段的性能进行测试，得到实验结果.

5.1   代价分析

针对模型构建过程中的存储代价、计算代价以及通信代价3个维度分析方案性能. 设N表示关键字集合的大小，M为文件总个数，n为布尔搜索请求中包含的关键字个数，m为搜索结果中文件个数，d为更新文件包含的关键字个数. 方案的代价分析如表2所示.

表  2  代价分析

Table  2.  Cost Analysis

复杂度类别	VBSE-BI方案			文献[23]方案
	用户端	服务器端		用户端	服务器端
${\text{Sto}}{{\text{r}}_{{\text{Index}}}}$	${\mathcal{O}}(1)$	${\mathcal{O}}(N)$		${\mathcal{O}}(1)$	${\mathcal{O}}(NM){\text{ + }}{\mathcal{O}}(N){\text{ + }}{\mathcal{O}}(M)$
${\text{Com}}{{\text{p}}_{{\text{Search}}}}$	${\mathcal{O}}(n)$	${\mathcal{O}}(mn)$		${\mathcal{O}}(n)$	${\mathcal{O}}(n + mn)$
${\text{Com}}{{\text{p}}_{{\text{ProveI}}}}$	-	${\mathcal{O}}(N{\log ^2}N\log \log N)$		-	${\mathcal{O}}(N{\log ^2}N\log \log N)$
${\text{Com}}{{\text{p}}_{{\text{ProveU}}}}$	-	${\mathcal{O}}(N\log N)$		-	-
${\text{Com}}{{\text{p}}_{{\text{ProveD}}}}$	-	${\mathcal{O}}(N\log N)$		-	-
${\text{Com}}{{\text{m}}_{{\text{Search}}}}$	${\mathcal{O}}(n + m)$	${\mathcal{O}}(n + m)$		${\mathcal{O}}(n)$	${\mathcal{O}}(n\log n + m)$
${\text{Com}}{{\text{p}}_{{\text{Verify}}}}$	${\mathcal{O}}(n + m)$	-		${\mathcal{O}}(n\log n + m)$	-
${\text{Com}}{{\text{p}}_{{\text{Update}}}}$	${\mathcal{O}}(d)$	${\mathcal{O}}(d)$		${\mathcal{O}}(\log N + d)$	${\mathcal{O}}(d)$
${\text{Com}}{{\text{m}}_{{\text{Update}}}}$	${\mathcal{O}}(d)$	${\mathcal{O}}(d)$		${\mathcal{O}}(d)$	${\mathcal{O}}(d)$
注：${\text{Sto}}{{\text{r}}_{{\text{Index}}}}$—存储空间复杂度；${\text{Com}}{{\text{p}}_{{\text{Search}}}}$—搜索计算复杂度；${\text{Com}}{{\text{p}}_{{\text{ProveI}}}}$—交集证明计算复杂度；${\text{Com}}{{\text{p}}_{{\text{ProveU}}}}$—并集证明计算复杂度；${\text{Com}}{{\text{p}}_{{\text{ProveD}}}}$—差集证明计算复杂度；${\text{Com}}{{\text{p}}_{{\text{Verify}}}}$—验证计算复杂度；${\text{Com}}{{\text{m}}_{{\text{Search}}}}$—搜索通信复杂度；${\text{Com}}{{\text{p}}_{{\text{Update}}}}$—更新计算复杂度；${\text{Com}}{{\text{m}}_{{\text{Update}}}}$—更新通信复杂度；-：无复杂度体现.

下载: 导出CSV 

| 显示表格

存储代价主要考虑云服务器的安全索引存储代价，设T为长度为N的查找表，索引的空间复杂度为$\mathcal{O}(N)$. 在计算代价方面，构建搜索令牌的计算代价与搜索关键字个数有关，时间复杂度为$\mathcal{O}(n)$. 服务器对搜索令牌进行搜索操作时的计算复杂度为$\mathcal{O}(mn)$，进行交集运算的渐近运行时间为$\mathcal{O}(N{\log ^2}N\log \log N)$，并集和差集云服务器的渐近运行时间复杂度为$\mathcal{O}(N\log N)$，用户端完成验证操作的渐近运行时间复杂度为$\mathcal{O}(n) + \mathcal{O}(m)$. 搜索通信代价主要由搜索关键字个数以及搜索结果中文件个数决定. 当用户想要搜索n个关键字的布尔集合时，和服务器交互一次，发送搜索令牌的通信复杂度为$\mathcal{O}(n)$，云服务器返回搜索结果的通信复杂度为$\mathcal{O}(m)$，因此通信的数据规模为的通信复杂度为$\mathcal{O}(n + m)$. 与同类型的文献[23]方案相比，本方案在支持更丰富的布尔查询语句的同时，降低了服务器端索引的存储代价以及搜索、验证以及更新的计算代价.

5.2   实验分析

本文对提出的方案进行了编程实现，然后通过对算法的性能测试来分析方案在实际应用中的表现. 方案部署一个远程服务器来模拟云服务器，处理器为Intel Core i7-2600 Quad-Core Processor 3.4 GHz，内存为8 GB；同时部署多台主机模拟用户端，每台主机模拟为一个和云服务器交互的用户. 此外，方案利用Ethereum仿真平台Ropsten Testnets模拟区块链存储平台，具体来说，利用Ethereum的web3 API包^[26]来构建区块链索引，调用Metamask^[27]创建本地钱包来实例化${\sum }_{BC}{}_{·}Init\text{()}$算法，调用signTransaction函数实例化${\sum }_{BC}{}_{·}Put\text{()}$算法来存储链式索引结构中的节点信息；调用sendRawTransaction函数接受已签名的交易同时输出交易的地址；搜索时，调用getTransaction函数来实例化${\sum }_{BC}{}_{·}Get\text{()}$算法将交易的地址作为输入并输出关联的交易内容，然后读取数据字段以检索链式索引中的节点信息. 方案调用OpenSSL_SHA256-HMAC^[28]算法实现伪随机函数F，G，P. 使用Enron邮件数据集^[29]来进行性能的评估，从邮件集合中随机选择1 000个文件作为测试用的文件集.

根据系统实现的功能，测试系统执行不同操作时的云服务器端和用户端的计算开销及通信开销，其中服务器计算开销主要测试的内容包括搜索时间、生成证明时间，用户的计算开销主要测试验证时间，通信开销主要测试云服务器返回搜索结果的数据量. 实验中每个数据均为实验重复50 次并取平均值后得到的结果.

1）计算开销. 计算开销可以分为区块链索引搜索开销、服务器本地证明开销以及用户端本地验证开销，如图3所示. 当搜索关键字数量为（2，4，6，8，10）时，搜索区块链索引的时间开销与关键字个数大致呈线性关系（1.817～5.755 s）. 证明过程耗时较搜索过程大，原因为包含较多指数运算和双线性配对运算，尽管关键字数量变化，时间开销相对稳定，维持在6.1～6.8 s之间，与理论分析一致. 由于这些计算的效率与所选用的曲线参数和配对算法有很大关系，通过多线程计算和预先计算，可以显著降低证明阶段的计算时间. 因此随着参数和算法的不断优化，其效率可以进一步得到提升. 此外，服务端的算法还可以进行一些实现方面的优化，从而可以大大降低证明阶段所花费的时间. 例如对集合证据使用多线程来计算，以及使用预先计算好的${P_i}$和${g^{{P_i}}}$等. 用户计算开销主要测试在不同数目关键字情况下进行搜索时用户完成验证操作的时间，开销与关键字个数无关，维持在1.0～1.8 s之间. 验证过程中耗时最多的操作为双线性配对过程，与服务器端的搜索和证明时间相比，用户端计算开销为服务器端计算开销的9.98%～14.03%. 因此，VBSE-BI方案在用户端的计算开销相对较低，验证操作高效快速，极大地减少了用户端的计算负担. 这使得方案在实际应用中具有较好的用户体验，特别是在资源受限的移动设备上，表现尤为突出.

图  3  计算开销与关键字数量之间的关系

Figure  3.  The relationship between computational cost and the number of keywords

下载: 全尺寸图片 幻灯片

2）通信开销. 通信开销主要包含搜索结果的数据量和额外证明的数据量. 图4表明了通信开销与搜索时布尔表达式中的关键字数量之间的关系. 当搜索时使用的关键字数量为（2，4，6，8，10）递增时，通信开销中搜索结果的数据量从758 B减少至201 B这是因为符合多个关键字布尔表达式的搜索结果减少，传输的数据量也相应减少. 证明数据量从502B增加至1 896 B，因为更多的关键字需要更多的证明数据来保证搜索结果的正确性和完整性，占总数据量的36.97%～76.54%. 因此，额外证明的数据量是影响通信开销的主要因素，与理论分析一致. 因此，对于频繁查询的关键字，预先生成并存储其证明数据，减少实时计算和传输的开销，可以显著减少VBSE-BI方案中的通信开销，提高整体性能. 特别是在处理较多关键字的搜索时，通过优化证明算法和减少冗余数据，可以有效地控制通信开销的增长，从而提高方案在实际应用中的效率和可扩展性.

图  4  通信开销与关键字数量之间的关系

Figure  4.  The relationship between communication cost and the number of keywords

下载: 全尺寸图片 幻灯片

6.   总　　结

本文提出一种基于区块链索引的可验证布尔搜索加密方案. 设计基于区块链的索引构建算法和索引动态更新算法，并利用可证安全的对称加密和同态加密机制对索引进行加密，实现多关键字布尔搜索. 针对布尔搜索的完整性验证需求，给出布尔搜索结果不可伪造性定义，并提出基于双线性映射累加器和扩展欧几里德算法的布尔运算完整性验证算法. 安全性分析表明，本方案在随机预言模型下能够抵抗动态选择关键字攻击，并且在双线性阶强Diffie-Hellman 假设下满足不可伪造性. 性能分析表明，本方案有效地降低了搜索时的通信代价以及用户端计算复杂度. 本方案提升可搜索加密的可用性和确保用户享受的合法权益不受损害具有重要意义. 本文搜索协议在进行搜索结果证明时的计算代价具有提升空间，因此在未来的研究中重点关注此方面效率的提高. 除此之外，未来考虑使方案满足有隐私保护需求的更多密文搜索场景，例如基于兴趣的推荐服务以及云边协同隐私保护查询等.

作者贡献声明：李宇溪负责模型设计，方案设计，算法设计，方案分析，论文撰写及修改；陈晶晶负责安全性分析，实验环境部署，论文撰写及修改；周福才负责模型设计，技术路线可行性分析；徐剑负责理论基础，整体思路确定；纪东负责实验分析，论文修改.