Shamir 秘密共享、GMW和BGW方案

一、Shamir秘密共享

Shamir秘密共享方案是一种将秘密拆分成多份并分配给多个参与者保存，只有在满足特定条件下才能恢复原始秘密的密码学方案。它具有良好的容错性、加法同态性和无条件安全性等特点。

具体地，Shamir秘密共享方案可以概括为以下步骤：

1. 首先，选择一个大质数$p$且$s<p$，并选择一个随机数$a_0$，并生成$n-1$个不同的随机数$a_1,a_2,\cdots ,a_{t-1}$。这些数可用于定义一个$t-1$阶多项式$f(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{t-1}{x}^{t-1}$。多项式中除了$a_0$以外的系数都是随机生成的。

2. 然后，将需要共享的秘密$s$作为多项式中的常量项，即$f(0)=s$，并计算出$f(1),f(2),...,f(n-1)$。每个参与者$i$将会收到一个秘密分片$(i,f(i))$，其中$i$是参与者的编号。

3. 如果我们至少获得了$t$个秘密分片，我们就可以使用拉格朗日插值公式重建出原始秘密$s$。具体地，可以使用以下公式：
   $$s=\sum _{j=1}^{t}f(j)\prod _{i\ne j,i=1}^t\frac{k-i}{j-i}$$
   其中，$k$是需要重建秘密的参与者数。

下面以一个简单的例子来说明Shamir秘密共享方案的应用。假设Alice和Bob想要合作保管一个密码，他们希望确保只有在两者都同意时才能访问该密码。为了实现这一目标，他们使用Shamir秘密共享方案进行分割。

首先，他们共同决定一个秘密值，并将其分解成两个部分：$s_1$和$s_2$。然后，他们随机生成两个随机数$a_0$和$a_1$，并计算出一个$t-1$阶多项式$f(x)=a_0+a_{1}x$。通过将$x=1$和$x=2$代入多项式，他们分别获得了$(1,f(1))=(1,s_1+a_0+a_1)$和$(2,f(2))=(2,s_2+2a_0+4a_1)$两个秘密分片。

现在，如果他们想要检索这个密码，只有当他们两个人共同持有各自的秘密分片时，他们才能还原出原始的秘密值。因为他们两个人各有一个秘密分片，只需要使用拉格朗日插值公式即可还原出原始的秘密值：

$$s=\frac{(2-1)(s_2+2a_0+4a_1)+(1-2)(s_1+a_0+a_1)}{(1-2)}=s_1+s_2$$

从这个例子中可以看出，Shamir秘密共享方案是一种实用而高效的方法，可以帮助多个参与者在保护隐私的前提下对敏感信息进行安全的共享和计算。它的容错性能力很好，可以适应各种网络条件和故障情况，并且具有无条件安全性。

---

二、GMW方案

GMW和BGW方案是两种秘密共享的基本方案，它们都可以用来将一个秘密拆分成多份并分配给多个参与者保存。它们的主要区别在于使用的加密算法不同。

GMW方案也被称为Shamir秘密共享的扩展方案，它使用了广泛的家族算法来进行私钥共享，具有高效的性质和通用的安全证明。

GMW方案的核心思想是将秘密拆分成多份，并分配给多个参与者。每个参与者在本地留存一个秘密分片，并使用插值算法将它们组合起来，还原出秘密。此外，为了保护参与者之间的数据隐私，在这个过程中应用了RSA算法或其他家族算法来加密每个参与者的秘密分片，使得单个参与者无法获得其他任何参与者手上的信息。

例如，假设Alice、Bob和Charlie希望合作保管一个密钥，他们使用Shamir秘密共享方案进行分割。首先，他们共同决定一个秘密值，并将其分解成三个部分（$s_1,s_2,s_3$），然后将这些部分秘密地分配给他们三个人。

Alice收到$s_1$、Bob收到$s_2$和Charlie收到$s_3$。现在，当Alice、Bob和Charlie需要通过组合他们的密钥部分生成原始密钥时，他们使用秘密共享方案中的插值算法，并确保每个步骤都进行加密来防止信息泄露。

---

GMW方案的核心思想是将秘密拆分成与者持有一个秘密分片，然后使用插值算法重新聚合这些分片，得到原始秘密。

具体来说，假设我们有一个秘密$s$需要共享给$t$个参与者（其中至少需要$k$个参与者才能重建秘密）。对于每个参与者$i=1,2,...,t$，首先选择一个随机数$a_i$，并计算出一个函数$f(x)=s+\sum _{i=1}^t{a}_i{x}^i$。每个参与者$i$都会获得一对(x, y)，其中x为随机数，y为$x$代入$f(x)$得到的结果。因此，每个参与者$i$都可独立存储自己的秘密分片$(x_i,y_i)$。

接下来，为了重建原始秘密，参与者之间需要交换信息以恢复出秘密值。具体来说，每个参与者都需要将自己的秘密分片发送给其他参与者。一旦所有参与者收到了足够数量的秘密分片，他们可以通过多项式插值算法计算出完整的多项式，并从中恢复出秘密值$s$。根据Lagrange插值定理，可以使用以下公式计算多项式：

$$f(x)=\sum _{i=1}^t{y}_i\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}$$

---

三、BGW方案

BGW是Ben-Or、Goldwasser和Wigderson的缩写。这种方法也被称为$\text{t,N}$阈值方案，其中$t$表示阈值，$N$表示总共有多少个参与者。它是基于交互式协议的一个秘密分享方案，利用了Shamir秘密共享方案、ElGamal加密和Garbled电路的特性，通过多次通信构建应用程序或协议。该方案将所有秘密操作编码成部分执行和计算，以保护隐私。

假设Alice、Bob和Charlie想要合作测试一个密钥，他们希望使用BGW方案。他们开始时决定了如何将密钥拆分成子密钥。然后，他们采取随机的ElGamal加密和解密协议，按照预定的顺序对拆分的密钥段加密，并将加密日志（Garbled circuit logs）发送回服务器。

对于密码学应用，BGW对于安全计算具有显著的贡献。例如，在联合梯度下降（Federated Gradient Descent）中，参与者之间可以使用BGW方案共享计算梯度的秘密值，而无需暴露原始数据，从而实现了严格的隐私保护。

---

BGW方案基于阈值密码学，也称为(t, n)阈值方案，其中t表示需要恢复原始秘密的最小参与者数，n表示总参与者数。

假设我们要将秘密$s$拆分成$n$份，并将其中$t$份重新聚合以求得原始秘密$s$。BGW方案采用了同态加密和Garbled电路的方法来实现对保护隐私敏感计算任务的支持。

首先，每个参与者都执行一组ElGamal加密（$E{G}_k(x)$，其中$k$是公钥，$x$是原始秘密/Plaintext）。然后，他们交换密文并在解密前将密文混合起来（Shuffle）。接下来，他们执行类似于Garbled电路的解密过程（Yao’s Garbled Circuits）以及其特有的部分执行方案。具体来说，他们会构造每个门关系的相应表，其中包括外部输入变量、中间值变量和输出临时变量。接着，他们通过网络发送这些表给下一个参与者，接收方将使用ElGamal解密的方法来解密这些表，并进行下一作。最后，当所有密文混合、加密和半执行（semi-computation）完成后，可以得到原始秘密的分量。

BGW方案的阈值门可以用以下公式表示：

$$\widehat{E(0,r)}=\prod _{i=1}^t{E}_i(0,r)$$

其中，$E(0,r)$是加密一个明文0，用随机数$r$成为其伪随机性的密文；$E_i(0,r)$是第$i$个秘密共享方案中的密文。

总之，GMW和BGW都是常见的机密分享方案。其核心思想是将保密数据拆分成若干片段，然后分发给不同的参与者。这样每个参与者都持有一部分信息，只有在集齐足够数量的信息时，才能还原出完整的秘密。GMW使用插值算法，而BGW使用ElGamal随机加密和Garbled电路等技术来实现秘密共享和计算任务。

---

学习导航：http://xqnav.top