Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1）

Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》。 该论文中主要针对e-voting mix-net构建中用到的shuffle homomorphic encryption场景，提出了an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions 算法，该算法在prove和verify the correctness of a shuffle of 100,000 ElGamal ciphertexts用时均在2分钟左右。

1. 背景知识

• 本论文的argument具有sublinear communication complexity，当shuffle N ( = m × n ) N(=m\times n) N(=m×n) ciphertexts时，需要传送 O ( m + n ) O(m+n) O(m+n) group elements 且若 m = n m=n m=n则最小的communication complexity 为 O ( N ) O(\sqrt{N}) O(N ​)。
• prover的computational complexity为 O ( N log ⁡ m ) O(N\log{m}) O(Nlogm) exponentiations for constant round arguments或者 若允许logarithmic number of rounds的话， prover的computational complexity可为 O ( N ) O(N) O(N) exponentiations。
• verifier的计算比较轻量。
• 构建full shuffle argument的基础为：Neff’s approach [Nef01] is based on the invariance of polynomials under permutation of the roots，即Nef01的shuffle算法基于的是：多项式的根permutation的话，其最终形成的多项式是不变的—— f ( x ) = ( x − r 1 ) ( x − r 2 ) . . . ( x − r n ) f(x)=(x-r_1)(x-r_2)...(x-r_n) f(x)=(x−r1​)(x−r2​)...(x−rn​)。
• 引入了multi-exponentiation argument，用于hide committed values。
• 基于hidden committed values的shuffle argument。与[Gro09]类似，做了些微改进。
• 主要是利用了EIGamal encryption的乘法同态性和Pedersen commitment的加法同态性。所以需要构建相应的common reference string σ = ( p k , c k ) \sigma =(pk,ck) σ=(pk,ck)， p k pk pk为EIGamal encryption的public keys， c k ck ck为Pedersen commitment的commitment key，两者可以基于不同的group实现，但是要求具有相同的prime order q q q。

其中EIGamal的知识详见：博客 EIGamal encryption VS Pairing encryption。

1. EIGamal具有乘法同态性：
2. Pedersen commitment具有加法同态性：

2. Shuffle argument

需要an argument of knowledge of permutation π ∈ ∑ N \pi\in \sum_{N} π∈∑N​ and randomness { ρ i } i = 1 N \{\rho_i\}_{i=1}^N {ρi​}i=1N​ such that for given ciphertexts { C i } i = 1 N \{C_i\}_{i=1}^N {Ci​}i=1N​, { C i ′ } i = 1 N \{C_i^{'}\}_{i=1}^N {Ci′​}i=1N​ we have C i ′ = C π ( i ) ε p k ( 1 ; ρ i ) C_i^{'}=C_{\pi(i)} \varepsilon_{pk}(1;\rho_i) Ci′​=Cπ(i)​εpk​(1;ρi​)。 Shuffle argument由multi-exponentiation argument和product argument组成：

• multi-exponentiation argument：用于证明the product of a set of ciphertexts raised to a set of committed exponents yields a particular ciphertext。
• product argument：用于证明a set of committed values has a particular product。

主要的实现步骤为：

1. Prover对permutation进行commit，即commit to π ( 1 ) , … , π ( N ) \pi(1),…,\pi(N) π(1),…,π(N)。【第一组commitment】
2. Verifier给Prover challenge x x x。
3. Prover commit to x π ( 1 ) , … , x π ( N ) x^{\pi(1)},…,x^{\pi(N)} xπ(1),…,xπ(N)。【第二组commitment】
4. Prover提供argument，证明其知道相应的openings of the commitments to permutations of respectively 1 , … , N 1,…,N 1,…,N和 x 1 , … , x N x^1,…,x^N x1,…,xN，同时证明这两组commitment采用的是相同的permutation。【即第二组commitment是对 x 1 , … , x N x^1,…,x^N x1,…,xN permuted in an order that was fixed before the prover saw x x x】。

• 4.1 为了证明两组commitment采用的是相同的permutation，Verifier给Prover random challenges y y y和 z z z。
• 4.2 Prover commit to 一系列 d 1 − z = y π ( 1 ) + x π ( 1 ) − z , … , d N − z = y π ( N ) + x π ( N ) − z d_1-z=y\pi(1)+x^{\pi(1)}-z,…,d_N-z=y\pi(N)+x^{\pi(N)}-z d1​−z=yπ(1)+xπ(1)−z,…,dN​−z=yπ(N)+xπ(N)−z。使用product argument，即可证明 ∏ i = 1 N ( d i − z ) = ∏ i = 1 N ( y i + x i − z ) \prod_{i=1}^{N}(d_i-z)= \prod_{i=1}^{N}(yi+x^i-z) ∏i=1N​(di​−z)=∏i=1N​(yi+xi−z)等式成立。【想象其为 z z z的N阶多项式， d i d_i di​是对其root根 y i + x i yi+x^i yi+xi的permute，基于Schwartz-Zippel lemma可知，针对特定的 z z z值Prover伪造找到相应 d i d_i di​值使该等式成立的概率不高于 N q − 1 \frac{N}{q-1} q−1N​，可忽略。同理，针对 y y y值，Prover伪造两组commitment使等式成立的概率也可忽略。】

5. Prover使用multi-exponentiation argument来证明存在 ρ \rho ρ值，使得$ ∏ i = 1 N C i x i = ε p k ( 1 ; ρ ) ∏ i = 1 N ( C i ’ ) x π ( i ) \prod_{i=1}^{N}C_i^{x^i}=\varepsilon_{pk}(1;\rho)\prod_{i=1}^{N}(C_i^’)^{x^{\pi(i)}} ∏i=1N​Cixi​=εpk​(1;ρ)∏i=1N​(Ci’​)xπ(i)等式成立。即可实现基于密文 C i ， C i ’ C_i，C_i^’ Ci​，Ci’​的shuffle证明，而Verifier不知道具体的permutation规则。

详细的shuffle argument算法流程为：

3. Multi-exponentiation Argument

将第二节shuffle argument算法流程中的 a ⃗ , b ⃗ \vec{a},\vec{b} a ,b 向量表示为N=n*m矩阵。 其中的multi-exponentiation argument可表示为： 简化描述，假设 ρ = 0 \rho=0 ρ=0，public info: C 1 ⃗ , . . . , C m ⃗ , C \vec{C_1},...,\vec{C_m},C C1​ ​,...,Cm​ ​,C，witness: a 1 ⃗ , . . . , a m ⃗ \vec{a_1},...,\vec{a_m} a1​ ​,...,am​ ​，需要证明： C = ∏ i = 1 m C i ⃗ a i ⃗ C=\prod_{i=1}^{m}\vec{C_i}^{\vec{a_i}} C=∏i=1m​Ci​ ​ai​ ​。 基本流程为：

1. Prover依次对 a 1 ⃗ , . . . , a m ⃗ \vec{a_1},...,\vec{a_m} a1​ ​,...,am​ ​进行commit，将相应的 c A ⃗ = ( c o m c k ( a 1 ⃗ ; r 1 ) , . . . , c o m c k ( a m ⃗ ; r m ) ) \vec{c_A}=(com_{ck}(\vec{a_1};r_1),...,com_{ck}(\vec{a_m};r_m)) cA​ ​=(comck​(a1​ ​;r1​),...,comck​(am​ ​;rm​))发送给verfier
2. Prover计算 E k = ∏ 1 ≤ i , j ≤ m ; j = ( k − m ) + i C i ⃗ a j ⃗ E_k=\prod_{1\leq i,j\leq m;j=(k-m)+i}\vec{C_i}^{\vec{a_j}} Ek​=∏1≤i,j≤m;j=(k−m)+i​Ci​ ​aj​ ​，将相应的 E 1 , E 2 , . . . , E 2 m − 1 E_1,E_2,...,E_{2m-1} E1​,E2​,...,E2m−1​发送给Verifier【其中 E m = C E_m=C Em​=C】。
3. Verifier给Prover challenge x x x。
4. Prover计算 a ⃗ = ∑ j = 1 m x j a j ⃗ \vec{a}=\sum_{j=1}^{m}x^j\vec{a_j} a =∑j=1m​xjaj​ ​，将相应的向量 a ⃗ \vec{a} a 发送给verifier。
5. Verifier验证 C x m ∏ k = 1 ; k ≠ m 2 m − 1 E k x k = ∏ i = 1 m C i ⃗ ( x m − i a ⃗ ) C^{x^m}\prod_{k=1;k\neq m}^{2m-1}E_k^{x^k}=\prod_{i=1}^{m}\vec{C_i}^{(x^{m-i}\vec{a})} Cxm∏k=1;k​=m2m−1​Ekxk​=∏i=1m​Ci​ ​(xm−ia )成立，则可证明 C = ∏ i = 1 m C i ⃗ a i ⃗ C=\prod_{i=1}^{m}\vec{C_i}^{\vec{a_i}} C=∏i=1m​Ci​ ​ai​ ​成立。相应的理论依据为： ∏ i = 1 2 m − 1 E k x k = ∏ i = 1 m C i ⃗ ( x m − i ∑ j = 1 m x j a j ⃗ ) = ∏ i = 1 m C i ⃗ ( x m − i a ⃗ ) = C x m ∏ k = 1 ; k ≠ m 2 m − 1 E k x k = C x m ∏ k = 1 ; k ≠ m 2 m − 1 ∏ 1 ≤ i , j ≤ m ; j = ( k − m ) + i C i ⃗ a j ⃗ x k = C x m ∏ i = 1 m C i ⃗ ∑ 1 ≤ j ≤ m ; k = m − i + j ; k ≠ m a j ⃗ x k \prod_{i=1}^{2m-1}E_k^{x^k}=\prod_{i=1}^{m}\vec{C_i}^{(x^{m-i}\sum_{j=1}^{m}x^j\vec{a_j})}=\prod_{i=1}^{m}\vec{C_i}^{(x^{m-i}\vec{a})}=C^{x^m}\prod_{k=1;k\neq m}^{2m-1}E_k^{x^k}=C^{x^m}\prod_{k=1;k\neq m}^{2m-1}{\prod_{1\leq i,j\leq m;j=(k-m)+i}\vec{C_i}^{\vec{a_j}x^k}}=C^{x^m}\prod_{i=1}^{m}{\vec{C_i}}^{\sum_{1\leq j\leq m;k=m-i+j;k\neq m}\vec{a_j}x^k} ∏i=12m−1​Ekxk​=∏i=1m​Ci​ ​(xm−i∑j=1m​xjaj​ ​)=∏i=1m​Ci​ ​(xm−ia )=Cxm∏k=1;k​=m2m−1​Ekxk​=Cxm∏k=1;k​=m2m−1​∏1≤i,j≤m;j=(k−m)+i​Ci​ ​aj​ ​xk=Cxm∏i=1m​Ci​ ​∑1≤j≤m;k=m−i+j;k​=m​aj​ ​xk，于是有： C x m = ∏ i = 1 m C i ⃗ ( x m − i ∑ j = 1 m x j a j ⃗ − ∑ 1 ≤ j ≤ m ; k = m − i + j ; k ≠ m a j ⃗ x k ) = ∏ i = 1 m C i ⃗ a i ⃗ x m = ( ∏ i = 1 m C i ⃗ a i ⃗ ) x m C^{x^m}=\prod_{i=1}^{m}{\vec{C_i}}^{(x^{m-i}\sum_{j=1}^{m}x^j\vec{a_j}-\sum_{1\leq j\leq m;k=m-i+j;k\neq m}\vec{a_j}x^k)}=\prod_{i=1}^{m}{\vec{C_i}}^{\vec{a_i}x^m}=(\prod_{i=1}^{m}{\vec{C_i}}^{\vec{a_i}})^{x^m} Cxm=∏i=1m​Ci​ ​(xm−i∑j=1m​xjaj​ ​−∑1≤j≤m;k=m−i+j;k​=m​aj​ ​xk)=∏i=1m​Ci​ ​ai​ ​xm=(∏i=1m​Ci​ ​ai​ ​)xm，从而有： C = ∏ i = 1 m C i ⃗ a i ⃗ C=\prod_{i=1}^{m}\vec{C_i}^{\vec{a_i}} C=∏i=1m​Ci​ ​ai​ ​成立。【注意，原论文有的公式有点typo。】

以上流程，可能存在witness泄露的来源点有： 1）为了防止在rewind 第3和第4步时，Verifier用不同的challenge x x x从Prover那获取不同的 a ⃗ = ∑ j = 1 m x j a j ⃗ \vec{a}=\sum_{j=1}^{m}x^j\vec{a_j} a =∑j=1m​xjaj​ ​，从而造成witness a 1 ⃗ , . . . , a m ⃗ \vec{a_1},...,\vec{a_m} a1​ ​,...,am​ ​的泄露，因此需要引入random vector a 0 ⃗ ← Z q n \vec{a_0}\leftarrow \mathbb{Z}_q^n a0​ ​←Zqn​，Prover先commit to a 0 ⃗ \vec{a_0} a0​ ​，然后收到challeng x x x后，直接reveal a ⃗ = a 0 ⃗ + ∑ j = 1 m x j a j ⃗ \vec{a}=\vec{a_0}+\sum_{j=1}^{m}x^j\vec{a_j} a =a0​ ​+∑j=1m​xjaj​ ​，从而能保证witness不被泄露。 2）在第2步给Verifier传输的 E k = ∏ 1 ≤ i , j ≤ m ; j = ( k − m ) + i C i ⃗ a j ⃗ E_k=\prod_{1\leq i,j\leq m;j=(k-m)+i}\vec{C_i}^{\vec{a_j}} Ek​=∏1≤i,j≤m;j=(k−m)+i​Ci​ ​aj​ ​值，可能也会造成witness a 1 ⃗ , . . . , a m ⃗ \vec{a_1},...,\vec{a_m} a1​ ​,...,am​ ​的泄露。可在此基础上乘以randomn ciphertext ε p k ( G b k ; τ k ) \varepsilon_{pk}(G^{b_k};\tau_k) εpk​(Gbk​;τk​)【相应地，Prover需在收到challeng x x x前，对 b k b_k bk​进行commit c B k = c o m c k ( b k ; s k ) c_{B_k}=com_{ck}(b_k;s_k) cBk​​=comck​(bk​;sk​)】，为了仍然保证 E m = C E_m=C Em​=C成立，则要求 b m = 0 , s m = 0 b_m=0,s_m=0 bm​=0,sm​=0。 若考虑 ρ ≠ 0 \rho\neq0 ρ​=0的正常情况，为了仍然保证 E m = C E_m=C Em​=C成立，相应的要求 τ m = ρ \tau_m=\rho τm​=ρ。 (      a 0 ⃗      a 1 ⃗ ⋯     a m − 1 ⃗      a m ⃗ ) ( C 1 ⃗ C 2 ⃗ ⋮ C m ⃗ ) ( C 1 ⃗ a 0 ⃗ C 1 ⃗ a 1 ⃗ ⋱ C 1 ⃗ a m − 1 ⃗ C 1 ⃗ a m ⃗ C 2 ⃗ a 0 ⃗ C 2 ⃗ a 1 ⃗ ⋱ C 2 ⃗ a m − 1 ⃗ C 2 ⃗ a m ⃗ ⋱ ⋱ ⋱ ⋱ ⋱ C m ⃗ a 0 ⃗ C m ⃗ a 1 ⃗ ⋱ C m ⃗ a m − 1 ⃗ C m ⃗ a m ⃗ ) ε p k ( G b 2 m − 1 ; τ 2 m − 1 ) E 2 m − 1 ⋮ ε p k ( G b m + 1 ; τ m + 1 ) E m + 1 ε p k ( 1 ; ρ ) E m ε p k ( G b 0 ; τ 0 ) E 0 ε p k ( G b 1 ; τ 1 ) E 1 ⋯ ε p k ( G b m − 1 ; τ m − 1 ) E m − 1 \begin{matrix} & \begin{pmatrix} \ \ \ \ \vec{a_0}&\ \ \ \ \vec{a_1} & \cdots &\ \ \ \vec{a_{m-1}} &\ \ \ \ \vec{a_m} \end{pmatrix} & \\ \begin{pmatrix} \vec{C_1}\\ \vec{C_2}\\ \vdots\\ \vec{C_m} \end{pmatrix} & \begin{pmatrix} \vec{C_1}^{\vec{a_0}}& \vec{C_1}^{\vec{a_1}} & \ddots & \vec{C_1}^{\vec{a_{m-1}}} & \vec{C_1}^{\vec{a_m}}\\ \vec{C_2}^{\vec{a_0}} & \vec{C_2}^{\vec{a_1}} & \ddots & \vec{C_2}^{\vec{a_{m-1}}} & \vec{C_2}^{\vec{a_m}}\\ \ddots & \ddots & \ddots & \ddots & \ddots\\ \vec{C_m}^{\vec{a_0}} & \vec{C_m}^{\vec{a_1}} & \ddots & \vec{C_m}^{\vec{a_{m-1}}} & \vec{C_m}^{\vec{a_m}} \end{pmatrix} & \begin{matrix} \\ \varepsilon_{pk}(G^{b_{2m-1}};\tau_{2m-1})E_{2m-1}\\ \vdots\\ \varepsilon_{pk}(G^{b_{m+1}};\tau_{m+1})E_{m+1}\\ \varepsilon_{pk}(1;\rho)E_m \end{matrix} \\ & \begin{matrix} \varepsilon_{pk}(G^{b_0};\tau_0)E_0& \varepsilon_{pk}(G^{b_1};\tau_1)E_1 & \cdots & \varepsilon_{pk}(G^{b_{m-1}};\tau_{m-1})E_{m-1} \end{matrix}& \end{matrix} ⎝⎜⎜⎜⎛​C1​ ​C2​ ​⋮Cm​ ​​⎠⎟⎟⎟⎞​​(    a0​ ​​    a1​ ​​⋯​   am−1​ ​​    am​ ​​)⎝⎜⎜⎜⎜⎛​C1​ ​a0​ ​C2​ ​a0​ ​⋱Cm​ ​a0​ ​​C1​ ​a1​ ​C2​ ​a1​ ​⋱Cm​ ​a1​ ​​⋱⋱⋱⋱​C1​ ​am−1​ ​C2​ ​am−1​ ​⋱Cm​ ​am−1​ ​​C1​ ​am​ ​C2​ ​am​ ​⋱Cm​ ​am​ ​​⎠⎟⎟⎟⎟⎞​εpk​(Gb0​;τ0​)E0​​εpk​(Gb1​;τ1​)E1​​⋯​εpk​(Gbm−1​;τm−1​)Em−1​​​εpk​(Gb2m−1​;τ2m−1​)E2m−1​⋮εpk​(Gbm+1​;τm+1​)Em+1​εpk​(1;ρ)Em​​​ 详细算法如下图所示：

3.1 Prover的计算压力

在上述Multi-exponentiation Argument中，Prover需要计算 E 0 , ⋯   , E 2 m − 1 E_0,\cdots,E_{2m-1} E0​,⋯,E2m−1​，即对于 k = 1 , ⋯   , 2 m − 1 k=1,\cdots,2m-1 k=1,⋯,2m−1，有： E k = ∏ 1 ≤ i , j ≤ m ; j = ( k − m ) + i C i ⃗ a j ⃗ = ∏ i = 1 , j = 1 ; j = ( k − m ) + i m , m C i ⃗ a j ⃗ E_k=\prod_{1\leq i,j\leq m;j=(k-m)+i}\vec{C_i}^{\vec{a_j}}=\prod_{i=1,j=1;j=(k-m)+i}^{m,m}\vec{C_i}^{\vec{a_j}} Ek​=∏1≤i,j≤m;j=(k−m)+i​Ci​ ​aj​ ​=∏i=1,j=1;j=(k−m)+im,m​Ci​ ​aj​ ​ 对应的计算量有： 1）需有 m 2 m^2 m2次 C i ⃗ a j ⃗ \vec{C_i}^{\vec{a_j}} Ci​ ​aj​ ​次product运算； 2） C i ⃗ a j ⃗ = ∏ l = 1 n C i l a i l \vec{C_i}^{\vec{a_j}}=\prod_{l=1}^{n}C_{il}^{a_{il}} Ci​ ​aj​ ​=∏l=1n​Cilail​​有 n n n次exponentiation运算in H \mathbb{H} H。 从而 E k E_k Ek​有 m n 2 mn^2 mn2次exponentiation运算in H \mathbb{H} H。

当 m m m较大时，Prover的计算压力很大，可通过多项式插值（FFT）或Toom-Cook或增加Verifier与Prover交互次数等方式来优化：

• FFT：
• Toom-Cook：
• 增加Verifier与Prover交互次数：基本思路为： m × m m\times m m×m矩阵内元素真正有效的仅为对角线上的元素，不需要计算所有 m 2 m^2 m2个元素，转为将 m × m m\times m m×m矩阵切分为小的block矩阵 μ × μ \mu \times \mu μ×μ（其中 m = μ m ′ m=\mu m' m=μm′），只需要关注对角线上的block，并使用递归证明对角线block上的内容即可。 ( C 1 ⃗ a 1 ⃗ ⋱ C 1 ⃗ a m − 1 ⃗ C 1 ⃗ a m ⃗ C 2 ⃗ a 1 ⃗ ⋱ C 2 ⃗ a m − 1 ⃗ C 2 ⃗ a m ⃗ ⋱ ⋱ ⋱ ⋱ C m ⃗ a 1 ⃗ ⋱ C m ⃗ a m − 1 ⃗ C m ⃗ a m ⃗ ) \begin{pmatrix} \vec{C_1}^{\vec{a_1}} & \ddots & \vec{C_1}^{\vec{a_{m-1}}} & \vec{C_1}^{\vec{a_m}}\\ \vec{C_2}^{\vec{a_1}} & \ddots & \vec{C_2}^{\vec{a_{m-1}}} & \vec{C_2}^{\vec{a_m}}\\ \ddots & \ddots & \ddots & \ddots\\ \vec{C_m}^{\vec{a_1}} & \ddots & \vec{C_m}^{\vec{a_{m-1}}} & \vec{C_m}^{\vec{a_m}} \end{pmatrix} ⎝⎜⎜⎜⎜⎛​C1​ ​a1​ ​C2​ ​a1​ ​⋱Cm​ ​a1​ ​​⋱⋱⋱⋱​C1​ ​am−1​ ​C2​ ​am−1​ ​⋱Cm​ ​am−1​ ​​C1​ ​am​ ​C2​ ​am​ ​⋱Cm​ ​am​ ​​⎠⎟⎟⎟⎟⎞​

3.2 Prover的计算优化实现

针对3.1中的计算压力，在https://github.com/3for/verifiable-shuffle中分别做了相应的优化实现：

# This parameter determine which version of the program is executed.
# 0 stands for no optimization inside of the code
# 1 uses multi-exponentiation techniques
# 2 uses multi-exponentiation techniques and FFT to find values E_i
# 3 uses multi-exponentiation techniques, extra interaction and Toom-Cook 4 to find values E_i, in this case m =16 or 64\n
3

参考资料： [1] 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》 [2] PPT 《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》 [3] 博客 向量的Hadamard product VS Inner product [4] 博客 EIGamal encryption VS Pairing encryption