有限域、循环群、离散对数与 Pedersen 承诺

2025-12-02 约 3972 字预计阅读 8 分钟

Scope: Pedersen commitment 的代数对象、分布论证与 binding reduction。

上一篇把 relation、instance、witness、soundness、zero knowledge、knowledge soundness 的接口钉住了。这一篇开始把这些抽象对象落到具体代数对象上，但只选最小够用的一组: 标量域 $\mathbb{Z}_q$、一个 prime-order 循环群 $G$、两个生成元 $g,h$，以及一个承诺式子

\[ C = g^m h^r. \]

这个式子看起来很短，但后面几篇会不断回到它。消息 $m$ 和随机数 $r$ 都是标量；群元素 $C$ 是公开 instance；opening 则是 witness $(m,r)$。如果把这些对象先写清楚，后面再看表示证明、Schnorr、Fiat-Shamir 时，很多结构就不再像“新协议”，而只是同一个关系换了一个验证方式。

Pedersen 承诺的两条核心推导分别对应 hiding 与 binding。对固定消息，随机 $r$ 使 $g^m h^r$ 在群上均匀分布，因此得到 perfect hiding；若有人给出两组不同的 opening，则从

\[ g^m h^r = g^{m'} h^{r'} \]

直接解出 $\log_g h$，因此 binding 只能是 computational 的。¹ ²

Scalar Field And Prime-Order Group

先固定最小代数环境。

取一个素数 $q$。记

\[ \mathbb{F}_q \cong \mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z}, \]

它既是一个有限域，也是后文的标量空间。然后取一个阶为 $q$ 的循环群 $G$，写作 multiplicative notation。群中的指数都按模 $q$ 运算，所以消息、随机数、挑战、响应这些标量对象都自然落在 $\mathbb{Z}_q$ 上。

有限域与循环群在这里组成一对绑定对象：

$\mathbb{Z}_q$ 提供标量运算
$G$ 提供指数编码后的公开对象

如果 $g \in G$ 是一个生成元，那么每个群元素都可写成 $g^a$，其中 $a \in \mathbb{Z}_q$。这就是后面所有基于离散对数的协议能够把“线性方程”搬到群里的根本原因。

Why Messages Live In $\mathbb{Z}_q$

Pedersen 承诺不是对任意大整数直接工作。它的自然消息空间是 $\mathbb{Z}_q$。原因不复杂:

群的指数本来就按模 $q$ 计算
即使输入写成整数，承诺只依赖其模 $q$ 的剩余类
binding 与 opening 的等式推导也都发生在 $\mathbb{Z}_q$

因此，写

\[ C = g^m h^r \]

时，默认应当读作

\[ m, r \in \mathbb{Z}_q,\quad C \in G. \]

因此，双开封导出的线性方程应在模 $q$ 的域中求解。

Two Generators, One Hidden Relation

再取另一个生成元 $h \in G$。由于 $G$ 是循环群，数学上必然存在某个

\[ \alpha \in \mathbb{Z}_q^{*} \]

使得

\[ h = g^\alpha. \]

循环群中的任意两个生成元都存在离散对数关系。这里的 generator independence 要求该关系对参与者未知：

setup 不应暴露这个关系，也就是 adversary 不应知道 $\alpha = \log_g h$。

参数生成必须保证没有参与者知道两个生成元之间的离散对数关系。随机取点只是实现这一条件的一种方式。

若有人知道 $\alpha$，绑定性会直接塌掉。这个结论后面会显式算出来。

Discrete Log Assumption

既然 $h=g^\alpha$，那么一个自然计算问题是:

给定 $(G, g, h)$，求出 $\alpha$。

这就是离散对数问题。对应的 hardness assumption 是，对所选群族与安全参数而言，没有高效算法能以非忽略概率恢复这个 $\alpha$。

Pedersen 的 binding 是计算性质：双开封算法可以直接转化为离散对数求解算法。

所以这篇一定要把两类安全性分开:

hiding 是信息论的
binding 是计算的

这两者不是对称性质。

Setup Requirement

Pedersen setup 常被写成“choose generators $g,h$”。更准确地说，应当是:

选定一个 prime-order 群 $G$
取两个生成元 $g,h \in G$
保证没有参与者知道 $\alpha = \log_g h$

如果 setup 方知道 $\alpha$，它就拿到了 equivocation trapdoor。因为

\[ C = g^m h^r = g^m g^{\alpha r} = g^{m+\alpha r}. \]

一旦知道 $\alpha$，就可以在保持 $C$ 不变的前提下，把 opening 从 $(m,r)$ 改写成任意别的消息。这个推导后面会正式写。

Pedersen Commitment As A Linear Encoding

现在给出构造。

给定公开参数 $(G, q, g, h)$，对消息 $m \in \mathbb{Z}_q$：

随机采样 $r \xleftarrow{\$} \mathbb{Z}_q$
输出承诺

\[ \mathrm{Com}(m; r) = g^m h^r \in G. \]

opening 就是二元组 $(m,r)$。验证则只需检查

\[ C \stackrel{?}= g^m h^r. \]

Instance And Witness View

如果用上一篇的关系语言来写，可以定义

\[ R_{\mathrm{Ped}}(C, (m,r)) = 1 \iff C = g^m h^r. \]

于是：

instance 是承诺值 $C$
witness 是 opening $(m,r)$

这正是标准的表示关系。下一篇将围绕该 relation 构造 proof of representation。

Commitment Equation Decomposition

下面把承诺式展开为线性分解。

若设

\[ h = g^\alpha, \]

则

\[ C = g^m h^r = g^m g^{\alpha r} = g^{m + \alpha r}. \]

承诺将标量对 $(m,r)$ 编码为同一个群元素中的线性组合

\[ m + \alpha r \pmod q. \]

如果 $\alpha$ 未知，这个线性关系仍然存在，但外部无法把 $C$ 反解成 $(m,r)$。这正是承诺同时具备 hiding 与 binding 的来源:

随机数 $r$ 提供遮蔽
未知的 $\alpha$ 阻止随意重写 opening

因此，Pedersen 在群中编码的是带随机掩码的线性关系。

Perfect Hiding: A Distribution Argument

先看 hiding。

Pedersen hiding 是一个严格的分布命题：

对任意固定消息 $m \in \mathbb{Z}_q$，当 $r \xleftarrow{\$} \mathbb{Z}_q$ 时，$\mathrm{Com}(m;r)$ 在群 $G$ 上均匀分布。

只要这个命题成立，perfect hiding 就立刻跟着成立，因为不同消息导出的承诺分布完全相同。

Step 1: Fix The Message

固定某个 $m$。考虑映射

\[ \phi_m : \mathbb{Z}_q \to G,\qquad r \mapsto g^m h^r. \]

因为 $h$ 是 $G$ 的生成元，而 $G$ 的阶是 $q$，映射

\[ r \mapsto h^r \]

是从 $\mathbb{Z}_q$ 到 $G$ 的双射。再左乘一个固定群元素 $g^m$，仍然是双射。因此 $\phi_m$ 是双射。

既然 $r$ 在 $\mathbb{Z}_q$ 上均匀，那么 $\phi_m(r)$ 就在 $G$ 上均匀。

Step 2: Compare Two Messages

设 $m_0, m_1 \in \mathbb{Z}_q$ 是任意两条消息。因为对每个固定消息，承诺分布都等于 $G$ 上的均匀分布，所以

\[ \mathrm{Com}(m_0; r) \equiv U_G \equiv \mathrm{Com}(m_1; r), \]

其中 $U_G$ 表示群上的均匀分布。

因此，哪怕攻击者算力无限，只看见 $C$ 也无法区分它来自 $m_0$ 还是 $m_1$。这就是 perfect hiding。

Why This Is Stronger Than Computational Hiding

这里没有使用离散对数假设，也没有限制攻击者算力。分布完全相同，所以 distinguisher 的优势恰好为 $0$。

perfect 在这里表示：

\[ \forall m_0, m_1,\quad \mathsf{Dist}(\mathrm{Com}(m_0; r), \mathrm{Com}(m_1; r)) = 0. \]

很多承诺方案只有 computational hiding，而 Pedersen 在这点上更强。

Computational Binding: Two Openings Break Discrete Log

现在看 binding。

同一个群元素 $C$ 对应许多可能的 $(m,r)$ 线性组合，因此 Pedersen 不具备 perfect binding。adversary 找到第二组 opening 的计算障碍是未知的 $\alpha = \log_g h$。

所以 binding 的正确表述是：

如果存在高效 adversary 能以非忽略概率输出同一承诺的两组不同 opening，那么就可用它来高效求解离散对数。

Step 1: Assume A Double Opening

假设 adversary 输出

\[ (C, m, r, m', r') \]

满足

\[ C = g^m h^r = g^{m'} h^{r'} \]

且

\[ m \ne m'. \]

由两式相等可得

\[ g^m h^r = g^{m'} h^{r'} \Longrightarrow g^{m-m'} = h^{r'-r}. \]

再代入 $h = g^\alpha$：

\[ g^{m-m'} = g^{\alpha(r'-r)}. \]

由于群阶是素数 $q$，指数在 $\mathbb{Z}_q$ 中比较，于是得到

\[ m - m' = \alpha (r' - r) \pmod q. \]

Step 2: Why $r' - r$ Must Be Invertible

若 $r' = r$，上式会推出 $m=m'$，这与双开封要求不同消息矛盾。因此

\[ r' - r \ne 0 \pmod q. \]

而在域 $\mathbb{Z}_q$ 里，每个非零元素都可逆，所以

\[ (r' - r)^{-1} \]

存在。于是可以直接解出

\[ \alpha = (m - m')(r' - r)^{-1} \pmod q. \]

也就是

\[ \alpha = \log_g h. \]

这正是 binding 规约的核心。

The Reduction View

把上面的等式链改写成规约语言就是：

规约者接收一个离散对数实例 $(G, q, g, h)$
它把这组参数直接交给双开封 adversary
若 adversary 返回同一承诺的两组不同 opening
规约者就按上式恢复 $\alpha = \log_g h$

因此，只要离散对数在该群上难解，高效双开封也应当难以发生。这就是 computational binding。

Key Observation. Pedersen binding reduction：从两个不同 opening 可计算出隐藏的离散对数关系。

If $\alpha$ Is Known, Binding Dies Immediately

前面已经说过 setup trapdoor 是危险点，这里把它正式算出来。

仍然写

\[ h = g^\alpha. \]

如果某人知道 $\alpha$，并且手里已经有一个合法 opening $(m,r)$，对应承诺

\[ C = g^m h^r = g^{m+\alpha r}, \]

那么它想把同一个 $C$ 改开为任意另一个消息 $m^{*}$，只需取

\[ r^{*} = r + (m - m^{*})\alpha^{-1} \pmod q. \]

验证一下：

\[ g^{m^{*}} h^{r^{*}} = g^{m^{*}} g^{\alpha r^{*}} = g^{m^{*} + \alpha r + m - m^{*}} = g^{m + \alpha r} = C. \]

知道 $\alpha$ 后，任意承诺都能被改开成指定消息。setup 因此必须公开参数，同时保证任何参与者都不知道生成元之间的离散对数关系。

一个阶为 11 的数值检查

取模 23 乘法群中阶为 11 的子群，令

\[ g=2,\qquad h=8=g^3. \]

这个参数只用于检查代数；$\alpha=3$ 已公开，因此不能提供实际 binding。

先看 hiding。固定 $m=4$，承诺指数为

\[ m+\alpha r=4+3r \pmod {11}. \]

当 $r$ 均匀遍历 $\mathbb{Z}_{11}$ 时，$4+3r$ 也均匀遍历 $\mathbb{Z}_{11}$，因为 3 在该域中可逆。故 $C=2^{4+3r}$ 均匀遍历整个子群。

再看双开封。取

\[ (m,r)=(4,2),\qquad (m',r')=(1,3). \]

两组 opening 都给出

\[ C=2^4 8^2=2^1 8^3=12 \pmod {23}. \]

由双开封恢复隐藏关系：

\[ \alpha=(m-m')(r'-r)^{-1}=3\cdot 1^{-1}=3 \pmod {11}. \]

这个小例子同时展示了两种量词：hiding 对 $\alpha$ 是否已知都是无条件的分布结论；binding 则要求 $\alpha$ 对 adversary 未知，并把双开封转换成 $\alpha$。

这也是为什么很多场景会通过 hash-to-group 或多方生成参数来避免单方持有 trapdoor。

Linear Relation View: Why This Matters For ZK

到这里，Pedersen 承诺已经不只是一个“藏消息”的工具了。更重要的是，它给了我们一个非常适合做零知识证明的 relation：

\[ C = g^m h^r. \]

这个 relation 有三个好处。

First, The Witness Structure Is Explicit

witness 是向量 $(m,r)$；“证明知道 opening”因此可写成“证明知道一个线性表示”。

Second, Verification Is Algebraic

验证条件就是一个显式群等式。Sigma 协议最喜欢这样的关系，因为：

可以围绕它构造 commitment-challenge-response
可以从两份 transcript 做 special soundness 提取
可以构造 honest-verifier simulator

Pedersen relation 可以直接充当后续协议的 statement layer。

Third, Additivity Comes For Free

虽然本文先只写单消息承诺，但它已经显露出线性结构：

\[ \mathrm{Com}(m_1; r_1)\mathrm{Com}(m_2; r_2) = g^{m_1+m_2} h^{r_1+r_2} = \mathrm{Com}(m_1+m_2; r_1+r_2). \]

群乘法对应标量加法。表示证明、范围证明和向量承诺都会复用这条线性结构。

这里先不展开多消息版本，只保留一个判断：Pedersen 的价值不只是 commitment，而是它把“线性关系 + 随机掩码 + 群验证”等式打包成了一个极小接口。

Summary

这一篇其实只固定了四件事。

第一，标量在 $\mathbb{Z}_q$ 上，群元素在 prime-order 循环群 $G$ 中，消息与随机数都应被视作模 $q$ 的对象。

第二，Pedersen 承诺

\[ C = g^m h^r \]

把 $(m,r)$ 编码成群里的线性组合。

第三，perfect hiding 来自一个严格的分布事实：对固定 $m$，映射

\[ r \mapsto g^m h^r \]

是到群 $G$ 的双射，因此承诺分布与消息无关。

第四，binding 只能是 computational 的。因为若存在两组不同 opening，就能从