定义布尔表达式
ϕ
(
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∏ngijxj)}
使用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)为:
上述协议可以验证如下的线性关系:
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∑nxj⋅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的幂次是定值。
定义:令 ( 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。
定义:令 ( 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←RC,(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 ϕ: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∏ng1jxj,⋯,j=1∏ngmjxj)
那么Generic Linear Protocol就是证明上述群同态关系的协议。
如果 ∣ H 1 ∣ × ∣ H 2 ∣ |H_1| \times |H_2| ∣H1∣×∣H2∣的最小素因子的大小至少为 ∣ C ∣ |C| ∣C∣,那么Sigma协议是Special HVZK的,并且提供Knowledge soundness。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)