GG20

GG20 协议是 Gennaro 和 Goldfeder 提出的另一种门限签名协议，与 GG18 类似，但在某些方面进行了改进。GG20 协议同样基于多方计算（MPC）和 Shamir's Secret Sharing (SSS) 技术，允许一组参与者在不泄露私钥的情况下生成数字签名。以下是 GG20 协议的详细描述和安全性证明。

GG20 协议概述

GG20 协议的目标是让 $n$ 个参与者中的至少 $t$ 个参与者共同生成一个签名，而不需要任何单一实体知道完整的私钥。协议基于椭圆曲线数字签名算法（ECDSA）。

协议步骤

1. 密钥生成：

   • 每个参与者 $P_i$ 生成一个私钥份额 $x_i$。
   • 所有参与者共同计算公钥 $Q = xG$，其中 $x = \sum_{i=1}^n x_i$ 是私钥，$G$ 是椭圆曲线生成元。

2. 签名生成：

   • 选择一个随机数 $k$，参与者共同生成 $k$ 的份额 $k_i$。
   • 计算 $R = kG$ 并广播 $R$ 的 $x$ 坐标 $r$。
   • 计算挑战值 $e = H(m || r)$，其中 $H$ 是哈希函数，$m$ 是消息。
   • 每个参与者计算部分签名 $s_i = k_i^{-1} (e x_i + r x_i)$。
   • 参与者共同计算完整签名 $s = \sum_{i=1}^t s_i$。

安全性证明

GG20 协议的安全性证明可以分为几个部分：

1. 秘密共享的安全性：

   • 在密钥生成阶段，每个参与者生成的私钥份额 $x_i$ 是保密的，只有该参与者知道。
   • 所有参与者共同计算的公钥 $Q$ 是公开的，但私钥 $x$ 仍然是保密的。

2. 签名生成的安全性：

   • 随机数 $k$ 的份额 $k_i$ 是保密的，只有生成该份额的参与者知道。
   • 计算出的 $R = kG$ 是公开的，但 $k$ 仍然是保密的。
   • 挑战值 $e$ 是公开的，但每个参与者的私钥份额 $x_i$ 是保密的。
   • 部分签名 $s_i$ 的计算涉及到私钥份额 $x_i$ 和随机数份额 $k_i$，但并不泄露这些份额的具体值。

3. 签名的正确性：

   • 最终签名 $s$ 是所有部分签名 $s_i$ 的和。
   • 由于每个部分签名 $s_i$ 都是按照 ECDSA 签名算法计算的，最终签名 $s$ 也是符合 ECDSA 签名算法的。

数学证明

为了更清晰地展示 GG20 协议的安全性，我们可以通过数学证明来详细说明。

1. 密钥生成阶段：

   • 每个参与者 $P_i$ 生成私钥份额 $x_i$。
   • 计算公钥 $Q = xG$，其中 $x = \sum_{i=1}^n x_i$。
   • 由于 $x_i$ 是保密的，$x$ 也是保密的。

2. 签名生成阶段：

   • 选择随机数 $k$，参与者共同生成 $k$ 的份额 $k_i$。
   • 计算 $R = kG$ 并广播 $R$ 的 $x$ 坐标 $r$。
   • 计算挑战值 $e = H(m || r)$。
   • 每个参与者计算部分签名 $s_i = k_i^{-1} (e x_i + r x_i)$。
   • 参与者共同计算完整签名 $s = \sum_{i=1}^t s_i$。

3. 签名验证：

   • 验证签名 $(r, s)$ 是否满足 ECDSA 签名验证公式： $$sG \stackrel{?}{=} eQ + rR$$
   • 由于 $s = \sum_{i=1}^t s_i$，每个 $s_i$ 都是按照 ECDSA 签名算法计算的，因此最终签名 $s$ 也是符合 ECDSA 签名算法的。

为什么 $\{t, n\}$ 和 $\{t+1, n\}$ 的签名结果是一样的

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

$$s = f(0) = \sum_{i=1}^t y_i \lambda_i$$

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

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

总结

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