概述
构造了一个具有完美完备性、完美零知识性和计算合理性的电路可满足性非交互式零知识论证，该论证具有亚线性大小和非常高效的公开可验证性
如果允许CRS较大，则非交互式ZKA需要的群元素可以降低至恒定数量
构造依赖于具有配对的群，安全性基于两个新的密码假设，不采用FS启发式和RO模型
1 Introduction
Goldwasser、Michali和Rackoff$[GMR89]$提出的零知识证明是密码学中的基本构造块，在许多协议中都有使用，零知识证明使证明者能够在不泄漏任何其他信息的情况下说服验证者一条语句的真实性，中心属性体现在完备性、合理性和零知识的概念中
零知识证明依赖于证明者和验证者之间的交互，许多密码任务是离线执行的；例如，签名或加密消息，对于这些任务，需要具有非交互式零知识（NIZK）证明，其中不存在交互，证明仅包含从验证人到验证人的单个消息，但是只有BPP中的语言在没有任何设置的平原模型中具有NIZK证明$[Ore87,GO94,GK96]$
Blum、Feldman和Michali$[BFM88]$在公共参考字符串模型中引入了NIZK证明，其中Prover和Verifier都可以访问以可信方式生成的CRS，这种NIZK证明有许多应用，从早期选择的密文攻击安全公钥密码系统$[DDN00,Sah01]$到最近的高级签名方案$[CGS07,BW06]$，因此，对基本假设$[FLS99,BCNP04,GO07]$、效率$[Dam92,DDP02,KP98,Gro10]$和NIZK证明$[DP92、Sah01,DDO+02]$提供的安全保证进行了大量研究
基于标准密码假设的NIZK证明过去效率低下，在实践中没有用处，为了克服这种低效性，应用密码学家依赖于所谓的Fiat-Shamir启发式，通过使用加密哈希函数计算Verifier的挑战，将公共掷币交互式零知识证明转换为NIZK Argument
Fiat-Shamir启发式可以给出非常有效的NIZK论证，这些论证在RO模型$[BR93]$中是安全的，其中加密哈希函数被建模为随机函数。例如，可以使用Fiat-Shamir启发式将亚线性大小的交互式公共掷币零知识论证$[Kil92]$转换为亚线性大小的非交互式零知识论证$[Mic00]$
不幸的是，有几个协议示例在RO模型中是安全的，但无论使用哪个哈希函数，都没有任何安全的标准模型实例化$[CGH98,CGH04,MRH04,BBP04,Nie02]$，这里特别相关的是Goldwasser和Kalai$[GK03]$演示了一个基于公共掷币识别方案的签名方案，该方案在随机预言模型中是安全的，但在现实生活中是不安全的，虽然Fiat-Shamir启发式可能对“自然”协议是安全的，但值得研究替代方法
克服传统NIZK证明效率低下的另一种方法是使用非交互式指定Verifier证明，在指定Verifier证明中，该证明不可公开验证；只能由指定的验证者进行验证，Damgård、Fazio和Nicolosi$[DFN06]$基于与Paillier加密相关的假设，给出了电路可满足性的有效线性尺寸非交互指定Verifier证明，指定Verifier证明足以用于某些应用，例如Cramer和Shoup的选择密文攻击安全公钥密码系统$[CS98]$
然而，在许多其他情况下，缺乏公开验证是有问题的，例如当只有一个指定的验证器时，不可能使用它们来构造高级数字签名，例如环签名和群签名，因为这里的不可否认性依赖于公开的可验证性
最近关于NIZK证明的工作使用了双线性群来提高效率，Groth、Ostrovsky和Sahai$[GOS06b,GOS06a]$给出了电路可满足性的NIZK证明，其中证明由$O(|C|)$个群元素组成，其中$C$表示电路中的门的数量，该方案的NIZK可以被设置为具有完美合理性和计算零知识性或者计算合理性和完美零知识性
Boyen、Waters、Groth和Sahai$[BW06,BW07,Gro06,GS08]$的工作探索了如何建立直接适用于双线性群的有效NIZK证明，而不是通过电路可满足性，在某些特殊情况下，例如在Chandran、Groth和Sahai$[CGS07]$的环签名中，这些技术导致了亚线性大小的NIZK证明，但一般来说，NIZK证明中的群元素数随着语句的大小线性增长
Abe和Fehr$[AF07]$给出了一种基于承诺而非加密的构造，但由于每条导线都有承诺，因此它们的电路尺寸也呈线性增长
从电路可满足性的NP完全问题来看，NIZK证明在电路大小上呈线性增长的原因是它们加密了电路中每条导线的值，Gentry的新全同态密码系统$[Gen09]$可以将NIZK证明简化为见证大小的线性：Prover加密电路的输入，并使用密码系统的同态属性计算电路的输出，然后Prover给出输入密文有效且输出密文包含1的NIZK证明，全同态加密只有在电路有小的Witness时才有帮助；如果电路具有线性数量的输入导线，则产生的NIZK证明在电路尺寸上也将是线性的
1.1 Our Contribution
Michali的CS证明$[Mic00]$表明了亚线性大小NIZK论证的可能性，但尽管进行了十多年的研究，Fiat-Shamir启发式是唯一已知的构造亚线性大小NIZK参数的策略，我们的目标是引入一种新型的亚线性大小NIZK论证，其中安全性不依赖于RO模型
我们构造了具有完美完备性、计算可靠性和完美零知识的电路可满足性的NIZK参数（定义见第2节），NIZK论证很短，验证效率很高，但Prover使用了超线性数量的群运算
我们首先给出一个NIZK论证，该论证由恒定数量的群元素组成，但有一个较长的CRS，然后我们证明了以增加NIZK论证的大小为代价来减少CRS的大小是可能的，从而使它们在电路大小上同时呈亚线性
本文提出的NIZK论证的合理性依赖于q-computational power DH和q-power knwoledge of exponent假设，q-CPDH假设是一种正常的计算困难性假设，但是q-PKE为一个所谓的指数知识假设
指数知识假设被认为是不可证伪的$[Nao03]$，但是采用非标准假设可能是不可避免的，因为Abe和Fehr$[AF07]$已经证明，NP完备语言的统计零知识性NIZK论证不能将”直接黑盒“的安全性规约到标准密码假设，除非$NP\subseteq P/Poly$成立
下表给出了本文和其他关于电路可满足性的NIZK证明与论证方案的比较，其中$k$代表安全参数，$G$为群元素的大小，$M,E$分别岱庙乘法和指数运算的次数，$P$代表双线性群中配对的次数
与其他基于配对的NIZK论证相比，我们的论证更小，验证速度更快，Prover使用超线性数量的乘法，计算成本可能会超过线性数的幂，公开可验证性意味着NIZK的论证可以转移；它们可以复制并分发到许多不同的实体，这些实体可以进行自己的独立验证，Verifier只需支付计算NIZK论证的一次性成本，而所有Verifier都享有低传输带宽和高效验证的优势
基于Fiat-Shamir启发式的NIZK论证比我们的NIZK论证更有效，这些是交互式零知识论证（交互似乎有帮助），依赖加密哈希函数来计算验证器的挑战，合理性的安全证明依赖于哈希函数可以建模为随机硬币来源的假设，这似乎意味着至少某种类型的知识提取假设，即只有当对手事先知道输入时，才能获得哈希值
此外，加密哈希函数是确定性的，因此将其视为随机函数显然是错误的，相反，据我们所知，q-KPE假设是正确的，即使随机预言假设是错误的，即使有导致不安全参数的Fiat-Shamir启发式示例$[GK03]$，基于Fiat-Shamir启发式的特定NIZK参数可能是正确的，然而，我们认为值得研究FS启发式的替代方案
Perfect Zaps
CRS模型假设一个可信的设置，用于生成公共参考字符串，并使其可供Prover和Verifier使用，如果没有这样的设置，我们仍然可以得到一个亚线性大小的两步可公开验证的witness不可区分的论证，其中Verifier的第一条消息可以多次重用，即所谓的Zap$[DN00]$，如下所示：Verifier生成一个CRS，Verifier序验证CRS是否格式良好（我们的CRS不是随机位字符串，但它确实具有某种结构，可以验证其格式良好），并且现在可以使用Verifier初始消息作为CRS进行任意多个ZAP，由于我们的NIZK论证是完全零知识，Zaps将完全无法区分
1.2 Outline of Our NIZK Argument
本文构造一个NIZK论证，证明是否存在一个二进制电路$C$的输入，使该电路的输出为1
在损失常数因子的情况下，我们可以假设$C$完全由与非门构建，此外如果我们标记输出导线$a$，我们可以通过令$a=\lnot(a\wedge b)$来强制$a=1$的方式来向电路中加入自环，从而？？？？？？？？没看懂这句话
NIZK论证依赖于长度缩减承诺，其中本文可以仅使用恒定数量的群元素在有限域$\Z_p$上承诺$n$个值，且要求承诺方案具有同态性，这意味着我们可以将两个承诺组合成一个新的
我们还使用由常量群元素组成的非交互式论证来证明关于承诺值的下列属性
- Entry-wise product：对$(a_1,...,a_n),(b_1,...b_n),(u_1,...,u_n)$的承诺值$c,d,v$满足$u_i=a_ib_i$
- Permutation：对$(a_1,...,a_n),(b_1,...b_n)$的承诺值$c,d$，满足$b_i=a_{\rho(i)}$其中$\rho$为公开的关于$n$个元素的置换
当$n=2N$时，Prover由一个电路可满足性的输入，其中$(a_1,...,a_n),(b_1,...b_n)$分别代表电路中每个与非门的输入，记0为false，1为true，若$u_i$为第$i$个与非门的输出，则有$1-u_i=a_ib_i$
Prover对下列三个大小为$2N$的元组进行承诺
$$ (a_1,...,a_N,b_1,...b_N),(b_1,...,b_N,0,...0),(u_1,...,u_N,0,...0) $$
然后Prover需要给出一个Entry-wise product论证，其中$c,d,v$都是对$(a_1,...,a_N,b_1,...b_N)$的承诺，用于证明对于所有的$i$，满足$a_i=a^2_i,b_i=b^2_i$，这一系列的约束条件限制了$(a_1,...,a_N,b_1,...b_N)\in \{0,1\}$
还需要注意的是，一个与非门的输出可能会作为另一个与非门的输入，这意味着$a_{i_1},...,a_{i_l},b_{j_1},...,b_{j_m}$可能会有相同的赋值，此时Prover需要为所有这些值选择一个包含循环的置换$i_1\rarr i_2\rarr...\rarr i_l \rarr j_1+N\rarr j_2+N\rarr ... \rarr j_m+N \rarr i_1$，并给出一个对$(a_1,...,a_N,b_1,...b_N)$的承诺置换论证，这确保了所有集的值满足输出导线$a_{i_2}=a_{i_1},...,b_{j_1}=a_{i_l},...,b_{j_m}=b_{j_{m-1}}$，从而$(a_1,...,a_N,b_1,...b_N)$与电路一致
Prover使用额外的承诺和entry-wise product和置换论证来表明其他两个元组$(b_1,...,b_N,0,...0),(u_1,...,u_N,0,...0)$与电路布线和$(a_1,...,a_N,b_1,...b_N)$一致
最后Prover使用entry-wise product论证来表明$(a_1,...,a_N,b_1,...b_N),(b_1,...,b_N,0,...0)$的entry-wise product为$(1-u_1,...,1-u_N,0,...0)$
上述展示了如何获取用于电路可满足性的恒定大小的NIZK论证，但是为了使用entry-wise product论证和置换论证，CRS的大小为$O(N^2)$个群元素，第九节展示了如何利用承诺将CRS减小到$n<N$
本文构造了一个合适的承诺方案，具有非交互式的entry-wise product和置换论证，承诺方案本质上是一个Pedersen承诺的变体，其中承诺密钥为$(g,g^x,...,g^{x^q})$，对$(a_1,...,a_q)$的承诺为一个群元素
$$ g^r \prod_{i=1}^q(g^{x^i})^{a_i} $$
该承诺方案的优点是，DLOG是一个简单的多项式$r+\sum^q_{i=1}a_ix^i$，此时若将两个承诺进行配对，我们可以得到指数为两个多项式的乘积，通过对多项式的乘积进行适当的线性组合，可以将entry-wise乘积和置换表示为这些多项式系数上的方程，然后利用q-CPDH假设得到这些系数相同的结论，从而承诺值分别满足entry-wise和置换关系
当配对承诺时（此时相当于指数中多项式相乘），存在各种奇怪的交叉项，NIZK论证的作用时抵消这些项，通常单个群元素与$g$配对就足以抵消所有的交叉项，因此非交互式的entry-wise乘积和置换本身就可以做到很高效
为了证明本文的NIZK论证满足合理性，需要对这些多项式系数进行推理，然而恶意的Prover可能会在不知道揭示值的情况下创建一个承诺，此时我们需要用q-PKE来确保Prover在给出NIZK论证时，证明他确实知道某个承诺的揭示值，这意味着存在一个抽取器，提供与Prover相同的输入时可以重建承诺值和揭示值
2 Definitions
- $R$：一个可以高效计算的二元关系
- $(C,w)\in R$：称$C$为statement，$w$为witness
- $L$：一个包含关系$R$的NP语言
- $L_N,R_N$：限制语言和关系的大小为$N$
- $K(k)$：关于$R$的非交互式论证的CRS生成器，输入为安全参数$k$和一些额外输入$N\in \N$，$N$表示statement的大小
- $\sigma$：算法$K$输出的CRS
- $P(\sigma,C,w)$：Prover算法，运行时间为PPT，输出证明$\pi$
- $V(\sigma ,C,\pi)$：Verifier算法，运行时间为PPT，输出0为拒绝，输出1为接收
称$(K,P,V)$为一个关于$R$的论证，满足下列性质
Perfect Completeness：完备性指的是诚实的Prover总是可以说服诚实的Verifier，对于任意敌手$\mathcal A$和$N=k^{O(1)}$，完备性满足
$$ Pr[\sigma \larr K(1^k,N) ;(C,w)\larr \mathcal A(\sigma );\pi \larr P(\sigma,C,w):V(\sigma,C,\pi)=1 \ if \ (C,w)\in R_N]=1 $$
也就是若Prover和Verifier都按照协议执行，则Verifier一定会输出1
Computational Soundness：合理性指的是，Prover无法让Verifier接收一个错误的陈述，对于非均匀多项式时间敌手$\mathcal A$和$N=k^{O(1)}$，计算合理性满足
$$ Pr[\sigma \larr K(1^k,N) ;(C,\pi)\larr \mathcal A(\sigma ):C\notin L \ \wedge V(\sigma ,C,\pi)=1]\approx 0 $$
简单来说就是Verifier一定会拒绝恶意的Prover
Perfect Witness-indistinguishability：证据不可区分指的是，在具有多个witness时，Verifier无法区分Prover使用的是哪个witness，对于任意敌手$\mathcal A$和$N=k^{O(1)}$，完美证据不可区分满足
$$ Pr[\sigma \larr K(1^k,N) ;(C,w_0,w_1)\larr \mathcal A(\sigma);\pi\larr P(\sigma,C,w_0):(C,w_0),(C,w_1)\in R_N\wedge \mathcal A(\pi)=1]=\\Pr[\sigma \larr K(1^k,N) ;(C,w_0,w_1)\larr \mathcal A(\sigma);\pi\larr P(\sigma,C,w_1):(C,w_0),(C,w_1)\in R_N\wedge \mathcal A(\pi)=1] $$
简单来说，就是在statement有多个witness时无法区分Prover用的是哪个witness生成的$\pi$
Perfect Zero-knowledge：零知识表示不会泄露除了statement为真以外的任何知识，若存在一个多项式模拟器$S=(S_1,S_2)$，其中$S_1$输出模拟的CRS和模拟陷门，$S_2$输入CRS、模拟陷门和statement并生成一个模拟论证，若任意敌手$\mathcal A$和$N=k^{O(1)}$满足下列性质，则称非交互论证$(K,P,V)$为完美零知识的
$$ Pr[\sigma \larr K(1^k,N) ;(C,w)\larr \mathcal A(\sigma );\pi \larr P(\sigma,C,w):(C,w)\in R_N \wedge \mathcal A(\pi)=1]=\\Pr[(\sigma,\tau) \larr S_1(1^k,N) ;(C,w)\larr \mathcal A(\sigma );\pi \larr S_2(\sigma,\tau,C):(C,w)\in R_N \wedge \mathcal A(\pi)=1] $$
简单来说，完美零知识就是任意敌手都无法区分真实协议生成的$\pi$和模拟器生成的$\pi$
3 Bilinear Groups
- 给定两个函数$f,g:\N\rarr [0,1]$，若对于$\forall c>0$，有$|f(k)-g(k)|=O(k^{-c})$，则记为$f(k)\approx g(k)$
- 当$f(k)\approx0$时记$f$为可忽略的，当$f(k)\approx 1$时记$f$为压倒性的
- $y=A(x;r)$：记算法$A$，输入$x$和随机性$r$，输出$y$
- $y\larr A(x)$：当随机性$r$为随机选择时采用这种记法
- $y\larr S$：从集合$S$中随机选择一个值$y$
- $[n]$：表示集合$\{1,2,...,n\}$
Bilinear Groups
记$\mathcal g$以安全参数$k$为输入，输出一个双线性群$(p,G,G_T,e)\larr \mathcal g(1^k)$，满足
- $p$：一个长度为$k$比特的素数
- $G,G_T$：阶为$p$的循环群
- $e$：$G\times G$说的双线性映射，满足$\forall a,b,:e(g^a,g^b)=e(g,g)^{ab}$
- 若$g$为$G$的生成元，则$e(g,g)$为$G_T$的生成元
- 可以高效确定$G,G_T$中的成员，群上运算和配对$e$都是可高效计算的，生成元也可高效生成
- 对群和群元素的描述的大小均为$O(k)$比特
NIZK论证的安全性基于两个新的假设：q-PKE假设和q-CPDH假设
The q-Power Knowledge of Exponent Assumption(KEA)：最早由Damgard$[Dam91]$提出，具体可以看Knowledge of Exponent Assumption(KEA1)
Bellare和Palacio$[BP04]$扩展到了KEA3，具体可以看KEA3
KEA3在$[AF07]$中被用于双线性群，并改名叫做扩展的指数知识假设（extended knowledge of exponent assumption
q-PKE假设实际上时KEA和KEA3的广义化，意思是给定$(g,g^x,...,g^{x^q},g^{\alpha x},...,g^{\alpha x^q})$，敌手无法在不知道$(a_0,...,a_q)$的情况下构造$c=\prod ^q_{i=0}(g^{x^i})^{a_i}$和$\hat c=\prod ^q_{i=0}(g^{\alpha x^i})^{a_i}$，满足$\hat c =c^\alpha$
利用Bellare和Palacio[BP04]中的记法，记$(y;z)\larr (\mathcal A||\chi_\mathcal A)(x)$表示$\mathcal A$输入$x$输出$y$，$\chi_\mathcal A$输入相同的$x$但是输出$z$
Definition 1(q-PKE)：$q(k)$-power knowledge of exponent assumption，说的是对于群$\mathcal G$，满足对于任意的非均匀PPT时间敌手$\mathcal A$，存在一个非均匀PPT抽取器$\chi_\mathcal A$，满足
$$ Pr[(p,G,G_T,e)\larr \mathcal g(1^k);g\larr G\backslash\{1\};\alpha,x\larr \Z^*_p;\sigma=(p,G,G_T,e,g,g^x,...,g^{x^q},g^{\alpha x},...,g^{\alpha x^q});(c,\hat c;a_0,...,a_q)\larr (\mathcal A||\chi_\mathcal A)(\sigma):\hat c=c^\alpha\wedge c\neq \prod ^n_{i=0}g^{a_ix^i}=0] $$
本文的附录A给出了一个启发式论证来证明q-PKE假设在一般群模型中成立
The q-Computational power Diffie-Hellman Assumption：也即给定$(g,g^x,...,g^{x^q},g^\beta,g^{\beta x},...,g^{\beta x^q})$，难以计算出缺失的某个元素$g^{\beta x^j}$
CDH假设是给定$g,g^\beta,g^x$，难以计算$g^{\beta x}$，q-CPDH实际上是对CDH的广义化
Definition 2(q-CPDH)：$q(k)$-computational power Diffie-Hellman assumption，说的是对于群$\mathcal G$和所有的$j\in \{0,1,...,q\}$、所有的非均匀PPT敌手$\mathcal A$，满足
$$ Pr[(p,G,G_T,e)\larr \mathcal g(1^k);g\larr G\backslash\{1\};\beta,x\larr \Z^*_p;\sigma=(p,G,G_T,e,g,g^x,...,g^{x^q},g^\beta,g^{\beta x},...,g^{\beta x^{j-1}},g^{\beta x^{j+1}},...,g^{\beta x^q}):y=g^{\beta x^j}]\approx 0 $$
同样在附录A给出了一个启发式论证
4 Knowledge Commitment
本文的NIZK proof采用一个Pedersen承诺的变体，将$a_1,...,a_q$承诺至$c=g^r\prod _{i\in [q]}g_i^{a_i}$
在3SAT的NIZK论证的安全性证明中，我们需要提取$a_1,...,a_q$的承诺至，但是承诺方案时完美隐藏的，且不会揭示承诺值，因此我们要求Prover创建一个承诺值$\hat c=\hat g^r \prod _{i\in [q]}\hat g_i^{a_i}$，并依赖于q-PKE假设来抽取承诺值，此时称$(c,\hat c)$为知识承诺（Knowledge Commitment），因为Prover不能在不知道承诺值的情况下给出一个合法的承诺值
然后接下来看几个算法
Key Generation
选择$gk=(p,G,G_T,e)\larr \mathcal g(1^k);g\larr G\backslash\{1\};\alpha,x\larr \Z^*_p$，承诺密钥为$ck=(gk,g,g_1,...,g_q,\hat g,\hat g_1,...,\hat g_q)=(gk,g,g^x,...,g^{x^q},g^{\alpha x},...,g^{\alpha x^q})$，陷门密钥为$tk=x$
Commitment
若对$a_1,...,a_q$进行承诺，选择$r\larr \Z_p$，计算$(c,\hat c)$如下
$$ c=g^r\prod _{i\in [q]}g_i^{a_i},\hat c=\hat g^r \prod _{i\in [q]}\hat g_i^{a_i} $$
对于给定的$(c,\hat c)\in G^2$，可以通过验证$e(g,\hat c)=e(c,\hat g)$的方式验证承诺
Trapdoor commitment
选择陷门随机性$t\larr \Z_p$，然后计算承诺$(c,\hat c)=(g^t,\hat g^t)$
Trapdoor opening
陷门揭示算法对消息$a_1,...,a_q\in \Z_p$的揭示，返回随机性$r=t-\sum _{i\in [q]}a_ix^i$，此时满足$c=g^r\prod _{i\in [q]}g_i^{a_i},\hat c=\hat g^r \prod _{i\in [q]}\hat g_i^{a_i}$
该承诺方案具有与标准Pedersen承诺相似的性质
Theorem 1：上述承诺方案为完美陷门和计算绑定的，若q-PKE假设成立，则存在对于任意非均匀PPT的承诺者$\mathcal A$和一个非均匀PPT抽取器$\chi _\mathcal A$，在给定$\mathcal A$的输入（包括随机掷币）时计算承诺的内容
证明可以看原文$[1]$
4.1 Restriction Argument
考虑一个子集$S\subset [q]$和承诺值$c$， 我们需要一个论证，使得揭示$r,a_1,...,a_q$时，那些非零值所对应的下标在集合$S$内
换句话说，我们需要一个论证，其承诺值满足
$$ c=g^r\prod _{i\in S}g_i^{a_i} $$
此时论证的形式为
$$ \pi=h^r\prod_{i\in S}h_i^{a_i} $$
该论证对应于一个基于$(h,\{h_i\}_{i\in S})$的附加论证，具体如下
$Setup$：$gk\larr\mathcal G(1^k);ck\larr K_{commit}(gk)$
$CRS$：给定$(ck,S)$作为输入，选择随机性$\beta \larr \Z^*_p$，计算CRS：$\sigma=(h,\{h_i\}_{i\in S})=(g^\beta,\{g^\beta_i\}_{i\in S})$
$Statement$：一个有效的知识承诺$(c,\hat c)$
$P's \ witness$：揭示$r,\{a_i\}_{i\in S}$，满足$c=g^r\prod _{i\in S}g_i^{a_i},\hat c=\hat g^r\prod _{i\in S}\hat g_i^{a_i}$
$Argument$：计算$\pi=h^r\prod_{i\in S}h_i^{a_i}$
$Verification$：当且仅当$e(c,h)=e(g,\pi)$时Verifier输出1
这里有个定理
Theorem 2：上述限制性承诺是完美完备和完美证据不可区分的，若q-CPDH假设成立，则对于任意非均匀PPT敌手，其输出$(r,a_1,...,a_q,\pi)$，满足$a_i\neq0 \wedge i\notin S$且$\pi$为一个合法的限制性论证的概率可忽略
本文将限制性论证的合理性表述为：无法找到违反限制的承诺的揭示，由于承诺方案时完美隐藏的，因此不能排除违反限制的揭示的存在，但是如果这个定理成立，则意味着它是一个知识承诺，则从承诺者抽取道德承诺值也一定满足这个限制条件
证明可以看原文$[1]$
5 Common Reference String
本节描述如何生成NIZK论证中的CRS
CRS中包含知识承诺密钥$ck$，$q=n^2+3n-2$，将$q$划分为下列三个限制性子集
$$ \widetilde S=\{1,2,...,n\},\bar S=\{(n+1),2(n+1),...,n(n+1)\},\dot S=\{l\in [q]\ |\ l\neq 0 \ mod \ n+2\} $$
零知识模拟论证采用相同的CRS，NIZK论证的模拟陷门与知识承诺的模拟陷门一致
CRS Generation
输入$1^k,n$，执行下列步骤
- 生成双线性群$(p,G,G_T,e)\larr \mathcal g(1^k)$，令$gk=(p,G,G_T,e)$
- 选择生成元$g\larr G\backslash\{1\}$，选择$x,\alpha \larr \Z_p^*$，计算
$$ ck=(gk,g,g_1,...,g_q,\hat g,\hat g_1,...,\hat g_q)=(gk,g,g^x,...,g^{x^{n^2+3n-2}},g^\alpha ,g^{\alpha x},...,g^{\alpha x^{n^2+3n-2}}) $$
- 生成$\widetilde \sigma \larr K_{restrict}(ck,\widetilde S)$
- 生成$\bar \sigma \larr K_{restrict}(ck,\bar S)$
- 生成$\dot\sigma \larr K_{restrict}(ck,\dot S)$
然后得到CRS：$\sigma =(ck,\widetilde \sigma,\bar\sigma,\dot\sigma)$，模拟陷门$tk=x$
给定一个CRS，难以找到$1,x,...,x^q$的一个非平凡线性组合，因为可以在$\Z _p[X]$上运行多项式分解算法来计算根$x$
Lemma 1：若q-CPDH假设在$\mathcal G$上成立且$q=n^2+3n-2$，给出一个随机的CRS$\sigma$，一个非均匀PPT时间敌手只能以可忽略的概率找到一个非平凡线性组合$(a_0,...,a_q)$，满足$\sum^q_{i=0}a_ix^i=0$
证明可以看原文$[1]$ page11
Verifying the common reference string
上述方法得到的CRS具有特定的数学结构，但我们不知道从随机比特的公共串中生成它的提取过程
然而我们可以验证$(p,G,G_T,e)$确实描述的是一个双线性群，这意味着同样可以验证$\sigma$是一个正确的CRS
首先需要先验证所有$\sigma$中的群元素都是非平凡的，这意味着五个秘密指数$(x,\alpha ,\widetilde \beta,\bar \beta,\dot \beta )$都是非零值，然后利用配对操作来验证CRS的结构，也即进行下列五个检查
$$ \begin{aligned} &\forall i\in [q]:e(g,g_{i+1})=e(g_1,g_i)\\ &\forall i\in [q]:e(g,\hat g_{i})=e(\hat g,g_i)\\ &\forall i\in \widetilde S:e(g,\widetilde h_{i})=e(\widetilde h,g_i)\\ &\forall i\in \bar S:e(g,\bar h_{i})=e(\bar h,g_i)\\ &\forall i\in \dot S:e(g,\dot h_{i})=e(\dot h,g_i)\\ \end{aligned} $$
通过验证CRS，Prover可以确保论证是完美证据不可区分的，这意味着即便是CRS来源不可信（比如恶意的Verifier），我们仍然可以得到一个两步的完美证据不可区分的论证，也即Zaps[DN00]，该论证方案中Verifier在第一步中发送CRS，然后Prover在第二步中利用同一个CRS，对不公的statement给出多个公开可验证的论证
6 Product Argument
接下来介绍一下对内积论证
考虑下面这三个承诺
$$ \begin{aligned} &\forall i\in [n]:u_i=a_ib_i\\ &c=g^r\prod _{i\in [n]} g_i^{a_i}\\ &d=g^s\prod _{j\in [n]} g_{j(n+1)}^{b_j}\\ &v=g^t\prod _{j\in [n]} g_i^{u_i}\\ \end{aligned} $$
以及这三个承诺对应的限制性论证$\hat c,\widetilde c,\hat d,\widetilde d,\hat v,\widetilde v$，我们可以假设承诺者知道揭示值$(a_1,...,a_n),(b_1,...b_n),(u_1,...,u_n)$，然后给出一个对应三个群元素的论证$(\pi,\hat \pi,\dot \pi)$，使得这些论证对于揭示值满足$\forall i\in [n]:u_i=a_ib_i$
先解释一下这么做的原因，考虑一个小例子，承诺值$c=g^r\prod _{i\in [n]} g_i^{a_i},d=g^s\prod _{j\in [n]} g_{j(n+1)}^{b_j}$是为了确保$\forall i\in [n]: a_ib_i=0$，此时这两个承诺值的离散对数为
$$ \begin{aligned} &\sum_{i\in [n]}a_ix^i\\ &\sum_{j\in [n]}b_jx^{j(n+1)}\\ \end{aligned} $$
此时对应的配对$e(c,d)$的离散对数为
$$ (\sum_{i\in [n]}a_ix^i )\cdot (\sum_{j\in [n]}b_jx^{j(n+1) })=\sum_{i\in[n]}\sum_{j\in[n]} a_ib_jx^{i+j(n+1)}=\sum_{i\in[n]}a_ib_ix^{i(n+2)}+\sum_{i\in[n]}\sum_{j\in[n]\backslash \{i\}}a_ib_jx^{i+j(n+1)} $$
观察等式的最右侧的第一项，根据$\forall i\in [n]: a_ib_i=0$，这个项应当为0，但是第二个求和号很复杂，因此构造$\pi$时应当考虑消除这个贼复杂的项
注意到等式最右侧的第一项中，$x$的幂均为$n+2$的整数倍，而第二个求和号中的$x$的幂不包含这些数（因为第二项的第二个求和号是对$j\in[n]\backslash \{i\}$求和），因此可以通过设定适当的限制性论证来确保消除这个贼复杂的项，同时又不影响第一项
Prover计算
$$ \pi=\prod _{i\in[n]}\prod _{j\in [n]\backslash\{i\}}g_{i+j(n+1)}^{a_ib_j} $$
及其对应的限制性论证$\hat \pi,\dot \pi$，从而Prover可以证明他知道由$\dot S$限制的揭示值$(z,\{z_l\}_{l\in \dot S})$，此时Verifier可以验证$e(c,d)=e(g,\pi)$来验证Prover的论证
接下来看看合理性，给定$\pi,\hat \pi,\dot \pi$，且满足$e(c,d)=e(g,\pi)$，此时Verifier可以知道$\forall i\in [n]: a_ib_i=0$，Verifier通过计算下列等式来验证
$$ \sum _{i\in [n]}a_ib_ix^{i(n+2)}+\sum_{i\in[n]}\sum_{j\in[n]\backslash \{i\}}a_ib_jx^{i+j(n+1)} =z+\sum_{l\in\dot S}z_lx^l $$
注意前面提到的$\dot S=\{l\in [q]\ |\ l\neq 0 \ mod \ n+2\}$，因此论证$\pi$中$x$的幂不会为$n+2$的整数倍，也即$\pi$中不包含$x^{n+2},...,x^{n(n+2)}$，同时根据上面提到的，这么做也确保了包含$x^{n+2},...,x^{n(n+2)}$的项的系数一定是$a_ib_i$，如果存在一个$i$，满足$a_ib_i=0$，则我们可以得到一个关于$x$的非平凡多项式等式，根据Lemma 1，这意味着我们可以由该等式恢复出$x$并攻破q-PKE假设
更一般的情况，我们考虑$a_ib_i=u_i$而不是$a_ib_i=0$，此时如果我们计算$e(v,\prod _{j\in[n]}g_{j(n+1)})$，我们可以将$\prod _{j\in[n]}g_{j(n+1)}$视为对$(1,1,...,1)$的承诺，从而这个配对可以得到$x^{n+2},...,x^{n(n+2)}$的系数为$(u_1\cdot 1,...,u_n\cdot 1)$，此时若有$a_ib_i=u_i$，则配对$e(c,d)$和$e(v,\prod _{j\in[n]}g_{j(n+1)})$中$x^{n+2},...,x^{n(n+2)}$的项具有相同的系数，而其他项的系数均不同
根据前面提到的那个小例子，我们此时可以选择适当的$\pi$，这样就可以在$\dot S$的限制下抵消所有的其他系数不同的项，从而达到了论证的合理性
一般情况下承诺也具有随机性，我们可以选择$\pi$来抵消这些项
下面是完整的论证过程
- $Statement$：对$c,d,v\in G$承诺
- $P's \ witness$：揭示$(r,a_1,...,a_n),(s,b_1,...,b_n),(t,u_1,...,u_n)$，满足
$$ \begin{aligned} &\forall i\in [n]:u_i=a_ib_i\\ &c=g^r\prod _{i\in [n]} g_i^{a_i}\\ &d=g^s\prod _{j\in [n]} g_{j(n+1)}^{b_j}\\ &v=g^t\prod _{j\in [n]} g_i^{u_i}\\ \end{aligned} $$
- $Argument$：计算论证$(\pi,\hat \pi ,\dot \pi)$
$$ \begin{aligned} &\pi=g^{rs} \prod_{i\in[n]}g_i^{a_is}\prod_{j\in[n]}g_{j(n+1)}^{rb_j-t} \prod _{i\in[n]}\prod _{j\in[n]\backslash\{ i\}} g^{a_ib_j-u_i} _{i+j(n+1)} \\ &\hat \pi=\hat g^{rs} \prod_{i\in[n]}\hat g_i^{a_is}\prod_{j\in[n]}\hat g_{j(n+1)}^{rb_j-t} \prod _{i\in[n]}\prod _{j\in[n]\backslash\{ i\}} \hat g^{a_ib_j-u_i} _{i+j(n+1)} \\ &\dot \pi=\dot g^{rs} \prod_{i\in[n]}\dot g_i^{a_is}\prod_{j\in[n]}\dot g_{j(n+1)}^{rb_j-t} \prod _{i\in[n]}\prod _{j\in[n]\backslash\{ i\}} \dot g^{a_ib_j-u_i} _{i+j(n+1)} \\ \end{aligned} $$
- $Verification$：当且仅当下列三个等式均成立时Verifier接受
$$ \begin{aligned} &e(g,\hat \pi)=e(\pi,\hat g)\\ &e(g,\dot \pi)=e(\pi,\dot h)\\ &e(c,d)=e(v,\prod _{j\in[n]}g_{j(n+1)})e(g,\pi) \end{aligned} $$
Theorem 3：乘积论证具有完美完备性，完美证据不可区分性，若q-CPDH假设成立，则非均匀PPT敌手输出承诺值$(c,d,v)$，使得Verifier接受论证$\pi$且论证满足存在某些$i\in[n]$，使得$a_ib_i\neq u_i$的概率可忽略
直接计算可以证明完美完备性，合理性的证明思路和上面介绍的小例子差不多，具体证明可以看原文$[1]$，page 13
证据不可区分性是这么回事，观察给定的$c,d,v$，正好有一个可接受的论证$\pi$满足验证方程
7 Permutation Argument
接下来介绍一下对置换的承诺
考虑下面两个承诺
$$ c=g^r\prod _{i\in [n]} g_i^{a_i},d=g^s\prod _{i\in [n]} g_i^{b_i} $$
和一个置换$\forall i\in[n]:b_i=a_{\rho(i)}$
该置换$\rho\in S_n$是公开的，接下来看如何给出满足这个置换的承诺
主要的思路是证明等式
$$ \sum _{i\in[n]} a_ix^{i(n+2)} =\sum_{i\in[n]}b_ix^{\rho(i)(n+2)} \tag{7.1} $$
由Lemma 1，我们可以知道这个等式表明了$\forall i\in[n]:b_i=a_{\rho(i)}$
为了得到这个等式，我们需要计算$e(c,\prod_{j\in[n]})g_{j(n+1)}$和$e(d,\prod_{j\in[n]})g_{\rho(j)(n+2)-j})$，这两个配对的DLOG分别是
$$ \begin{aligned} &(r+\sum_{i\in[n]}a_ix^i)\sum_{j\in[n]}x^{j(n+1)}=r\sum_{j\in[n]}x^{j(n+1)}+\sum_{i\in[n]}a_ix^{i(n+2)}+\sum_{i\in[n]}\sum_{j\in[n]\backslash\{i\}} a_ix^{i+j(n+1)}\\ &(s+\sum_{i\in[n]}b_ix^i)\sum_{j\in[n]}x^{\rho(j)(n+2)-j}=s\sum_{j\in[n]}x^{\rho(j)(n+2)-j}+\sum_{i\in[n]}b_ix^{\rho(i)(n+2)}+\sum_{i\in[n]}\sum_{j\in[n]\backslash\{i\}} b_ix^{i+\rho(j)(n+2)-j}\\ \end{aligned} $$
这两个DLOG中，我们需要的是上面验证等式中的$\sum _{i\in[n]} a_ix^{i(n+2)}$和$\sum_{i\in[n]}b_ix^{\rho(i)(n+2)}$，其他多余的项我们需要通过论证来消去，做法和内积论证一致，Verifier通过验证下列配对来实现
$$ e(c,\prod _{j\in[n]}g_{j(n+1)})=e(d,\prod _{j\in[n]}g_{\rho(j)(n+2)-j})e(g,\pi) $$
和内积论证一样，Prover还需要提供限制性论证$\hat \pi,\dot \pi$来确保$\pi$中不包含$x^{n+2},...,x^{n(n+2)}$的项，此时协议满足合理性，验证等式为(7.1)
下面是完整的论证过程
- $Statement$：对$c,d\in G$和$\rho\in S_n$承诺
- $P's \ witness$：揭示$(r,a_1,...,a_n),(s,b_1,...,b_n)\in \Z_p$，满足
$$ \begin{aligned} &\forall i\in[n]:b_i=a_{\rho(i)}\\ &c=g^r\prod _{i\in [n]} g_i^{a_i}\\ &d=g^s\prod _{i\in [n]} g_i^{b_i} \end{aligned} $$
- $Argument$：计算论证$(\pi,\hat \pi ,\dot \pi)$
$$ \begin{aligned} &\pi=\prod _{j\in [n]} g^r_{j(n+1)}g^{-s}_{\rho(j)(n+2)-j} \prod _{i\in [n]}\prod _{j\in[n]\backslash \{i\} } g^{a_i}_{j(n+1)+i}g^{-b_i}_{\rho(k)(n+2)+i-j} \\ &\hat \pi=\prod _{j\in [n]} \hat g^r_{j(n+1)}\hat g^{-s}_{\rho(j)(n+2)-j} \prod _{i\in [n]}\prod _{j\in[n]\backslash \{i\} } \hat g^{a_i}_{j(n+1)+i} \hat g^{-b_i}_{\rho(k)(n+2)+i-j} \\ &\dot \pi=\prod _{j\in [n]} \dot g^r_{j(n+1)}\dot g^{-s}_{\rho(j)(n+2)-j} \prod _{i\in [n]}\prod _{j\in[n]\backslash \{i\} } \dot g^{a_i}_{j(n+1)+i}\dot g^{-b_i}_{\rho(k)(n+2)+i-j} \\ \end{aligned} $$
- $Verification$：当且仅当下列三个等式均成立时Verifier接受
$$ \begin{aligned} e(g,\hat \pi)&=e(\pi,\hat g)\\ e(g,\dot \pi)&=e(\pi,\dot h)\\ e(c,\prod _{j\in[n]}g_{j(n+1)})&=e(d,\prod _{j\in[n]}g_{\rho(j)(n+2)-j})e(g,\pi) \end{aligned} $$
Theorem 4：置换论证具有完美完备性，完美证据不可区分性，若q-CPDH假设成立，则非均匀PPT敌手输出承诺值$(c,d)$，使得Verifier接受论证$\pi$且论证满足存在某些$i\in[n]$，使得$b_i\neq a_{\rho(i)}$的概率可忽略
证明思路和内积论证类似
8 Constant Size NIZK Argument for Circuit Satisfiability
现在，我们将给出二进制电路$C$可满足性的NIZK论证，该论证由恒定数量的群元素组成，但是缺点是CRS很大
不失一般性，我们假设电路仅包含与非门，记$a$为电路的输出导线，并通过加入一个额外的自循环与非门$a=\lnot(a\wedge b)$来强制$a$为$true$，从而我们可以将可满足性问题规约至存在一组导线的真值赋值，满足电路内所有与非门
接下来看这个对电路可满足性的完整的NIZK论证
- $CRS$：生成CRS串$\sigma=(ck,\widetilde \sigma,\bar \sigma,\dot \sigma)$，其中$n=2N$
- $statement$：对于包含$N$个与非门的电路$C$，证明存在一组导线的赋值，满足该电路得内部一致性（也即满足所有的与非门）
- $Witness$：$2N$个作为导线赋值的输入$(a_1,...,a_N),(b_1,...,b_N)\in \{0,1\}$，记$(u_1,...,u_N)$为输出导线，记$(r_1,...,r_N)$为$(a_1,...,a_N,b_1,...,b_N)$中的其余值（要么是电路的输入，要么是与非门的输出导线多次作为其他与非门的输入的副本）
$Argument$：
- 构建关于$(a_1,...,a_N,b_1,...,b_N)$的限制性知识承诺$(c_{a||b},\hat c_{a||b},\widetilde c_{a||b})$
- 构建关于$(a_1,...,a_N,b_1,...,b_N)$的限制性知识承诺$(d_{a||b},\hat d_{a||b},\bar d_{a||b})$
- 构建关于$(b_1,...,b_N,a_1,...,a_N)$的限制性知识承诺$(c_{b||a},\hat c_{b||a},\widetilde c_{b||a})$
- 构建关于$(b_1,...,b_N,0,...,0)$的限制性知识承诺$(c_{b||0},\hat c_{b||0},\widetilde c_{b||0})$
- 构建关于$(u_1,...,u_N,r_1,...,r_N)$的限制性知识承诺$(c_{u||r},\hat c_{u||r},\widetilde c_{u||r})$
- 构建关于$(u_1,...,u_N,0,...,0)$的限制性知识承诺$(c_{u||0},\hat c_{u||0},\widetilde c_{u||0})$
- 以$\prod _{i=1}^{2N}g_i$与$c_{a||b}$和$d_{a||b}$进行内积论证，使该论证包含一个$c_{a||b}$中的entry-wise product，证明$c_{a||b}$和$d_{a||b}$包含相同的值（$\prod _{i=1}^{2N}g_i$实际上是对$(1,...,1,1,...,1)$的承诺）
- 对$c_{a||b}$和$d_{a||b}$内积论证，使该论证包含一个$c_{a||b}$中的entry-wise product，证明$(a_1,...,a_N),(b_1,...,b_N)\in \{0,1\}$
- 展示值与导线内部一直，也即$(a_{i_1},...,a_{i_l},b_{j_1},...,b_{j_m})$均对应于相同的导线，然后选择一个置换$\rho\in S_{2N}$，满足包含$i_1\rarr i_2\rarr...\rarr i_l \rarr j_1+N\rarr j_2+N\rarr ... \rarr j_m+N \rarr i_1$这样的循环，然后给出$c_{a||b}$中包含$\rho$置换的值的承诺（这步是证明$a_{i_2}=a_{i_1},...,b_{j_1}=a_{i_l},...,b_{j_m}=b_{j_{m-1}}$成立）
- 给出关于$c_{u||r}$和$c_{a||b}$的置换论证，证明输出值$(u_1,...,u_n)$与输入值$(a_1,...,a_N,b_1,...,b_N)$一致（$(r_1,...,r_N)$是$(a_1,...,a_N,b_1,...,b_N)$中剩余的$N$个值，对应于电路中输入或输出导线的副本，也即确保一致性）
- 给出关于$c_{b||a}$的置换论证
- 给出关于$c_{b||0}$的内积论证，包含$c_{b||a}$和$\prod ^N_{j=1}g_{j(n+1)}$（对$(1,...,1,0,...,0)$的承诺）
- 给出关于$c_{u||0}$的内积论证，包含$c_{u||r}$和$\prod ^N_{j=1}g_{j(n+1)}$（对$(1,...,1,0,...,0)$的承诺）
- 通过内积论证$c^{-1}_{u||0} \prod ^N_{i=1}g_i$（对$(1-u_1,...,1-u_N,0,...,0)$的承诺），展示与非门满足statement（这个内积论证是$c_{b||0},d_{a||b}$的entry-wise product）
上述论证由六个知识承诺及其对应的限制性论证组成，此外还包含五个内积论证和三个置换论证，一共42个群元素
Verifier当且仅当论证中的六个知识承诺具有正确的形式，且这六个知识承诺对应的限制性论证验证通过，五个内积和三个置换论证验证通过时接受
Theorem 5：上述关于电路可满足性的NIZK论证在$q=4N^2+6N-2$的情况下，q-PKE和q-CPDH假设成立时，具有完美完备性、完美零知识性和计算合理性
证明没看，虽然内容不多，打算有空再补，需要一点时间捋一下思路
9 Reducing the Common Reference String
大概看了一下，用到了Clos-network$[Clo53]$中的置换思想，简单来说就是通过块内置换和块之间的随机抽样，使得可以通过小集合的置换构造大集合的置换
但是Clos-network的思想非常依赖于置换$\rho$，因为块之间的分布是固定的，和置换$\rho$无关，具体会不会改变承诺值之间的分布不太晓得，有空再填坑吧
总结
主要是提出了一种新的证明思路，就是利用双线性配对的方式来完成证明的构造和验证，从而实现零知识
文章也基于前面的研究提出了两个新的假设：q-PKE和q-CPDH，本文的方案也都是基于这两个假设构建的
本文的两个方案，一个是置换论证，一个是内积论证，置换论证是确保值被打乱，内积论证则是用于验证两个向量的内积
论文在构造CRS方面也有一些比较巧妙的方案，因为配对过程中会导致离散对数中产生很多不必要的杂项
而本文的思路是通过将原集划分为三个互不相交的子集，然后一个子集用于完成验证，另外两个子集作为限制性条件辅助验证，从而消除这些杂项，一个非常巧妙的方法
不过本文在开始时也强调了一点，方案适用于与非门电路，对于其他的电路不适用，简单来说就是不具备通用性
此外就是方案是可以做到完美完备性、完美零知识性和计算合理性的，总的来说也还不错
缺点在于整个方案比较重，总共需要42个群元素才能完成对电路可满足性的论证
原文的第九节也给出了优化CRS大小的方案，比如说引入Clos-network的方案来通过小集合上的置换构造大集合上的置换，从而满足方案的要求
还有比较常见的时间换空间的思想，用多个小的论证来代替一个大的论证，这个思想的效果比较明显，可以做到CRS和论证加起来需要的元素比整个电路还小，也即可以做到亚线性，但是配对是一个开销比较大的计算，显然在电路很大的时候不太现实
后记
前后看了三天，这段时间是打算把ZKP所有用到的算法都看一遍，首先是之前看过的Groth16，本来打算复习一下的，看了一眼子集俩月前写的博客发现看不懂，于是递归学习看到了Groth10
看完之后感觉这个方案很重，也可能是之前看了Groth16的原因，毕竟Groth16是在这篇文章上改进的，改进到了只需要三个群元素，这篇文章零零总总需要42个群元素，多太多了
还有就是Groth10的一些缺点，第一个就是CRS都很大
文章里面也提到了，电路很大的时候生成的CRS也会很大，CRS大也就意味着生成过程的开销很大
如果说为了一个只需要证明几次甚至一次的statement生成一个这么大的CRS，那显然是一种得不偿失的行为
所以后来有其他的学者研究了可更新CRS的模型，可更新意味着对于一个新的statement而言，只需要更新CRS的一部分即刻，不用大费周章的重新生产
另一个缺点就是不具备通用性，原文特别强调了电路仅包含与非门，也即不适用于其他的电路，这种局限性就比较头疼
这个看完了，后续再认真看一下Groth16吧，希望自己会有新的收获
Reference
$[1]$ Jens Groth:Short Pairing-Based Non-interactive Zero-Knowledge Arguments. ASIACRYPT 2010: 321-340