# 一个对SDH问题解的ZKPoK协议

**Strong Diffie-Hellman (SDH)** 问题定义如下：
> 给定$(q+2)$长的元组 $\left(g_1, g_2, g_2^\gamma, g_2^{\left(\gamma^2\right)}, \ldots, g_2^{\left(\gamma^q\right)}\right)$ 作为输入，输出 $\left(g_1^{1 /(\gamma+x)}, x\right)$ ，其中$x \in \mathbb{Z}_p^*$。

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

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

秘密值：$\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,wg_2^x)=e(g_1,g_2)$

## 协议
证明者选择随机数$\alpha, \beta \stackrel{\mathrm{R}}{\leftarrow} \mathbb{Z}_p$，计算：
$$
\begin{equation}
T_1 \leftarrow u^\alpha \quad T_2 \leftarrow v^\beta \quad T_3 \leftarrow A h^{\alpha+\beta}\\
\delta_1 \leftarrow x \alpha \quad \delta_2 \leftarrow x \beta
\end{equation}
$$

接下来证明者和验证者执行ZKPoK协议，证明拥有满足如下五个关系的知识$\left(\alpha, \beta, x, \delta_1, \delta_2\right)$：
$$
\begin{array}{cc}
u^\alpha=T_1 \\ v^\beta=T_2 \\
e\left(T_3, g_2\right)^x \cdot e(h, w)^{-\alpha-\beta} \cdot e\left(h, g_2\right)^{-\delta_1-\delta_2}=e\left(g_1, g_2\right) / e\left(T_3, w\right) \\
T_1^x u^{-\delta_1}=1 \\ T_2^x v^{-\delta_2}=1
\end{array}
$$
注意第三个等式是由$e(A,wg_2^x)=e(g_1,g_2)$变形而来。

具体ZKPoK协议如下:
1. Prover计算并发送$R_1\ldots R_5$：
$$
\begin{array}{ll}
R_1 \leftarrow u^{r_\alpha} & R_2 \leftarrow v^{r_\beta} \\
R_3 \leftarrow e\left(T_3, g_2\right)^{r_x} \cdot e(h, w)^{-r_\alpha-r_\beta} \cdot e\left(h, g_2\right)^{-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 \quad s_\beta \leftarrow r_\beta+c \beta \quad s_x \leftarrow r_x+c x \quad s_{\delta_1} \leftarrow r_{\delta_1}+c \delta_1 \quad s_{\delta_2} \leftarrow r_{\delta_2}+c \delta_2
$$
4. Verifier验证：
$$
\begin{aligned}
u^{s_\alpha} & \stackrel{?}{=} T_1^c \cdot R_1 \quad (1)\\
v^{s_\beta} & \stackrel{?}{=} T_2^c \cdot R_2 \quad (2)\\
e\left(T_3, g_2\right)^{s_x} \cdot e(h, w)^{-s_\alpha-s_\beta} \cdot e\left(h, g_2\right)^{-s_{\delta_1}-s_{\delta_2}} & \stackrel{?}{=}\left(e\left(g_1, g_2\right) / e\left(T_3, w\right)\right)^c \cdot R_3 \quad (3) \\
T_1^{s_x} \cdot u^{-s_{\delta_1}} & \stackrel{?}{=} R_4 \quad (4)\\
T_2^{s_x} \cdot v^{-s_{\delta_2}} & \stackrel{?}{=} R_5 \quad (5).
\end{aligned}
$$

## 证明
### 完备性
对一个拥有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+c x} u^{-r_{\delta_1}-c x \alpha}=\left(u^\alpha\right)^{r_x} u^{-r_{\delta_1}}=T_1^{r_x} u^{-r_{\delta_1}}=R_4,
$$
所以最后两个验证方程成立。

$$
\begin{aligned}
&e\left(T_3, g_2\right)^{s_x} \cdot e(h, w)^{-s_\alpha-s_\beta} \cdot e\left(h, g_2\right)^{-s_{\delta_1}-s_{\delta_2}} \\
&\quad=e\left(T_3, g_2\right)^{r_x+c x} \cdot e(h, w)^{-r_\alpha-r_\beta-c \alpha-c \beta} \cdot e\left(h, g_2\right)^{-r_{\delta_1}-r_{\delta_2}-c x \alpha-c x \beta} \\
&\quad=e\left(T_3, g_2^x\right)^c \cdot e\left(h^{-\alpha-\beta}, w g_2^x\right)^c \cdot\left(e\left(T_3, g_2\right)^{r_x} \cdot e(h, w)^{-r_\alpha-r_\beta} \cdot e\left(h, g_2\right)^{-r_{\delta_1}-r_{\delta_2}}\right) \\
&\quad=e\left(T_3 h^{-\alpha-\beta}, w g_2^x\right)^c \cdot e\left(T_3, w\right)^{-c} \cdot\left(R_3\right) \\
&\quad=\left(e\left(A, w g_2^x\right) / e\left(T_3, w\right)\right)^c \cdot R_3 \\
&\quad=\left(e\left(g_1, g_2\right) / e\left(T_3, w\right)\right)^c \cdot R_3 .
\end{aligned}
$$
所以验证方程（3）成立。
### 知识证明
抽取器rewind证明者到收到挑战$c$前的时间点，对于不同的挑战$c^{\prime} \neq c$，证明者给出不同的一组应答$s_\alpha^{\prime}, s_\beta^{\prime}, s_x^{\prime}, s_{\delta_1}^{\prime},s_{\delta_2}^{\prime}$，且都满足5个验证方程。

令 $\Delta c=c-c^{\prime}, \Delta s_\alpha=s_\alpha-s_\alpha^{\prime}$, $\Delta s_\beta, \Delta s_x, \Delta s_{\delta_1},\Delta s_{\delta_2}$同理.
对验证方程(1) ，两个实例相除得到：$u^{\Delta s_\alpha}=T_1^{\Delta c}$.
令 $\tilde{\alpha}=\Delta s_\alpha / \Delta c$. 于是有$u^{\tilde{\alpha}}=T_1$.

类似地对于验证方程（2），可以得到$\tilde{\beta}=\Delta s_\beta / \Delta c$ 使得$v^{\tilde{\beta}}=T_2$.

对验证方程 (4)，两个实例相除得到 $T_1^{\Delta s_x}=u^{\Delta s_{\delta_1}}$，减掉 $T_1=u^{\tilde{\alpha}}$ 得到$u^{\tilde{\alpha} \Delta s_x}=u^{\Delta s_{\delta_1}}$或 $\Delta s_{\delta_1}=\tilde{\alpha} \Delta s_x$.
类似地对验证方程（5），得到 $\Delta s_{\delta_2}=\tilde{\beta} \Delta s_x$.

最后，对两个验证方程（3）的实例相除，得到：
$$
\begin{aligned}
\left(e\left(g_1, g_2\right) / e\left(T_3, w\right)\right)^{\Delta c} &=e\left(T_3, g_2\right)^{\Delta s_x} \cdot e(h, w)^{-\Delta s_\alpha-\Delta s_\beta} \cdot e\left(h, g_2\right)^{-\Delta s_{\delta_1}-\Delta s_{\delta_2}} \\
&=e\left(T_3, g_2\right)^{\Delta s_x} \cdot e(h, w)^{-\Delta s_\alpha-\Delta s_\beta} \cdot e\left(h, g_2\right)^{-\tilde{\alpha} \Delta s_x-\tilde{\beta} \Delta s_x}
\end{aligned}
$$

取第$\Delta c$个根，且令$\tilde{x}=\Delta s_x / \Delta c$，得到
$$
e\left(g_1, g_2\right) / e\left(T_3, w\right)=e\left(T_3, g_2\right)^{\tilde{x}} \cdot e(h, w)^{-\tilde{\alpha}-\tilde{\beta}} \cdot e\left(h, g_2\right)^{-\tilde{x}(\tilde{\alpha}+\tilde{\beta})}
$$
重写为
$$
e\left(g_1, g_2\right)=e\left(T_3 h^{-\tilde{\alpha}-\tilde{\beta}}, w g_2^{\tilde{x}}\right)
$$
或者如果令 $\tilde{A}=T_3 h^{-\tilde{\alpha}-\tilde{\beta}}$，为
$$
e\left(\tilde{A}, w g_2^{\tilde{x}}\right)=e\left(g_1, g_2\right) .
$$
于是抽取器得到了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$上成立，那么模拟器输出的$\left(T_1, T_2, T_3\right)$ 的分布和任何证明者输出的分布不可区分。

模拟器选择挑战 $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{gathered}
R_1 \leftarrow u^{s_\alpha} \cdot T_1^{-c} \quad R_2 \leftarrow v^{s_\beta} \cdot T_2^{-c} \quad R_4 \leftarrow T_1^{s_x} \cdot u^{-s_{\delta_1}} \quad R_5 \leftarrow T_2^{s_x} \cdot v^{-s_{\delta_2}} \\
R_3 \leftarrow e\left(T_3, g_2\right)^{s_x} \cdot e(h, w)^{-s_\alpha-s_\beta} \cdot e\left(h, g_2\right)^{-s_{\delta_1}-s_{\delta_2}} \cdot\left(e\left(T_3, w\right) / e\left(g_1, g_2\right)\right)^c .
\end{gathered}
$$
$R_1, R_2, R_3, R_4, R_5$ 和真实脚本分布一致。

模拟器输出最终脚本$\left(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}\right)$，和协议脚本不可区分。

[^1]: 给定 $u, v, h, u^a, v^b, h^c \in G_1$ 判定$a+b=c$ 是否成立是困难的。