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

零知识证明线性关系:Generic Linear Protocol,第1张

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=1ngijxj)}
使用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,,αnZq,向 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,jRZq,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,ij=1ngijαt,j,i=1,,m,发送给 V V V V V V发起挑战:随机选择 c ← R C c \leftarrow_R C cRC,发送给 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+αjc,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=1ngijαz,j==ut,iuic,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=1nxjDlogg(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=gxw=ux} 安全性 Knowledge soundness

定义:令 ( P , V ) (P,V) (P,V)是关于关系 R ⊆ X × Y R \subseteq X \times Y RX×Y和挑战 C C C的Sigma协议,我们说这个协议提供知识可靠性(Knowledge soundness),如果存在有效的确定性算法 E x t Ext Ext(知识提取器,witness extractor),它有如下性质:给定声明 y ∈ Y y \in Y yY,以及对应的两个可接受会话 ( 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 xX,使得条件 ( 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 PV先产生 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 RX×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) cRC,(t,z)RSim(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 ϕ:H1H2是群同态。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=1ng1jxj,,j=1ngmjxj)
那么Generic Linear Protocol就是证明上述群同态关系的协议。

Sigma协议的安全性

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/2992488.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存