可验证秘密共享（VSS）：从诚实假设到恶意安全的密码学构造

概述

秘密共享（Secret Sharing）的基本思想是将一个秘密拆分为多个份额，分发给不同参与者，使得只有满足特定条件的参与者子集才能重构秘密，而任何不足条件的子集则获得零信息。Adi Shamir 于 1979 年提出的 $(k, n)$ 门限方案，通过多项式插值实现了信息论级别的安全保证。

然而，Shamir 原始方案存在一个关键假设：所有参与者都是诚实的。他们按协议生成份额并诚实分发，不会故意伪造或篡改数据。在理想环境下，这个假设是合理的；但在实际应用中，可能存在以下威胁：

• 恶意分发者：分份额的一方不是按协议计算份额，而是发送伪造的份额来操控最终重构的秘密。
• 恶意参与者：某些参与者在重构阶段提交虚假份额，导致其他参与者得到错误的秘密。
• 外部攻击者：截获并篡改通信过程中的份额数据。

本文将系统介绍 VSS 的数学构造、核心协议设计模式，以及它在国密 SM2 阈值签名和分布式密钥生成（DKG）中的实际应用。

VSS 的核心动机与安全模型

诚实半诚实模型 vs 恶意模型

在密码学中，我们通常区分两种安全模型：

诚实半诚实（Honest-but-Curious）模型：

• 所有参与者都按协议执行，但会尝试从收到的消息中推断额外信息
• Shamir 原始方案在此模型下是安全的
• 每个参与者只能看到自己的份额，无法推断秘密或其他份额

• 参与者可以任意偏离协议，包括发送伪造份额、篡改数据等
• 需要 VSS 方案才能保证安全性
• 每个参与者在接收份额后，能够验证份额的有效性

VSS 的两个阶段

标准的 VSS 协议由两个阶段组成：

Phase 1: Commitment (承诺阶段)
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│  Dealer (D) │────▶│   Party 1   │────▶│   Party 2   │─── ...
└─────────────┘     └─────────────┘     └─────────────┘
      │                  │                  │
      │                  │                  │
      ▼                  ▼                  ▼
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│  Commit_1   │     │  Commit_2   │     │  Commit_n   │
└─────────────┘     └─────────────┘     └─────────────┘

Phase 2: Reveal & Verification (揭示与验证阶段)
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│  Party 1    │────▶│  Party 2    │────▶│  Party 3    │─── ...
│  (reveal)   │     │  (verify)   │     │  (verify)   │
└─────────────┘     └─────────────┘     └─────────────┘
      │
      ▼
┌─────────────┐
│ Reconstruct │
│   Secret    │
└─────────────┘

承诺阶段：

• 分发者（Dealer）选择一个随机多项式 $f(x)$，其中 $f(0) = s$（秘密）
• 计算所有份额 $f(1), f(2), \ldots, f(n)$
• 对每个份额生成一个承诺（commitment），发布到公共信道上
• 承诺必须满足：给定承诺，可以验证对应的份额；但给定承诺，无法推断份额

• 分发者向每个参与者发送对应的份额
• 每个参与者使用公开承诺验证自己收到的份额是否有效
• 如果验证失败，该参与者可以拒绝份额并报告作弊
• 所有诚实参与者验证通过后，使用份额重构秘密

为什么需要承诺？

Shamir 方案的致命缺陷在于：如果分发者发送伪造的份额，参与者无法检测。例如，分发者可以选择一个恶意构造的多项式，使得：

• 所有诚实参与者的份额看起来"合法"
• 但任意 $k$ 个诚实参与者的份额组合会得到错误的秘密
• 只有包含恶意参与者的集合才能还原正确秘密

承诺机制的引入，使得份额在发布前就被"锁定"。分发者一旦发布了承诺，就无法在不被发现的情况下更改份额——这正是 VSS 的核心安全属性。

VSS 的数学构造：Shamir + Pedersen 承诺

基础定义

设我们有一个 $(k, n)$ 门限方案，秘密 $s \in \mathbb{Z}_q$ 分布在 $n$ 个参与者中。构造 VSS 需要以下步骤：

Step 1: 参数选择

• 选择一个安全素数 $p$，使得 $q | (p-1)$，即 $q$ 是 $p-1$ 的素因子
• 选择一个生成元 $g \in \mathbb{Z}_p^*$，其阶为 $q$
• 选择另一个随机生成元 $h \in \mathbb{Z}_p^*$，且 $\log_g h$ 未知（离散对数问题）

Step 3: 份额计算与承诺 对于每个参与者 $i$（$i = 1, 2, \ldots, n$）：

• 份额：$s_i = f(i) \pmod{q}$
• 承诺：$C_i = g^{s_i} \cdot h^{r_i} \pmod{p}$，其中 $r_i \in_R \mathbb{Z}_q$

Pedersen 承诺具有两个关键性质：

• 隐藏性（Hiding）：给定承诺 $C$，无法推断消息 $m$。因为 $h$ 的离散对数未知，$r$ 的选择使得 $C$ 看起来完全随机。

• 绑定性（Binding）：给定 $C$，无法找到另一对 $(m', r')$ 使得 $C(m', r') = C$。如果存在这样的对，则：

VSS 协议的完整流程

Phase 1: Commitment
1. 分发者选择随机多项式 f(x) = s + a₁x + ... + a_{k-1}x^{k-1}
2. 计算份额 sᵢ = f(i), i = 1,...,n
3. 计算 Pedersen 承诺 Cᵢ = g^{sᵢ} · h^{rᵢ} mod p
4. 广播所有承诺 {Cᵢ} 到公共信道
5. （可选）广播辅助承诺：A_j = g^{a_j} · h^{ρ_j} mod p, j = 1,...,k-1
           用于验证多项式的一致性

Phase 2: Reveal & Verification
6. 分发者向参与者 i 发送份额 sᵢ 和随机数 rᵢ
7. 参与者 i 验证：
   - Cᵢ ≟ g^{sᵢ} · h^{rᵢ} mod p  （验证份额对应承诺）
   - f(0) = s, f(i) = sᵢ          （验证多项式结构）
8. 如果验证失败，报告分发者作弊；否则接受份额

验证的多项式一致性

上述方案需要额外验证多项式的一致性——确保所有份额来自同一个 $k-1$ 次多项式。可以通过零知识证明实现：

分发者发布辅助承诺： $$A_j = g^{a_j} \cdot h^{\rho_j} \pmod{p}, \quad j = 1, 2, \ldots, k-1$$

每个参与者验证： $$C_i \stackrel{?}{=} g^{f(i)} \cdot h^{\sum_{j=1}^{k-1} a_j \cdot i^j} \pmod{p}$$

由于 $f(i) = s + \sum_{j=1}^{k-1} a_j \cdot i^j$，这要求： $$C_i \stackrel{?}{=} g^s \cdot \prod_{j=1}^{k-1} A_j^{i^j} \pmod{p}$$

参与者可以独立验证此等式，无需知道 $a_j$ 的具体值。

安全性分析

定理：在上述 VSS 方案下，恶意分发者最多只能让重构失败，无法操控重构结果。

证明思路：

• 完整性（Integrity）：分发者发布承诺后，份额被绑定。任何修改都会导致承诺不匹配。

• 私有性（Privacy）：即使分发者是恶意的，诚实参与者获得的份额仍然隐藏了秘密。因为 $r_i$ 是随机的，Pedersen 承诺提供了信息论级别的隐藏性。

• 有效性（Validity）：如果所有诚实参与者都验证通过，那么他们收到的份额必然来自同一个多项式 $f(x)$。由 Shamir 方案的插值唯一性，重构结果是确定性的。

VSS 的工程实现与国密适配

基于 SM2 的 VSS 实现

在国密体系中，我们可以将 VSS 与 SM2 算法结合使用。由于 SM2 基于椭圆曲线群，而非 $\mathbb{Z}_p^*$，需要调整承诺方案。

椭圆曲线上的 Pedersen 承诺：

在椭圆曲线群 $E(\mathbb{F}_p)$ 上，选取生成元 $G$，承诺形式变为： $$C(s, r) = s \cdot G + r \cdot H$$ 其中 $H$ 是另一个随机点，且离散对数 $\log_G H$ 未知。

验证过程：

• 分发者发布 $A_j = a_j \cdot G$（辅助点）
• 参与者验证：$C_i \stackrel{?}{=} s \cdot G + \sum_{j=1}^{k-1} a_j \cdot i^j \cdot G$

# 使用 gmssl 实现 VSS
from gmssl import sm2, func
import hashlib
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

class VerifiableSecretSharing:
    def __init__(self, k, n):
        self.k = k  # 门限值
        self.n = n  # 总参与人数
        # 注意：国密 SM2 使用自定义曲线，此处仅示意
    
    def generate_polynomial(self, secret):
        """生成随机多项式 f(x) = secret + a1*x + ... + a_{k-1}*x^{k-1}"""
        coeffs = [secret]
        for _ in range(self.k - 1):
            coeffs.append(func.random_num(1, self.curve.order - 1))
        return coeffs
    
    def compute_share(self, coeffs, participant_id):
        """计算份额 f(participant_id)"""
        result = 0
        for i, coeff in enumerate(coeffs):
            result = (result + coeff * pow(participant_id, i)) % self.curve.order
        return result
    
    def create_pedersen_commitment(self, value, randomness):
        """创建 Pedersen 承诺 C = value*G + randomness*H"""
        G = self.curve.generator
        # H 为随机点，实际应预先生成
        H = ec.EllipticCurvePublicNumbers(
            0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
            0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5,
            self.curve
        ).public_key()
        
        # C = value * G + randomness * H
        point_G = G * value
        point_H = H * randomness
        # 合并点（实际应使用椭圆曲线加法）
        return point_G  # 简化示意
    
    def verify_commitment(self, commitment, share, randomness, aux_commitments):
        """验证份额对应的承诺"""
        # C_i =?= g^{s_i} * product(A_j^{i^j})
        pass

注意：以上代码仅为示意。实际实现需要使用完整的椭圆曲线运算库，并且要正确处理点加法和标量乘法。

分布式密钥生成（DKG）中的应用

VSS 的一个重要应用是分布式密钥生成（Distributed Key Generation，DKG）。在 DKG 中，没有单个分发者，而是所有参与者共同生成密钥。

Feldman 的 DKG 方案（Feldman, 1987）：

• 每个参与者 $i$ 独立选择一个随机多项式 $f_i(x)$
• 发布承诺 $C_{i,j} = g^{f_i(j)} \cdot h^{r_{i,j}}$
• 最终秘密份额：$s_i = \sum_{j=1}^n f_j(i)$
• 最终公钥：$P = \sum_{j=1}^n g^{f_j(0)}$

• 没有单一可信分发者
• 即使部分参与者恶意，诚实参与者仍可获得正确的份额
• 适用于国密 SM2 阈值签名场景

国密标准中的 VSS 应用

在国密标准体系中，VSS 的思想已经体现在以下场景中：

• GM/T 0034-2014《基于 SM2 的证书认证系统密码规范》：要求密钥管理系统支持密钥分片存储，防止单点故障。

• GM/T 0038-2014《证书认证密钥管理系统检测规范》：检测密钥管理系统是否实现了密钥的分片存储和重构机制。

• GM/T 0132-2023《信息系统密码应用实施指南》：建议在密钥管理中采用门限机制，结合 VSS 确保安全性。

VSS 与相关技术的对比

VSS vs 普通秘密共享

VSS vs 盲签名

虽然两者都涉及"验证而不泄露"的概念，但目标不同：

• VSS：验证份额的正确性，不泄露秘密本身
• 盲签名：让签名者无法看到消息内容，同时保证签名的有效性

VSS vs 零知识证明

VSS 通常结合零知识证明来实现，但两者是不同层次的概念：

• 零知识证明：证明者向验证者证明某个命题为真，而不泄露任何额外信息
• VSS：一种协议构造，确保份额的有效性和秘密的安全性

• 证明多项式的次数不超过 $k-1$
• 证明承诺与份额的一致性
• 验证 DKG 过程的正确性

性能分析与工程实践

计算复杂度

对于 $(k, n)$ VSS 方案：

• $n = 100, k = 3$ 时，分发者耗时约 3ms
• 每个参与者验证耗时约 0.3ms

通信开销

VSS 需要额外的通信：

• 分发者广播 $n$ 个承诺，每个约 32 字节（256 位群元素）
• 分发者发送 $n$ 个份额，每个约 32 字节
• 辅助承诺约 $k$ 个，每个 32 字节
• 总通信量约 $(2n + k) \times 32$ 字节

国密场景下的优化建议

• 批量验证：使用批量检查技术（如批量 Pedersen 验证）减少计算开销
• 增量更新：对于动态参与的 VSS，支持份额的增量更新而非重新分发
• 压缩承诺：利用同态性质，将 $n$ 个承诺压缩为常数个（需牺牲某些安全性）

总结与展望

可验证秘密共享（VSS）是现代密码学的核心构造之一，它将 Shamir 秘密共享的信息论安全性提升到了恶意安全模型。通过结合 Pedersen 承诺和零知识证明，VSS 使得每个参与者能够在不泄露秘密的情况下验证份额的有效性。

在国密应用中，VSS 的思想已经体现在：

• 密钥管理系统（GM/T 0038）的分片存储要求
• 证书认证系统（GM/T 0034）的密钥安全管理规范
• 信息系统密码应用（GM/T 0132）的门限密钥管理建议

• 阈值签名方案：结合 VSS 实现抗篡改的多方签名
• 安全多方计算：作为 MPC 协议的底层原语
• 区块链与 DeFi：用于钱包安全、链下隐私计算等场景
• 国密后量子迁移：探索格密码基础上的 VSS 构造

相关实践

• SM2 阈值签名实现
• 国密数字信封技术原理与实现
• 秘密共享与门限密码学