Shoup's RSA Threshold Signature

系统中有 \(l\) 个参与者，编号分别为 \(1,2,\cdots, l\) ，而门限值记为 \(k\) ，也就是这个门限签名可表示为 \((k, l)\) 。为了和 Shoup 原始论文中的符号一致，这里没有采用本文开头使用的 \((t, n)\) 记号。

选择两个素数 \(p\) 和 \(q\) ，设 \(p=2p' + 1, q=2q' + 1\) ，其中 \(p', q'\) 也都是素数。RSA 模 \(n=pq\) ，令 \(m = p'q'\) ，并选择公共一个素数指数 \(e, \; e > l\) 。 RSA 公钥就是 \((e,n)\) 。

选择一个 \(d\) ，它要满足 \(de = 1 \pmod m\) ，这个 \(d\) 就是要分享给 \(l\) 个参与者的秘密值。

下面采用 Shamir's Secret Sharing 方法来把 \(d\) 分享给 \(l\) 个参与者：随机取 \(k-1\) 个数 \(a_1, a_2, \cdots, a_{k-1}\) ，构造下面多项式： \[f(X) = d + a_1 X + a_2 X^2 + \cdots + a_{k-1}X^{k-1}\] 记 \(s_i = f(i) \pmod m\) 其中 \(i=1,2\cdots, l\) ，这个 \(s_i\) 就是每个参与者得到的“部分秘密”，参与者将使用它生成部分签名。

定义 \(\Delta = l!\) ，消息 \(M\) 的摘要为 \(x=\text{Hash}(M)\) ，对于参与者 \(i, \;i=1,2,\cdots,l\) 计算： \[x_i = x^{2 \cdot \Delta \cdot s_i}\] 这个 \(x_i\) 就是参与者 \(i\) 的部分签名。

对于任意大小为 \(k\) 的集合 \(S\) ， \(S\) 是 \(\{1,2,\cdots,l\}\) 的子集，定义： \[\lambda_{i,j}^S = \Delta \cdot \prod_{j' \in S \setminus {j}} \frac{i-j'}{j-j'}\] 这个式子是从标准拉格朗日插值公式系数而来，只是多乘以了一个常量 \(\Delta\) 。

假设我们收集了 \(k\) 个成员的“部分签名”，把成员组成的集合记为 \(S=\{i_1, \cdots, i_k\} \subset \{1, 2, \cdots, l\}\) ，记 \(i_j \subset S,\; j=1,\cdots,k\) ，用下面方式组合部分签名： \[w = x_{i_1}^{2 \cdot \lambda_{0, i_1}^S} x_{i_2}^{2 \cdot \lambda_{0, i_2}^S} \cdots x_{i_j}^{2 \cdot \lambda_{0, i_j}^S} \cdots x_{i_k}^{2 \cdot \lambda_{0, i_k}^S}\]

用下面方式计算最终的组合签名： \[y=w^a x^b\] 其中 \(a\) 和 \(b\) 都是整数，它们由 \((4 \cdot \Delta^2) \cdot a + e \cdot b = 1\) 计算而来，由于 \(e\) 是素数， \(4 \cdot \Delta^2\) 和 \(e\) 互素，由 \(4 \cdot \Delta^2\) 和 \(e\) 上的扩展欧几里德算法可以得到满足要求的 \(a\) 和 \(b\) 。

如果 \(y^e \pmod n = x\) 成立，则通过签名验证，这和常规的 RSA 签名验证逻辑是一样的。