零知识证明线性关系：Generic Linear Protocol

Generic Linear Protocol

定义布尔表达式
ϕ ( x 1 , ⋯   , x n ) : = { ∧ i = 1 m ( u i = = ∏ j = 1 n g i j x j ) } \phi(x_1,\cdots,x_n) := \{ \wedge_{i=1}^m (u_i ==\prod_{j=1}^n g_{ij}^{x_j}) \} ϕ(x1​,⋯,xn​):={∧i=1m​(ui​==j=1∏n​gijxj​​)}
使用Sigma Protocol模板（详见零知识证明），令 X : = Z q n X:=Z_q^n X:=Zqn​， Y : = ϕ Y:=\phi Y:=ϕ（包含 g i , j ,   ∀ i , j g_{i,j},\, \forall i,j gi,j​,∀i,j与 u i ,   ∀ i u_i,\, \forall i ui​,∀i），关系为：
R : = { ( ( α 1 , ⋯   , α n ) , ϕ ) ∈ X × Y : ϕ ( α 1 , ⋯   , α n ) = = t r u e } R:=\{ ((\alpha_1,\cdots,\alpha_n),\phi) \in X \times Y : \phi(\alpha_1,\cdots,\alpha_n)==true \} R:={((α1​,⋯,αn​),ϕ)∈X×Y:ϕ(α1​,⋯,αn​)==true}
那么一个关于关系 R R R的通用线性协议 ( P , V ) (P,V) (P,V)为：

初始化：确定一个素数 q q q阶的乘法循环群 G G G， g g g是生成元。 P P P拥有关于声明 ϕ \phi ϕ的证据 α 1 , ⋯   , α n ∈ Z q \alpha_1,\cdots,\alpha_n \in Z_q α1​,⋯,αn​∈Zq​，向 V V V证明 ( { α j } , ϕ ) (\{\alpha_j\},\phi) ({αj​},ϕ)满足关系 R R R P P P发送承诺：首先生成 α t , j ← R Z q , j = 1 , ⋯   , n \alpha_{t,j} \leftarrow_R Z_q,j=1,\cdots,n αt,j​←R​Zq​,j=1,⋯,n，然后计算 u t , i ← ∏ j = 1 n g i j α t , j , i = 1 , ⋯   , m u_{t,i} \leftarrow \prod_{j=1}^n g_{ij}^{\alpha_{t,j}},i=1,\cdots,m ut,i​←∏j=1n​gijαt,j​​,i=1,⋯,m，发送给 V V V V V V发起挑战：随机选择 c ← R C c \leftarrow_R C c←R​C，发送给 P P P P P P给出回应：计算 α z , j ← α t , j + α j c , j = 1 , ⋯   , n \alpha_{z,j} \leftarrow \alpha_{t,j} + \alpha_j c,j=1,\cdots,n αz,j​←αt,j​+αj​c,j=1,⋯,n，发送给 V V V V V V验证关系：判断 ∏ j = 1 n g i j α z , j = = u t , i ⋅ u i c , i = 1 , ⋯   , m \prod_{j=1}^n g_{ij}^{\alpha_{z,j}} == u_{t,i} \cdot u_i^c, i=1,\cdots,m ∏j=1n​gijαz,j​​==ut,i​⋅uic​,i=1,⋯,m是否都满足

上述协议可以验证如下的线性关系：
D l o g g ( u i ) = ∑ j = 1 n x j ⋅ D l o g g ( g i j ) ,    i = 1 , ⋯   , m Dlog_g(u_i) = \sum_{j=1}^n x_j \cdot Dlog_g(g_{ij}),\,\, i=1,\cdots,m Dlogg​(ui​)=j=1∑n​xj​⋅Dlogg​(gij​),i=1,⋯,m
这里的 D l o g g ( g i j ) Dlog_g(g_{ij}) Dlogg​(gij​)都是常数。因为 g i j g_{ij} gij​都是由声明 ϕ \phi ϕ所固定的，关于 g g g的幂次是定值。

Some Case Schnorr’s protocol：令 n = 1 , m = 1 n=1,m=1 n=1,m=1，布尔函数为 ϕ ( x ) : = { u = g x } \phi(x):=\{u=g^x\} ϕ(x):={u=gx}Okamoto’s protocol：令 n = 1 , m = 2 n=1,m=2 n=1,m=2，布尔函数为 ϕ ( x ) : = { u = g x h y } \phi(x):=\{u=g^x h^y\} ϕ(x):={u=gxhy}Chaum-Pedersen protocol：令 n = 1 , m = 1 n=1,m=1 n=1,m=1，布尔函数为 ϕ ( x ) : = { v = g x ∧ w = u x } \phi(x):=\{v=g^x \wedge w=u^x\} ϕ(x):={v=gx∧w=ux} 安全性 Knowledge soundness

定义：令 ( P , V ) (P,V) (P,V)是关于关系 R ⊆ X × Y R \subseteq X \times Y R⊆X×Y和挑战 C C C的Sigma协议，我们说这个协议提供知识可靠性（Knowledge soundness），如果存在有效的确定性算法 E x t Ext Ext（知识提取器，witness extractor），它有如下性质：给定声明 y ∈ Y y \in Y y∈Y，以及对应的两个可接受会话 ( t , c , z ) , ( t , c ′ , z ′ ) , c ≠ c ′ (t,c,z),(t,c',z'),c \neq c' (t,c,z),(t,c′,z′),c=c′，那么 E x t Ext Ext总是输出 x ∈ X x \in X x∈X，使得条件 ( x , y ) ∈ R (x,y) \in R (x,y)∈R满足。

作用：约束Prover，它不能欺骗。有上述性质的协议 ( P , V ) (P,V) (P,V)acts as a "proof of knowledge" ，我们调用 P ， V P，V P，V先产生 t t t，然后生成可接受的会话 ( c , z ) (c,z) (c,z)，然后回滚 P P P到产生 t t t之后的状态，再生成另一个可接受的会话 ( c ′ , z ′ ) (c',z') (c′,z′)，然后就可以计算出关于声明 y y y的证据 x x x。

Special HVZK

定义：令 ( P , V ) (P,V) (P,V)是关于关系 R ⊆ X × Y R \subseteq X \times Y R⊆X×Y和挑战 C C C的Sigma协议，我们说这个协议是诚实验证者特殊零知识的（Special HVZK），如果存在有效概率算法 S i m Sim Sim（模拟器，simulator），它有如下性质：

对于任意的输入 ( y , c ) ∈ Y × C (y,c) \in Y \times C (y,c)∈Y×C， S i m Sim Sim总是输出 ( t , z ) (t,z) (t,z)，使得 ( t , c , z ) (t,c,z) (t,c,z)是关于 y y y的可接受会话。对于所有的 ( x , y ) ∈ R (x,y) \in R (x,y)∈R，计算 c ← R C , ( t , z ) ← R S i m ( y , c ) c \leftarrow_R C,(t,z) \leftarrow_R Sim(y,c) c←R​C,(t,z)←R​Sim(y,c)，那么会话 ( t , c , z ) (t,c,z) (t,c,z)都有相同的分布。

作用：约束Verifier，它无法获得知识。因为即使没有证据 x x x，模拟器依然生产了可接受会话 ( t , c , z ) (t,c,z) (t,c,z)。

Sigma协议与群同态

如果令 H 1 , H 2 H_1,H_2 H1​,H2​是两个有限交换群，其中 H 1 H_1 H1​是加法群， H 2 H_2 H2​是乘法群。再令 ϕ : H 1 → H 2 \phi:H_1 \rightarrow H_2 ϕ:H1​→H2​是群同态。Sigma协议就是证明这个群同态的安全协议。

再令 H 1 : = Z q n H_1 := Z_q^n H1​:=Zqn​， H 2 : = G m H_2 := G^m H2​:=Gm，其中 G G G是 q q q阶乘法群。令群同态为
ϕ ( x 1 , ⋯   , x n ) : = ( ∏ j = 1 n g 1 j x j , ⋯   , ∏ j = 1 n g m j x j ) \phi(x_1,\cdots,x_n) := (\prod_{j=1}^n g_{1j}^{x_j},\cdots,\prod_{j=1}^n g_{mj}^{x_j}) ϕ(x1​,⋯,xn​):=(j=1∏n​g1jxj​​,⋯,j=1∏n​gmjxj​​)
那么Generic Linear Protocol就是证明上述群同态关系的协议。

Sigma协议的安全性

如果 ∣ H 1 ∣ × ∣ H 2 ∣ |H_1| \times |H_2| ∣H1​∣×∣H2​∣的最小素因子的大小至少为 ∣ C ∣ |C| ∣C∣，那么Sigma协议是Special HVZK的，并且提供Knowledge soundness。