多项式承诺 | Codeboy's Blog

形式陈述

多项式承诺允许发送者先发布一个简短承诺 $C$ ，以后针对指定点 $z$ 给出数值 $y$ 和证明 $\pi$ ，让接收者检验“所承诺多项式在 $z$ 处取值为 $y$ ”。这里给出基本的、确定性的 KZG 构造：诚实输入是有限域 $\mathbb F_p$ 上次数至多 $d$ 的多项式，承诺与单点证明各为一个群元素。其安全结论是逐点求值绑定：高效攻击者不能把同一个承诺在同一个点打开为两个不同的值。

参数与公开幂表

对每个安全参数 $\lambda$ ，高效参数生成算法给出素数阶均为 $p$ 的循环群 $G,G_T$ 、 $G$ 的生成元 $g$ ，以及可高效计算的对称双线性配对

e:G\times G\longrightarrow G_T,\qquad e(g^a,g^b)=e(g,g)^{ab},\qquad e(g,g)\ne1.

群描述、编码、群运算和成员资格检验均公开；非退化性保证 $E=e(g,g)$ 生成 $G_T$ 。次数上限 $d=d(\lambda)\ge1$ 为可高效确定的多项式有界整数，所有指数和多项式系数都在 $\mathbb F_p$ 中运算。以下安全实验使用经典 uniform 概率多项式时间对手，概率包含参数生成、设置和对手的随机性。这里固定的是两个输入来自同一群的对称配对；非对称配对版本需要另行指定两个源群及相应假设。

设置算法均匀采样 $\tau\leftarrow\mathbb F_p^\times$ ，公布结构化参考串

\mathsf{SRS}=(g,g^\tau,g^{\tau^2},\ldots,g^{\tau^d}).

公开参数还包含群与配对的完整描述。设置后秘密标量 $\tau$ 不提供给攻击者；安全实验只交出公开幂表。表中有 $d+1$ 个源群元素，允许任何人计算次数至多 $d$ 的多项式在 $\tau$ 处的群编码，而无需知道 $\tau$ 。

承诺、打开与验证

给定 $f(X)=\sum_{i=0}^d a_iX^i$ ，承诺算法计算

C=\operatorname{Commit}(\mathsf{SRS},f) =\prod_{i=0}^d\left(g^{\tau^i}\right)^{a_i} =g^{f(\tau)}.

要打开点 $z\in\mathbb F_p$ ，发送者先求 $y=f(z)$ ，再在多项式环中做精确除法：

q_z(X)=\frac{f(X)-y}{X-z},\qquad f(X)-y=(X-z)q_z(X).

因为 $f(z)-y=0$ ，余式确为零，商多项式次数至多 $d-1$ 。若商为零，则取 $q_z=0$ 。发送者用同一公开幂表计算

\pi=\operatorname{Open}(\mathsf{SRS},f,z)=g^{q_z(\tau)},

并发送 $(y,\pi)$ 。验证者检查 $C,\pi\in G$ 与 $z,y\in\mathbb F_p$ 的合法编码及成员资格，然后接受当且仅当

\boxed{\quad e(C/g^y,g)=e(\pi,g^\tau/g^z).\quad}

式中 $A/B$ 表示群元素 $A$ 乘以 $B$ 的群逆元。验证者从公开的 $g^\tau$ 和自己算出的 $g^z$ 得到右侧第二个输入，不需要恢复任何离散对数。

正确性直接来自精确除法恒等式：

\begin{aligned} e(\pi,g^\tau/g^z) &=E^{q_z(\tau)(\tau-z)}\\ &=E^{f(\tau)-f(z)}\\ &=e(C/g^y,g). \end{aligned}

所以每个合法 $f,z$ 都被接受，包括 $z=\tau$ 。诚实证明是先求出多项式 $q_z$ 再将它编码，并没有计算标量 $1/(\tau-z)$ ；因此 $z=\tau$ 时不会出现除以零。

直觉

若直接发送 $f$ 的全部系数，接收者当然可以计算 $f(z)$ ，但通信量随次数增加。KZG 把系数通过公开幂表合成为 $g^{f(\tau)}$ ：接收者手里只有一个群元素，发送者以后每次也只需补充一个证明群元素。这里压缩的是承诺和证明的通信长度；公开幂表仍随 $d$ 增长。

证明的核心是因式定理。声称 $f(z)=y$ ，等价于说 $f(X)-y$ 含因子 $X-z$ 。因此发送者可以交出商多项式的编码 $g^{q_z(\tau)}$ ，让配对在指数里检查乘法关系。左侧编码“从承诺中减去 $y$ ”，右侧编码“商乘上 $\tau-z$ ”，两侧应当相等。

配对提供的能力恰好是检查两个指数的乘积。给出 $g^a,g^b$ 后，可以在目标群得到 $E^{ab}$ ，却不因此得到源群中的 $g^{ab}$ 。这也解释了为何不能把本构造的安全性直接写成源群 DDH 假设：同一个对称配对已经能高效检验 DDH 三元组。KZG 的逐点绑定需要下文明确陈述的 $d$ -SDH 假设。

“承诺”一词在这里突出先固定、后证明取值的接口。普通承诺方案还要求隐藏消息，而本页基本构造是确定性的。理解它时，应先分清可验证求值与消息隐藏，再判断外围协议还需要哪一种性质。

例子与边界

用两个不同的模数走完一次协议

取标量域 $\mathbb F_{11}$ 。让 $G,G_T$ 分别是模 $23$ 乘法群中 $\langle2\rangle$ 的一份副本，两者阶均为 $11$ ，并定义

e(2^a,2^b)=2^{ab}\pmod{23}.

指数按模 $11$ 计算，群元素按模 $23$ 计算。这个微型群可以枚举全部离散对数，因而只演示协议算术，不提供密码安全性。

设 $d=2$ 、 $\tau=3$ ，则

\mathsf{SRS}=(2,2^3,2^9)=(2,8,6)\pmod{23}.

取 $f(X)=2X^2+3X+4\in\mathbb F_{11}[X]$ 。由于 $f(3)=31\equiv9\pmod{11}$ ，有 $C=2^9=6\pmod{23}$ 。诚实发送者实际使用公开幂表计算同一个值：

C=2^4\cdot8^3\cdot6^2\equiv6\pmod{23}.

现在打开 $z=5$ 。先算 $y=f(5)=69\equiv3\pmod{11}$ ，再求商：

f(X)-3=2X^2+3X+1=(X-5)(2X+2) \quad\text{于 }\mathbb F_{11}[X].

所以 $q_5(X)=2X+2$ ， $q_5(3)=8$ ，证明为

\pi=2^8\equiv3\pmod{23}.

验证者得到 $g^\tau/g^z=2^{3-5}=2^9=6$ 。另外 $g^y=2^3=8$ ，而 $8^{-1}=3\pmod{23}$ ，所以 $C/g^y=6\cdot3=18=2^6$ 。两个配对值分别为

\begin{aligned} e(18,2)&=e(2^6,2)=2^6=18,\\ e(3,6)&=e(2^8,2^9)=2^{72}=2^6=18 \qquad(\bmod23). \end{aligned}

这里 $72\equiv6\pmod{11}$ ，两侧一致，打开通过。整个过程中没有把模 $23$ 的群逆元和模 $11$ 的标量逆元混为一谈。

设置秘密泄漏后，具体怎样改口

沿用上例的 $C=6,z=5$ ，若攻击者知道 $\tau=3$ ，便可把声称的值由 $y=3$ 改成 $y'=4$ 。在标量域中， $\tau-z=9$ ，且 $9^{-1}=5\pmod{11}$ 。在群中， $C/g^4=9$ ，于是构造

\pi'=\left(C/g^4\right)^{1/(\tau-z)} =9^5\equiv8\pmod{23}.

新的验证等式仍成立：

e(9,2)=9, \qquad e(8,6)=e(2^3,2^9)=2^{27}=2^5=9\pmod{23}.

同一个 $C$ 在同一个 $z$ 上，现在既能打开为 $3$ ，又能打开为 $4$ 。一般而言，掌握 $\tau$ 后，对任意 $C\in G$ 、任意 $z\ne\tau$ 和任意声称值 $y$ ，公式

\pi=(C/g^y)^{(\tau-z)^{-1}}

都能生成通过验证的证明。这正是设置秘密不能泄漏的原因。例外点 $z=\tau$ 的验证式退化为 $e(C/g^y,g)=1$ ，由非退化性要求 $C=g^y$ ；此时证明 $\pi$ 不影响验收结果，并不能用上述求逆公式任意改值。

基本版本为什么不隐藏多项式

取两个候选常数多项式 $f_0(X)=0$ 与 $f_1(X)=1$ ，它们的承诺分别恒为单位元 $1$ 与生成元 $g$ ，公开比较即可完全区分。因此基本 KZG 不满足普通承诺方案的选择消息隐藏性。对其他候选多项式，也可公开计算其确定性承诺再比较；这些承诺不必总是不同，常数 $0,1$ 已足以给出隐藏实验的反例。原论文对随机多项式恢复困难所用的隐藏定义，与这里的选择消息不可区分实验不同；需要隐藏性的应用须另外采用带随机化的构造。

推论与应用

从两种合法打开提取一个 SDH 解

先准确固定困难问题。对上述参数族和同样分布的 $\tau$ ， $d$ -SDH 假设断言：给定群、配对及完整公开幂表

(G,G_T,p,e,g,g^\tau,\ldots,g^{\tau^d}),

没有经典 PPT 算法能够以非可忽略概率输出 $(c,W)$ ，满足

c\in\mathbb F_p,\qquad \tau+c\ne0,\qquad W=g^{1/(\tau+c)}.

假设中的攻击者已经拥有配对和所有公开幂；它不是普通 CDH 或 DDH 的另一个名称。这里“非可忽略”使用计算安全中随 $\lambda$ 增长的定义，次数上限为多项式有界，使挑战长度和协议运行时间都处于相应模型内。

逐点绑定实验把诚实生成的公开参数交给攻击者，允许它自适应地选择并输出

(C,z,y,\pi,y',\pi'),\qquad y\ne y'.

攻击者在两个打开都通过验证时获胜； $C$ 可以是任意合法群元素，不要求它事先调用诚实承诺算法。下面把每一次获胜直接变成一个 $d$ -SDH 解。

归约拿到 SDH 挑战后，把原样的幂表和群描述交给攻击者。如果攻击者给出两种通过验证的不同取值，令

\Delta=y'-y\ne0,\qquad R=\pi/\pi'.

将第一条验证等式除以第二条，左侧的 $C$ 消去，得到

e(R,g^{\tau-z})=E^\Delta.

若 $z=\tau$ ，左侧等于 $1$ ，右侧却因 $E$ 阶为 $p$ 且 $\Delta\ne0$ 而不等于 $1$ 。所以获胜输出必有 $z\ne\tau$ ；归约无需知道 $\tau$ ，也无需另行检测这一条件。

归约只计算普通有限域逆元 $\Delta^{-1}$ ，并令

W=R^{\Delta^{-1}}.

双线性随即给出

e(W^{\tau-z},g) =e(W,g^{\tau-z}) =E.

映射 $A\mapsto e(A,g)$ 是单射：若 $A=g^a$ 映到 $1$ ，则 $E^a=1$ ，故 $a=0$ 于 $\mathbb F_p$ ，从而 $A=1$ 。因此上式推出

W^{\tau-z}=g,\qquad W=g^{1/(\tau-z)}.

归约返回 $(-z,W)$ 就完成 SDH 挑战。这里把群元素写成 $g^a$ 只是证明单射性的数学论证，算法不计算这个 $a$ ，也不调用离散对数 oracle。每次绑定攻击成功都会得到合法 SDH 解，成功概率没有损失；除运行攻击者和核验输出外，归约只增加常数次群运算、指数运算及一次标量求逆。由 $d$ -SDH 困难性，逐点绑定攻击的成功概率可忽略。

简短证明带来了什么

对于诚实系数输入，直接承诺需要合并 $d+1$ 项群幂；构造一次打开需要求值、精确除法和商的群编码，工作量随次数增长。验证式只包含固定数目的群运算和两次配对，与 $d$ 无关。这里的“常数大小”指固定安全参数下的群元素个数，群编码的比特长度仍随安全参数变化。

借助多项式插值，可以把 $n\le p$ 个数据 $v_i$ 放在预定的互异节点 $x_i$ 上，得到次数小于 $n$ 的 $f$ ，然后用 KZG 承诺这份编码。若 $d\ge n-1$ ，打开 $(x_i,v_i)$ 就成为对第 $i$ 个数据的短证明。插值提供数据到多项式的映射，配对提供验证接口，逐点绑定阻止同一位置被高效地打开为两个值。

本页证明的量词只涉及一个承诺、一个点与两个不同值。它没有构造从任意恶意承诺中提取系数的算法，也没有证明恶意方在多个不同点提交的全部取值来自同一个次数至多 $d$ 的多项式。公开幂表的长度限制了诚实算法可直接处理的次数；要把任意攻击者的行为解释为“已经掌握一个有界次数多项式”，还需要单独陈述并证明提取性等更强性质。因而将本构造接入证明系统时，应把外围协议需要的性质与这里已经证明的逐点绑定逐一对应。

参考资料

Aniket Kate, Gregory M. Zaverucha and Ian Goldberg, Polynomial Commitments, extended report, 2010-12-01：§2 Definition 2.3 的 $d$ -SDH；§3.1 的求值绑定实验；§3.2 的构造与 Theorem 3.2；Appendix C.1 的绑定性归约。本文使用基本确定性构造，并将其恢复型隐藏定义与选择消息隐藏区分。
Justin Thaler, Proofs, Arguments, and Zero-Knowledge, manuscript dated 2023-07-18，§15.2，印刷页 233–238：配对与可信设置下的 KZG，以及求值绑定和更强提取性质的区分。

形式陈述 ​

参数与公开幂表 ​

承诺、打开与验证 ​

用两个不同的模数走完一次协议 ​

设置秘密泄漏后，具体怎样改口 ​

基本版本为什么不隐藏多项式 ​

从两种合法打开提取一个 SDH 解 ​

简短证明带来了什么 ​

反向链接