秘密共享与门限密码学：从 Shamir 方案到现代阈值签名
概述
秘密共享（Secret Sharing）是密码学中的一个核心原语：将一个秘密拆分为多个份额（share），分发给不同参与者，使得只有满足特定条件的参与者子集才能重构秘密，而任何不足条件的子集则获得零信息。
这一概念由 Adi Shamir 和 George Blakley 于 1979 年独立提出，最初用于解决密钥管理的"安全性 vs 可靠性"矛盾——单份密钥存储面临丢失风险，多份存储则增加泄露面。秘密共享通过数学结构同时实现信息论级别的安全性和灵活的可用性控制。
随着云计算、加密货币和分布式系统的发展，秘密共享已从理论构造演变为现代密码系统的基础设施组件，广泛应用于密钥托管、安全多方计算（MPC）、阈值签名和去中心化托管等领域。
基本定义
(t, n)-门限方案
一个 (t, n)-门限方案将秘密 s 拆分为 n 份份额，满足：
- 可用性：任意 t 份或更多份额可以重构秘密
- 安全性：任意少于 t 份份额获得关于秘密的零信息
| 情形 | 含义 |
|---|---|
| t = 1 | 任意一人即可恢复（等价于全量复制） |
| t = n | 所有人必须参与（等价于 XOR 分割） |
| 1 < t < n | 真正的门限方案，需要真正的数学构造 |
信息论安全 vs 计算安全
| 安全级别 | 含义 | 代表方案 |
|---|---|---|
| 信息论安全 | 即使攻击者拥有无限算力也无法从不足份额中获取任何信息 | Shamir 方案（有限域上）、Blakley 方案 |
| 计算安全 | 在特定计算困难性假设下安全 | 基于同态加密的方案、Rabin IDA 方案 |
Shamir 门限方案
数学基础
Shamir 方案基于一个基本事实：t 个点唯一确定一个 t-1 次多项式。
- 2 个点确定一条直线（一次多项式）
- 3 个点确定一条抛物线（二次多项式）
- t 个点确定一个 t-1 次多项式
协议构造
秘密分发（Sharing）：
- 设秘密为 s，在有限域 GF(p) 上操作（p 为素数，且 p > n）
- 随机选择 t-1 个系数 a₁, a₂, ..., a_{t-1} ∈ GF(p)
- 构造多项式：f(x) = s + a₁x + a₂x² + ... + a_{t-1}x^{t-1}
- 为每个参与者 i 计算份额 (i, f(i))，其中 i ∈ {1, 2, ..., n}
- 秘密 s = f(0)（即常数项）
给定任意 t 个份额 (x₁, y₁), ..., (xₜ, yₜ)，通过拉格朗日插值恢复 f(0)：
f(0) = Σᵢ yᵢ · Lᵢ(0) (mod p)其中 Lᵢ(0) 为拉格朗日基多项式在 x=0 处的取值：
Lᵢ(0) = Π_{j≠i} (0 - xⱼ) / (xᵢ - xⱼ) (mod p)有限域的必要性
Shamir 方案必须在有限域上操作。如果使用普通整数运算，攻击者可以从单个份额中获取关于秘密的部分信息（如奇偶性）。有限域上的模运算消除了这一信息泄漏。
示例（整数运算 vs 有限域运算）：
假设秘密 S = 1234，t = 3，在整数上构造 f(x) = 1234 + 166x + 94x²。
- 份额 (1, 1494)：攻击者知道 S = f(0)，结合 f(1) = 1494 = S + 166 + 94，可以推断 S 的某些性质
- 在 GF(p) 上：攻击者从 f(1) = 1494 (mod p) 无法推出任何关于 S 的信息
安全性证明
定理：在 (t, n)-Shamir 方案中，任意 t-1 个份额与秘密 s 统计独立。
证明思路：对于任意 t-1 个份额和任意候选秘密 s'，恰好存在一个 t-1 次多项式经过这 t-1 个点且 f(0) = s'。由于系数是均匀随机选择的，所有 s' 的概率均等。
Blakley 门限方案
几何构造
Blakley 方案使用几何超平面代替多项式：
- 在 k 维空间中，t 个超平面相交于唯一一点
- 秘密编码为该交点的某一个坐标
- 每个参与者获得一个超平面（即一个 (k-1) 维子空间）
与 Shamir 方案的对比
| 维度 | Shamir | Blakley |
|---|---|---|
| 数学基础 | 多项式插值 | 超平面交集 |
| 份额大小 | 等于秘密大小 | 等于秘密的 t 倍 |
| 空间效率 | 最优 | 较低 |
| 构造复杂度 | 低 | 较高 |
| 安全级别 | 信息论安全 | 信息论安全 |
可验证秘密共享（VSS）
问题
基础 Shamir 方案假设分发者和参与者都是诚实的。实际中存在两个攻击向量：
- 恶意分发者：分发者可能给不同参与者分配不一致的份额，导致无法正确重构
- 恶意参与者：在重构阶段，参与者可能提交错误的份额
Verifiable Secret Sharing
VSS 方案允许每个参与者验证自己收到的份额与分发者承诺的一致性，而不泄露份额本身。
核心思想：分发者在分发份额时同时发布密码学承诺（如离散对数承诺），参与者可以验证自己的份额是否与承诺匹配。
Ben-Or、Rabin 和 Goldwasser 提出的 VSS 方案可以容忍最多 t/3 个恶意参与者和一个恶意分发者，即使攻击者可以实时调整策略（适应性攻击）。
Feldman VSS
Feldman VSS 基于 Pedersen 承诺：
- 分发者选择多项式 f(x) = a₀ + a₁x + ... + a_{t-1}x^{t-1}，其中 a₀ = s
- 发布承诺：Cⱼ = g^{aⱼ} (mod p)，j = 0, 1, ..., t-1
- 给参与者 i 分配份额 (i, f(i))
- 参与者 i 验证：g^{f(i)} 是否等于 Πⱼ Cⱼ^{iʲ}
g^{f(i)} = g^{Σⱼ aⱼ·iʲ} = Πⱼ (g^{aⱼ})^{iʲ} = Πⱼ Cⱼ^{iʲ}主动秘密共享（Proactive Secret Sharing）
问题
如果份额长期存储在不安全的服务器上，攻击者可以逐步入侵并收集份额。一旦收集到 t 个份额，秘密即被泄露。
解决方案
主动秘密共享通过定期刷新份额来应对：
- 分发者生成一个常数项为零的新随机多项式 δ(x)
- 计算每个参与者的新份额：new_shareᵢ = old_shareᵢ + δ(i)
- 所有非更新的旧份额失效
- 秘密不变（因为 δ(0) = 0）
- 攻击者必须在一个刷新周期内收集到 t 个份额
- 可以安全地更改阈值参数
门限密码系统
概念
门限密码系统将秘密密钥拆分为 n 份，使得：
- 至少 t 个参与者可以联合执行密码操作（签名、解密）
- 少于 t 个参与者无法执行任何密码操作
门限签名
(t, n)-门限签名方案：
- 密钥生成：分布式生成密钥对 (sk, pk)，sk 被拆分为 n 份
- 签名：至少 t 个参与者联合生成有效签名 σ = Sign(sk, m)
- 验证：使用公钥 pk 验证，与普通签名方案一致
#### Schnorr 门限签名
基于 Schnorr 签名的门限方案是最优雅的构造之一：
- 公钥：X = gˣ (mod p)，私钥 x 被共享为 x = Σᵢ xᵢ
- 签名：σ = (R, s)，其中 R = gᵏ，s = k + H(R||m)·x
- 门限签名时：每个参与者计算部分签名 sᵢ = kᵢ + H(R||m)·xᵢ，最终 s = Σᵢ sᵢ
#### ECDSA 门限签名
ECDSA 的门限化更具挑战性，因为签名过程涉及非线性的乘法运算。主要方案包括：
- Gennaro-Goldfeder-Narayanan 方案（GG18）：需要 9 轮通信
- Lindell 方案：2 轮通信，基于 Paillier 加密
- Canetti-Gennaro-Goldfeder 方案（CGGMP20）：支持任意阈值
BLS（Boneh-Lynn-Shacham）签名基于双线性对，天然支持门限操作：
- 签名聚合：σ = ∏ᵢ σᵢ（双线性对下的乘法）
- 无需交互式协议，非交互式聚合
- 签名大小恒定（单个群元素）
门限解密
类似地，公钥加密方案可以门限化：
- 私钥被拆分为 n 份
- 至少 t 个参与者联合解密
- 适用于 RSA、ElGamal、Paillier 等方案
应用场景
密钥管理
| 场景 | 方案选择 | 说明 |
|---|---|---|
| 企业 CA 根密钥 | (3,5)-门限签名 | 5 个 HSM 中任意 3 个即可签发证书 |
| 加密货币钱包 | Shamir Secret Sharing | BIP-39 助记词分片（SLIP-39） |
| 云服务密钥托管 | 主动秘密共享 | 定期刷新份额防止长期攻击 |
| 密码管理器主密钥 | (2,3)-门限 | 3 台设备中任意 2 台即可解锁 |
安全多方计算
秘密共享是安全多方计算（MPC）的基础组件：
- GMW 协议：基于秘密共享和混淆电路的通用 MPC
- BGW 协议：基于 Shamir 秘密共享的诚实多数 MPC
- SPDZ 协议：支持恶意安全性的预处理 MPC
NIST 标准化进展
NIST 自 2019 年起推动门限密码标准化：
- NIST IR 8214A（2020）：门限密码原语标准路线图
- NIST IR 8214B（2022）：门限 EdDSA/Schnorr 签名方案
- NIST IR 8214C（2023/2025）：多方门限方案征集
局限性与发展方向
已知局限性
| 局限性 | 说明 |
|---|---|
| 份额大小下界 | 信息论安全要求每个份额 ≥ 秘密大小 |
| 单重构点 | 秘密必须在某一时刻完整存在（分发和重构时） |
| 无可验证性 | 基础 Shamir 方案无法验证份额正确性 |
| 份额分发安全 | 分发阶段需要安全信道 |
| 长期安全性 | 静态份额面临持续威胁，需要主动刷新 |
前沿方向
- 高效 VSS：降低验证和通信开销
- 动态门限：支持参与者集合的动态变化
- 同态秘密共享：在份额上直接进行计算
- 后量子门限密码：基于格密码的门限方案
- 去中心化密钥生成（DKG）：无需可信分发者的密钥生成
参考来源
- Shamir, A. (1979). "How to share a secret." *Communications of the ACM*, 22(11): 612–613.
- Blakley, G.R. (1979). "Safeguarding Cryptographic Keys." *AFIPS Conference Proceedings*, 48: 313–317.
- Feldman, P. (1987). "A Practical Scheme for Non-interactive Verifiable Secret Sharing." *FOCS '87*.
- Ben-Or, M., Goldwasser, S., Wigderson, A. (1988). "Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computation." *STOC '88*.
- Gennaro, R., Goldfeder, S., Narayanan, A. (2016). "Threshold-optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security." *ACNS 2016*.
- Komlo, I., Goldberg, I. (2021). "FROST: Flexible Round-Optimized Schnorr Threshold Signatures." *SAC 2020*.
- NIST IR 8214A (2020). "Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives."
- NIST IR 8214B (2022). "Notes on Threshold EdDSA/Schnorr Signatures."
- NIST IR 8214C (2025). "NIST First Call for Multi-Party Threshold Schemes."
- Krenn, S., Loruenser, T. (2023). *An Introduction to Secret Sharing: A Systematic Overview and Guide for Protocol Selection.* Springer.
相关实践
- 如需了解门限签名在区块链钱包中的工程实践，请参阅《国密算法在 JWT 中的应用：SM2-SM3 签名与 SM4-CBC 加密实战》
- 如需了解 Schnorr 签名算法的数学原理，请参阅《Schnorr 签名算法原理：数学基础、协议设计与门限签名》