Skip to main content

GG18

在 GG18 协议中，门限签名的关键是利用 Shamir's Secret Sharing (SSS) 和多方计算（MPC）技术来确保签名的安全性和正确性。你提到的一个重要问题是为什么在 {t,n}\{t, n\} 和 {t+1,n}\{t+1, n\} 的情况下，签名结果是一样的。这个问题与 Shamir's Secret Sharing 的性质和多项式插值有关。

Shamir's Secret Sharing 的性质​

Shamir's Secret Sharing 通过多项式插值的方式将秘密分成多个份额，并且只需要至少 tt 个份额就可以重构秘密。具体来说，假设我们有一个秘密 ss，我们可以构造一个 t−1t-1 次多项式 f(x)f(x)，使得 f(0)=sf(0) = s：

f(x)=s+a∗1x+a2x2+⋯+a∗t−1xt−1f(x) = s + a*1 x + a_2 x^2 + \cdots + a*{t-1} x^{t-1}

然后，我们可以生成 nn 个份额 (xi,yi)(x_i, y_i)，其中 yi=f(xi)y_i = f(x_i)。

多项式插值和线性同态性​

Shamir's Secret Sharing 的一个重要性质是多项式插值和线性同态性。具体来说，给定 tt 个份额 (x1,y1),(x2,y2),…,(xt,yt)(x_1, y_1), (x_2, y_2), \ldots, (x_t, y_t)，我们可以通过拉格朗日插值法重构多项式 f(x)f(x)，从而重构秘密 ss。

s=f(0)=∑_i=1tyiλis = f(0) = \sum\_{i=1}^t y_i \lambda_i

其中，λi\lambda_i 是拉格朗日插值系数。

GG18 协议中的部分签名计算​

在 GG18 协议中，计算部分签名的过程涉及到秘密份额的加权和求和。假设每个参与者 PiP_i 计算部分签名 sis_i，然后我们需要至少 tt 个参与者的部分签名来重构完整签名 ss。

由于 Shamir's Secret Sharing 的线性同态性，无论我们使用 tt 个还是 t+1t+1 个份额，只要这些份额是正确的，我们重构出来的结果都是一样的。这是因为多项式 f(x)f(x) 的唯一性，即给定 tt 个点可以唯一确定一个 t−1t-1 次多项式。

数学证明​

假设我们有 tt 个参与者的部分签名 s1,s2,…,sts_1, s_2, \ldots, s_t，我们可以通过加权求和得到完整签名 ss：

s=∑_i=1tsiλis = \sum\_{i=1}^t s_i \lambda_i

如果我们有 t+1t+1 个参与者的部分签名 s1,s2,…,st+1s_1, s_2, \ldots, s_{t+1}，我们同样可以通过加权求和得到完整签名 ss：

s=∑_i=1t+1siλi′s = \sum\_{i=1}^{t+1} s_i \lambda_i'

由于多项式 f(x)f(x) 的唯一性和线性同态性，这两个公式得到的 ss 是一样的。

总结​

在 GG18 协议中，部分签名的计算依赖于 Shamir's Secret Sharing 的多项式插值和线性同态性。这些性质确保了无论我们使用 tt 个还是 t+1t+1 个参与者的部分签名，只要这些份额是正确的，最终重构出来的签名结果都是一致的。这就是为什么在 {t,n}\{t, n\} 和 {t+1,n}\{t+1, n\} 的情况下，签名结果是一样的。