Page 453 - 《软件学报》2025年第8期

3876 软件学报 2025 年第 36 卷第 8 期

在进行联合搜索时, BDXT 方案要求客户端与服务器之间进行两次交互, 这不仅增加了通信开销, 也带来了较
大的计算开销. 具体来讲, 在第 1 轮通信中, 客户端会将关键词 w 1 对应的文件地址信息发送给服务器, 然后服务器
反馈所有含有关键词 w 1 的文件 (包含已被删除的文件); 在第 2 轮通信中, 客户端基于服务器的反馈, 筛选出未被
删除的含关键词 w 1 的文件, 然后将其他关键词的文件标签发送给服务器供其在布隆过滤器中对这些标签进行检
测, 服务器检测后将结果返回给客户端, 客户端据此剔除非目标文件. 上述过程中第 1 轮通信的复杂度为 O(a w +d w ),
其中 a w 表示更新计数器值最小的关键词 w 1 添加的文件数量, d w 表示关键词 w 1 删除的文件数量. 第 2 轮通信的
复杂度为 O(q), q 表示联合查询中关键词的个数.
相比之下, ODXT 虽降低了通信开销, 但计算开销显著增加. 与 BDXT 相同, ODXT 在进行联合搜索时, 客户
端首先计算 w 1 对应的文件地址信息及其他关键词的令牌信息, 随后传输给服务器. 服务器基于这些信息计算各关
键词令牌的标签, 以判断 w 1 对应的文件是否匹配其他关键词, 并统计匹配计数连同加密文件信息发送给客户端.
客户端接收到回传数据后, 通过计数及文件操作记录剔除掉已删除的文件, 完成搜索. 值得注意的是, RFBC 和
ODXT 的联合搜索的计算复杂度均为 O(a w +d w +q), 但 ODXT 在计算令牌信息及标签信息时引入了模幂运算, 这带
来了较大的计算开销.
(3) 不合理更新下的搜索时间
RFBC 在进行联合搜索操作时优化了这一流程, 无需模幂运算和多轮通信, 客户端只需将关键词 w 1 的最新状
态及其他关键词令牌发送给服务器, 服务器检索出 w 1 对应的文件后, 利用布隆过滤器排除没有包含所有关键词的
文件以及被删除的文件, 仅返回过滤后的加密文件索引, 最后客户端使用私钥解密以获得搜索结果. 因此, 在合理
更新前提下, RFBC 的搜索效率高于 BDXT 和 ODXT.
图 6 展示了不同比例的不合理更新对联合搜索效率的影响. 图中, iup 代表不合理更新占关键词文件数据对总
数的比例, 该比例从 0.1 开始, 以 0.1 为间隔递增至 0.4. 由图 6 可知, 随着不合理更新比例的提高, 在相同的更新量
条件下, 3 种方案的联合搜索所需时间均有所缩短. 但值得注意的是, 由于方案 RFBC 具备鲁棒性, 其搜索效率显
著优于 BDXT 和 ODXT.
因为 BDXT 和 ODXT 均无法处理不合理的更新, 导致这些不合理更新产生的无效密文仍会被存储到服务器
中. 当进行联合查询时, 这些无效的密文仍会参与计算, 增加了计算开销, 因此二者在不同比例不合理更新下的搜
索表现均差于 RFBC.
RFBC 方案在更新时会对不合理的更新操作进行过滤, 因此在进行联合查询时, RFBC 检索出来的文件都是合
理添加或删除的 (不包括重复添加或删除的文件). 此外, RFBC 也无需对不合理的更新操作进行复杂计算. 以更新
6
6
1.0×10 个关键词文件对时为例, 假设此时不合理更新比例 iup 为 0.1, 那么 BDXT 和 ODXT 需要存储 1.0×10 条
5
数据, 并对这些数据进行运算处理, 而 RFBC 通过布隆过滤器过滤掉其中的不合理的更新, 即过滤掉 1.0×10 条数
5
据, 只需存储并处理剩余的 9.0×10 条合理的数据更新请求. 此外, 与 ODXT 和 BDXT 相比, RFBC 在关键词文件
6
数据对逐渐增大的情况下优势更加明显 (斜率更低), 具体来讲, 当关键词文件数据对为 10 且不合理更新比例 iup
分别为 0.1、0.2、0.3 和 0.4 时, RFBC 的搜索操作开销分别约为 ODXT 和 BDXT 的 24.3% 和 26.8%、21.2% 和
27.4%、21.5% 和 27.1% 以及 20.8% 和 27.9%. 平均来看, RFBC 在不合理更新下的搜索时间开销分别约为 ODXT
和 BDXT 的 21.9% 和 27.3%.
此外, 图 7 进一步展示了不合理更新对方案 RFBC 联合搜索效率的影 响, 从图 7 中可以看出, 随着不合理更
新比例的增加, RFBC 的搜索时间逐渐减少. 其原因如前所述, 随着不合理更新比例的增加, 服务器将过滤掉更多
的不合理更新操作, 仅需处理合理更新的关键词文件数据对.
(4) 不同更新计数器数值下的搜索时间
图 8 显示了更新计数器值最小的关键词对应的文件数量对联合搜索效率的影响, 其中联合查询 q = w 1 ˄w 2 ˄…˄
w 8 , 我们假设 w 1 的更新计数器值最小且逐渐增大. 当进行联合搜索时, 搜索包含的关键词越多需要检查的文件就
越多, 因此搜索时间会受关键词数量的影响. 同时, 由于添加的文件数量远大于检索关键词数量, 再结合上文我们