Pedersen 承诺方案：同态性与隐藏性原理

概述

承诺方案（Commitment Scheme）是密码学中的基础原语，类似于"密封的信封"：发送方可以承诺一个值，而接收方在承诺期间无法得知该值；但承诺一旦发出，发送方也无法更改它。

1991 年，Vigené Pedersen 在"Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing"一文中提出了著名的 Pedersen 承诺方案。这个方案的核心优雅之处在于：

• 计算绑定性：在离散对数问题困难假设下，承诺者无法找到两个不同的值产生相同的承诺
• 信息论隐藏性：承诺值对观察者完全隐藏，即使拥有无限计算能力也无法获取信息
• 加法同态性：两个承诺的乘积等于它们对应值的和的承诺

数学构造

基本设定

Pedersen 承诺在循环群 $G$ 上定义，其中离散对数问题困难。设：

• $G$ 是一个阶为素数 $q$ 的循环群
• $g, h$ 是 $G$ 的两个生成元
• 关键要求：已知 $g$ 和 $h$，但不知道离散对数关系 $log_g h$

• 有限域 $\mathbb{Z}_p^*$ 的素数阶子群（$p$ 为大素数，$q | p-1$）
• 椭圆曲线群

承诺算法

承诺过程：给定消息 $m \in \mathbb{Z}_q$ 和随机数 $r \in_R \mathbb{Z}_q$，承诺值为：

$$C = g^m \cdot h^r \mod p$$

或用乘法记号：$C = \text{Commit}(m, r) = g^m h^r$

参数公开：$(p, q, g, h)$ 是系统公共参数，所有参与者都知道。

验证算法

打开承诺时，承诺者公开 $(m, r)$，验证者检查：

$$C \stackrel{?}{=} g^m \cdot h^r \mod p$$

安全属性证明

隐藏性（Hiding）

定理：Pedersen 承诺是信息论隐藏的。

证明：对于任意承诺 $C$ 和任意消息 $m'$，存在唯一的随机数 $r'$ 使得：

$$C = g^{m'} \cdot h^{r'}$$

解得：$r' = log_h(C \cdot g^{-m'})$

由于 $r'$ 均匀分布在 $\mathbb{Z}_q$ 中（因为 $r$ 是均匀随机的），观察者看到的承诺分布与消息无关。即使拥有无限计算能力，也无法从 $C$ 推断出 $m$。

关键点：隐藏性不依赖计算假设，是信息论安全的。

绑定性（Binding）

定理：Pedersen 承诺是计算绑定的，基于离散对数问题的困难性。

证明（反证法）：假设攻击者能找到碰撞，即：

$$g^m \cdot h^r = g^{m'} \cdot h^{r'}$$

其中 $m \neq m'$ 或 $r \neq r'$。则：

$$g^{m-m'} = h^{r'-r}$$

令 $\Delta m = m - m'$，$\Delta r = r' - r$，则：

$$g^{\Delta m} = h^{\Delta r} = g^{x \cdot \Delta r}$$

其中 $x = log_g h$。因此：

$$\Delta m \equiv x \cdot \Delta r \pmod{q}$$

$$x \equiv \Delta m \cdot (\Delta r)^{-1} \pmod{q}$$

由于 $\Delta m \neq 0$ 且 $\Delta r \neq 0$（否则 $m=m'$ 且 $r=r'$），攻击者可以计算 $x = log_g h$，这与离散对数问题困难性矛盾。□

关键点：绑定性依赖于离散对数问题的困难性。如果知道 $log_g h$，就可以自由改变承诺。

同态性（Homomorphism）

定理：Pedersen 承诺支持加法同态。

证明：

$$\text{Commit}(m_1, r_1) \cdot \text{Commit}(m_2, r_2) = g^{m_1} h^{r_1} \cdot g^{m_2} h^{r_2} = g^{m_1 + m_2} h^{r_1 + r_2} = \text{Commit}(m_1 + m_2, r_1 + r_2)$$

同理，标量乘法：

$$\text{Commit}(m, r)^k = g^{km} h^{kr} = \text{Commit}(km, kr)$$

这个同态性质是 Pedersen 承诺最重要的特性，使其能够在不知道具体值的情况下对承诺进行运算。

与椭圆曲线的结合

在实际应用中，Pedersen 承诺通常在椭圆曲线群上实现，以获得更高的安全强度和小尺寸。

EC-Pedersen 承诺

设 $E$ 是定义在有限域 $\mathbb{F}_p$ 上的椭圆曲线，$G$ 是 $E$ 上一个阶为素数 $q$ 的子群。

• 选择两个生成元 $G, H \in G$，使得不知道 $log_G H$
• 承诺：$\text{Commit}(m, r) = mG + rH$
• 验证：$C \stackrel{?}{=} mG + rH$

• 相同安全强度下密钥尺寸更小（256 位曲线提供 128 位安全）
• 运算效率更高（标量乘法比模幂运算快）
• 与国密 SM2 曲线兼容

国密适配

在国密体系中，可以使用 SM2 曲线的参数：

• 曲线方程：$y^2 = x^3 + ax + b \mod p$
• 素数 $p = $ FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
• 基点 $G = (x_G, y_G)$
• 阶 $n = $ FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 72035605 AAAAAAAB

$$C = mG + rH = mG + rsG = (m + rs)G$$

应用场景

盲签名（Blind Signature）

Pedersen 承诺与盲签名天然契合。Chaum 的盲签名方案中，用户先对消息做盲化（使用随机数 $r$），然后请求签名者签名。Pedersen 承诺提供了更安全的盲化机制：

• 用户计算 $C = g^m h^r$
• 签名者对 $C$ 签名（不知道 $m$）
• 用户解开签名，得到对 $m$ 的有效签名

零知识证明

Pedersen 承诺是构建零知识证明的基础组件：

证明知晓承诺值：用户可以向验证者证明他知道 $C = g^m h^r$ 中的 $m$ 和 $r$，而不泄露具体值。这通过 Schnorr 协议实现：

• 用户选择随机 $k$，计算 $t = g^k h^s$
• 验证者发送挑战 $c$
• 用户响应 $z = k + cm$
• 验证者检查 $g^z h^w \stackrel{?}{=} t \cdot C^c$

安全多方计算

在多方的秘密共享和投票系统中，Pedersen 承诺用于：

• 验证秘密共享的正确性
• 防止恶意参与者的欺骗行为
• 实现可验证的阈值签名

与 RSA 承诺的对比

Pedersen 承诺与基于 RSA 的承诺方案（如 Goldwasser-Micali）有重要区别：

实现示例

# 简化的 Pedersen 承诺实现（使用大素数群）
import hashlib
import random

def generate_params(bit_length=2048):
    """生成 Pedersen 承诺参数"""
    # 生成大素数 p 和 q，使得 q | (p-1)
    # 实际实现需要使用安全的素数生成算法
    p = generate_safe_prime(bit_length)
    q = (p - 1) // 2
    # 选择生成元 g 和 h
    g = random.randint(2, p - 2)
    h = random.randint(2, p - 2)
    # 确保 h 不是 g 的幂（简化处理，实际需要验证）
    return p, q, g, h

def commit(p, q, g, h, message, randomness):
    """创建承诺"""
    # C = g^m * h^r mod p
    C = pow(g, message, p) * pow(h, randomness, p) % p
    return C

def verify(p, q, g, h, C, message, randomness):
    """验证承诺"""
    return C == pow(g, message, p) * pow(h, randomness, p) % p

def homomorphic_add(p, C1, C2):
    """同态加法：C1 + C2 = Commit(m1 + m2, r1 + r2)"""
    return C1 * C2 % p

安全考虑与最佳实践

参数选择

• 素数大小：建议使用至少 2048 位的 $p$，或 256 位的椭圆曲线
• 生成元选择：$g$ 和 $h$ 应该是独立的生成元，不知道 $log_g h$
• 随机数：$r$ 必须使用密码学安全的随机数生成器

常见攻击

• 已知离散对数攻击：如果知道 $log_g h$，可以伪造承诺
• 防护：选择参数时确保不知道这个关系

• 小群攻击：如果群的阶有小因子
• 防护：使用素数阶群

• 随机数重用：如果 $r$ 重用，可以恢复消息
• 防护：每次承诺使用唯一的随机数

国密标准中的位置

目前国密标准中尚未正式规定 Pedersen 承诺方案，但其在以下场景有潜在应用价值：

• 国密盲签名系统
• 基于 SM2 的可验证秘密共享
• 国密电子投票系统

总结

Pedersen 承诺方案以其优雅的安全属性和实用的同态特性，成为现代密码学不可或缺的工具。它的核心价值在于：

• 信息论隐藏性：即使在理论上的无限计算能力下也无法破解
• 计算绑定性：基于离散对数问题的困难性
• 加法同态性：支持在承诺值上进行运算

在国密领域，虽然还没有官方标准的 Pedersen 承诺实现，但随着区块链技术的发展和隐私保护需求的增加，基于 SM2 曲线的 Pedersen 承诺方案有望在未来国密标准中得到应用。

参考

• Pedersen, V. G. (1991). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. *CRYPTO 1991*, LNCS 576, Springer.
• Damgård, I. (1991). Ideal System Independence for Oblivious Transfer. *Journal of Cryptology*, 14(1), 33-48.
• Benaloh, J. (1987). Dense Secret Sharing Scheme. *Workshop on the Theory and Application of Cryptographic Techniques*.
• NIST SP 800-57 Part 1 Rev. 5 - 密钥管理指南
• GM/T 0003-2012 - SM2 椭圆曲线公钥密码算法

相关实践

• 盲签名算法原理
• 零知识证明基础
• SM2 数字签名算法深度解析