Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments

1. 背景知识

在Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》论文的基础上，Lipmaa 2012年论文《Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments 》中指出：
NIZK proofs无法在无random oracles（如Fiat-Shamir heuristics）或trusted setup（如common reference string）的情况下构建成功。如[BFM88]论文中展示了如何通过common reference string (CRS) model来构建NIZK proofs。

在减少communication complexity和verifier’s computational complexity这两方面，有大量的文献做了研究。

相比于Groth 2010论文，Lipmaa取得了如下进展：

主要特点为：

• 采用了非对称pairing（运算效率更高），而不是对称pairing；

• 采用了更弱的安全假设——
  Power Symmetric Discrete Logarithm，而不是
  Power Computational Diffifie-Hellman。本论文主要基于两个assumption: computational assumption($\hat{\Lambda-PSDL}$Λ−PSDL^​)和knowledge assumption($\Lambda-PKE$Λ−PKE)，而Groth10中采用的是$[an^2]-PKE$[an2]−PKE和$[an^2]-CPDH$[an2]−CPDH假设。
  
  

Lipmaa 2012的改进流程如下：
1）将$\vec{a},\vec{b},\vec{c}$a,b,c的commit key缩小统一均为$g_{\lambda_1}, ..., g_{\lambda_n}$gλ1​​,...,gλn​​：

从而使构建的$F(x)$F(x)多项式的最高阶不大于$2\lambda_n$2λn​，CRS大小$|\hat{\Lambda}|<2\lambda_n$∣Λ^∣<2λn​ group elements【for $i\in [n], g^{2\lambda_i}不应在CRS中$i∈[n],g2λi​不应在CRS中】，而不再是Groth10的$\Theta (n^2)$Θ(n2)。通过构建 a progression-free subset of odd integers of cardinality $n$n，对应地CRS仅需有$\Theta (\lambda_n)=n^{1+o(1)}$Θ(λn​)=n1+o(1)个 generators $\{g^{x^l}: l\in \hat{\Lambda}\}${gxl:l∈Λ^}

2. Progression-Free Sets

Progression-Free Sets定义为：

3. Knowledge commitment scheme

4. Hadamard product argument

5. Permutation Argument

6. Circuit Satisfiability Constant Size NIZK Argument