多项式承诺：KZG-Toy模板网

这篇具有很好参考价值的文章主要介绍了多项式承诺：KZG。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考文献：

Merkle, R. ”Protocols for Public Key Cryptosystems.” Proc. 1980 Symp. on Security and Privacy, IEEE Computer Society (April 1980), 122-133.
Benaloh J, Mare M. One-way accumulators: A decentralized alternative to digital signatures[C]//Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1993: 274-285.
Kate A, Zaverucha G M, Goldberg I. Constant-size commitments to polynomials and their applications[C]//International conference on the theory and application of cryptology and information security. Springer, Berlin, Heidelberg, 2010: 177-194.

One-way accumulators（1993）

定义

我们说函数 $\times Y \to X$ 是准交换的（quasi-commutative），如果对于任意的 $\in X$ ，以及任意的 $y_1,y_2 \in Y$ ，有
$f(f(x,y_1),y_2) = f(f(x,y_2),y_1)$

单向累加器（One-way accumulators）是一种准交换的单向哈希函数（OWHF），即 $y_1,\cdots,y_m$ 的累积哈希（accumulated hash）
$h(h(\cdots h(x,y_1),\cdots),y_m)$

不会因为 $y_i$ 的顺序改变而改变。

实例化：

安全素数（safe prime）： $p = 2 p^{'} + 1$ ，其中 $p^{'}$ 是奇素数
刚性整数（rigid integer）： $n = p q$ ，其中素数 $p, q$ 是安全的，且 $∣ p ∣ = ∣ q ∣$
基于 RSA 假设的 Hash 函数： $e_n(x,y) = x^y \pmod n$

应用

使用 $e_n(x,y) = x^y \pmod n$ 作为单向累加器，其中的 $n$ 是 CRS，没人知道它的因子 $p, q$ ，可以利用 MPC 来生成。花费大代价生成后，它可以被任意重用。

时间戳（Time Stamping）：一群人需要对自己的实时文档打时间戳，并在一段时间后，让其他人相信这个时间戳的有效性。
- 假设某一轮里，有 $y_1,\cdots,y_m$ 个（被常规哈希过的）文件需要打时间戳。
- 首先对当前时间 $t$ 做共识，设置初始 $x=t^2 \pmod n$ 。
- 各参与者 $P_j$ 公布自己的 $y_j$ ，各自收集后计算 $\prod_j y_j$ 和 $y_j' = Y/y_j$ ，然后计算 $z_j=x^{y_j'}$ 和 $z=x^Y$
- 易知 $z=h(z_j,y_j)$ ，因此 $P_j$ 保留二元组 $z_j,y_j)$ 作为证据。
- 当向他人证明 $y_j$ 对应文档的时间戳时，只需同时提供这个二元组即可。
隶属证明（Membership Testing）：一群人组成一个匿名团体，想要向成员或非成员证明自己真的属于这个团体。
- 首先对团体的初值 $x$ （比如团体的描述）做共识。
- 各参与者 $P_j$ 选择自己的 $y_j$ （比如自己的假名），然后公布。
- 各自收集后计算 $\prod_j y_j$ 和 $y_j' = Y/y_j$ ，然后计算 $z_j=x^{y_j'}$ 和 $z=x^Y$
- 易知 $z=h(z_j,y_j)$ ，因此 $P_j$ 保留二元组 $z_j,y_j)$ 作为证据。
- 向成员证明时，向他展示这个二元组，验证 $h(z_i,y_i)=h(z_j,y_j)$ （因为 $z$ 可被成员所重构，因此不必存储）
- 向非成员证明时，他从公开资料中获取 $z, n$ ，然后向他展示这个二元组，验证 $z=h(z_j,y_j)$
- Merkle Tree（1980）也可以完成隶属证明，但它的复杂度是路径长度 $O(\log n)$ ，而单向累加器仅为 $O (1)$

KZG（2010）

多项式承诺

KZG 将 $\mathbb Z_p$ 上的 $O (t)$ 个数值 $m_1,\cdots,m_t$ ，打包进一个多项式 $\phi(x) \in \mathbb Z_p[x]$ 中， $\deg \phi = t$ ，仅需对多项式 $\phi(x)$ 做大小为 $O (1)$ 的承诺即可。

KZG 基于离散对数问题，以及它的一系列变体，

多项式承诺：KZG

多项式承诺协议（polynomial commitment scheme）抽象为算法六元组，

多项式承诺：KZG

我们说一个多项式承诺协议 $(S e t u p, C o m m i t, O p e n, V e r i f y P o l y, C r e a t e W i t n e s s, V e r i f y E v a l)$ 是安全的（secure），如果满足以下性质：

多项式承诺：KZG

KZG 给出了两种构造方案，第一种是计算隐藏的，第二种是无条件隐藏的。

Computationally hiding

对于一个多项式 $\phi(x)$ ，为了证明在点 $i$ 处的值为 $\phi(i)$ ，只需证明
$\mid (\phi(x)-\phi(i))$

也就是说，存在多项式 $\psi(x)$ ，满足
$\psi_i(x) = \frac{\phi(x)-\phi(i)}{x-i}$

基于 DL 假设、t-SDH 假设，构造的承诺方案 $PolyCommit_{DL}$ 如下：

多项式承诺：KZG

Unconditionally hiding

为了实现无条件隐藏的性质，添加一个随机多项式 $\hat \phi(x) \in _R \mathbb Z_p[x]$

利用 $PolyCommit_{DL}$ 的同态性质，有

多项式承诺的同态： $\phi=\phi_1+\phi_2 \iff C_{\phi} = C_{\phi_1} C_{\phi_2}$
函数值证据的同态： $\phi(i)=\phi_1(i)+\phi_2(i) \iff w_{\phi(i)} = w_{\phi_1(i)} w_{\phi_2(i)}$

基于 t-SDH 假设，构造的承诺方案 $PolyCommit_{Ped}$ 如下：

多项式承诺：KZG

Batch Opening

有时候，需要打开多个位置的函数值，即 $\subset \mathbb Z_p$ ，其中 $∣ B ∣ < t$

对于 $PolyCommit_{DL}$ 方案，计算一批证据
$w_B = g^{\psi_B(\alpha)}$

其中
$\psi_B(x) = \frac{\phi(x)-r(x)}{\prod_{i \in B}(x-i)}$

这里的 $r (x)$ 是多项式除法的余数。

批算法 $CreateWitnessBatch(PK,\phi(x),B)$ 输出 $B,r(x),w_B>$
批算法 $VerifyEvalBatch(PK,C,B,r(x),w_B)$ 验证
$\overset{?}{=} e(g^{\prod_{i \in B}(\alpha-i)}, w_B) \cdot e(g^{r(\alpha)}, g)$