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

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

选择 P 1 作为秘密重构参与方, P 2 作为秘密分发参与方, P 3 ,...,P N 作为普通参与方.
预处理阶段如下.
(1) P 1 输入集合元素 X 1 由 k 个哈希函数生成布谷鸟哈希表 TC 1 , 如图 6 步骤 1-1 所示.
k
.
(2) P i , i ∈ [2,N] 输入集合元素 X i 由 个哈希函数生成朴素哈希表 TS i P 2 作为秘密分发者为 TS 2 中每个 bin
生成秘密 s, 得到 b 个秘密值 s m , m ∈ [1,b], 如图 6 步骤 1-2 和 1-3 所示. 为了保证每个秘密可以在任意门限值下正
确重构, 要求在生成秘密份额时额外生成 N −t 个冗余份额值 (在第 3.2 节的引理 1 中进行了详细说明), 因此 P 2 需
(
要将每个秘密 s m 和需要生成的份额数量 2N −t N 个参与方和 N −t 个冗余份额值) 执行 F RSS-Gen 秘密份额生成算
N
1
法, 每个秘密对应插值出一个 t −1 次多项式 f m (·), 每个秘密对应 2N −t 个秘密份额 s m → {s ,..., s , s N+1 ,..., s 2N−t }.
m
m
m
m
在线阶段如下.
j
(1) P 2 共享秘密份额 s m, m ∈ [1,b] 给参与方 P j , j ∈ [1,N], 如图 6 步骤 2-1 所示. 此外, 将冗余秘密份额 {s N+1 ,...,
m
s 2N−t } 和原始秘密的哈希 H(s m ) 发给 P 1 , 如图 6 步骤 2-2 所示.
m
,
(2) P i , i ∈ [2,N] 将朴素哈希表 TS i [m] 中的每个元素 ( TS i [m][q] q 是朴素哈希表每个 bin 中元素的位置索引)
与在线阶段步骤 i i {TS i [m][q],
s , m ∈ [1,b] 异或, 即
(1) 中获得的秘密份额
m TS i [m][q]⊕ s , 构建一个新的键值对
m
i
TS i [m][q]⊕ s }.
m
i
(3) P i , i ∈ [2,N] 输入自己的点集对执行 F Encode , 编码一个 OKVS 结构 D i = F Encode (TS i [m][q],TS i [m][q]⊕ s ), 如
m
图 6 步骤 3 所示. P i , i ∈ [2,N] 执行一个简单的洗牌算法, 打破数据结构 D i 与参与方之间的关系, 将洗牌之后的数
P 1 , 如图 6 步骤 4 所示.
据结构 D i 发给
(4) P 1 本地解码数据结构 D i , i∈[2, N] 得到对应的秘密份额, 如图 6 步骤 5 所示.
I
(5) P 1 将布谷鸟哈希表 TC 1 和数据结构 D i , i∈[2, N] 输入多参与方门限测试算法 F MTT , 输出交集 , 如图 6 步
骤 6 和 7 所示.
3.2 安全证明
引理 1. 弹性秘密共享的正确性验证.
[36]
证明: 在弹性秘密共享中, Reed-Solomon Codes 解码需要确保错误共享的数量不超过 (n−t)/2 , 因此需要添
η ⩾ n−t, 在本文协议中参与方
加 η 个冗余值, 保证任意门限值下正确份额的数量满足 t +η ⩾ t +(n+η−t)/2, 因此
数量表示符号为 N, 因此协议中的冗余值为 η ⩾ N −t. 在下文的验证中依然采用 n 进行普适性验证.
编码 Reed-Solomon Codes: 对于 n 个抽样元素 a i ∈ F q , i ∈ [1,n] q 是一个素数幂, 对包含 个信息符号的数据
k
,
包进行编码 m i ∈ F q , 首先生成一个消息多项式 f(x):

f(x) = m 1 +m 2 x+...+m k x k−1 (4)
然后计算每个数据元素 a i 对应的多项式值 :
c i

c i = f(a i ) ∈ F q , i ∈ [1,n] (5)
得到对应的码字 c 是:

c = (c 1 ,...,c n ) (6)
k F q 上形成一个线性码, 最
当信息符号的所有值在 F q 上, 可以得到 q 个 n 长的码字. 很容易看到, 这些码字 c 在
小距离为 d = n−k +1 (这对任何 ( n,k) 线性码都是最优的). 这是由里德和所罗门提出的, 即所谓的 ( n,k,d) 里德-所
罗门码.
解码 Reed-Solomon Codes: 获得一组来自码字 c 的向量 b = (b 1 ,...,b n ) ∈ F q , 其中包含了 t (t ⩽ (d −1)/2) 个错误.
解码算法的目标是在多项式 f(x) = m 1 +m 2 x+...+m k x k−1 中找到定义了原始码字 c 的消息多项式 f(x). 需要预先计
算多项式:

n ∏
g 0 = (x−a i ) ∈ F q (7)
i=1
在解码过程中可以找到一个多项式次数 deg ⩽ n−1 的特殊多项式 g 1 (x) ∈ F q , 使得: