1. 背景知识
Lipmaa 2014年论文《Efficient NIZK Arguments via Parallel Verification of Benes Networks》，提出了：
- 一种新的permutation argument，通过使用2014年论文Almost Optimal Short Adaptive Non-Interactive Zero Knowledge 中的product and shift arguments 和paralellizable variant of the Benes network。
Groth 2010年论文 Short Pairing-based Non-interactive Zero-Knowledge Arguments 中提出的CIRCUITSAT argument采用模块化的方式，由一些basic argument——少于10个的basic Hadamard product和permutation argument组成：
- Hadamard product：Given three committed vectors, one of them is an entry-wise product of the other two。
- permutation argument：Given two comitted vectors and a public permutation π \pi π，the coefficients of one vector are π \pi π-permuted coefficients of the second vector。【注意：其中的permutation为public的，对verifier亦为公开的。】
存在的问题是：
- 以上Hadamard product和permutation argument 需要的CRS长度均为vector dimension n n n的平方。
- 以上Hadamard product和permutation argument Prover的computation (in exponentiations)也均为vector dimension n n n的平方。
在Almost Optimal Short Adaptive Non-Interactive Zero Knowledge和Efficient Modular NIZK Arguments from Shift and Product 的基础上，借助Benes Networks to combine Θ ( log n ) \Theta(\log n) Θ(logn) product and shift arguments。
