2024-05-29  2024-05-29    7771 字  16 分钟
- 论文笔记

多项式承诺

1. 什么是承诺

密码学承诺方案是一个涉及两个参与方的的二段式交互协议，参与双方分别被称为承诺方和验证方。该协议共分为三个步骤：

  1. 第一阶段被称为承诺阶段，此阶段承诺方通过$C←Com(x)$计算声明x的承诺C并发送给验证方。
  2. 第二阶段被称为打开承诺阶段，此阶段承诺方发送 “承诺C所对应的声明x的证明$\pi$“给验证方，该证明也可以称为打开承诺。
  3. 第三阶段为打开承诺验证阶段，此阶段接受方验证证明$\pi$的合法性。如果$\pi$合法，则认为承诺C确实是声明x对应的承诺。

承诺方案需要满足的三个基本性质：

  • 正确性：按照上述三个过程生成的承诺和打开承诺一定能通过成员验证。
  • 绑定性(Binding)：对于任意PPT敌手，找到两个声明$x_1≠x_2$,使得$C_1=C_2$的概率可以忽略。即难以找到两个不同的声明，使得其对应的承诺相同。
  • 隐藏性(Hiding):对于任意PPT敌手，声明$x_1$和声明$x_2$的承诺$C_1,C_2$不可区分。即承诺C不泄露声明的额外信息。

2. 承诺有什么用

在生活中经常需要用到承诺，比如：

  1. Alice和Bob想要玩一个猜数字游戏，游戏规则如下： - Alice从集合A={0,1}中随机选择$a\in_R{x_0,x_1}$，然后Bob输出对a的猜测b，如果b=a，则Bob获胜，否则Alice获胜。 - 在这个游戏当中，如果没有任何限制，那么即使Bob猜出了正确的a，Alice也可以声称Bob猜错了，从而保证自己总是赢得游戏。如：Alice选择$a=x_1$，Bob在游戏中猜测$b=x_1$，此时本应Bob获得游戏胜利，但是Alice可以告诉Bob自己选择的$a=x_0$，从而赢得游戏。导致上述结果的原因是Alice可以随意更改a的值，我们可以使用承诺解决上述问题。 - 我们更改游戏规则为：Alice首先选择$a \in_R {x_0,x_1}$并计算承诺$C=Com(a)$并将其发送给Bob，Bob输出对a的猜测b。 - 在上述游戏中，假如Alice选择了$a=x_1$并计算了$C=Com(a)$给Bob，此时如果Alice在上述游戏中想通过修改$a=x_0$来获得游戏胜利的方式是不可行的。因为Bob可以计算$C’=Com(a)$，然后通过验证$C’=C$是否相等验证Alice是否修改了声明a。 - 由于承诺的隐藏性，Bob不能从C中获得任何声明a的信息，因此Bob得到C并不会增加游戏获胜的概率。 - 由于承诺的绑定性，Alice不能选择两个不同的$x_0,x_1$ 使得$C=Com(x_0)=Com(x_1)$，因此Alice不能作弊。

  2. 信息科学中也有类似的承诺技术存在。例如，某些网站在提供下载文件时，也会提供对应文件的单向哈希值。这里，单向哈希值便是一种对文件数据的承诺（承诺阶段）。用户将文件数据下载好之后（打开承诺），检测接收到的文件数据是否有丢失或变化，如果校验通过，相当于网站兑现了关于文件数据完整性的承诺（打开承诺验证）。

  3. Sigma协议(零知识证明中的使用) 承诺在非交互式零知识证明中发挥着关键性作用，可以保证没有秘密的敌手无法伪造合法的证明。比如在Schnoor协议中，Alice想要向Bob证明自己拥有一个公钥$PK=sk·G$对应的私钥$sk$而不暴露$sk$的其他信息就用到了承诺。(具体参见附录1)

  4. 秘密共享中的承诺 在一个(t,n)秘密共享中，一个dealer(秘密分发者)给n个participator(参与者)分发秘密s的share(秘密份额)$s_i$。传统的秘密共享中、dealer知晓完整的密钥s，有作恶的可能。例如对部分$P_i$发放错误的share。参与者$P_i$也可能提供非真实的share去扰乱正常的reconstruct(秘密重构)过程。使用多项式承诺则可以避免上述问题。（参见Feldman承诺）

  5. zk-SNARK中的承诺 听说在zk-SNARK中，多项式承诺扮演着重要角色，不过我没看过这个。。

3. 常见的承诺

关于承诺，有非常多种类，这里简单列举几个常见的承诺方式。

哈希承诺

  1. 承诺阶段 对于一个声明$x$，承诺者计算$C=H(x)$作为承诺发给验证者
  2. 承诺打开 承诺者将声明x发送给验证者
  3. 打开承诺验证 验证者计算$C’=H(x)$，然后判断等式$C’=C$是否成立，如果成立，则验证者认为承诺$C$对应的声明确实是$x$

基于加密算法的承诺

  1. 承诺阶段 对于一个声明$x$，承诺者计算$C=E_K(x)$作为承诺发给验证者
  2. 承诺打开 承诺者将声明x发送给验证者
  3. 打开承诺验证 验证者计算$C’=E_K(x)$，然后判断等式$C’=C$是否成立，如果成立，则验证者认为承诺$C$对应的声明确实是$x$

Pederson承诺

公共参数：选择乘法群$G=Z_q^*$,生成元为$g,h$,公开三元组$(g,h,q)$

  1. 承诺阶段 对于一个声明$x$，承诺者选择一个随机数$r\in_RZ_q$计算$C=g^xh^r\ mod\ q$作为承诺发给验证者
  2. 承诺打开 承诺者将声明$x$和随机数$r$发送给验证者
  3. 打开承诺验证 验证者计算$C’=g^xh^r\ mod\ q$，然后判断等式$C’=C$是否成立，如果成立，则验证者认为承诺$C$对应的声明确实是$x$

4. KZG多项式承诺

KZG承诺简介

首先明确的是：多项式承诺$C$的承诺对象是一个多项式$f(x)$。验证者如果对打开承诺的验证通过了，则说明承诺者确实知道声明$f(x)$。 KZG 多项式承诺（KZG Polynomial Commitment）也被称为卡特多项式承诺,由Kate，Zaverucha和Goldberg在2010年提出$^{[1]}$。KZG多项式承诺的承诺值是椭圆曲线上的一个点，且打开承诺只需要发送一个固定大小的椭圆曲线上的点，而不必将整个多项式发送给验证者。

KZG预备知识

为了学习KGZ承诺需要一些必备的预备知识。列举如下：

  1. 椭圆曲线相关知识
  2. 双线性映射相关知识
  3. 因式定理$^{[2]}$，代数基本定理
  4. 拉格朗日插值公式 参考视频: KZG的数学原理

KZG承诺的过程（单点承诺）

KZG多项式承诺分为以下几个阶段，这里首先对承诺的全过程进行综述，然后再解释为什么要这么做。

可信设置阶段： 生成一个随机数$\alpha$，然后计算$PK=(P,\alpha P,\alpha^2P,…,\alpha^nP)$作为公钥发布。随后将$\alpha$永久销毁。假设承诺者想要对多项式$f(x)=a_0+a_1x+a_2x^2+…+a_nx^n$进行承诺：

  1. 承诺阶段 假设$PK=(P,\alpha P,\alpha^2P,…,\alpha^nP)=(pk_0,pk_1,pk_2,…,pk_n)$，承诺者首先计算$^{(1)}$承诺$$C=f(\alpha)P=a_0pk_0+a_1pk_1+a_2pk_2+…+a_npk_n$$ 并将其发送给验证者。(容易看出，承诺$C$是椭圆曲线上的一个点)
  2. 打开承诺 承诺者计算$q(x)=\frac{f(x)-f(i)}{x-i}=b_0+b_1x+b_2x^2+…+b_nx^n$，然后计算 “$f(x)$在$i$点取值为$f(i)$“的证明$$\pi=q(\alpha)P=b_0pk_0+b_1pk_1+b_2pk_2+…+b_npk_n$$最后将打开承诺$(i,y=f(i),\pi)$发送给验证者。
  3. 打开承诺验证 验证者判断等式$$e(C,P)=e(\pi,pk_1-iP)e(P,P)^{f(i)}$$是否成立，如果成立，则接受承诺者的打开承诺$C$。也就是相信承诺者确实知道承诺$C$对应的多项式$f(x)$，且$f(x)$在$i$处的取值确实为$y=f(i)$ 。
  4. 说明 传统的打开承诺是直接将多项式$f(x)$的系数${a_0,…a_n}$发送给验证者，然后验证者重新计算$C’=f(\alpha)P=a_0pk_0+a_1pk_1+a_2pk_2+…+a_npk_n$并比较等式$C’=C$是否成立，如果成立则打开承诺验证成功。这种方式的缺点是打开承诺需要暴露多项式$f(x)$，并且打开承诺需要将多项式的所有系数发送给验证者，导致通信开销与多项式的次数成正比。

KZG多点承诺

上面的介绍说明了如何证明一个多项式在某点 $i$ 的取值为$f(i)$，它意味着你可以仅靠发送单个的群元素（可以是48字节大小，例如BLS12381)来证明任何次数的多项式在任意点的取值。下面我们讨论如何仅使用一个元素证明一个多项式在任意多个点处的取值。（可信设置阶段和上述单点承诺一样，不再赘述）

  1. 承诺阶段 假设$PK=(P,\alpha P,\alpha^2P,…,\alpha^nP)=(pk_0,pk_1,pk_2,…,pk_n)$，承诺者首先计算承诺$C=f(\alpha)P=a_0pk_0+a_1pk_1+a_2pk_2+…+a_npk_n$ 并将其发送给验证者。(容易看出，承诺$C$是椭圆曲线上的一个点)
  2. 打开承诺 假设承诺者想要证明自己知道多项式$f(x)$在横坐标集合${z_0,z_1,…,z_{k-1}}$处的函数值${f(z_0),f (z_1),…,f(z_{k-1})}$，他首先使用拉格朗日插值法计算过k个点 ${(z_i,f(z_i)}_{i=0}^{k-1})$ 的多项式:

$$I(x)=\sum_{i=0}^{k-1}f(z_i)\prod_{j=0,j\neq i}^{k-1} \frac{x-z_j}{z_i-z_j}$$

承诺者计算零多项式 $Z(x)=(x-z_0)···(x-z_{k-1})$ 并据此计算

$$q(x)=\frac{f(x)-I(x)}{Z(x)}=c_0+c_1x+c_2x^2+…+c_nx^n$$ 然后承诺者计算 “$f(x)$在k个点 $(z_i){i=0}^{k-1}$ 处的取值分别为 ${(f(z_0)){i=0}^{k-1}}$” 的证明 $$\pi=q(\alpha)P=c_0pk_0+c_1pk_1+c_2pk_2+…+c_npk_n$$ 并将打开承诺 $((z_i,f(z_i))_{i=0}^{k-1},\pi)$ 发送给验证者。

  1. 打开承诺验证 验证者首先计算插值多项式$I(x)$和零多项式$Z(x)$，然后使用公钥$PK$计算出$Z(\alpha),I(\alpha)$，并判断等式 $$e(C,P)=e(\pi,Z(\alpha)P)e(P,P)^{I(\alpha)}$$ 是否成立，如果成立，则接受承诺者的打开承诺$C$。也就是相信承诺者确实知道承诺 $C$ 对应的多项式 $f(x)$，且 $f(x)$ 在k个点 ${(z_i){i=0}^{k-1}}$ 处的取值确实分> 别为 ${(f(z_0)){i=0}^{k-1}}$ 。

KZG承诺的解释

KZG承诺的打开承诺实际上是"承诺者想要向验证者证明自己知道承诺$C$对应的多项式$f(x)$"，为了不暴露$f(x)$本身，承诺者证明 “自己知道$f(x)$在横坐标$i$处的取值$y=f(i)$"。

  1. 令$g(x)=f(x)-f(i)$，则上述证明等价于证明$g(x)$存在零点$i$ ；
  2. 由因式定理知，$g(x)$可分解为$g(x)=(x-i)q(x)$，即$q(x)=\frac{f(x)-f(i)}{x-i}$,显然，只有承诺者知道$f(x)$，故只有他能计算出$q(x)$.
  3. 承诺者计算横坐标$i$处的打开承诺$\pi=q(\alpha)$P，并将其发送给验证者。
  4. 根据等式$g(x)=(x-i)q(x)$可知，$f(\alpha)=(\alpha-i)q(\alpha)+f(i)$，故验证者可以检查等式$e(f(\alpha)P,P)=e(((\alpha-i)q(\alpha)+f(i))P,P)$，也就是检查等式$e(C,P)=e(\pi,(pk_1-iP)e(P,P))^{f(i)}$是否成立。如果成立，则打开承诺验证通过。

在KZG多点承诺中，承诺方想要向验证者证明自己知道 “$f(x)$ 在k个点 $(z_i){i=0}^{k-1}$ 处的取值确实分别为${(f(z_0)){i=0}^{k-1}}$"，这里的证明思路实际上上面的单点证明相同。

  1. 首先使用拉格朗日插值公式计算出过k个点 ${(z_i,f(z_i)){i=0}^{k-1}}$ 的插值多项式 $I(x)$（这意味着 $I(z_i)=f(z_i)$）。令 $g(x)=f(x)-I(x)$，则上述证明等价于证明 $g(x)$ 存在零点 ${(z_i){i=0}^{k-1}}$
  2. 由因式定理知，$g(x)$可分解为$$g(x)=q(x)\prod_{i=0}^{k-1}(x-i)$$假设$Z(x)=\prod_{i=0}^{k-1}(x-i)$，则有 $q(x)=\frac{f(x)-I(x)}{Z(x)}$,显然，只有承诺者知道 $f(x)$，故只有他能计算出 $q(x)$.
  3. 承诺者计算横坐标 $i$ 处的打开承诺 $\pi=q(\alpha)P$，并将其发送给验证者。
  4. 后面的验证同理。

注释解释

（1）这里使用承诺$C=f(\alpha)P$作为多项式$f(x)$的承诺是安全的。 1. 假设敌手可以寻找一个多项式$f’(x)\neq f(x)$使得$f’(\alpha)P=C$， 2. 那么$(f’(\alpha)-f(\alpha))P=0$，即函数$r(x)=f’(x)-f(x)$存在零点$\alpha$ 。 3. 由于敌手不知道$\alpha$的值，因此它只能令多项式$r(x)$有尽可能多的零点，从而使得$r(x)$有更大的几率存在零点$\alpha$ 。 4. 由代数基本定理可知，在实数域上的非零n次多项式至多只有n个零点。而$f’(x)\neq f(x)$，故$r(x)\neq 0$。所以$r(x)$最多有n个零点。假设椭圆曲线群$G$的阶为$p=2^{128}$，那么攻击者求出满足条件的$f’(x)$的概率为$n/p=n/2^{128}$。这是一个可以忽略的概率，在现实中，可以认为攻击者不可能找到这个$f’(x)$。 （2）

矢量承诺

尽管卡特承诺被设计成多项式承诺，但它作为矢量承诺来使用也大有用处。回忆一下，一个矢量承诺是针对矢量$a_0,…,a_{n-1}$的承诺，并且允许你证明任意位置i对应$a_i$ 。我们可以使用卡特承诺的方案来重现这一场景：使p(X)为对所有的计算$p(i)=a_i$的一个多项式，我们知道这样一个多项式存在，并且可以通过拉格朗日插值来计算它：$$p(x)=\sum_{i=0}^{k-1}a_i\prod_{j=0,j\neq i}^{k-1} \frac{x-j}{i-j}$$使用这个多项式，我们可以就可以利用一个单一群元素来证明这个矢量中任意数量的元素！注意到比起默克尔树(在证明大小方面)这个方案更加高效：仅证明一个元素，默克尔证明就需要花费 log n 大小的哈希！

Feldman承诺

  1. 承诺阶段: 对于一个多项式$f(x)=a_0​+a_1​x+a_2​x^2+…+a_{k−1​}x^{k−1}$，承诺者计算承诺$C=(c_0,c_1,…,c_{k-1})=(g^{a_0}​,g^{a_1}​,…,g^{a_{k−1}})$ 并将其发送给验证者。

  2. 打开承诺: 假设承诺者想要证明自己知道多项式$f(x)$在横坐标集合$\mathbb{Z}={z_0,z_1,…,z_{k-1}}$处的函数值$\mathbb{f(z)}={f(z_0),f(z_1),…,f(z_{k-1})}$，他可以直接将$\mathbb{f(z)}$发送给验证者。

  3. 打开承诺验证: 对于集合$\mathbb{Z}$任意一点$z_i$，验证者验证$$g^{f(z_i)}​=∏{j=0}^{k−1}​(c_j​)^{{z_i}^j} \ mod \ p$$ 是否成立，如果成立，则接受承诺者的打开承诺$C$。也就是相信承诺者确实知道承诺 $C$ 对应的多项式 $f(x)$，且 $f(x)$ 在k个点 ${(z_i){i=0}^{k-1}}$ 处的取值确实分别为 ${(f(z_i))_{i=0}^{k-1}}$ 。

基于Feldman承诺的VSS

在普通的Shamir(t,n)秘密共享之中，存在以下问题：

  • 密钥分发者知晓完整的密钥，有作恶的可能，例如对部分秘密持有者发放错误的分片数据。
  • 密钥分片的持有者可能提供非真实的分片数据

当考虑存在不诚实参与方时，对于一个秘密需要有相应的算法来验证其确实是秘密的有效份额，否则不存在秘密可言。本文将介绍基于Shamir密钥分享的改进机制：可验证的秘密共享（verifiable secret sharing, VSS）。关于VSS的方案有很多，这里直接介绍比较实用的Feldman VSS方案。【注：VSS概念由Benny Chor, Shafi Goldwasser, Silvio Micali等人在1985年首次提出 】

Feldman方案： 实际工程中使用的密钥分享都是有限域上的循环群的运算，采用公共g作为生成元。为了使得分发的秘密碎片的数据可验证，秘密分发者除了给出秘密的分片数据外，还要提供对应的系数承诺(c0​,c1​,…)。

符号约定： 设 p 是一个大素数，q 为 p -1 的一个大素数因子，g 属于 $𝑍_𝑝^∗$且为 q 阶元素,(p, q, g) 是公幵可知的，n 是参与者的数目，s 为要共享的密钥，k 是门限值。

秘密分发阶段：

  • 选定多项式：$a(x)=a_0​+a_1​x+a_2​x^2+…+a_{k−1​}x^{k−1}$，其中$a_0$代表秘密，

  • 计算承诺（commitment）：$c_0​=g^{a_0}​,c_1​=g^{a_1}​,…,c_{k−1}​=g^{a_{k−1}}$​ 以上运算是在mod p基础上的。

  • 将承诺 $c_i$ ​和 $s_i$ 一同发送给参与者 $P_i$​.【具体工程实现中，由于承诺对所以参与者都是一样的，也可先广播承诺给所有参与者，然后单独秘密发送分片，以减少消息传输量】。

  • 当第i个参与者收到数据碎片 $s_i$ 时，作如下验证： $$g^{s_i}​=∏_{j=0}^{k−1}​(c_j​)^{i^j} \ mod \ p \ \ (其中i=1,2,…,n)$$ 容易验证等式成立。由于承诺绑定了系数，如果分发者给出承诺不是用多项式方程真实系数，会导致验证失败。

5. 参考文献：

[1]. Constant-size commitments to polynomials and their applications

[2]. 因式定理：设f(x)为一多项式，则x-a为f(x)的因式"等价于f(a)=0。 [3]. 代数基本定理：代数基本定理说明，任何复系数一元n次多项式方程在复数域上至少有一根。由此推出，n次复系数多项式方程在复数域内有且只有n个根（重根按重数计算）。

附录1

Schnoor协议的具体内容如下：

对上图进行解释如下：

  - Alice：随机地选择一个标量r，然后计算出R=rG（椭圆曲线上的一点），将R发送给Bob；（R实际上是一个对r的承诺）
  - Bob：回应一个随机标量 c ；（挑战）
  - Alice：通过计算$z=r+c·sk$，将标量 z 回应给Bob；（针对挑战c的响应）
  - Bob：然后验证$z·G=c·PK+R$ 。

首先需要知道的是：确定性算法很容易受到各种攻击，如重放攻击，穷举攻击等。因此在上述Schnoor协议中，加入了随机数r，保证该协议是一个一个概率性算法。

承诺的作用： 假设Alice不发送r的承诺R给Bob，协议的其他部分不变，那么将导致不知道私钥$sk$的人也能完成协议的证明。

  • 比如Bob直接将挑战c发送给Alice，Alice可以计算$R = r * G - cPK \wedge z = r$，随后将$(z,R)$发送给Bob，这样Bob的验证等式为：$z * G = r * G = R + cPK$这是永远成立的，这导致不知道私钥的人也能证明自己拥有私钥。
  • 在引入承诺之后，由于Alice不能修改r的值，因此收到Bob的c之后，必须使用私钥sk才能计算出合法的z，从而保证了协议的不可为造性。
← SPSEQ匿名凭证
Linux →