一个对SDH问题解的ZKPoK协议

Strong Diffie-Hellman (SDH) 问题定义如下：

给定

$(q+2)$长的元组

$(g_1,g_2,g_2^{\gamma },g_2^{\left({\gamma }^2\right)},\dots ,g_2^{\left({\gamma }^q\right)})$ 作为输入，输出

$(g_1^{1/(\gamma +x)},x)$ ，其中

$x\in {\mathbb{Z}}_p^{\ast }$。

SDH假设就是，不存在多项式时间算法可以以不可忽略概率解决SDH问题。

Schnorr协议，是一个证明「知道离散对数」的ZKPoK。以下ZKPoK协议是对Schnorr协议的扩展，可以以零知识的方式证明「知道SDH问题的解」。（至于我为什么要介绍这个协议，以后就慢慢知道了。

）

秘密值：

$\gamma$
公开值：

$g_1,u,v,h\in G_1,g_2,w\in G_2$, 其中

$w=g_2^{\gamma }$

要证明的witness是SDH问题的解：

$(A,x)$，其中

$A\in G_1$ ，

$x\in {\mathbb{Z}}_p$，满足关系：

$$A^{\gamma +x}=g_1$$
即

$e(A,w{g}_2^x)=e(g_1,g_2)$

协议

证明者选择随机数

$\alpha ,\beta \stackrel{\mathrm{R}}{\leftarrow }{\mathbb{Z}}_p$，计算：

$$\begin{gathered} T_1\leftarrow u^{\alpha }{T}_2\leftarrow v^{\beta }{T}_3\leftarrow A{h}^{\alpha +\beta } \\ {\delta }_1\leftarrow x\alpha {\delta }_2\leftarrow x\beta \end{gathered}$$

接下来证明者和验证者执行ZKPoK协议，证明拥有满足如下五个关系的知识

$(\alpha ,\beta ,x,{\delta }_1,{\delta }_2)$：

$$\begin{array}{c}{u}^{\alpha }=T_1\\ v^{\beta }=T_2\\ e{(T_3,g_2)}^x\cdot e(h,w{)}^{-\alpha -\beta }\cdot e{(h,g_2)}^{-{\delta }_1-{\delta }_2}=e(g_1,g_2)/e(T_3,w)\\ T_1^x{u}^{-{\delta }_1}=1\\ T_2^x{v}^{-{\delta }_2}=1\end{array}$$
注意第三个等式是由

$e(A,w{g}_2^x)=e(g_1,g_2)$变形而来。

具体ZKPoK协议如下:

1. Prover计算并发送
   $R_1\dots R_5$：
   
   $$\begin{array}{ll}{R}_1\leftarrow u^{r_{\alpha }}& R_2\leftarrow v^{r_{\beta }}\\ R_3\leftarrow e{(T_3,g_2)}^{r_x}\cdot e(h,w{)}^{-r_{\alpha }-r_{\beta }}\cdot e{(h,g_2)}^{-r_{{\delta }_1}-r_{{\delta }_2}}\\ R_4\leftarrow T_1^{r_x}\cdot u^{-r_{{\delta }_1}}& R_5\leftarrow T_2^{r_x}\cdot v^{-r_{{\delta }_2}}\end{array}$$
2. Verifier采样挑战值
   $c$并发送给Prover。
3. Prover计算：
   
   $$s_{\alpha }\leftarrow r_{\alpha }+c\alpha s_{\beta }\leftarrow r_{\beta }+c\beta s_x\leftarrow r_x+cx{s}_{{\delta }_1}\leftarrow r_{{\delta }_1}+c{\delta }_1{s}_{{\delta }_2}\leftarrow r_{{\delta }_2}+c{\delta }_2$$
4. Verifier验证：
   
   $$\begin{array}{rl}{u}^{s_{\alpha }}& \stackrel{?}{=}{T}_1^c\cdot R_1(1)\\ v^{s_{\beta }}& \stackrel{?}{=}{T}_2^c\cdot R_2(2)\\ e{(T_3,g_2)}^{s_x}\cdot e(h,w{)}^{-s_{\alpha }-s_{\beta }}\cdot e{(h,g_2)}^{-s_{{\delta }_1}-s_{{\delta }_2}}& \stackrel{?}{=}{\left(e(g_1,g_2)/e(T_3,w)\right)}^c\cdot R_3(3)\\ T_1^{s_x}\cdot u^{-s_{{\delta }_1}}& \stackrel{?}{=}{R}_4(4)\\ T_2^{s_x}\cdot v^{-s_{{\delta }_2}}& \stackrel{?}{=}{R}_5(5).\end{array}$$

证明

完备性

对一个拥有SDH对

$(A,x)$的诚实证明者：

$$u^{s_{\alpha }}=u^{r_{\alpha }+c\alpha }={\left(u^{\alpha }\right)}^c\cdot u^{r_{\alpha }}=T_1^c\cdot R_1,$$
所以前两个验证方程成立。

$$T_1^{S_x}{u}^{-s_{{\delta }_1}}={\left(u^{\alpha }\right)}^{r_x+cx}{u}^{-r_{{\delta }_1}-cx\alpha }={\left(u^{\alpha }\right)}^{r_x}{u}^{-r_{{\delta }_1}}=T_1^{r_x}{u}^{-r_{{\delta }_1}}=R_4,$$
所以最后两个验证方程成立。

$$\begin{array}{rl}& e{(T_3,g_2)}^{s_x}\cdot e(h,w{)}^{-s_{\alpha }-s_{\beta }}\cdot e{(h,g_2)}^{-s_{{\delta }_1}-s_{{\delta }_2}}\\ & =e{(T_3,g_2)}^{r_x+cx}\cdot e(h,w{)}^{-r_{\alpha }-r_{\beta }-c\alpha -c\beta }\cdot e{(h,g_2)}^{-r_{{\delta }_1}-r_{{\delta }_2}-cx\alpha -cx\beta }\\ & =e{(T_3,g_2^x)}^c\cdot e{(h^{-\alpha -\beta },w{g}_2^x)}^c\cdot (e{(T_3,g_2)}^{r_x}\cdot e(h,w{)}^{-r_{\alpha }-r_{\beta }}\cdot e{(h,g_2)}^{-r_{{\delta }_1}-r_{{\delta }_2}})\\ & =e{(T_3{h}^{-\alpha -\beta },w{g}_2^x)}^c\cdot e{(T_3,w)}^{-c}\cdot \left(R_3\right)\\ & ={\left(e(A,w{g}_2^x)/e(T_3,w)\right)}^c\cdot R_3\\ & ={\left(e(g_1,g_2)/e(T_3,w)\right)}^c\cdot R_3.\end{array}$$
所以验证方程（3）成立。

知识证明

抽取器rewind证明者到收到挑战

$c$前的时间点，对于不同的挑战

$c^{\prime }\ne c$，证明者给出不同的一组应答

$s_{\alpha }^{\prime },s_{\beta }^{\prime },s_x^{\prime },s_{{\delta }_1}^{\prime },s_{{\delta }_2}^{\prime }$，且都满足5个验证方程。

令

$\mathrm{\Delta }c=c-c^{\prime },\mathrm{\Delta }{s}_{\alpha }=s_{\alpha }-s_{\alpha }^{\prime }$,

$\mathrm{\Delta }{s}_{\beta },\mathrm{\Delta }{s}_x,\mathrm{\Delta }{s}_{{\delta }_1},\mathrm{\Delta }{s}_{{\delta }_2}$同理.
对验证方程(1) ，两个实例相除得到：

$u^{\mathrm{\Delta }{s}_{\alpha }}=T_1^{\mathrm{\Delta }c}$.
令

$\tilde{\alpha }=\mathrm{\Delta }{s}_{\alpha }/\mathrm{\Delta }c$. 于是有

$u^{\tilde{\alpha }}=T_1$.

类似地对于验证方程（2），可以得到

$\tilde{\beta }=\mathrm{\Delta }{s}_{\beta }/\mathrm{\Delta }c$ 使得

$v^{\tilde{\beta }}=T_2$.

对验证方程 (4)，两个实例相除得到

$T_1^{\mathrm{\Delta }{s}_x}=u^{\mathrm{\Delta }{s}_{{\delta }_1}}$，减掉

$T_1=u^{\tilde{\alpha }}$ 得到

$u^{\tilde{\alpha }\mathrm{\Delta }{s}_x}=u^{\mathrm{\Delta }{s}_{{\delta }_1}}$或

$\mathrm{\Delta }{s}_{{\delta }_1}=\tilde{\alpha }\mathrm{\Delta }{s}_x$.
类似地对验证方程（5），得到

$\mathrm{\Delta }{s}_{{\delta }_2}=\tilde{\beta }\mathrm{\Delta }{s}_x$.

最后，对两个验证方程（3）的实例相除，得到：

$$\begin{array}{rl}{\left(e(g_1,g_2)/e(T_3,w)\right)}^{\mathrm{\Delta }c}& =e{(T_3,g_2)}^{\mathrm{\Delta }{s}_x}\cdot e(h,w{)}^{-\mathrm{\Delta }{s}_{\alpha }-\mathrm{\Delta }{s}_{\beta }}\cdot e{(h,g_2)}^{-\mathrm{\Delta }{s}_{{\delta }_1}-\mathrm{\Delta }{s}_{{\delta }_2}}\\ & =e{(T_3,g_2)}^{\mathrm{\Delta }{s}_x}\cdot e(h,w{)}^{-\mathrm{\Delta }{s}_{\alpha }-\mathrm{\Delta }{s}_{\beta }}\cdot e{(h,g_2)}^{-\tilde{\alpha }\mathrm{\Delta }{s}_x-\tilde{\beta }\mathrm{\Delta }{s}_x}\end{array}$$

取第

$\mathrm{\Delta }c$个根，且令

$\tilde{x}=\mathrm{\Delta }{s}_x/\mathrm{\Delta }c$，得到

$$e(g_1,g_2)/e(T_3,w)=e{(T_3,g_2)}^{\tilde{x}}\cdot e(h,w{)}^{-\tilde{\alpha }-\tilde{\beta }}\cdot e{(h,g_2)}^{-\tilde{x}(\tilde{\alpha }+\tilde{\beta })}$$
重写为

$$e(g_1,g_2)=e(T_3{h}^{-\tilde{\alpha }-\tilde{\beta }},w{g}_2^{\tilde{x}})$$
或者如果令

$\tilde{A}=T_3{h}^{-\tilde{\alpha }-\tilde{\beta }}$，为

$$e(\tilde{A},w{g}_2^{\tilde{x}})=e(g_1,g_2).$$
于是抽取器得到了SDH对

$(\tilde{A},\tilde{x})$。

零知识性

输出协议脚本的模拟器构造如下：
取

$A\stackrel{\mathrm{R}}{\leftarrow }{G}_1$ 和

$\alpha ,\beta \stackrel{\mathrm{R}}{\leftarrow }{\mathbb{Z}}_p$
计算

$T_1\leftarrow u^{\alpha },T_2\leftarrow v^{\beta },T_3\leftarrow A{h}^{\alpha +\beta }$.

如果判定性线性假设^[1]在

$G1$上成立，那么模拟器输出的

$(T_1,T_2,T_3)$ 的分布和任何证明者输出的分布不可区分。

模拟器选择挑战

$c\stackrel{\mathrm{R}}{\leftarrow }{\mathbb{Z}}_p$ 和值

$s_{\alpha },s_{\beta },s_x,s_{{\delta }_1},s_{{\delta }_2}\stackrel{\mathrm{R}}{\leftarrow }{\mathbb{Z}}_p$。计算：

$$\begin{array}{c}{R}_1\leftarrow u^{s_{\alpha }}\cdot T_1^{-c}{R}_2\leftarrow v^{s_{\beta }}\cdot T_2^{-c}{R}_4\leftarrow T_1^{s_x}\cdot u^{-s_{{\delta }_1}}{R}_5\leftarrow T_2^{s_x}\cdot v^{-s_{{\delta }_2}}\\ R_3\leftarrow e{(T_3,g_2)}^{s_x}\cdot e(h,w{)}^{-s_{\alpha }-s_{\beta }}\cdot e{(h,g_2)}^{-s_{{\delta }_1}-s_{{\delta }_2}}\cdot {\left(e(T_3,w)/e(g_1,g_2)\right)}^c.\end{array}$$

$R_1,R_2,R_3,R_4,R_5$ 和真实脚本分布一致。

模拟器输出最终脚本

$(T_1,T_2,T_3,R_1,R_2,R_3,R_4,R_5,c,s_{\alpha },s_{\beta },s_x,s_{{\delta }_1},s_{{\delta }_2})$，和协议脚本不可区分。

---

1. 给定

   $u,v,h,u^a,v^b,h^c\in G_1$ 判定
   $a+b=c$ 是否成立是困难的。 ↩︎