第 3 章：Shamir 秘密共享

学习定位：前置为第 2 章和实验 1；配套完成实验 2：Shamir。过关条件是任意合法 \(t\) 份恢复、非法 ID 被拒绝，并能解释少于门限为何不泄密。

Shamir Secret Sharing（SSS）解决的是这样一个问题：把秘密分散给 \(n\) 个参与者，使任意至少 \(t\) 人能够恢复秘密，而少于 \(t\) 人无法获得关于秘密的信息。

先把边界说清楚：**Shamir 是秘密共享方案，不是签名方案，也不是完整的门限签名协议。**它可以成为门限签名中的密钥共享层，但它本身不会验证消息、生成数字签名或抵抗所有恶意参与者。

学习目标

完成本章后，你应该能够：

1. 解释 \(t\)-of-\(n\) 门限的含义；
2. 用次数 \(t-1\) 的随机多项式生成份额；
3. 用任意合格参与者集合恢复秘密；
4. 解释为什么少于 \(t\) 个份额不泄漏秘密；
5. 说明普通 Shamir 与 VSS、DKG、门限签名的区别；
6. 识别重复标识符、零标识符、弱随机数和错误域等实现陷阱。

3.1 直觉：把秘密藏在多项式的截距里

一条直线由两个不同点唯一确定。只知道直线上的一个点时，可能穿过该点的直线有很多条，其纵轴截距也可能是任意值。

Shamir 把秘密 \(s\) 放在多项式常数项：

\[ f(0)=s \]

对于 2-of-n，选择一条随机直线：

\[ f(X)=s+a_1X \]

每个参与者得到直线上的一个不同点。任意两点能确定直线并得到截距，单独一点则不能。

对于一般的 t-of-n，选择次数为 \(t-1\) 的随机多项式：

\[ f(X)=s+a_1X+a_2X^2+\cdots+a_{t-1}X^{t-1} \]

次数不超过 \(t-1\) 的多项式由 \(t\) 个横坐标不同的点唯一确定，这就产生了门限。

3.2 参数与威胁模型

记：

• \(n\)：参与者总数；
• \(t\)：恢复门限，满足 \(1\le t\le n\)；
• \(q\)：素数域模数；
• \(s\in\mathbb Z_q\)：待共享秘密；
• \(i\in\mathbb Z_q^*\)：参与者的非零、唯一标识符；
• \(s_i=f(i)\)：参与者 \(i\) 的份额。

如果共享的是 Schnorr 私钥，那么 Shamir 多项式必须在签名群的标量域 \(\mathbb Z_q\) 中运算，而不是在曲线坐标的基域 \(\mathbb F_p\) 中运算。

普通 Shamir 的经典保密结论基于以下条件：

1. Dealer（分发者）诚实地选取并分发份额；
2. 非常数系数均匀随机且独立；
3. 参与者通过机密且认证的信道接收份额；
4. 攻击者得到的有效份额少于 \(t\)。

普通 Shamir 本身不能让参与者发现 Dealer 是否给不同人发送了互不一致的份额，也不能阻止参与者在恢复时提交假份额。这些问题需要可验证秘密共享（VSS）等机制处理。

3.3 份额生成算法

由 Dealer 执行：

1. 检查 \(1\le t\le n\)，并准备 \(n\) 个互不相同的非零标识符；

2. 将秘密编码为标量 \(s\in\mathbb Z_q\)；

3. 独立均匀采样 \(a_1,\ldots,a_{t-1}\leftarrow\mathbb Z_q\)；

4. 定义

   \[ f(X)=s+\sum_{j=1}^{t-1}a_jX^j \]

5. 对每个参与者 \(i\)，计算并私下发送

   \[ (i,s_i)=(i,f(i)) \]

这里的“份额”必须同时包含标识符和值。只保存 \(s_i\) 而丢失 \(i\)，恢复时就不知道该使用哪个拉格朗日系数。

关于最高次系数为零

标准 Shamir 证明通常要求 \(a_1,\ldots,a_{t-1}\) 各自在整个域中独立均匀采样，零也包括在内。如果恰好 \(a_{t-1}=0\)，实际多项式次数会降低；但观察者并不知道这一事件，标准分布下少于 \(t\) 个份额仍不泄漏秘密。在密码学使用的大域中，最高次系数为零的概率为 \(1/q\)，可以忽略。

不要自作主张地把最高次系数条件化为“非零”：以 2-of-n 为例，强制 \(a_1\ne0\) 后，观察份额 \(s_i\) 会排除候选秘密 \(s=s_i\)，从而破坏标准的完美隐私分布。教学用小域为了固定演示次数可以显式挑选一个非零系数，但必须说明这不是一般采样算法。正式实现应逐字遵循所选协议规范。

3.4 恢复算法

选择任意至少 \(t\) 个有效份额。为便于说明，先取恰好 \(t\) 个，其标识符集合为 \(S\)。对每个 \(i\in S\)，计算零点处的拉格朗日系数：

\[ \lambda_i^S= \prod_{\substack{j\in S\\j\ne i}} \frac{0-j}{i-j} = \prod_{\substack{j\in S\\j\ne i}} \frac{-j}{i-j} \pmod q \]

然后恢复：

\[ s=f(0)=\sum_{i\in S}\lambda_i^S s_i\pmod q \]

上标 \(S\) 提醒我们：**拉格朗日系数依赖本次使用的参与者集合。**在 2-of-3 系统中，集合 \(\{1,2\}\) 和 \(\{1,3\}\) 使用的系数不同。

拥有多于 \(t\) 个份额时，可以选择其中任意 \(t\) 个有效份额进行插值，也可以对全部点进行相应插值。真实系统还必须考虑坏份额检测；“多拿几个未经验证的份额”不会自动带来健壮性。

3.5 完整小例子：在 \(\mathbb F_{17}\) 中实现 2-of-3

这里使用很小的域只是为了手算。它完全不安全，不能用于真实密钥。

令秘密为：

\[ s=5 \]

门限 \(t=2\)，所以选择一次多项式。假设随机系数为 \(a_1=7\)：

\[ f(X)=5+7X\pmod {17} \]

给三个参与者分配标识符 \(1,2,3\)：

现在只使用参与者 1 和 3，即 \(S=\{1,3\}\)。

参与者 1 的系数：

\[ \lambda_1^{\{1,3\}} =\frac{-3}{1-3} =\frac{-3}{-2} =3\cdot2^{-1} =3\cdot9 \equiv10\pmod {17} \]

参与者 3 的系数：

\[ \lambda_3^{\{1,3\}} =\frac{-1}{3-1} =-1\cdot2^{-1} =16\cdot9 \equiv8\pmod {17} \]

恢复秘密：

\[ s=10\cdot12+8\cdot9=192\equiv5\pmod {17} \]

结果与原秘密一致。

顺便检查：

\[ \lambda_1+\lambda_3=10+8=18\equiv1\pmod {17} \]

常数多项式在插值后仍应保持原值，所以拉格朗日系数之和为 1 是一个有用的调试性质，但它不能替代完整测试。

3.6 为什么少于门限的份额不泄漏秘密

仍看 2-of-n。攻击者知道一个份额 \((i,s_i)\)，而：

\[ s_i=s+a_1i \]

对任意候选秘密 \(s'\in\mathbb Z_q\)，总能找到唯一一个斜率：

\[ a_1'=(s_i-s')i^{-1} \]

使直线 \(f'(X)=s'+a_1'X\) 穿过已知点。由于原斜率是均匀随机的，观察到这个点以后，每个候选秘密仍然同样可能。

一般情形中，少于 \(t\) 个约束仍留下足够的随机系数自由度，能与任意候选常数项兼容。因此 Shamir 在理想模型下提供信息论保密性：它不依赖攻击者算力有限。

但这项结论并不意味着任何“看起来像 Shamir”的实现都安全。随机系数可预测、份额通过日志泄漏或标量编码错误，都会破坏理论前提。秘密空间很小本身不会让少于门限的纯 Shamir 份额泄密；但若同时公开了 Feldman 承诺、校验值或其他猜测验证器，攻击者就可能枚举候选秘密，因此后续协议必须把这些公开信息一起纳入分析。

3.7 Shamir 与门限 Schnorr 如何连接

设 Schnorr 私钥为：

\[ x=f(0)\in\mathbb Z_q \]

参与者 \(i\) 持有密钥份额：

\[ x_i=f(i) \]

群公钥为：

\[ X=xG \]

若签名集合为 \(S\)，则由插值关系：

\[ x=\sum_{i\in S}\lambda_i^Sx_i \]

两边同乘生成元 \(G\)：

\[ X=xG =\sum_{i\in S}\lambda_i^S(x_iG) \]

定义验证份额（公开份额）：

\[ X_i=x_iG \]

就得到：

\[ X=\sum_{i\in S}\lambda_i^S X_i \]

这说明密钥份额可以带权参与群运算，而不必先把完整私钥 \(x\) 重构到某台机器上。门限签名的价值恰恰在于：协作产生签名，但不恢复完整私钥。

如果某个所谓“门限签名实现”先收集 \(t\) 个份额、恢复 \(x\)，再调用普通签名函数，它只是“先秘密共享、后集中签名”。恢复节点在那一刻拥有完整私钥，失去了 TSS 的核心安全性质。

3.8 普通 Shamir 不提供什么

它不是签名

Shamir 不接收消息 \(m\)，不生成可由公钥验证的签名，也不提供不可伪造性。

它不验证份额

持有 \((i,s_i)\) 的参与者仅凭普通 Shamir 无法确认这个值是否与其他人的份额属于同一个多项式。

它不消除可信 Dealer

Dealer 在生成阶段知道完整秘密和所有份额，还可以作恶。分布式密钥生成（DKG）用于让多方共同生成共享密钥，使完整私钥从未在单点出现。

它不自动容错

一个恶意或损坏的份额可能导致恢复出错误结果。检测、归责、剔除和重试属于 VSS 或更完整协议的职责。

它不保护静态存储

份额仍是高价值秘密。磁盘加密、访问控制、硬件隔离、备份策略和安全删除需要另外设计。

3.9 从 Shamir 到可验证秘密共享

Feldman VSS 为多项式系数发布群承诺：

\[ A_j=a_jG,\qquad j=0,\ldots,t-1 \]

其中 \(a_0=s\)，所以 \(A_0=sG=X\)。参与者 \(i\) 可以检查：

\[ s_iG\stackrel?= \sum_{j=0}^{t-1}i^jA_j \]

因为右侧等于：

\[ \sum_{j=0}^{t-1}i^j(a_jG) =\left(\sum_{j=0}^{t-1}a_ji^j\right)G =f(i)G \]

这让参与者验证自己的份额是否与公开承诺一致。

但要注意：

• Feldman 承诺依赖离散对数困难性，不提供信息论隐藏；
• 如果被承诺的秘密来自很小的可枚举空间，攻击者可能猜测后计算 \(sG\) 比较；
• 广播渠道必须一致，否则 Dealer 可能给不同参与者展示不同承诺；
• 完整的投诉、剔除和 DKG 流程远不止这一条等式。

Pedersen VSS 会加入额外随机盲化以提供隐藏性，代价是协议和承诺结构更复杂。

3.10 实现时必须明确的边界

参与者标识符

• 必须非零：若 \(i=0\)，则 \(s_i=f(0)=s\)，直接得到完整秘密；
• 必须唯一：重复标识符会导致插值分母为零；
• 必须规范映射到标量：字符串或用户 ID 应通过协议定义的分配/编码规则得到标量，并在当前 roster 内显式检查非零与唯一；不要假定任意字符串到有限域存在天然无碰撞的哈希映射；
• 不能把数组下标、显示顺序和密码学标识符悄悄混为一谈。

份额结构

一个可用的份额记录至少需要绑定：

• 协议和版本；
• 密钥或会话标识；
• 参与者标识符；
• 门限与总人数；
• 份额值；
• 所用群/套件；
• 完整性或来源认证信息。

把裸标量复制到另一个密钥会话中可能产生灾难性混淆。

序列化

标量必须使用固定长度、规范字节序和唯一编码。反序列化时应拒绝超出范围的非规范表示，而不是在所有场景下静默 % q；具体规则应服从所选协议和曲线库。

秘密生命周期

避免在调试输出、错误文本、panic 信息和测试快照中打印份额。Rust 的所有权可以减少意外复制，但不能自动保证内存清零、无 swap、无 core dump 或无侧信道。

3.11 建议的动手验证

实现完整门限签名前，可以先对一个小素数域版本做性质测试：

1. 随机生成 \(s,t,n\) 和多项式；
2. 枚举或随机选择多个大小为 \(t\) 的参与者子集；
3. 检查每个子集都恢复同一个 \(s\)；
4. 打乱份额顺序，确认结果不变；
5. 构造重复 ID、ID 为零、份额不足和份额值越界，确认接口明确拒绝；
6. 篡改一个份额，观察普通 Shamir 为什么无法判断是谁作恶；
7. 再加入 Feldman 承诺，验证篡改份额会使检查等式失败。

小素数版本的目的在于观察协议，而非复用到生产代码。随后应把字段类型替换为曲线库提供的 Scalar，并保留同样的性质测试。

3.12 常见误区

误区一：“把私钥切成三段就是 2-of-3”

把字节分成三段需要三段全部到齐；简单复制或 XOR 也不会自动得到任意两份可恢复的门限结构。Shamir 的门限来自多项式插值。

误区二：“Shamir 已经是一套门限签名”

错误。它只共享秘密。门限签名还必须安全地产生并协调 nonce、绑定消息与参与者、验证签名份额并抵抗恶意行为。

误区三：“恢复时把所有份额值直接相加”

通常错误。份额需要乘以与参与集合对应的拉格朗日系数。

误区四：“参与者 ID 可以从 0 开始”

错误。ID 0 的份额就是 \(f(0)=s\)。

误区五：“份额超过门限，坏份额会被多数自动抵消”

错误。普通插值不会自动识别错误值；必须增加验证或纠错机制。

误区六：“共享曲线私钥时在 \(\mathbb F_p\) 上插值”

错误。曲线私钥是群作用的标量，必须在子群阶定义的 \(\mathbb Z_q\) 上共享与插值。

误区七：“重构测试通过，就可以部署”

错误。测试只能说明某些功能路径正确，不能证明随机数、侧信道、恶意参与者处理、持久化和网络协议安全。

3.13 章节检查题

1. 为什么 3-of-5 Shamir 使用次数至多为 2 的多项式？
2. 最高次系数为零时，多项式次数会怎样变化？为什么标准 Shamir 仍不应擅自将采样改为“最高次系数必须非零”？
3. 2-of-3 中，参与者集合从 \(\{1,2\}\) 换成 \(\{1,3\}\) 后，原拉格朗日系数还能复用吗？
4. 在本章 \(\mathbb F_{17}\) 的例子中，仅持有份额 \((1,12)\) 时，秘密能否是 \(6\)？若能，对应斜率是多少？
5. 为什么共享 Schnorr 私钥要使用 \(\mathbb Z_q\)，而不是 \(\mathbb F_p\)？
6. 普通 Shamir 为何无法发现 Dealer 给出的份额不一致？
7. Feldman VSS 的份额验证等式是什么？
8. “恢复私钥后再普通签名”和真正门限签名的安全边界有何不同？

本章小结

Shamir 用“随机多项式的常数项”承载秘密，用“多项式次数加一”定义门限。它为门限 Schnorr 提供了密钥份额和拉格朗日权重，但安全签名还需要 nonce 协议、消息绑定、签名份额验证以及应对恶意参与者的完整状态机。