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

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分钟左右。

• 本论文的argument具有sublinear communication complexity，当shuffle $N(=m\times n)$N(=m×n) ciphertexts时，需要传送$O(m+n)$O(m+n) group elements 且若$m=n$m=n则最小的communication complexity 为 $O(\sqrt{N})$O(N​)。
• prover的computational complexity为$O(N\log{m})$O(Nlogm) exponentiations for constant round arguments或者 若允许logarithmic number of rounds的话， prover的computational complexity可为$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−r1​)(x−r2​)...(x−rn​)。
• 引入了multi-exponentiation argument，用于hide committed values。
• 基于hidden committed values的shuffle argument。与[Gro09]类似，做了些微改进。
• 主要是利用了EIGamal encryption的乘法同态性和Pedersen commitment的加法同态性。所以需要构建相应的common reference string $\sigma =(pk,ck)$σ=(pk,ck)，$pk$pk为EIGamal encryption的public keys，$ck$ck为Pedersen commitment的commitment key，两者可以基于不同的group实现，但是要求具有相同的prime order $q$q。

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

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

参考资料：
[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