Page 447 - 《软件学报》2025年第8期
P. 447

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



                 33. ID ← Dec(sk, R)
                 34. RETURN ID
                 35. Client use I to CLEAN-UP file identifiers for w 1
                    服务器接收到这些信息后, 根据布隆过滤器的地址列表取出每个关键词对应的添加布隆过滤器和删除布隆过滤
                 器, 然后根据令牌列表中的首个元素, 也就是关键词               w 1 的令牌, 结合状态信息检索得到该关键词最新添加的文件对
                 应的加密文件标识符以及前一个状态. 通过二者可检索到                  w 1 过去添加的所有加密文件标识符, 每检索到一个加密文
                 件标识符都对其进行如下判断: 若文件标识符不在关键词                  w 1 的删除布隆过滤器中, 服务器则会将加密文件索引               c i
                 添加到索引集合      I 中, 进一步判断加密文件索引       c i 是否包含其他关键词, 若     c i 并未被其他关键词的删除操作所删除,
                 则将  c i 添加到恢复集合   R  中. 服务器再将集合    R  与集合  I 发送给客户端, 客户端收到这些信息后利用私钥解密得到
                 联合查询的结果. 这里, 我们对为何要选出更新计数器               UpdCnt 中值最小的关键词做出说明. 主要原因是该策略能够
                 减少查询过程所需的时间, 考虑如下情况, 假设关键词对应的更新计数器为                      n c , 联合查询的关键词个数为     n w , 根据上
                 述查询步骤可知, 服务器端对这         n c 个文件, 进行  n w 次布隆过滤器比较操作 (这里我们对两个布隆过滤器的操作视为
                 一次操作), 故算法时间复杂度为         O(n c ×n w ). 因此, 当  n w 固定时, 选择最小的  n c 会最小化服务器端操作. 同时, 由于在
                 查询过程的前半段, 即客户端侧, 所有操作的执行次数同样与                 n c 有关, 同理, 选择最小的   n c 会最小化客户端的操作.
                    在进行一次搜索之后, 客户端需使用集合              I 对  w 1 的文件进行 “清除” 操作, 即服务器将     w 1 过去存储的文件全
                 部删除, 并对未删除过的文件进行重新添加并初始化其对应的布隆过滤器.

                 3.4   安全性分析
                    下面我们证明本文方案         RFBC  满足前向隐私、Type-III 后向隐私以及鲁棒性.
                    在  RFBC  的更新中, 每次合理地添加关键词文件对信息都会生成一个随机状态, 因此服务器无法预测下一个
                 状态信息, 每次合理地删除关键词文件对时都是通过哈希值进行操作, 因此服务器也无法得到任何关键词文件对
                 的明文信息. 同时, 当更新不合理时, RFBC         会过滤掉这些不合理的请求. 从而, RFBC          保证了前向隐私与鲁棒性. 经
                 过一次联合搜索后, RFBC      将包含更新计数器值最小的关键词的对应文件进行 “删除”, 即使服务器保存了过去的
                 搜索令牌以及其他相关信息也查询不到过去删除过的文件. 因此, RFBC                       保证了后向隐私. 下面详细地对方案
                 RFBC  的安全性进行形式化证明.
                    定理                RFBC   RFBC    RFBC  RFBC
                        1. 定义本文方案    L    = (L Setup  = ⊥,L Updt  ,L Srch  ), 其中,
                                                         L RFBC  = ⊥,
                                                          Setup
                                                                  ′
                                                   L RFBC (w,op,ind) = L (op),
                                                    Updt
                                                   ′′
                                          L RFBC (q) = L (cxTimeDB(q),cxDelHist(q),Upd(q)),
                                           Srch
                 那么  RFBC  是一个支持前向隐私、Type-III 后向隐私以及鲁棒性的自适应安全联合对称可搜索加密方案.
                    证明: 我们将通过下面的一系列游戏来证明定理                1.
                    游戏  G 0 : 该游戏表示真实的安全游戏. 因此, 该游戏满足下列等式:

                                                       Π
                                                  Pr[Real (λ) = 1] = Pr[G 0 = 1].
                                                       A
                    游戏  G 1 : 除使用随机字符串代替伪随机函数          F 1 与  F 2 外, 该游戏与  G 0 相同. 在该游戏中, 映射  Tw  记录了关
                 键词及对应的令牌信息, 即        (w, t w ), 映射  C  记录了文件标识符及对应的文件标识符密文, 即         (ind, c). 当进行联合查
                 询时, 该游戏判断映射      Tw  是否包含该联合查询的所有关键词, 若包含这些关键词, 则游戏返回对应的令牌; 否则,
                 随机选择一个令牌来代替         t w , 并将元组  (w, t w ) 存储到映射  Tw  中. 对于联合搜索的结果, 映射  C  与映射  Tw  的操作
                 类似. 显然, 敌手   β  无法以不可忽略不计的概率         λ 区分伪随机函数与随机函数生成的随机字符串, 因此游戏                  G 1 与
                 G 0 是不可区分的, 因此该游戏满足:

                                               Pr[G 0 = 1]−Pr[G 1 = 1] ⩽ Adv prf  (λ).
                                                                    F 1 ,F 2 ,β
                    游戏  G 2 : 在该游戏的更新协议中, 我们使用随机预言机            RO 1 生成同样长度的字符串来代替哈希函数             H 1 的输
   442   443   444   445   446   447   448   449   450   451   452