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

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

(
,
,
个数和哈希表长度最小值 b 的关系, k = 3 时 b = 1.27n k = 4 时 b = 1.09n k = 5 时 b = 1.05n n 为元素集合大小).
朴素哈希表 (simple hash) 使用 k 个 hash : {0,1} → {0,1} 函数 H 1 ,...,H k , 将数据元素 x 映射到朴素哈希表中,
λ
∗
与布谷鸟哈希不同的是, 朴素哈希表每个 bin 中可以存放多个映射元素, 以应对冲突问题, 如图 4 所示.

H 1 (x 1 )
H 1 (x 1 )
x 1
H 2 (x 1 )
H 1 (x 2 ) H 2 (x 1 ) H 1 (x 2 )
H 2 (x 2 )
x 2
H 2 (x 3 )
H 2 (x 3 ) H 2 (x 2 ) H 1 (x 3 )
H 1 (x 3 )
x 3
图 4 朴素哈希表示意图

在朴素哈希中, 有多个数据元素 (图 4 中的 x 1 、 、 ), 每个数据元素使用多个哈希函数 (图 4 中显示有两个
x 3
x 2
哈希函数 H 1 和 H 2 ) 映射到哈希表中的位置.
映射过程: 数据元素 x 1 使用哈希函数 H 1 映射到哈希表中 H 1 (x 1 ) 的位置, 同时也使用哈希函数 H 2 映射到 H 2 (x 1 )
.
位置. 数据元素 x 2 使用哈希函数 H 1 映射到位置 H 1 (x 2 ), 同时也使用哈希函数 H 2 映射到位置 H 2 (x 2 ) x 3 数据元素使
H 2 (x 3 ). 朴素哈希的特点是简单直接, 当遇
用哈希函数 H 1 映射到位置 H 1 (x 3 ), 同时也使用哈希函数 H 2 映射到位置
到哈希冲突的问题, 即不同的数据元素使用哈希函数映射到了相同的位置, 此时朴素哈希并不会“踢出”数据元素,
而是采用如链地址法 (如图 4 中所示) 的方式解决冲突.
2.2 弹性秘密共享
(t,n) Shamir 秘密共享 [35] s n 个
是由秘密分发者选择一个秘密 s, 将秘密 进行特定运算, 得到 n 个秘密份额, 将
t
秘密份额分别交给 n 个参与方保存, 当不少于 个参与方同时拿出自己所拥有的秘密份额 s i , i ∈ [1,n], 即可还原出
原始秘密 s. 在其基本形式中, (t,n) Shamir 秘密共享要求所有参与方是诚实的, 并在重构秘密时提供正确的秘密份
额. 在现实加密场景中, 通常需要防止参与方的恶意行为. 随着研究的深入, 一个秘密共享的强化版本被设计出来,
称为弹性秘密共享 (RSS) [27,36] , 即使部分参与方输入了错误的份额, 只要提供的正确秘密份额数量达到门限值 t 依
t 个参与方提供正确的秘密份额, 即可
然可以恢复秘密. 形式上, 所有参与方将他们的份额集中在一起, 当不少于
还原原始秘密, 如图 5 所示. 弹性秘密共享正确性验证在第 3.2 节的引理 1 进行详细说明.

秘密 S

s 1 s 2 s t s N
... ...
参与方 1 参与方 2 参与方 t 参与方 N
~ ~ ~
~ s t s N
s 1 s 2
重构算法

正确份额数量不少于 t
秘密 S

图 5 弹性秘密共享功能示意图