Cramer等人2011年论文《On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations》。
要点： 【正如 Thomas Attema等人发表于CRYPTO 2020中的论文《Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics》中所指出的。详情参见博客 Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics学习笔记】 （1）借助安全多方计算技术，实现了对arbitrary constraints on vectors of committed elements的证明。 （2）考虑的是单个element of Z q \mathbb{Z}_q Zq 的homomorphic commitment scheme，对应a vecotr的commitment size为 O ( n ) O(n) O(n)，其中 n n n为vector size。主要是利用 ∑ \sum ∑-protocol实现了乘法关系的证明，即 x i y i = z i x_iy_i=z_i xiyi=zi。（Thomas Attema等人发表于CRYPTO 2020中的论文《Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics》中 对此仅需了改进，实现了packed commitment。详情参见参见博客 Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics学习笔记 1.3节内容。） （3）其本质思想是 h ( X ) = f ( X ) g ( X ) h(X)=f(X)g(X) h(X)=f(X)g(X) 多项式乘积证明，可将多项式 f ( X ) f(X) f(X) 、 g ( X ) g(X) g(X) 、 h ( X ) h(X) h(X)看成是分别对应multiplication gates的packed-secret sharings of left inputs、right inputs和outputs。（详情参见参见博客 Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics学习笔记 1.3节内容。）
本文主要内容为：
-
提供了a zero-knowledge protocol用于证明 the committed values x i , y i , z i x_i,y_i,z_i xi,yi,zi for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l，满足 x i y i = z i x_iy_i=z_i xiyi=zi 其中 x i , y i , z i x_i,y_i,z_i xi,yi,zi 值均来自于有限域内。 For error probability 2 − u 2^{-u} 2−u, the size of the proof is linear in u u u and only logarithmic in l l l。 因此，对于任意fixed error probability，the amortized complexity 随着 l l l的增加会消失。 特别地，当the committed values来自于a field of small constant size是，可进一步改进之前方案 的complexity by a factor of l l l。
-
为circuit satisifiability of circuit C C C构建的zero-knowledge interactive proof，相应的proof size为 O ( ∣ c ∣ ) O(|c|) O(∣c∣)。
-
generalize a protocol——用于verify l l l instances of an algebraic circuit D D D over K K K with v v v inputs。即已知committed values x i , j x_{i,j} xi,j和 z i z_i zi with i = 1 , ⋯ , l i=1,\cdots, l i=1,⋯,l and j = 1 , ⋯ , v j=1,\cdots,v j=1,⋯,v，Prover需证明 D ( x i , 1 , ⋯ , x i , v ) = z i D(x_{i,1},\cdots,x_{i,v})=z_i D(xi,1,⋯,xi,v)=zi for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l。 有一个有趣的属性是，the amortized complexity of verifying one circuit only depends on the multiplicative depth of the circuit and not the size。因此，对于具有small multiplicative depth的circuit，the amortized cost要小于the number of multiplications in D D D。
-
借助preprocessing，实现了信息论安全的homomorphic commitments to integer valuse。仅需a constant number of multiplications per commitment。
-
实现了verify l l l integer multiplications with low amortized complexity。
-
本文的所有协议的安全假设依赖于commitment scheme本身，即factoring。而这些协议也可扩展至使用standard computationally securce commitment，相应的安全假设则基于strong RSA assumption。
本文主要关注的是commitments to elements in a finite field K K K， or to integers，同时假设这些commitments具有同态属性，即 [ x ] ⋅ [ y ] = [ x + y ] [x]\cdot [y]=[x+y] [x]⋅[y]=[x+y]。
commitment scheme 的一个经典应用是： the Prover needs to convince the Verifier that the values he commits to satisfy a certain algebraic relation。 即 the Prover commits to x 1 , ⋯ , x v x_1,\cdots,x_v x1,⋯,xv and the Verifier wants to know that D ( x 1 , ⋯ x v ) = 0 D(x_1,\cdots x_v)=0 D(x1,⋯xv)=0 for an algebraic circuit D defined over K K K or over the integers。 若 D D D仅适用linear operations，则利用commitment的同态属性，Verifier可自己计算a commitment to D ( x 1 , ⋯ , x v ) D(x_1,\cdots,x_v) D(x1,⋯,xv) and Prover opens this to reveal 0。 但是，当 D D D中有乘法时，则需要a zero-knowledge protocol来让the Prover convinces the Verifier that three committed values x , y , z x,y,z x,y,z 满足 x y = z xy=z xy=z。
-
在 Cramer 等人1999年论文《Efficient multiparty computations secure against an adaptive adversary》中，利用homomorphic commitments over any finite field K K K构建了类似的multiplication protocol，相应的soundness error为 1 / ∣ K ∣ 1/|K| 1/∣K∣，当 K K K为a field with small size (constant or logarithmic in the security parameter)时，soundness error 1 / ∣ K ∣ 1/|K| 1/∣K∣值过大。为了实现smaller error，目前知道的唯一解决办法是repeat the protocol，相应的communication complexity为 Θ ( K u ) \Theta(\mathcal{K}u) Θ(Ku) for soundness error 2 − u 2^{-u} 2−u and commitment size为 K \mathcal{K} K bits。
-
Fujisaki等人1997年论文《 Statistical zero knowledge protocols to prove modular polynomial relations》 和 Damg˚ard 等人 2002年论文《 A statistically-hiding integer commitment scheme based on groups with hidden order》 中提出了a multiplication protocol for integer commitments，相应的communication complexity 为 Θ ( K + l + k ) \Theta(\mathcal{K}+l+k) Θ(K+l+k)，其中 k k k为Prover’s secret integers的bit size，同时需要依赖额外的假设——strong RSA assumption。若我们考虑仅需要factoring假设的commitment scheme时，相应的complexity为 Θ ( ( K + k ) l ) \Theta((\mathcal{K}+k)l) Θ((K+k)l)。
-
Cramer等人2009年论文《On the amortized complexity of zero-knowledge protocols》中 指出，很多应用中Prover需要make many ZK proofs of similar statements，因此可以进一步进行改进——make the amortized complexity per proof be small by combining all the proofs into one protocol。 在本文中即意味着，the Prover commits to x i , y i , z i x_i,y_i,z_i xi,yi,zi for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l 然后wants to convince the Verifier that x i y i = z i x_iy_i=z_i xiyi=zi for all i i i。Cramer等人2009年论文《On the amortized complexity of zero-knowledge protocols》中的算法实现了amortized complexity Θ ( K + l ) \Theta(\mathcal{K}+l) Θ(K+l)，但是要求所有的 x i x_i xi是一样的（或者所有的 y i y_i yi是一样的），这在实际应用时很难满足。
-
构建了a zero-knowledge protocol，适用于任意的 x i , y i , z i x_i,y_i,z_i xi,yi,zi，同时适于任意的homomorphic commitment scheme。 当选择standard unconditionally binding and computationally hiding commitment scheme时，the amortized complexity为 O ( u l ⋅ K ) O(\frac{u}{l}\cdot \mathcal{K}) O(lu⋅K) bits for error probability 2 − u 2^{-u} 2−u。相比于Cramer 等人1999年论文《Efficient multiparty computations secure against an adaptive adversary》的 Θ ( K u ) \Theta(\mathcal{K}u) Θ(Ku)改进了 l l l倍。 （特别地，当 l = u l=u l=u，amortized complexity为 O ( K ) O(\mathcal{K}) O(K)。）
-
实现了unconditionally secure homomorphic commitments assuming preprocessing。可以使协议的效率更高，as only a constant number of multiplications per commitment is required。
-
当需要verify l l l instances of an algebraic circuit D D D over K K K with v v v inputs，相当于：given committed values x i , j , z i x_{i,j},z_i xi,j,zi with i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l and j = 1 , ⋯ , v j=1,\cdots,v j=1,⋯,v，Prover需要证明 D ( x i , 1 , ⋯ , x i , v ) = z i D(x_{i,1},\cdots,x_{i,v})=z_i D(xi,1,⋯,xi,v)=zi for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l。The amortized cost to verify one circuit with multiplicative depth δ \delta δ为 O ( 2 δ K + v K + δ log l ) O(2^{\delta}\mathcal{K}+v\mathcal{K}+\delta\log l) O(2δK+vK+δlogl) bits for an error probability of 2 − l 2^{-l} 2−l，与circuit size无关。 对于具有small multiplicative depth 的circuit（如 the classes K − S A C 0 K-SAC^0 K−SAC0或 K − S A C 1 K-SAC^1 K−SAC1），这种方法具有优势，the amortized communication cost要小于the number of multiplications in D D D。
-
允许Verifier将function的计算外包给第三方，只要Verifier choose the random challenge in the protocol，this would be secure if the prover is malicous and the third party is semi-honest。
-
最终实现的zero-knowledge protocol为：使用black-box access to homomophic commitments to k k k-bit integers。为了check l l l integer multiplications and error probability 2 − l 2^{-l} 2−l，the amortized complexity 为 O ( K + k + l log ( l ) ) O(\mathcal{K}+k+l\log(l)) O(K+k+llog(l))。当其中的commitment使用standard computationally secure scheme时，相比于之前需要strong RSA assumption的方案，此处不需要任何assumption。
-
当使用information theoretically secure commitments based on preprocessing时，本文构建的协议具有perfect zero-knowledge against general verifiers。 当使用standard computationally secure commitments时，仅具有honest verifier zero-knowledge。
-
本文用到的技术有点类似于[IKOS09]中的“MPC-in-the-head”技术，但是有以下差异：both strategies都用到了“virtual players”，即，the Prover in his head imagines n n n players that receive shares of his secret values and he must later reveal information to the verifier relating to these shares。[IKOS09]中的协议complexity为 O ( n ) O(n) O(n)，因为其Prover需commit to the view of each virtual player。而本文利用了commitment scheme的同态属性，将complexity降为 O ( log n ) O(\log n) O(logn)，这也是为啥our amortized overhead vanishes instead of being constant, as one would get using MPC-in-the-head。 另外，将本文协议和“multiparty computation in the head” 技术结合，在某些参数情况下可改进其communication complexity。
-
同时期，Ben_Sasson等人2011年论文《Near-linear unconditionally-secure multiparty computation with a dishonest minority》中展示了a multiparty protocol for honest majority that checks several multiplicative relations on secret-shared values with low amortized complexity。该技术基于secret sharing，但是the checking works in a different way since in that setting there is no single prover who knows all values。
本文的研究成果可应用于：
-
give ZK proofs for satisfiability of a Boolean circuit C C C：Prover commits to the bits on each wire in the circuit，然后opens the output as 1 and shows that, for each AND-gate, the corresponding multiplicative relation holds for the committed bits。 若基于ideal commitment model，[IKOS09] 实现了constant communication overhead和polynomial computation overhead。 [DIK10] 中则实现了communication overhead和computation overhead均为poly-logarithmic。 而若使用ideal homomorphic commitment model，本文的协议实现了communication overhead和computation overhead均为constant。 而若使用information theoretically secure homomophic scheme，则需要额外的local computation，相应的communication overhead为constant的，computation overhead为polynomial。与[IKOS09]相比，涉及的constant值更小。同时，对于linear operations，本文不需要任何communication cost。
-
类似于[CDN01]中所示，可基于additively homomorphic encryption scheme实现general multiparty computation。相比于之前的技术，a player可用本文协议证明that his input satisfy a given condition much more efficiently that by previous techniques。
-
可用于anonymous credentials和group signatures。可基于Fiat-Shamir heuristic来实现non-interactive zero-knowledge proof。当需要证明a committed number在指定范围内时，一种解决方案是——可用[Bou00]中的proof技术来"transfer" the values to an integer commitment scheme来证明。其本质是multiplication proofs，因此可使用本文的方案来实现。
[ v ] [v] [v] 表示a commitment to v v v。 假设commitment操作对应于an additive group。
该commitment scheme具有同态属性： [ v ] ⋅ [ v ′ ] = [ v + v ′ ] [v]\cdot [v']=[v+v'] [v]⋅[v′]=[v+v′] for all v , v ′ v,v' v,v′ in the proper domain (either a finite field K K K or the integers)。
v ⃗ = ( v 1 , ⋯ , v m ) \vec{v}=(v_1,\cdots,v_m) v =(v1,⋯,vm) 为a vector with entries in K K K (or in the integers)。 [ v ⃗ ] [\vec{v}] [v ]表示a vector of commitments, one to each coordinate in v ⃗ \vec{v} v 。 若 u ⃗ = ( u 1 , ⋯ , u m ) \vec{u}=(u_1,\cdots,u_m) u =(u1,⋯,um)为a vector of the same length as v ⃗ \vec{v} v 时，则 [ v ⃗ ] u ⃗ = ∏ i [ v i ] u i [\vec{v}]^{\vec{u}}=\prod_i[v_i]^{u_i} [v ]u =∏i[vi]ui，实际为a commitment containing the inner product of u ⃗ \vec{u} u and v ⃗ \vec{v} v 。
[ u ⃗ ] ∗ [ v ⃗ ] [\vec{u}]*[\vec{v}] [u ]∗[v ]表示the component-wise product。
(1) Field Scenario： 设 K K K 为a finite field， L L L为an extension of K K K，本文考虑 K K K为a small constant size field的情况。 设 a ∈ L a\in L a∈L为Verifier的private valuse，假设Prover有a list A A A of uniform values u 1 , ⋯ , u i , ⋯ ∈ K u_1,\cdots,u_i,\cdots\in K u1,⋯,ui,⋯∈K，且对每一个 u i u_i ui Prover同时有a value m u i = a ⋅ u i + b u i m_{u_i}=a\cdot u_i+b_{u_i} mui=a⋅ui+bui，其中 b u i b_{u_i} bui为uniform in L L L且为Verifier的private value。 可将 m u i m_{u_i} mui看成是an information theoretic message authentication code (MAC) on u i u_i ui，而将 ( a , b u i ) (a,b_{u_i}) (a,bui) 看成是the key to open such a MAC on u i u_i ui。如[BDOZ11, DPSZ12]等论文中所示，可通过a functionality for the preprocessing phase of a multiparty computation protocol来实现。 相应的commitment可设计为：
- Prover为了commit to v ∈ K v\in K v∈K，Prover首先将 u − v u-v u−v发送给Verifier。
- 然后设置 m v = m u = a ⋅ u + b u m_v=m_u=a\cdot u+b_u mv=mu=a⋅u+bu，其中 u u u 为the first unused value in the list A A A。
- Verifier更新相应的key值 b v = b u + a ⋅ ( u − v ) b_v=b_u+a\cdot (u-v) bv=bu+a⋅(u−v)。
- 最终的commitment to
v
v
v值为：
而open commitment
[
v
]
[v]
[v]时，Prover可将
v
,
m
v
v,m_v
v,mv发送给Verifier，Verifier验证
a
⋅
v
+
b
v
=
m
v
a\cdot v+b_v=m_v
a⋅v+bv=mv是否成立即可。
以上commitment具有的属性为：
- unconditionally binding。错误的概率不高于 1 / ∣ L ∣ 1/|L| 1/∣L∣。实际设计师，通常要求 ∣ L ∣ = 2 Θ ( K ) |L|=2^{\Theta(\mathcal{K})} ∣L∣=2Θ(K)，其中 K \mathcal{K} K为security parameter。
- unconditionally hiding。即Verifer收到a commitment u − v u-v u−v only knows a a a, b u 1 , ⋯ , b u i , ⋯ b_{u_1},\cdots,b_{u_i},\cdots bu1,⋯,bui,⋯，这些均与 v v v无关。
- 同态属性，即满足
[
v
]
⋅
[
v
′
]
=
[
v
+
v
′
]
[v]\cdot [v']=[v+v']
[v]⋅[v′]=[v+v′]：
（2）Integer Scenario 此处构建 unconditionally secure commitments on k k k-bits integers。 与之前的Field Scenario 不同： 设 a a a为a prime in the interval [ − 2 K , ⋯ , 2 K ] [-2^{\mathcal{K}},\cdots,2^{\mathcal{K}}] [−2K,⋯,2K]， a a a为Verifier的私有信息。假设Prover有a list A A A of integer values u 1 , ⋯ , u i , ⋯ u_1,\cdots,u_i,\cdots u1,⋯,ui,⋯ 均匀分布在 [ − 2 k + K , ⋯ , 2 k + K ] [-2^{k+\mathcal{K}},\cdots,2^{k+\mathcal{K}}] [−2k+K,⋯,2k+K]，且对于每个 u i u_i ui，Prover还有相应的integer m u i = a ⋅ u i + b u i m_{u_i}=a\cdot u_i+b_{u_i} mui=a⋅ui+bui，其中 b u i b_{u_i} bui为a uniform integer in [ − 2 k + 3 K , ⋯ , 2 k + 3 K ] [-2^{k+3\mathcal{K}},\cdots,2^{k+3\mathcal{K}}] [−2k+3K,⋯,2k+3K] 且为Verifier的私有信息。 相应的commitment构建过程为：
-
Prover为了commit to the integer v ∈ [ − 2 k , ⋯ , 2 k ] v\in [-2^k,\cdots,2^k] v∈[−2k,⋯,2k]，Prover将 u − v u-v u−v发送给Verifier。
-
Prover设置 m v = m u = a ⋅ u + b u m_v=m_u=a\cdot u+b_u mv=mu=a⋅u+bu，其中 u u u为the first unused value in the list A A A。
-
Verifier更新相应的key值 b v = b u + a ⋅ ( u − v ) b_v=b_u+a\cdot (u-v) bv=bu+a⋅(u−v)。
-
整个commitment to v v v可表示为：
-
为了open commitment [ v ] [v] [v]，Prover仅需将 v , m v v,m_v v,mv发送给Verifier，Verifier验证 a ⋅ v + b v = m v a\cdot v+b_v=m_v a⋅v+bv=mv 是否成立即可。
以上commitment scheme具有的属性为：
- 同态属性
- unconditionally hiding
- unconditionally binding (基于factoring假设——a ( k + K ) (k+\mathcal{K}) (k+K)-bits integer contains at most ( k + K ) / K (k+\mathcal{K})/\mathcal{K} (k+K)/K prime factors of length K \mathcal{K} K and the number of K \mathcal{K} K-bits primes is Θ ( 2 K / K ) \Theta(2^{\mathcal{K}}/\mathcal{K}) Θ(2K/K)，此commitment scheme的error probability为 Θ ( ( ( k + K ) / K ) ⋅ ( 2 K / K ) ) = Θ ( ( k + K ) / 2 K ) \Theta(((k+\mathcal{K})/\mathcal{K})\cdot (2^{\mathcal{K}}/\mathcal{K}))=\Theta((k+\mathcal{K})/2^{\mathcal{K}}) Θ(((k+K)/K)⋅(2K/K))=Θ((k+K)/2K)，若 k = O ( K ) k=O(\mathcal{K}) k=O(K)，则the error probability为 O ( K / 2 K ) O(\mathcal{K}/2^{\mathcal{K}}) O(K/2K)。 )
目前的linear secret sharing scheme有：
- [KW93, CDM00] 中的monotone span program formalism。
- [CCG+07] 中的linear code based formalism。
本文关注的是支持several values from the underlying field can be shared simultaneously，详细的设计思路为： 设置
K
K
K 为a finite field，
m
m
m为a positive integer。针对
m
m
m-dimensional
K
K
K-vector space
K
m
K^m
Km，index set为
I
=
{
1
,
2
,
⋯
,
m
}
I=\{1,2,\cdots,m\}
I={1,2,⋯,m}，
x
⃗
=
(
x
i
)
i
∈
I
\vec{x}=(x_i)_{i\in I}
x
=(xi)i∈I 表示the coordinates of
x
⃗
∈
K
m
\vec{x}\in K^m
x
∈Km。接下来，考虑的都是finite space的linear functions。同时注意，由于这些函数具有（additive） group homomorphisms，通常为regular，即each element in the image has the same number of pre-images，又称为the cardinality of the kernel。 For a non-empty set
A
⊆
I
A\subseteq I
A⊆I, the restriction to
A
A
A is the
K
K
K-linear function： 
设
C
⊆
K
m
C\subseteq K^m
C⊆Km 为 a
K
K
K-linear subspace，
A
,
S
∈
I
A,S\in I
A,S∈I为non-empty sets。则可称
S
S
S offers uniformity if
π
S
(
C
)
=
K
∣
S
∣
\pi_S(C)=K^{|S|}
πS(C)=K∣S∣，注意by the regularity of
π
S
\pi_S
πS，若
c
c
c为uniform in
C
C
C，则
π
S
(
c
)
\pi_S(c)
πS(c)为uniform in
K
∣
S
∣
K^{|S|}
K∣S∣。 接下来从subspace
C
C
C中选择一组随机vector，即
c
⃗
∈
C
\vec{c}\in C
c
∈C，使得
π
S
(
c
⃗
)
=
s
⃗
\pi_S(\vec{c})=\vec{s}
πS(c
)=s
，其中
S
S
S为a set offering uniformity，
s
⃗
\vec{s}
s
为the vector of secret values to be shared。The shares are then the coordinates of
c
⃗
\vec{c}
c
that are not in
S
S
S。
当存在a function f : K ∣ A ∣ → K ∣ S ∣ f:K^{|A|}\rightarrow K^{|S|} f:K∣A∣→K∣S∣ 时，则可称 A A A determines S S S，对所有的 v e c c ∈ C vec{c}\in C vecc∈C，有 ( f ∘ π A ) ( c ⃗ ) = π S ( c ⃗ ) (f\circ \pi_A)(\vec{c})=\pi_S(\vec{c}) (f∘πA)(c )=πS(c )。若相应的 f f f存在，其为 K K K-linear function。若 c ⃗ \vec{c} c 为uniformly chosen from C C C 且 A A A determines S S S，则 π A ( c ⃗ ) \pi_A(\vec{c}) πA(c ) determines π S ( c ⃗ ) \pi_S(\vec{c}) πS(c ) with probability 1。
若存在满射的
K
K
K-linear function： 
则可称
A
A
A和
S
S
S为mutually independent。 注意当且仅当
A
A
A和
S
S
S为mutually independent 且
A
A
A determines
S
S
S时，
π
S
(
C
)
=
{
0
}
\pi_S(C)=\{0\}
πS(C)={0}。 特别地，若
c
⃗
\vec{c}
c
is uniformly chosen from
C
C
C，则
π
S
(
C
)
≠
{
0
}
\pi_S(C)\neq\{0\}
πS(C)={0}；若
A
A
A和
S
S
S为independent的，则
π
A
(
c
⃗
)
\pi_A(\vec{c})
πA(c
)和
π
S
(
c
⃗
)
\pi_S(\vec{c})
πS(c
)为独立分布的。
- 乘法属性：（Schur-product，或称 component-wise product，或称 Hadamard product）
- Sweeping vecotrs：
基本信息为：
- public info：commitments [ x ⃗ ] , [ y ⃗ ] , [ z ⃗ ] [\vec{x}],[\vec{y}],[\vec{z}] [x ],[y ],[z ]。【注意此处的commitment size为 3 l 3l 3l，即本论文的vector commitment size为 O ( l ) O(l) O(l)，其中 l l l为vector size。】
- private info： x ⃗ = ( x 1 , ⋯ , x l ) , y ⃗ = ( y 1 , ⋯ , y l ) , z ⃗ = ( z 1 , ⋯ , z l ) \vec{x}=(x_1,\cdots,x_l),\vec{y}=(y_1,\cdots,y_l),\vec{z}=(z_1,\cdots,z_l) x =(x1,⋯,xl),y =(y1,⋯,yl),z =(z1,⋯,zl)。
- relation： x ⃗ ∗ y ⃗ = z ⃗ \vec{x}*\vec{y}=\vec{z} x ∗y =z ，即 for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l，有 x i y i = z i x_iy_i=z_i xiyi=zi。
假设Prover和Verifier均同意使用 an l l l-multisecret linear secret sharing scheme ( C , S ) (C,S) (C,S)， 有 d d d个players，提供 r ^ \hat{r} r^-product reconstruction，具有的privacy threshold为 t t t。 定义generator g : K l + e → C g: K^{l+e}\rightarrow C g:Kl+e→C for ( C , S ) (C,S) (C,S)，KaTeX parse error: Expected 'EOF', got '\right' at position 22: …}:K^{l+\hat{e}}\̲r̲i̲g̲h̲t̲ ̲\hat{C} for ( C ^ , S ) (\hat{C},S) (C^,S)，相应的public basis分别为 K l + e K^{l+e} Kl+e和 K l + e ^ K^{l+\hat{e}} Kl+e^，这样the linear mapping g g g (或 g ^ \hat{g} g^) can be computed as the action of a matrix M M M (或 M ^ \hat{M} M^)。
基本思路为：
- 当 ( C , S ) (C, S) (C,S)具有product reconstruction特性时，Prover使用 ( C , S ) (C,S) (C,S)来表示secret shares x ⃗ , y ⃗ \vec{x},\vec{y} x ,y ，使用 ( C ^ , S ) (\hat{C},S) (C^,S)来表示secret shares z ⃗ \vec{z} z ，这样 the resulting vectors of shares c ⃗ x , c ⃗ y , c ⃗ ^ z \vec{c}_x,\vec{c}_y,\hat{\vec{c}}_z c x,c y,c ^z满足 c ⃗ x ∗ c ⃗ y = c ⃗ ^ z \vec{c}_x * \vec{c}_y = \hat{\vec{c}}_z c x∗c y=c ^z。
- Prover commits to the randomness used in all sharings，借助同态属性，Verifier可计算commitments to any desired share。
- Verifier选择 t t t个随机的coordinate位置，要求Prover open the commitments to the shares in those positions。
- Verifier可验证the shares in x ⃗ , y ⃗ \vec{x},\vec{y} x ,y multiply to the shares in z ⃗ \vec{z} z 。
整个机制是安全的，因为任意的 t t t个shares不会泄露任何信息。但是若 x ⃗ ∗ y ⃗ ≠ z ⃗ \vec{x}*\vec{y}\neq \vec{z} x ∗y =z ，则 c ⃗ x ∗ c ⃗ y = c ⃗ ^ z \vec{c}_x * \vec{c}_y=\hat{\vec{c}}_z c x∗c y=c ^z最多仅在 r ^ \hat{r} r^个位置成立，因此，Verifier有很大的概率能找到相应的位置使得验证不通过。
详细的协议表示为： 
。。。。。。
设 D D D 为an arithmetic circuit over K K K with v v v inputs and one ouput， c ⃗ 1 , ⋯ , c ⃗ v ∈ K m \vec{c}_1,\cdots,\vec{c}_v\in K^m c 1,⋯,c v∈Km，定义 D ( c ⃗ 1 , ⋯ , c ⃗ v ) ∈ K m D(\vec{c}_1,\cdots,\vec{c}_v)\in K^m D(c 1,⋯,c v)∈Km 为the vector whose j j j-th coordinate为 D ( ( c ⃗ 1 ) j , ⋯ , ( v ⃗ ) j ) D((\vec{c}_1)_j,\cdots,(\vec{v})_j) D((c 1)j,⋯,(v )j)，即apply D D D to the j j j-th coordinate of all input vectors。
相应的circuit证明协议为： 
