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

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

算法 3. 多参与方门限测试算法 ( F MTT ).

输入: 布谷鸟哈希表 TC[i], OKVS 编码之后的数据结构 D j 和原始秘密 H(s i ), 其中 i 为哈希表的长度;
输出: 达到门限值的交集集合 I.
1. for i = 1 to b do
N
2. for j = 2 to do
3. s i,j = F Decode (D j ,TC[i]) //秘密重构者通过 TC[i] 中的数据元素解码数据结构 D j , 得到 i 组秘密份额.
4. end for
5. end for
6. for i = 1 to b do
′
7. s = F RSS-Rec (s i,1 ,..., s i,N ) //输入 i 组秘密份额到弹性秘密份额重构算法, 重构出 i 个秘密.
i
8. end for
9. for i = 1 to b do
10. if H(s ) == H(s i ) // 当 s == s i 时, 此时由 TC[i] 解码出来的秘密份额与原始秘密相同.
′
′
i i
11. insert TC[i] to //此时 TC[i] 中的数据元素为交集, 将其插入交集集合 .

I
I
12. else continue
13. end for
14. return I //输出交集集合 .
I
2.4 单向散列函数
单向散列函数有一个输入和一个输出, 其中输入称为消息 (message), 输出称为散列值 (hash value). 单向散列
函数可以根据消息的内容计算出散列值, 而散列值就可以被用来隐藏原始消息的内容.
首先, 我们将明确给出单向散列函数的数学定义: 设 H(·) 为一个单向函数, 其输入为 x, 输出为 y.
X
输入类型及范围: 输入 x 属于集合 , 其中 X 可以是某一特定数据类型的集合, 例如 X 可以是长度为 n 比特的
n
二进制字符串集合, 即 X = {0,1} , 或者是某一特定有限域上的元素集合等, 具体取决于协议所处理的数据类型.
Y
输出类型及范围: 输出 y 属于集合 , 通常 Y 也是某一特定数据类型的集合. 当 H(·) 用于数据哈希, 输出集合
λ
Y 是长度为 λ 比特的二进制字符串集合, 即 Y = {0,1} .
在本文 H(·) 用于数据哈希, 其作用是将任意长度的数据 x ∈ X 映射为固定长度的哈希值 y ∈ Y.
2.5 安全模型
本文在无合谋的半诚实模型下证明了协议的安全性, 假设所有协议参与者都在概率多项式时间内运行. 各
方诚实地执行协议, 腐败的参与方不表现出主动的恶意行为, 也不偏离协议. 本文采用理想-现实模型进行安全性
证明.
定义 2. 令 f : ({0,1} ) → ({0,1} ) 是一个确定性函数, f i 为安全计算协议 π 的底层执行功能函数. P i 分别拥有
∗ N
∗ N
Y i C 为腐败的参与方集合,
输入和输出数据集 X i 和 , λ 为安全参数.
π
:
现实模型 View (λ,X 1 ,...,X N ) N 个参与方 P i 分别输入 X i 到协议 π 中, 获得输出 . 即:
Y i
C
Y i ← π(X i ) (2)
Ideal (λ,(X 1 ,...,X N ), f C (X 1 ,...,X N )): 模拟器 ( Sim) 模仿现实模型中敌手视图, 控制腐败方的输入和
f
理想模型 C
输出.
安全性: 如果在多项式时间 S 内, 对于任意 C ⊆ [N] 满足:

f c π
∗ N
Ideal {S,(X 1 ,...,X N ), f C (X 1 ,...,X N )} X∈({0,1} ) ∗ N ≡View {X 1 ,...,X N } X∈({0,1} ) (3)
C C
则认为协议在多项式时间内是安全的.