Page 391 - 《软件学报》2026年第4期

1832 软件学报 2026 年第 37 卷第 4 期

.
′
H(s m ) D , j ∈ [1,N], j , i 是其他参与方 P j 发给 P i 的 OKVS 数据结构, 由于 P i 没有其他参与方的输入, 基于 OKVS
j
′
编码的安全性保证了 P i 在理想世界获得的 D , j ∈ [1,N], j , i 与真实世界获得的 D j , j ∈ [1,N], j , i 是不可区分的,
j
j
,
′
即 {D } = {F(X j ,TS j , s m)} F 为真实协议执行中根据输入执行的算法. 因此秘密重构者理想世界的视图与现实世界
j
视图是计算不可区分的. 即:

λ c π
{Sim i (1 ,X i ,I i )}≡{View ({X 1 ,...,X N },λ)} (21)
i
5 实验结果与分析
本文设计的两种协议均使用 C++实现, 调用 GMP、NTL、LIBOTE 和 CRYPTO++等密码学库并在 Linux
Ubuntu 20.04 系统上进行演示实验, 其中 CPU 为 AMD RYZEN7 6800H @ 3.20 GHz, 运行内存为 32 GB. 设置协议
σ = 40. 本文在实验部分选择构造哈希表的哈希函数数量与生成的哈希表长
计算安全参数 λ = 128, 统计安全参数
度为 k = 3, b = 1.27n. 为保证比对实验的准确性, 本文与其他文献的对比实验均在同一网络带宽环境下运行. 数据
集大小、参与方数量等设置在第 5.3 节实验数据部分进行具体说明.
5.1 计算复杂度
第 1 种 TMP-PSI 协议中存在 3 类参与方 (秘密分发者, 秘密重构者和其他参与方). 预处理阶段, 秘密分发者
生成朴素哈希表和秘密份额的计算复杂度为 O(kn+bN), 在线阶段, 秘密分发者执行 OKVS 编码协议的计算复杂
O(2kn+bN). 预处理阶段, 秘密重构者生成布谷鸟哈希表
度为 O(kn), 因此协议中秘密分发者的整体计算复杂度为
其计算复杂度为 O(n). 在线阶段, 秘密重构者执行 OKVS 解码算法的计算复杂度为 O(nN), 执行 RSS 的重构算法
复杂度为 O(bN logN), 因此协议中秘密重构者的整体计算复杂度为 O(bN logN +nN). 其他参与方生成朴素哈希表
并执行 OKVS 编码协议, 其计算复杂度为 O(2kN).
第 2 种 ETMP-PSI 协议, 协议中只有两类参与方 (秘密分发者和秘密重构者). 秘密分发者与秘密重构者的计
算复杂度与 TMP-PSI 协议相同.
5.2 通信复杂度
在 TMP-PSI 协议在线阶段, 秘密分发者为其余 N −1 个参与方发送秘密份额给其他参与方, 其通信复杂度与

参与方数量 N 和朴素哈希表的长度 b 有关, 通信复杂度为 O(b(N −1)λ). 重构时, 秘密分发者发送 OKVS 数据结构
O(bNλ). 在线阶段, 秘密重构者接收到秘
给重构方, 通信复杂度为 O(bλ), 因此协议中秘密分发者的通信复杂度为
密分发者发来的份额值, 其通信复杂度与哈希表的长度和冗余值的大小有关, 通信复杂度为 O(b(N −t +1)λ). 重构
时, 秘密重构者得到其余 N −1 个参与方发送的信息, 其通信复杂度为 O((N −1)bλ), 因此协议中秘密重构者的通信
O(bλ). 重构时, 其
复杂度为 O(b(2N −t)λ). 在线阶段, 其他参与方接收到秘密分发者发来的份额值, 通信复杂度为
他参与方发送 OKVS 数据结构, 通信复杂度为 O(bλ), 因此协议中秘密分发者的通信复杂度为 O(2bλ).
在 ETMP-PSI 协议的在线阶段, 秘密分发者为其余 N −1 个参与方分发秘密份额, 秘密份额的数量与参与方数
量 N 以及朴素哈希表的长度 b 有关, 此外每个 bin 分发的份额数量为 N −t +1, 因此其通信复杂度为 O(b(N −1)(N−
t +1)λ). 重构时, 秘密分发者发送 OKVS 编码之后的数据结构, 通信复杂度为 O(bNλ), 秘密分发者的总通信复杂度
2 O(b(N −t +1)λ). 重构时, 秘
为 O(bN λ). 在线阶段, 秘密重构者接收到秘密分发者发送的秘密份额, 通信复杂度为
密重构者得到其余 N −1 个参与方的 OKVS 数据结构, 通信复杂度为 O(b(N −1)λ), 因此协议中秘密重构者的通信
O(b(2N −t)λ).
复杂度为
5.3 实验数据
10
6
12
8
14
本节首先在参与方集合 n = 2 , 2 , 2 , 2 , 2 , 2 16 的设置下, 测试了两个协议在预处理阶段生成布谷鸟哈希表
和朴素哈希表的运行时间, 如表 2 所示.
8
6
n = 2 , 2 , 2 , 2 , 2 , 2 16 的设置下, 不经意键值对存储 (OKVS) 的运行时间和通信开销,
10
14
12
然后测试了数据集
如表 3 所示.