【密码学】【多方安全计算】Secret Sharing秘密共享浅析

Secret Sharing秘密共享浅析

秘密共享（Secret Sharing）是实现多方安全计算的一种常用方式，MPC当然也可以用混淆电路（Garbled Circuit）实现，本文旨在浅析秘密共享的基本原理，有对混淆电路感兴趣的同学可阅读下一篇博客。

什么是秘密共享

Secret Sharing被称为秘密共享或私密共享，有一个秘密数值D，数值D被分解为n个片段并设置一个阈值k，当拥有k个以上片段时才可以恢复数值D，这种秘密分享叫做阈值秘密分享。

普通的秘密分享指将秘密数值D，分解成n个片段，当n个片段都被集合起来时才可以恢复秘密值D。

普通的秘密共享的问题在于，秘密的安全性得到了保证，但是管理的风险增加了，如果有一个片段被丢失将导致整个秘密无法被恢复。所以在业界常用的是阈值秘密共享。本文也就此进行讨论。

加解密过程

在阈值秘密分享中，每个i人手中的信息被记为D_i，从D计算出D_1,…,D_n的过程被称为加密。从k个D_i中计算D的过程称之为解密。
1.加密过程
随机生成k-1个数，a_1,…,a_{k-1}，加上a_0==D凑够k个数。多项式的定义：D_i = a_0 + … + a_{k-1}*i^(k-1)。
2.解密过程
凑齐k个人，每人手中有i和D_i。D_i值为上述多项式计算出来的结果，k个多项式就构成了一个方程组，其中a_0,…,a_{k-1}为未知数。通过对方程组的求解即可获得未知数的值。其中a_0为D。

这里方程组未知数的个数为k，所以需要k个以上的方程才能明确未知数的值。如果凑的人数少于k，是无法求解出未知数的。

验证加解密

我们可以设置一个秘密值D来对上述的过程进行验证。我们假设秘密值D=7，只有凑够了k=3人时才可以解密出D的值。
我们构造k个系数，其中a_0=D=7，剩下两个参数我们随机指定，a_1=0,a_2=1。

假设我们有n个人有可能需要了解秘密D，我们给他们每个人的信息如下：
D_1 = q(1)= D + a_1 + a_2 = 8
D_2 = q(2) = D + 2a_1 + 4a_2 = 11
D_3 = q(3) = D + 3a_1 + 9a_2 = 16
…
D_n = q(n) = D + n*a_1 + n^2 * a_2

假设现在第 1, 3, 10 三个人凑到一起了，他们可以凑出来以下方程组:
D_1 = 8 = D + a_1 + a_2
D_3 = 16 = D + 3a_1 + 9a_2
D_10 = 107 = D + 10a_1 + 100a_2

求解这个方程组，我们得到 a_0=D=7，a_1=0, a_2=1 。其中 a_0=7 就是要揭示的秘密。

参考文献

如何共享一个秘密
密钥分享Secret Sharing介绍