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

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

弹性秘密共享在实现过程中分为两个阶段: 一是秘密份额分享阶段, 二是秘密份额重构阶段. 本文基于拉格朗
日插值和里德-所罗门解码分别设计了弹性秘密共享份额生成算法和弹性秘密份额重构算法, 如算法 1 和算法 2
所示. 与同态加密算法相比, 降低了计算复杂度.
算法 1. 弹性秘密共享份额生成算法 ( F RSS-Gen ).

输入: 输入一个秘密值 s 和需要生成的份额数量 n;
输出: n 个秘密份额值 s i , i ∈ [1,n].
1. for i = 1 to n do //生成随机值.
2. rand() //选择一个随机值生成函数.
3. r i = rand()
4. end for
t−1
5. 随机抽样 t −1 个随机值 {r 1 ,...,r t−1 }, 生成一个 t −1 次多项式 f(x) = s+r 1 x+...+r t−1 x , 使得 f(0) = s.
6. 随机选择 n 个随机值 {x 1 ,..., x n }.
7. for i = 1 to n do //计算秘密份额.
8. c i = f(x i )
9. end for
10. 输出 s i = c i ||x i , i ∈ [1,n].

算法 2. 弹性秘密份额重构算法 ( F RSS-Rec ).

输入: 一个秘密份额集合 s i , i ∈ [1,n];
′
输出: 重构结果 s .
1. 将 n 个秘密份额 s i , i ∈ [1,n] 输入.
Decode(·) (见引理 ′
2. 使用里德-所罗门解码算法 1), 解码得到一个多项式 f (·).
3. f (·) = Decode(s i )
′
′
′
4. 计算秘密 s = f (0).
′
5. 输出 s .
2.3 不经意键值对存储
不经意键值对存储 (oblivious key-value store, OKVS) 是一种数据结构 [1] , 用来隐藏数据中键值对的映射关系
以及原始数据, 它由编码算法生成, 并可以通过解码算法进行查询.
K×V 是有限键值字段, 并返回一个抽象数据结构
编码算法 F Encode : 输入一组 {(k 1 ,v 1 ),...,(k q ,v q )} ∈ K×V , 其中
D = F Encode (K,V); 解码算法 F Decode : 输入一个数据结构 D, 一个查询值 k, 返回一个值 v = F Decode (D,k). 当输入的查询
值 k = k q 时, 则返回的值 v = v q .
KVS 的正确性需要保证对于所有的 M ∈ K×V, 其中密钥是不同的.
(1) Pr[F Encode (M) = ⊥] 可以忽略不计.
(2) 当 F Encode (M) = D , ⊥, 即编码成功. 使得存在 (k,v) ∈ M, 使得 F Decode (D,k) = v, 即解码结果唯一.
定义 1. 对于一个概率多项式时间算法 S , 存在一个可忽略函数 µ(λ). 如果对于所有大小为 m 的 K 1 K 2 作为数
,
D 的输入, 输出的结果是不可区分的, 那么 KVS 是一个不经意键值对存储.
据结构

|Pr[S (D,K 1 )]−Pr[S (D,K 2 )]| < µ(λ) (1)
由于 OKVS 编码结构在通信过程中开销较小, 本文将 OKVS 与弹性秘密共享结合, 设计了一种高效的多参与
方门限测试算法, 如算法 3 所示. 该算法具有较小的通信和计算开销.