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

张恩 等: 兼顾通信轮数与计算开销的门限多方隐私集合交集协议 1831

1
N
f m (·), 每个秘密对应 2N −t 个秘密份额 s m → {s ,..., s , s N+1 ,..., s 2N−t }, 如图 7 步骤 1-1 所示.
m m m m
(2) P j , j ∈ [2,N] 输入集合元素 X j 由 k 个哈希函数生成朴素哈希表 TS j 和布谷鸟哈希表 TC j , 如图 7 步骤 1-2 所示.
在线阶段如下.
j
(1) P 1 将秘密份额 {s m, s N+1 ,..., s 2N−t } 和 H(s m ) 发给重构方 P j , j ∈ [2,N], 如图 7 步骤 2 所示.
m
m
i
i TS i [m][q]⊕ s , 其中
(2) 所有参与方 P i , i ∈ [1,N] 将朴素哈希表 TS i [m] 中的每个元素与 s , m ∈ [1,b] 异或, 即 m
m
i
TS i [m][q] ← h k (X i ) 并构建一个新的点集对 {TS i [m][q],TS i [m][q]⊕ s }.
m
i
(3) P i , i ∈ [1,N] 输入自己的点集对 {TS i [m][q],TS i [m][q]⊕ s } 执行 F Encode 得到一个 OKVS 结构 D i = F Encode
m
(TS i [m][q],TS i [m][q]⊕ s ), 如图 7 步骤 3 所示. P i , i ∈ [1,N] 执行一个简单的洗牌算法, 将洗牌之后的数据结构 D i
i
m
P j , j ∈ [2,N], 如图 7 步骤 4 所示.
发给重构参与方
(4) P j , j ∈ [2,N] 本地解码数据结构 D i , i ∈ [1,N] 得到对应的秘密份额, 如图 7 步骤 5 所示.
(5) P j , j ∈ [2,N] 将布谷鸟哈希表 TC j 和秘密份额输入多参与方门限测试算法 F MTT 得到各自的交集 , 如图 7
I j
步骤 6 和 7 所示.
4.2 安全证明
定理 2. Π N,n,t 在半诚实场景下是安全的.
ETMP-PSI
证明: 首先验证该协议在执行过程中的正确性, 然后证明该协议在半诚实模型下的安全性.
k
● 正确性. 预处理阶段, 每个秘密重构者 P i , i ∈ [2,N] 通过 个哈希函数映射出布谷鸟哈希表 TC i 和朴素哈希
.
表 TS i P i 可以通过 TC i [m] 表中的值, 在对应份额中找到 N −t 个冗余值生成的对应秘密共享份额. P i 只需要在与
其他参与方交互过程中得到 t −1 个正确的份额即可重构秘密多项式 f(·). 秘密重构者解密操作如下.
在线阶段, 当 P i 获得其余 N −1 个参与方编码的 OKVS 数据结构 D i , 将布谷鸟哈希表中的数据元素作为查询
元素输入, 每个数据元素对应得到 N −1 个份额值. 正确性证明方式与定理 1 中的正确性证明方式相同.
Π N,n,t 在半诚实模型下
● 安全性. 当秘密分发者 P 1 不与其他秘密重构者 P i , i ∈ [2,N] 合谋的情况下, 此协议 ETMP-PSI
P i , i ∈ [2,N] 的视图 (依然采用第 3.1 节中的符号).
是安全的. 模拟器分别模拟腐败的秘密分发者 P 1 , 腐败的秘密重构者
第 1 种情况, 模拟器 ( Sim 1 ) 模拟腐败的秘密分发者 P 1 的视图. Sim 1 收到来自 P 1 的输入 X 1 和安全参数 λ.
(1) 在预处理阶段, Sim 1 根据 P 1 的输入 X 1 构造朴素哈希表 TS 1 .
(2) 在线阶段, Sim 1 抽样一个洗牌规则 seed 执行洗牌算法, 获得输出 D .
′
1
′
(3) Sim 1 输出 P 1 的视图为 (X 1 ,D ).
1
′ seed 的选择是参与
P 1 与其他诚实参与方进行洗牌算法, 只需证明输出值 D 的隐私性即可, 秘密洗牌算法中
1
方私有的, P 1 不知道其他参与方的洗牌规则使得 P 1 无法区分模拟器在理想模型中随机生成的 D 和真实协议中执
′
1
行打乱洗牌算法得到的 D 1 . 因此秘密分发者 P 1 的视图在理想世界与现实世界上是计算不可区分的. 即:

c
λ π
{Sim (1 ,X 1 )}≡{View ((X 1 ,...,X N ),λ)} (20)
1
1
第 2 种情况, 模拟器 ( Sim i ) 模拟腐败的秘密重构者 P i , i ∈ [2,N] 的视图. Sim i 收到来自 P i , i ∈ [2,N] 的输入 X i
和安全参数 λ 和交集 .
I i
(1) 在预处理阶段, Sim i 根据 P i , i ∈ [2,N] 的输入 X i 构造布谷鸟哈希表 TC i 和朴素哈希表 TS i .
′
(2) 在线阶段, Sim i 均匀随机采样 b 个秘密 s , m ∈ [1,b] 以及 2N −t 个随机点值执行弹性秘密共享生成算法,
m
N ′
1 ′
{s ,..., s , s N+1 ′ ,..., s 2N−t ′ H(s ).
′
计算秘密份额 m m m m } 和 m
,
(3) Sim i 根据交集 I i 均匀随机抽样 n−|I i | 个随机值 X r = {x 1 , x 2 ,..., x n−|I i | } Sim i 可以模拟出其他参与方发送的消
1 ′
N ′
′
息 D ← F Encode ({I i ,X r },{s ,..., s , s N+1 ′ ,..., s 2N−t ′ }), j ∈ [1,N], j , i.
j m m m m
1 ′
N ′
N ′
1 ′
(4) Sim i 输出 P i 的视图为 (X i ,{s ,..., s , s N+1 ′ ,..., s 2N−t ′ },H(s ),D ), 其中 {s ,..., s , s m N+1 ′ ,..., s 2N−t ′ } 和 H(s ) 模拟
′
′
′
m
m
m
m
m
m
m
m
m
j
′
的是秘密分发者 P 1 发送给重构者的消息. D 模拟的是其他参与方 P j , i ∈ [1,n], j , i 发送给 P i 的消息.
j
N ′
1 ′
1
N
{s ,..., s , s N+1 ′ ,..., s 2N−t ′ {s ,..., s , s N+1 ,..., s 2N−t } 是计
模拟器模拟出的 m m m m } 与真实协议执行过程中 P 1 随机抽样的 m m m m
算不可区分的. H(·) 的单向不可逆性, 保证了重构方无法区分模拟器生成的秘密和真实协议执行过程中产生的