Efficient Zero-Knowledge Arguments from Two-Tiered Homomorphic Commitments 学习笔记
1. 引言
Groth 2011年论文《Efficient Zero-Knowledge Arguments from Two-Tiered Homomorphic Commitments》，发表于Asia crypto 2011。
本文：
-
基于double pairing assumption构建了two-tiered homomorphic commitments scheme 。
-
基于本文的two-tiered homomorphic commitments scheme狗啊见的zero-knowledge argument，具有：
– sublinear communication complexity
– perfect completeness
– perfect special honest verifier zero-knowledge
– computational soundness -
将本文的zero-knowledge argument用于实现range proof时，如证明a committed value belongs to a specific N N N-bit integer interval，相应的communication cost为 O ( N 1 3 ) O(N^{\frac{1}{3}}) O(N31) 个 group elements。
-
构建的circuit satisfiability argument的communication complexity为 O ( N 1 3 ) O(N^{\frac{1}{3}}) O(N31)个group elements，其中 N N N为gate数量。
该argument具有quasi-linear computational complexity for the prover，同时具有very efficient verification。
相关的对比见 如下表1和表2 ：（其中Prover的computation保守估计为 O ( N log 2 N ) O(N\log^2 N) O(Nlog2N)，若借助FFT，可进一步reduce为 O ( N log N ) O(N\log N) O(NlogN)。）
其中：
– [8] Cramer等人1994年论文《Proofs of partial knowledge and simplified design of witness hiding protocols》，基于的是DLOG assumption。
– [22] Groth 2019年论文《Linear algebra with sub-linear zero-knowledge arguments》，基于的是DLOG assumption。 -
本文的zero-knowledge argument可实例化为in asymmetric bilinear group，在该group下computational double pairing assumption成立。而[6,7] 论文中的range proof是基于 q q q-SDH assumption in bilinear group。
-
主要技术贡献是：batch product argument。已知 3 N 3N 3N个committed elements u i , v i , w i ∈ Z p u_i,v_i,w_i\in\mathbb{Z}_p ui,vi,wi∈Zp，构建了zk argument 证明 u i v i = w i u_iv_i=w_i uivi=wi。
借助commitment 的同态属性，同时支持对committed elements的加法和乘法运算，从而允许the prover to commit to the wires in a circuit and prove that they respect the N A N D NAND NAND-gate。
而对于range proof，将数值以 N N N个bit位表示 w 1 , ⋯ , w N w_1,\cdots,w_N w1,⋯,wN，则可转为证明 w i w i = w i w_iw_i=w_i wiwi=wi， which can only be true if w i ∈ { 0 , 1 } w_i\in\{0,1\} wi∈{0,1}。然后利用commitment的同态属性计算 w = ∑ i = 1 N w i 2 i − 1 w=\sum_{i=1}^{N}w_i2^{i-1} w=∑i=1Nwi2i−1，即可证明 w ∈ [ 0 ; 2 N ) w\in [0;2^N) w∈[0;2N)。也可扩展为证明 w ∈ [ A , B ) w\in [A,B) w∈[A,B)。
2. 相关定义
2.1 two-tiered homomorphic commitment
本文涉及的commitment scheme 有：
- Pedersen commitment
- commitment scheme for group elements
- Pedersen commitment + commitment scheme for group elements
(1) Pedersen commitment：
public key中包含the description of a group of prime order
p
p
p和group elements
g
,
h
g,h
g,h。
commitment to
a
∈
Z
p
a\in\mathbb{Z}_p
a∈Zp表示为：
c
=
g
a
h
r
c=g^ah^r
c=gahr，其中
r
r
r为随机值。
具有加法同态属性，即
c
⋅
c
’
=
(
g
a
h
r
)
(
g
b
h
s
)
=
g
a
+
b
h
r
+
s
c\cdot c’=(g^ah^r)(g^bh^s)=g^{a+b}h^{r+s}
c⋅c’=(gahr)(gbhs)=ga+bhr+s 为a commitment to
a
+
b
a+b
a+b。
commitment to vector
(
a
1
,
a
2
,
⋯
,
a
n
)
∈
Z
p
n
(a_1,a_2,\cdots, a_n)\in\mathbb{Z}_p^n
(a1,a2,⋯,an)∈Zpn可表示为：
c
=
h
r
∏
k
=
1
n
g
k
a
k
c=h^r\prod_{k=1}^{n}g_k^{a_k}
c=hr∏k=1ngkak
(2) commitment scheme for group elements：
Abe等人2010年论文《Structure-preserving signatures and commitments to group elements》
和
Groth 2009年论文《Homomorphic trapdoor commitments to group elements》
中均提出了commitment scheme for group elements。
其中的一种commitment scheme是使用a bilinear with a pairing
e
:
G
×
G
^
→
T
e: \mathbb{G}\times\hat{\mathbb{G}}\rightarrow \mathbb{T}
e:G×G^→T
其中
G
,
G
^
,
T
\mathbb{G},\hat{\mathbb{G}},\mathbb{T}
G,G^,T均为cyclic groups of prime order
p
p
p，将
G
\mathbb{G}
G和
G
^
\hat{\mathbb{G}}
G^ 称为base group，
T
\mathbb{T}
T称为target group。
该pairing应为efficiently computable, non-trivial and bilinear，即：
∀
x
,
y
,
a
,
b
\forall x,y,a,b
∀x,y,a,b均有
e
(
x
a
,
y
b
)
=
e
(
x
,
y
)
a
b
e(x^a,y^b)=e(x,y)^{ab}
e(xa,yb)=e(x,y)ab
对于specific non-trivial group elements
v
,
u
1
,
⋯
,
u
m
∈
G
^
v,u_1,\cdots,u_m\in\hat{\mathbb{G}}
v,u1,⋯,um∈G^，a commitment to vector
(
c
1
,
⋯
,
c
m
)
∈
G
(c_1,\cdots,c_m)\in\mathbb{G}
(c1,⋯,cm)∈G 可表示为：
C
=
e
(
t
,
v
)
∏
j
=
1
m
e
(
c
j
,
u
j
)
C=e(t,v)\prod_{j=1}^{m}e(c_j,u_j)
C=e(t,v)∏j=1me(cj,uj)，其中
t
t
t为random point
t
∈
G
t\in\mathbb{G}
t∈G。
以上commitment具有computationally binding under the computational double pairing assumption，即已知
u
,
v
∈
G
^
u,v\in\hat{\mathbb{G}}
u,v∈G^，很难找到
s
,
t
∈
G
s,t\in\mathbb{G}
s,t∈G，使得
e
(
s
,
u
)
=
e
(
t
,
v
)
e(s,u)=e(t,v)
e(s,u)=e(t,v) 成立。
同时在Abe和Groth论文中证明了，the hardness of the computational double pairing assumption 与 the hardness of decision Diffie-Hellman assumption in
G
^
\hat{\mathbb{G}}
G^ 相当。
根据pairing的bilinearity属性有：
C
⋅
C
’
=
(
e
(
t
,
v
)
∏
j
=
1
m
e
(
c
j
,
u
j
)
)
(
e
(
t
’
,
v
)
∏
j
=
1
m
e
(
c
j
’
,
u
j
)
)
=
e
(
t
t
’
,
v
)
∏
j
=
1
m
e
(
c
j
c
j
’
,
u
j
)
C\cdot C’=( e(t,v)\prod_{j=1}^{m}e(c_j,u_j))( e(t’,v)\prod_{j=1}^{m}e(c_j’,u_j))= e(tt’,v)\prod_{j=1}^{m}e(c_jc_j’,u_j)
C⋅C’=(e(t,v)∏j=1me(cj,uj))(e(t’,v)∏j=1me(cj’,uj))=e(tt’,v)∏j=1me(cjcj’,uj)
即为a commitment to the entry-wise product of the messages。
(3) Pedersen commitment + commitment scheme for group elements：
将Pedersen commitment scheme 和 commitment scheme for group elements结合，可实现commit to commitments。
即若
c
j
=
h
r
j
∏
k
=
1
n
g
k
a
j
k
c_j=h^{r_j}\prod_{k=1}^{n}g_k^{a_{jk}}
cj=hrj∏k=1ngkajk，
C
=
e
(
t
,
v
)
∏
j
=
1
m
e
(
c
j
,
u
j
)
C=e(t,v)\prod_{j=1}^{m}e(c_j,u_j)
C=e(t,v)∏j=1me(cj,uj)，最终可获得 a single target group element that is a commitment to
m
n
mn
mn values
{
a
j
k
}
j
=
1
,
k
=
1
m
,
n
\{a_{jk}\}_{j=1,k=1}^{m,n}
{ajk}j=1,k=1m,n。
因两种commitment scheme都是homomorphic the product of two commitments
C
⋅
C
’
C\cdot C’
C⋅C’ 为 a commitment to the sums of the messages
a
j
k
+
a
j
k
’
a_{jk}+a_{jk}’
ajk+ajk’
two-tiered commitment scheme包含3个算法
(
K
,
c
o
m
,
c
o
m
(
2
)
)
(\mathcal{K}, com, com^{(2)})
(K,com,com(2))，其中：
1）
K
\mathcal{K}
K为key generator 输入为security parameter
λ
\lambda
λ，数字
m
,
n
m,n
m,n，输出为public key
c
k
ck
ck。the commitment key specifies cyclic groups
Z
p
,
G
\mathbb{Z}_p,\mathbb{G}
Zp,G和
T
\mathbb{T}
T of prime order
p
p
p。【一共有
m
+
n
+
2
m+n+2
m+n+2个group elements in
G
\mathbb{G}
G and
G
^
\hat{\mathbb{G}}
G^】
2）
c
o
m
c
k
:
Z
p
n
×
Z
p
→
G
com_{ck}:\mathbb{Z}_p^n\times \mathbb{Z}_p\rightarrow \mathbb{G}
comck:Zpn×Zp→G，即对应本文的Pedersen commitment。
3）
c
o
m
c
k
2
:
G
m
→
T
com_{ck}^2:\mathbb{G}^m\rightarrow \mathbb{T}
comck2:Gm→T，即对应本文的commitment scheme for group elements.
具有如下特性：
- 同态属性：当the maps c o m c k com_{ck} comck and c o m c k 2 com_{ck}^2 comck2 为 Z p \mathbb{Z}_p Zp-linear时，该two-tiered commitment scheme具有同态属性。
- computationally binding 属性
- perfectly hiding属性
2.2 Special honest verifier zero-knowledge arguments of knowledge
3. batch product argument (相当于Hadamard product argument)
针对的场景为：
- public info：commitments C U 1 , C V 1 , C W 1 , ⋯ , C U M , C V M , C W M C_{U_1},C_{V_1},C_{W_1},\cdots,C_{U_M},C_{V_M},C_{W_M} CU1,CV1,CW1,⋯,CUM,CVM,CWM
- private info： { u i j k ∈ Z p , v i j k ∈ Z p , w i j k ∈ Z p } i = 1 , j = 1 , k = 1 M , m , n \{u_{ijk}\in\mathbb{Z}_p, v_{ijk}\in\mathbb{Z}_p,w_{ijk}\in\mathbb{Z}_p \}_{i=1,j=1,k=1}^{M,m,n} {uijk∈Zp,vijk∈Zp,wijk∈Zp}i=1,j=1,k=1M,m,n 以及 相应的随机值 r i , j , s i , j , t i , j ∈ Z p r_{i,j},s_{i,j},t_{i,j} \in\mathbb{Z}_p ri,j,si,j,ti,j∈Zp。
- relation：
u i j k v i j k = w i j k u_{ijk}v_{ijk}=w_{ijk} uijkvijk=wijk 且
c u i , j = c o m c k ( u i j 1 , ⋯ , u i j n ; r i j ) c_{u_{i,j}}=com_{ck}(u_{ij1},\cdots,u_{ijn}; r_{ij}) cui,j=comck(uij1,⋯,uijn;rij) 且 C U i = c o m c k 2 ( c u i 1 , ⋯ , c u i m ) C_{U_i}=com_{ck}^2(c_{u_{i1}},\cdots,c_{u_{im}}) CUi=comck2(cui1,⋯,cuim) 且
c v i , j = c o m c k ( v i j 1 , ⋯ , v i j n ; s i j ) c_{v_{i,j}}=com_{ck}(v_{ij1},\cdots,v_{ijn}; s_{ij}) cvi,j=comck(vij1,⋯,vijn;sij) 且 C V i = c o m c k 2 ( c v i 1 , ⋯ , c v i m ) C_{V_i}=com_{ck}^2(c_{v_{i1}},\cdots,c_{v_{im}}) CVi=comck2(cvi1,⋯,cvim) 且
c w i , j = c o m c k ( w i j 1 , ⋯ , w i j n ; t i j ) c_{w_{i,j}}=com_{ck}(w_{ij1},\cdots,w_{ijn}; t_{ij}) cwi,j=comck(wij1,⋯,wijn;tij) 且 C W i = c o m c k 2 ( c w i 1 , ⋯ , c w i m ) C_{W_i}=com_{ck}^2(c_{w_{i1}},\cdots,c_{w_{im}}) CWi=comck2(cwi1,⋯,cwim)