Shamir 门限秘密共享方案

秘密共享的概念

秘密共享是指将一个秘密分发给一组参与方，每个参与方只获取这个秘密的一部分，这样一个或者少数几个参与者就无法复原出原始数据，只有满足一定数量的参与方把各自的数据凑在一起才能还原出真实的数据。计算时，各参与方直接用自己的本地数据进行计算，并且在适当的时候交换一些数据（也不包含原始数据信息）。计算结束后，结果仍以秘密共享的方式分散在各参与方那里，并在使用方最终需要结果时将某些数据合起来。通过这种方式，秘密共享技术保证了计算过程中各个参与方看到的都是一些随机数，但是最后仍然得到了想要的结果。

Shamir门限

Shamir门限秘密共享方案有两个参数 $ n $ 和 $ t $，因此也写作 $ (t, n)-\operatorname{门限方案} $。$ n $ 表示秘密分割参与者的数量；$ t $ 即门限值，表示至少几个参与者聚到一起才可以恢复秘密信息。

Shamir门限秘密共享方案流程

将秘密信息 $ s $ 拆分为 $ n $ 份，每个参与方获得一份，每一份被称作一个 $ Share $，每个参与者秘密地保存好自己的 $ Share $
拆分时，预先设定至少 $ t(t \leq n) $ 个参与者聚在一起才可以恢复 $ s $
需要恢复 $ s $ 时，至少有 $ t $ 个参与者聚到一起，他们拿出各自的 $ Share $，通过计算恢复出 $ s $；而少于 $ t $ 个参与者聚到一起是无法恢复 $ s $ 的

Shamir门限秘密共享方案原理

Shamir门限秘密共享方案的实现原理是对于任意一个 $ t - 1 $ 次多项式函数，只需要获得其多项式曲线上的 $ t $ 个点就可以通过多项式插值（如拉格朗日插值法）确定该多项式函数。利用多维空间中的点，将共享的秘密看成 $ t $ 维空间上的一个点，每个子秘密为包含这个点的 $ t - 1 $ 维超平面的方程，构造 $ n $ 个这样的平面分发给 $ n $ 个参与方，任意 $ t $ 个 $ t - 1 $ 维超平面的焦点刚好确定共享的秘密，而 $ t - 1 $ 个子秘密，即 $ t - 1 $ 个 $ t - 1 $ 维超平面仅能确定其交线，得不到共享秘密的任何信息。

Shamir门限秘密共享方案秘密分发过程

设多项式为 $ f(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + \cdots + a_{1}x + a_{0} \operatorname{mod}(p) $， $ p $ 是一个大素数，其中 $ f(0) = a_{0} = s $ （ $ s $ 是要保护的秘密），且 $ ( s < p ) $

秘密拥有者随机生成 $ t - 2 $ 个小于 $ p $ 的随机数 $ a_{1}, a_{2}, \cdot, a_{t - 1} $，并随机选取 $ n $ 个互不相同的整数 $ x_{1}, x_{2}, \cdot, x_{n} $
将 $ n $ 个整数带入多项式函数，计算得到 $ n $ 个值 $ s_{1} = f(x_{1}), s_{2} = F{X_{2}}, \cdot, s_{n} = f(x_{n}) $
3。将计算得到的 $ n $ 个值分别发给 $ n $ 各参与方，即第 $ i $ 个参与方获得 $ (x_{i}, s_{i}) $（作为GAI参与方需要严格保守的秘密）
销毁 $ f(x) $

Shamir门限秘密共享方案恢复秘密过程

以 $ (3, 4)-\operatorname{门限} $ 为例，假设秘密 $ s = 2 $，$ p = 23 $，构造的 $ f(x) $ 如下：$ f(x) = 2x^{2} + 3x + 2 \operatorname{mod}(23) $

根据函数可知此处 $ t = 3 $，另取 $ x_{1} = 1, x_{2} = 2, x_{3} = 3, x_{4} = 4 $，代入函数得 $ f(1) = 7, f(2) = 16, f(3) = 6, f(4) = 0 $。随机选取其中3组数据 $ (1, 7) 、(3, 6)、(3, 0) $，并使用拉格朗日插值公式进行恢复：

$$ s = 7 \times \frac{(0 - 3) \times (0 - 4)}{(1 - 3) \times (1 - 4)} + 6 \times \frac{(0 - 1) \times (0 - 4)}{(3 - 1) \times (3 - 4)} + 0 \times \frac{(0 - 1) \times (0 - 3)}{(4 - 1) \times (4 - 3)} \operatorname{mod}(23) = 2 $$

经过上述计算成功恢复出秘密 $ s = 2 $

通过秘密共享实现隐私计算的原理

加法

下面以 $ (2, 2)-\operatorname{门限} $ 的加法为例，假设 Alice 和 Bob 为输入方，Alice 拥有隐私输入 $ a $，Bob 拥有隐私输入 $ b $，Uzer 为结果使用方，设计两个计算方 CP1 和 CP2，计算过程如下：

Alice 方将隐私输入 $ a $ 随机拆分成 $ a_{1} $ 和 $ a_{2} $，使得 $ a = a_{1} + a_{2} $，然后将 $ a_{1} $ 发送给 CP1，$ a_{2} $ 发送给 CP2
Bob 方将隐私输入 $ b $ 随机拆分成 $ b_{1} $ 和 $ b_{2} $，使得 $ b = b_{1} + b_{2} $，然后将 $ _{1} $ 发送给 CP1，$ b_{2} $ 发送给 CP2
CP1 计算 $ a_{1} + b_{1} = c_{1} $，并将 $ c_{1} $ 发送给 Uzer
CP2 计算 $ a_{2} + b_{2} = c_{2} $，并将 $ c_{2} $ 发送给 Uzer
Uzer 计算 $ c_{1} + c_{2} $就可以获得 $ a + b $ 两数之和（$ c_{1} + c_{2} = a_{1} + b_{1} + a_{2} + b_{2} = a + b $）并且计算过程中计算方无法获知隐私输入以及隐私输出的具体值，数据输出方也无法获得隐私输出的具体值

乘法

下面假设 Alice 和 Bob 为输入方，Alice 拥有隐私输入 $ a $，Bob 拥有隐私输入 $ b $，Uzer 为结果使用方，设计四个计算方 CP1、CP2、CP3 和 CP4，计算过程如下：

Alice 方将隐私输入 $ a $ 随机拆分成 $ a_{1} $ 和 $ a_{2} $，使得 $ a = a_{1} + a_{2} $，然后将 $ a_{1} $ 发送给 CP1 和 CP3，$ a_{2} $ 发送给 CP2 和 CP4
Bob 方将隐私输入 $ b $ 随机拆分成 $ b_{1} $ 和 $ b_{2} $，使得 $ b = b_{1} + b_{2} $，然后将 $ _{1} $ 发送给 CP1 和 CP4，$ b_{2} $ 发送给 CP2 和 CP3
CP1 计算 $ a_{1} \times b_{1} = c_{1} $，并将 $ c_{1} $ 发送给 CP1
CP2 计算 $ a_{2} \times b_{2} = c_{2} $，并将 $ c_{1} + c_{2} $ 发送给 Uzer
CP2 计算 $ a_{1} \times b_{2} = c_{3} $，并将 $ c_{3} $ 发送给 CP4
CP2 计算 $ a_{2} \times b_{1} = c_{4} $，并将 $ c_{3} + c_{4} $ 发送给 Uzer
Uzer 计算 $ c_{1} + c_{2} + c_{3} + c_{4} $就可以获得 $ a \times b $ 两数之积（$ c_{1} + c_{2} + c_{3} + c_{4} = a_{1} \times b_{1} + a_{2} \times b_{2} + a_{1} \times b_{2} + a_{2} \times b_{1} = a \times b $）并且计算过程中计算方无法获知隐私输入以及隐私输出的具体值，数据输出方也无法获得隐私输出的具体值

参考文献

深入浅出隐私计算：技术解析与应用实践/李伟荣著.北京：机械工业出版社，2022.1