密码协议学习笔记(8.15):知识证据详解-526互联

在开始前,先回顾以下的知识点:

给定以大素数$p$为阶的循环群$G$,$g,h\in G$是两个生成元(在素数阶群上等价于非恒等元),求解$t$,使得$h^t=g$在计算上是不可行的.

已知$a,b\in Z_p$但不知道其具体值,给定以大素数$p$为阶的循环群$G$,$g$是其生成元,只知道$g^a,g^b$的情况下,计算$g^{ab}$在计算上是不可行的.

已知$a,b,c\in Z_p$,但不知道其具体值,给定以大素数$p$为阶的循环群$G$,$g$是其生成元,对于如下两个四元组

$$(g,g^a,g^b,g^c)$$

$$(g,g^a,g^b,g^{ab})$$

以不可忽略的正确概率进行区分,在计算上是不可行的.

考虑如下的问题:

在以大素数$p$为阶的循环群$G$上,生成元$g$是公开信息,Alice的手中持有私钥$s$,现在Alice向Bob发送$d_1=g^s$,Alice要如何证明$d_1$就是以$g$为底,以$s$为指数的值呢?

思路:如果$G$的另一个生成元$h$是公开的(但没人知道$g^{?}=h$),Bob持有另外一个值$d_2$,并且Bob相信$d_2=h^s$,那么Alice可以使用以下的方法证明二者的指数相等

该方案需要使用一个Hash函数,记为$H:\{0,1\}^{*}\to [0,p-1]$,记$||$为字符串拼接操作(博主有时候在多个字符串拼接起来作为函数输入的情况下,会混用拼接符号与逗号,如$f(\cdot||\cdot)$与$f(\cdot,\cdot)$)

Bob在收到知识证据后,计算

$$a'=g^rd_1^c$$

$$b'=h^rd_2^c$$

$$c'=H(d_1||d_2||a'||b')$$

然后判断$c=c'$是否成立,若成立,则认可$d_1=g^s$(或者说,认可$d_1=g^{\log_hd_2}$)

实际上

$$\begin{aligned}
a'=&g^rd_1^c\\
=&g^{\omega-sc}\cdot (g^{s})^c\\
=&g^{\omega}\\
=&a
\end{aligned}$$

$$\begin{aligned}
b'=&h^rd_2^c\\
=&h^{\omega-sc}\cdot (h^{s})^c\\
=&h^{\omega}\\
=&b
\end{aligned}$$

那么显然有

$$\begin{aligned}
c'=&H(d_1||d_2||a'||b')\\
=&H(d_1||d_2||a||b)\\
=&c
\end{aligned}$$

注意,两个生成元$g,h$之间的对数$t=\log_hg$不可公开(或者干脆随机生成$g,h$,让生成者也不知道$t$是多少).否则,如果有人知道了$t$,使得$h^t=g$,那么它就可以在仅知道$d_2=h^s$的情况下,计算出$(d_2)^t=(h^s)^t=h^{ts}=g^s=d_1$

问题来了,如何让Bob在不知道$s$的情况下,相信自己手中的$d_2=h^s$呢?借助可信第三方TTP不失为一个办法,然而既然有了TTP,干嘛还需要知识证据呢?

在此方案中,验证者只需要认可加密的函数值(即$Y_i=y_i^{p(x)}$)正确地来自于加密的系数(即$C_j=g^{\alpha_j}$)构成的函数即可.

给定大质数分发者Deliver做如下工作,以加密的秘密碎片形式分发秘密碎片:

选取形如$$p(x)=\alpha_0+\alpha_1x+\alpha_2x^2+\cdots+\alpha_{t-1}x^{t-1}$$的随机多项式,其中$\alpha_i\in[1,p-1]$
计算出$p(1),p(2)\cdots,p(n)$
计算$s_1,s_2,\cdots,s_n$,其中$$s_i=h^{p(i)}$$
使用参与者的公钥$y_1,y_2,\cdots,y_n$计算并公开加密的秘密碎片$Y_1,Y_2,\cdots,Y_n$,其中$$Y_i=(y_i)^{p(i)}$$

为了达到加密的秘密碎片的公开可验证,Deliver需要进行以下操作:

计算并公开多项式$p(x)$的每个系数$\alpha_0,\alpha_1,\cdots,\alpha_{t-1}$分别对应的公共承诺$C_0,C_1,\cdots,C_{t-1}$,其中$$C_j=g^{\alpha_j}$$
通过公共承诺计算出对每个成员$P_1,P_2,\cdots,P_n$的私人承诺$X_1,X_2,\cdots,X_n$,其中$$\begin{aligned}
X_i=&\Pi_{j=0}^{t-1}(C_j)^{(i^j)}\\
=&\Pi_{j=0}^{t-1}(g^{\alpha_j})^{(i^j)}\\
=&g^{\alpha_0}\cdot g^{\alpha_1\cdot i}\cdot g^{\alpha_2i^2}\cdots g^{\alpha_{t-1}i^{t-1}}\\
=&g^{\alpha_0+\alpha_1i+\alpha_2i^2+\cdots+\alpha_{t-1}i^{t-1}}\\
=&g^{p(i)}
\end{aligned}$$ 但私人承诺可以不必直接公开,实际上,公共承诺与私人承诺是等价的,因为任何人都可以通过公开的公共承诺,计算对某个成员的私人承诺.
选取随机数$\omega_1,\omega_2,\cdots,\omega_n\in[0,p-1]$
计算$a_{1},a_{2},\cdots,a_{n}$,其中$$a_{i}=g^{\omega_i}$$
计算$b_{1},b_{2},\cdots,b_{n}$,其中$$b_{i}=y_i^{\omega_i}$$
计算公共质询值$$c=H(X_1,X_2,\cdots,X_n,Y_1,Y_2,\cdots,Y_n,a_{1},a_{2},\cdots,a_{n},b_{1},b_{2},\cdots,b_n)$$
计算对成员$P_1,P_2,\cdots,P_n$的应答$r_1,r_2,\cdots,r_n$,其中$$r_i=\omega_i-p(i)c$$
将$PROOF_D=(c,r_1,r_2,\cdots,r_n)$作为知识证据公开

获得Deliver的公开信息后,任何人想验证加密的秘密碎片$Y_1,Y_2,\cdots,Y_n$的有效性,需要进行以下步骤:

在既不知道$p(x)$的表达式中的系数$\alpha_j$,也不知道任何一个$p(i)$的情况下,通过$PROOF_D$,来确认$Y_i=y_i^{p(x)}$的确来自于$C_j=g^{\alpha_j}$构成的函数