Page 436 - 《软件学报》2026年第3期

张明川 等: 支持索引动态更新的高效可搜索属性加密方案 1399

② 云服务器选用一个分布均匀的散列函数 (如 Murmur Hash、City Hash、Cuckoo Hash 等) 将大整数 KW 映
∗
∗
射到哈希表的相应槽位上, 得到关键词的索引位置 H(KW ). 由于哈希函数对同一关键词总是产生相同的输出, 因
此在索引构建过程中, 可以在此步骤过滤重复的关键词. 该步骤利用哈希函数确定性的输出特性, 实现对重复关键
词的自然去重操作.
③ 对哈希表的每个非空槽位, 当关键词对应多个数据项时, 采用概率平衡的跳表结构来组织这些关联数据.
每个跳表节点存储一对值 < Fi,FMi > (即该加密数据的编号 FileID 和标识组件 FileMatch), 其中 FileID 是云服务
器按照加密数据接收时间顺序生成的唯一标识号, FileMatch 是数据所有者的身份标识组件. 通过随机化的层次分
配机制, 使每个节点以 1/2 的概率向上提升层级, 从而自动维持跳表的平衡状态.
(2) 检索操作
① 数据访问者用相同的哈希函数对要查询的关键词进行处理, 生成检索令牌发送给云服务器.
② 云服务器对检索令牌中的每个查询关键词使用相同的散列函数计算出相应的槽位, 直接访问跳表底层链
表以获取与检索关键词对应的数据编号集合. 对于包含了多个关键词的复合查询, 还需要根据查询谓词对获取的
数据编号集合执行相应的集合运算.
从性能角度分析, 哈希表定位关键词的时间复杂度为 O(1), 获取跳表中对应的完整数据编号列表需要 O(n) 的
O(k ·n). 其中
遍历时间, 对单关键词的检索复杂度为 O(n). 对于包含了 k 个关键词的复合查询, 总体检索复杂度为
n 仅代表检索关键词关联的数据条目数而非整个数据集, 因而在大规模数据中具有效率优势.
(3) 索引更新
为实现对检索索引的安全动态更新, 引入了在检索索引中加入 BLS 短签名验证机制, 在保持云端加密数据关
键词数量不变的情况下, 实现对索引中关键词的安全替换操作. 这种更新操作不需要重建整个索引, 同时能够保证
其他加密数据的索引不受更新操作的影响. 相关验证组件由数据所有者的唯一标识号生成, 确保只有合法的数据
所有者才能完成对指定加密数据的关键词更新. 具体过程如下.
① 数据所有者将包含了原关键词、目标关键词、标识组件和签名组件的更新令牌发送给云服务器.
② 云服务器根据更新令牌的原关键词定位对应的跳表, 在跳表中查找与标识组件相等的加密数据并进行签
名验证, 完成更新请求的合法判定.
③ 若更新请求合法, 云服务器修改相应的跳表指针, 将加密数据从原关键词对应的跳表中移除. 而后检查目
标关键词在索引中是否存在, 若目标关键词尚未建立索引, 则在全局哈希表中创建该关键词的新索引项. 若已存
在, 则将加密数据按编号顺序 FileID 加入目标关键词的跳表, 完成索引更新操作.
后文图 3 展示了更新请求合法时, 将数据 F7 中的关键词从 KW1 更新为 KW2 时跳表指针的变换过程: 首先
F7 的位置并记录每一层的前驱节
在 KW1 对应的跳表中, 从最高层开始, 通过标识组件 FM7 在跳表中查找数据
点, 而后从上到下依次解除 F7 在各层与其相邻节点的链接关系 ( F4 和 F10、 F2 和 F9). 其次在 KW2 对应的跳表
F7 的适当插入位置并记录每层前驱节点, 然后根据记录的前驱信息从上到下依次建立
中, 同样从最高层开始查找
F7 与新相邻节点 ( F4 和 F10) 的链接关系. 其中, 检索过程用蓝色虚线表示, 指针的重构过程用红色实线表示. 从
O(logn),
性能角度分析: 由于跳表的层级结构特性, 因而在 KW1 和 KW2 中查找数据 F7 的操作时间复杂度均为
链接关系更新操作时间复杂度均为 O(1). 因此, 整个更新过程的总时间复杂度为 O(logn). 其中 n 仅代表与检索关
键词关联的数据数量而非整个数据集.

3 方案构造

3.1 系统模型
本文方案的系统模型如图 4 所示, 包含 4 个实体: 权威中心、数据所有者、数据访问者和云服务器.
(1) 权威中心: 可信的属性授权实体. 负责生成系统主私钥和系统主公钥, 根据数据访问者的属性生成相应的
属性密钥和解密私钥.