NIZK from Non-Interactive Batch Arguments

Abstract

NIZK中最重要的两个性质是零知识性和简洁性，之前的工作中，Kitagawa等人研究了如何基于NP语言的SNARG构建NIZK，该研究介绍了如何利用论证系统中的简洁性，并将其转换为零知识性（？）

本文研究类似的问题，即利用简洁性来获取零知识性，本文的出发点为NP的批处理论证，批处理论证允许Prover向Verifier证明$T$个NP Statement$x_1,\dots,x_T$，且证明大小与$T$呈亚线性关系

与NP的SNARG不同，批处理论证的NP可以基于群的假设（有配对和无配对都可）构建，也可以基于格的假设构建，但是批处理的挑战在于：证明大小仅均摊到Statement的数量上，不过可以将相关的witness编码到少数实例中

本文介绍了如何基于一个局部伪随机数生成器和双模承诺方案（Dual-Mode Commitment Scheme）来构建NP的批处理论证，以获得NP的NIZK，本文的研究提供了一种新的从简洁性到零知识性的通用方法，并强调了简洁性与零知识性之间的联系

1 Introduciton

非交互式ZKP的概念最早于$[BRM88]$这篇论文中提出，在非交互式论证中，对于一个NP预言$\mathcal L$，Prover需要用条单一的消息$\pi$，向Verifier证明$x\in \mathcal L$，此类论证系统有两个重要的性质

• 零知识性：证明$\pi$没有泄露除了$x\in \mathcal L$以外的任何信息，此时将此类论证系统称为NIZK论证

NP的NIZK与平面模型（Plain Model）不同，之前的研究已证明平面模型中无法构建基于NP的NIZK，除非$\mathrm{NP}\sube \mathrm{BPP}$，后者已被证否，因此平面模型中无法构建基于NP的NIZK，也即平面模型中的NIZK只能证明BPP中的语言，无法证明NP语言，因此后续的NIZK的该方案都是基于CRS模型构建的

• 简洁性（Succinct）：简洁性要求证明大小和Verifier验证证明的时间与NP关系（Statement）呈亚线性关系，此类论证系统也简写为SNARG

这里有两个点需要回顾一下

• 论证（Argument）：论证表明Prover的算力被限制为多项式有界的，也即Prover的算力不是无穷的，Prover拥有无穷算力的证明系统称为证明（Prover）
• 简洁性：最早应该是Micali于1994年的论文提出的概念，其称为简洁非交互式ZK，简洁性中的亚线性关系在不同的文献有不同的定义，比较普遍的两种说法是亚线性意味着证明大小和验证时间与Statement呈对数关系，也有的文献说的是对数多项式（Ploylogarithmic）关系

之前的许多非交互式协议同时实现了简洁性和零知识性，称为zkSNARG，构建此类协议也很简单，找一个SNARG，再找一个NIZK，捏一起就可以了，问题在于，这两个基本性质之间是否存在形式上的联系

Kitagawa等人的研究表明，利用单向函数可以为NP语言的SNARG构建一个NIZK（从而得到zkSNARG），可以这么做是因为证明长度比witness要短得多，从信息论的角度来说，证明不会揭示witness太多的信息，然后他们再将这个方案与泄露弹性（Leakage-Resilient）密码机制结合在一起，得到了NIZK

这里这个泄露弹性用的是resilient这个单词，不是抗碰撞的那个resistance

没太理解泄露弹性，问了一下师姐，师姐原话说的是熵足够大的情况下，泄露一部分随机性也不会有什么影响

Batch Arguments and Zero-Knowledge

之前的研究表明，NP的SNARG具有很强的简洁性，需要在很理想的模型中构建，或者需要一些不可证伪的假设，所以本文不打算琢磨这个点

本文琢磨另一个更弱的概念，批处理NP语言的SNARG（Batch ARG，BARG），这个方向最近两年也有不少学者在研究，而且可以用标准密码假设构建

BARG中需要处理$T$个NP Statement $x_1,\dots,x_T$，并要求证明大小为$poly(\lambda,s)\cdot o(T)$，其中$s$表示计算NP关系的电路的大小

不难看出，BARG的证明大小和开销可以均摊到多个Statement中，从而实现简洁性，但是这也可能带来witness的泄露，总而言之就是存在下面这个问题

是否可以从NP的非交互式批处理论证中构建NP的NIZK论证

Our result

本文结合了双模承诺方案和具有超线性拉伸（Super-Linear Stretch）的低局部性（Low Locality）伪随机数生成器，构造了NP语言的NIZK

双模承诺方案可以从任意有损或双模公钥加密方案中构建（基于已知的标准假设）

低局部性：每个输出比特仅取决于输入种子的少量比特，本文采用的局部性可达到$c\log \lambda$，其中$c<1$，$\lambda$表PRG输入种子长度（或者干脆采用Goldreich的PRG族实例化）

这个低局部性不知道和前面的泄露弹性的概念是不是有什么关联，因为输出比特仅取决于种子的少量比特，因此不决定输出的那些输入比特泄露的话应该也没什么问题，吧？

尽管本文的方案依赖的附加组件比单向函数更强，但是由于目前已知的情况是，没有任何底层的基本组合可以构建NP的NIZK，因此这里用一个非正式的定理概括一下本文的研究结果

Thm 1（Informal）：令$G:\{0,1\}^\lambda\rarr \{01,\}^{\lambda^\delta}$为一局部性为$c\log \lambda$，超线性拉伸为$\delta$的PRG（$c<1$且足够小，$\delta>1$且足够大），假设存在双模承诺方案、NP语言的非交互式批处理论证（具有较小的证明大小），且$G$的困难性为亚指数的，则存在NP的NIZK

本文的研究重点关注论证系统的简洁性和零知识性之间的联系，并为构造NP的NIZK提供了一种新的通用方法，最后通过将其与满足特定效率性质的NP的NIZK相结合，从而得到零知识的批处理论证

综上，本文的方法也适用于仅依赖于低局部性的PRG和双模承诺方案（这两者单独使用都无法构建NP的NIZK），从而将NP的非交互式批处理论证构造转化为零知识的批处理论证

2 Technical Overview

本文基于Kitagawa等人的研究成果，他们的研究中对Feige等人隐藏比特（Hidden-Bits）进行了实例化，并与隐藏比特生成器（Hidden-Bits Generator，HBG）相结合，将NP的SNARG转化为NP的NIZK

隐藏比特模型之前刷9th BIU的时候看过，还记得一点，可以看$[2]$简单了解一下

NIZKs in the hidden-bits model

隐藏比特模型是一个用于构建NIZK的理想化模型，该模型中需要一个可信方为Prover构造一个随机串$(r_1,\dots,r_m)\larr \{0,1\}$，Prover选择一个子集$I\sube [m]$（集合的选择与证明$\pi$独立），并将集合$\{r_i\}_{i\in I}$和证明$\pi$发送给Verifier

这里注意，这个随机串只有Prover知道，Verifier不知道

该模型可以确保Prover无法决定随机串的生成过程，且Verifier也无法知道$i\notin I$以外的随即比特，$[FLS90]$介绍了如何在该模型中构建了一个对于图的哈密顿性（NPC问题）的NIZK，且方案满足统计合理性和完美零知识性

Hidden-Bits Generators

之前有许多学者都研究了如何利用密码学原语，将隐藏比特模型中的NIZK转化为CRS模型中的NIZK，这里本文主要关注Quach等人$[QRW19]$引入的抽象概念：隐藏比特生成器（Hidden-Bits Generator，HBG）

HBG是一种用于生成隐藏比特的密码学原语，Prover后续可以揭示其希望揭示的比特，同时保持未揭示的比特的隐藏性，此外，HBG确保了Prover对生成的比特串仅有有限的控制权

换言之，HBG提供了隐藏比特模型中随机串的可信密码是先，因此可以结合隐藏比特模型中的NP的NIZK，HBG可以得到CRS模型中的NP的NIZK

下面是Kitagawa等人$[KMY20]$论文中隐藏比特模型的形式化描述（默认安全参数为$\lambda$）

• $Setup$：输出长度为$m$的CRS串$crs$
• $GenBits$：输入$crs$，输出长度为$m$的隐藏比特串$\mathbf r\in\{0,1\}^m$，同时输出生成器状态$\mathrm {st}$
• $Prove$：输入$\mathrm {st}$和一个索引集$I\sube [m]$，输出一个证明$\pi$，证明用于揭示$\mathbf r$中对应于索引集$I$的比特，这里将这些揭示的比特记为$\mathbf r_I\in \{0,1\}^{|I|}$
• $Veirfy$：输入$crs,I,\mathbf r_I,\pi$，输出1表示接受，输出0表示拒绝

上述模型满足下列几个性质

• 正确性（Correctness）：简单来说就是若Prover按照协议执行协议，则Verifier一定输出接受
• 绑定性（Binding）：绑定性表明，计算有界的算法（敌手）无法违背算法

具体而言，对于由$Setup$构造的$crs$，记$\mathcal V^{crs}\sub \{0,1\}^m$表示合法的隐藏比特串集合，任意高效敌手无法为索引集$I$和对应的$\mathbf r_I$构造一个合法的证明$\pi$，使得$\mathbf r_I$不属于任意合法的$crs$串$\mathbf r'\in \mathcal V^{crs}$所对应的揭示集合$\mathbf r'_I$​

此外还要求与$crs$相关的隐藏比特串是稀疏的：$|\mathcal V^{crs}|\leq 2^{m^\gamma\cdot poly(\lambda)}$，其中$\gamma<1$

• 隐藏性：隐藏性要求$\mathbf r$中未被揭示的比特为伪随机的，也即对于诚实生成的$\mathbf r$和$\pi$，以及对应的索引集$I$，对于随机生成的比特串$\hat {\mathbf r}\larr \{0,1\}^m,\bar I=[m]\backslash I$，下面两个分布在计算上不可区分

$$ \begin{aligned} (crs,I,\mathbf r_I,\mathbf r_{\bar I},\pi)\\ (crs,I,\mathbf r_I,\hat {\mathbf r_{\bar I}},\pi) \end{aligned} $$

Kitagawa等人在论文中介绍了如何通过将NP的SNARG和泄露弹性的（弱）伪随机函数（PRF）相结合来构建满足上述性质的隐藏比特生成器

• CRS包含两个部分：（1）$m$个随机点，对应于PRF$(x_1,\dots,x_m)$；（2）SNARG的CRS
• 隐藏比特串由PRF密钥$k$和上述$m$个PRF确定：$r_i\larr PRF(k,x_i),i\in [m]$
• 证明为存在$k$，使得对于索引集中的所有元素$i\in I$，存在$k$，使得$r_i=PRF(k,x_i)$

Replacing the SNARG with a batch argument

本文注意到上述的SNARG证明的揭示几乎是一个批处理语言，因为需要证明索引集中的元素$\forall i\in I$，都有$r_i=PRF(k,x_i)$，这里可以用一个三元组$(i,x_i,r_i)$来表示一个实例，对应的witness为PRF的密钥$k$​

这里需要注意，批处理不要求Prover在每个实例中都使用同一个密钥$k$，也即如果希望用BARG替换上面Kitagawa等人的SNARG方案，则只能证明局部一致性，而不是全局一致性

局部一致性指的是只能证明某个密钥$k_i$对应于输出的比特$r_i$，全局一致性则可以证明所有的$r_i$均来自于同一个密钥$k$

Enforcing consistency

局部一致性比较弱，因为找到一个可以构造任意候选的隐藏比特的串是平凡的

这里为了强制Prover构建批处理论证时在所有的实例中都是用同一个密钥$k$，需要让Prover对密钥$k$进行一个承诺，记为$c$，并将对$c$的揭示也作为揭示的一部分，此时批处理的NP就变成了存在$k$，使得$c$是对$k$的揭示，且$\forall i \in I,PRF(k,x_i)=r_i$

这里也不一定要用PRF，可以用PRG来代替PRF，Kitagawa等人的PRF也是用PRG构建的，只是为了正式一点，写成了PRF

本文下面用的是PRG来构建，并记PRG的第$i$位输出为$PRG_i:\{0,1\}^\lambda\rarr \{0,1\}$，PRG的种子记为$\mathbf s\in \{0,1\}^\lambda$

为了生成隐藏比特串，这里首先选择随机种子$\mathbf s$，然后对其承诺，承诺值记为$c$​

基于$\mathbf s$的隐藏比特串记为$\mathbf r\larr PRG(\mathbf s)$，隐藏比特串揭示至$\mathbf r_I$为一个批处理论证$\pi$，对应于下列这个语言

$$ \forall i\in I:\exist \mathbf s\in \{0,1\}^\lambda,c=Comm(\mathbf s)\wedge PRG_i(\mathbf s)=r_i \tag 1 $$

由于承诺方案满足统计绑定性，且批处理论证满足计算合理性，因此方案可以满足前面的绑定性要求

本文的安全性分析中要求承诺具有更强的可抽取性，从而可以基于基础BARG的半自适应合理性（semi soundness）上构建绑定性

相比之下，Kitagawa等人的方案依赖于具有自适应合理性的SNARG，难以在黑盒中归约为可证伪的假设，且此类构造的HBG也不满足隐藏性，这里主要有两个长度问题：

• 由于需要对$\mathbf s$进行承诺，后续还需要对$c$进行揭示，由于$c$满足统计隐藏性，因此$c$的长度至少会与$\mathbf s$一样长
• 批处理论证的简洁性要求$|\pi|=poly(\lambda,|C|,\log |I|)$，其中$C$为验证上述语言1的电路

这里与SNARG不同，$\pi$的大小与$|C|$呈多项式关系，且由于$C$需要以$\mathbf s$作为输入，因此必然有$|C|\geq |\mathbf s|$，也就意味着$|\pi|\geq |\mathbf s|$

$[KMY20]$认为，可以通过弱PRF潜在的泄露弹性来实现隐藏性，这里通过前面的分析可以知道，PRF密钥只会在SNARG中泄露，因为SNARG的长度小于PRF的密钥长度

且通过上述分析，在本文的方法中，对PRG种子的承诺和BARG的证明长度都有可能泄露PRG种子的信息，因此不能直接利用泄露弹性来实现隐藏性

Leveraging locality

前面提到了PRG的低局部性，本文打算利用这一个点来实现隐藏性

回顾一下之前的批处理语言，可以注意到每个单独的实例都是在检查PRG的一个输出比特，由于BARG的证明长度与检查单个实例的电路大小相关，因此如果验证PRG的输出比特的电路比PRG的种子长度小得多，则方案可以基于BARG的简洁性来构建

这里引入低局部性的概念，若PRG的输出仅依赖于输入种子的$k$比特，则称该PRG为$k$-局部的（$k$-local），且这个$k$-local的PRG可以用大小小于$2^k\cdot poly(\lambda)$的电路完成验证，结合之前的验证等式$r_i=PRG_i(\mathbf s)$，如果这个PRG是$k$-local的，则只需要检查种子的$k$比特即可

举个例子，如果PRG的局部性为常量，并且承诺方案按位对$\mathbf s$进行承诺，则验证PRG的单比特输出只需要大小为$\lambda^\delta$的电路（这里$\delta> 0$取决于BARG方案和使用的承诺方案），这里如果令种子长度$n>\lambda^\delta$，则可以依赖于PRG的泄露弹性来表ingBARG证明输出拥有最高的最小熵（前面提到了本文的方案令$k=c\log \lambda$，其中$c<1$为常数）

此外本文还要求$k$-local的PRG满足泄露弹性（这里用到了$[GW11]$里面的一个GW leakage-simulation引理），简单来说就是如果敌手对于$PRG(\mathbf s)$和随机选择的$\mathbf t\larr\{0,1\}^m$在计算上不可区分，此时考虑一个泄露的信息$\mathrm{aux}$，则对于串$(\mathbf t,\mathrm{aux}^*)$，存在一个辅助分布，使得敌手对该串与$(PRG(\mathbf s),\mathrm{aux})$也是计算不可区分的

这里问了一下师姐，说人话就是：如果$PRG$和$\mathbf t$是计算不可区分的，此时泄露一点与种子$\mathbf s$相关的信息$\mathrm{aux}$，只要泄露的$\mathrm{aux}$足够短（PRG的熵值足够大），则不会影响PRG的伪随机性

Dual-mode commitments

解决了隐藏性的问题，还有以恶个问题是确保PRG的种子的承诺不会泄露有关种子的信息，这一点可以依赖于承诺方案的计算隐藏性，且可以用对全零串的承诺来代替对种子的承诺，但是这样没用

BARG证明中需要完成对承诺的揭示，同样的这里用上面那个GW啥玩意引理，可以得到，将对种子和对全零串的承诺与前面的串进行一个联合，可以得到联合后的两个分布$(Comm(\mathbf s),PRG(\mathbf s),\mathrm{aux}),(Comm(\mathbf 0),t,\mathrm{aux}^*)$也是计算不可区分的

但是仔细思考的话，这里有一个循环依赖的问题，$\mathrm{aux}$的长度就是BARG证明的长度，该长度至少与承诺大小一样（因为承诺需要作为BARG的输入），因此这里不能采用PRG的那种方式来利用承诺，本文的解决方案是利用双模承诺$[GOS06,PW08]$

具体而言，双模承诺可以让CRS在两个计算不可区分的模式上进行采样

• 可抽取模式：用于实现绑定性
• 统计隐藏模式：承诺值在输入上满足统计隐藏性

双模承诺可基于有损公钥加密方案（Lossy Public-Key Enc. Scheme）构建，其底层基于数论困难性假设$[PW08,HLOV11,AFMP20]$

隐藏证明中的想法是首先将双模承诺从绑定模式切换到隐藏模式（这个步骤只会修改方案中的公共参数），此时只要CRS处于隐藏模式，PRG的种子的承诺都是统计隐藏的，此时再利用前面的那个什么GW引理来证明这两个分布$(Comm(\mathbf s),PRG(\mathbf s),\mathrm{aux}),(Comm(\mathbf 0),t,\mathrm{aux}^*)$再计算上不可区分，从而表明隐藏比特串中未揭示的比特位是一致随机的，且保持隐藏性

这里有个前提：要求PRG的困难性是亚指数的

Upgrading BARGs to zkBARGs

如果需要加入零知识性的话，有点复杂，因为本文注意到BARG的NIZK并不这么简单，因为BARG的验证算法首先需要读取Statement串$(x_1,\dots,x_T)$，这意味着验证电路的大小至少与$T$呈线性关系

不过NIZK的证明大小可以与验证电路的大小呈多项式关系，但是本文还是考虑了一些通用的方法来构建本文的zkBARG

• Index BARGs：在NP的索引BARG中，Statement总是为$[T]$中的整数，验证算法只需要输入上界$T$即可，验证时间为$T$的对数多项式时间

可以将索引BARG和NIZK结合起来，得到零知识的索引BARG，然后利用一个变换，从而得到关于NP的zkBARG（这里用到了$[CJJ21b]$中的变换，这个变换会保留零知识性）

• BARGs with split verification：若验证算法可以被分解为两个部分，则称其为拆分验证（Split Verification）：（1）（不满足简洁性）依赖于Statement的预处理步骤，输出一个短验证密钥$vk$（2）（简洁性）以验证密钥$vk$和证明$\pi$为输入，验证证明是否接受

重点在于在线验证步骤可以利用大小与$T$呈对数多项式关系的电路完成，若BARG满足可拆分验证的性质，则可以用NIZK来证明BARG的证明满足在线验证，从而得到zkBARG的拆分验证版本

‍

3 Preliminaries

按照惯例，先介绍符号和记法

• $\lambda$：安全参数
• $[n]$：小于$n$的正整数集
• $\mathcal D_1=\{\mathcal D_{1,\lambda}\}_{\lambda\in \N},\mathcal D_2=\{\mathcal D_{2,\lambda}\}_{\lambda\in \N}$：表示在安全参数$\lambda$下的两个分布

对于函数$s=s(\lambda),\epsilon=\epsilon(\lambda)$，若对于任意非负多项式$poly(\cdot )$和任意敌手$\mathcal A$（建模为大小至多为$s(\lambda)\cdot poly(\lambda)$的布尔电路），以及任意足够大的$\lambda\geq \lambda_{\mathcal A}$，都有下列不等式成立

$$ |\Pr[\mathcal A(x)=1:x\larr \mathcal D_{1,\lambda}]-\Pr[\mathcal A(x)=1:x\larr \mathcal D_{2,\lambda}]|\leq \epsilon (\lambda) $$

则称这两个分布为$(s,\epsilon)$不可区分的，简记为$(s,\epsilon)-ind$，这里的不可区分性区分计算性和统计性

• 计算不可区分：若存在一可忽略函数$\epsilon(\lambda)$，使得两个分布为$(1,\epsilon)-ind$，则为计算不可区分
• 统计不可区分：两个分布的统计距离为$negl(\lambda)$

Min-entropy

这里介绍一下最小熵的概念，本文沿用$[DRS04]$的说法

对于一个离散的随机变量$X$，记其最小熵为

$$ \mathbf H_{\infin}(X)=-\log(\max_x\Pr[X=x]) \tag 2 $$

对于两个离散随机变量$X,Y$（可能具有关联性），在$Y$的条件下，$X$的平均最小熵为

$$ \mathbf H_{\infin}(X|Y)=-\log(\mathbb E_{y\larr Y}\max_x\Pr[X=x|Y=y]) \tag 3 $$

简单来说，式3的意思就是：给定相关值$Y$时，任意计算无界的敌手猜测$X$的最佳概率为$2^{-\mathbf H_{\infin}(X|Y)}$

关于最小熵的概念，本文需要用到两个引理和一个定理（相关的参考文献可在原文第七页找到）

• Conditional Min-Entropy$[DRS04,Lemma 2.2b]$
• Gentry-Wichs Leakage Lemma$[GW11,Lemma 3.1]$
• Leftover Hash Lemma with Conditional Min-Entropy$[BDK+11,Thm 3.2]$

看不懂这几个引理定理，数学太差了

Pseudorandom generators

伪随机数生成器定义为$PRG_\lambda:\{0,1\}^\lambda\rarr \{0,1\}^{m(\lambda)}$，要求伪随机数生成器与真随机数是$(s,\epsilon)-ind$的

此外，若存在常数$\alpha>0$和一个可忽略函数$\epsilon=negl(\lambda)$，使得$PRG$为$(2^{\lambda^\alpha},\epsilon)$安全的，则称该PRG为亚指数安全的

对于前面提到的低局部性，这里给出正式定义：PRG的局部性定义为其输出比特串$PRG(x)$仅与输入种子$x$的至多$k=k(\lambda)$比特的相关联

Dual-mode commitments

双模承诺最早由$[DN02]$提出，有的文献也将其称为混合承诺（Mixed Comm.）

和前面提到的一样，双模承诺是CRS模型中的非交互式承诺方案，CRS可以从两个计算不可区分的分布中的一个进行采样，正式定义如下

Def 1（Dual-Mode Bit Commitment）：双模比特承诺定义为一个三元组$\Pi_{BC}=(Setuo,Commit,Verify)$

• $Setup(1^\lambda,mode)\rarr (crs,td)$：输入模式$mode\in \{bind,hide\}$，算法输出对应的CRS和陷门（陷门可能为空
• $Commit(crs,b)\rarr(c,\sigma)$：对$b\in \{0,1\}$进行承诺，得到承诺值$c$和揭示值$\sigma$
• $Verify(crs,c,b,\sigma)\rarr \{0,1\}$：验证$c,\sigma$是否是$b$的承诺

上述双模比特承诺需要满足下列性质

• 正确性（Correctness）：
• 模式不可区分性（Mode Ind）：任意敌手无法区分承诺过程中使用的模式
• 绑定模式可抽取性（Extractable in Binding Mode）：要求绑定模式下存在一个抽取器算法，该抽取器可以利用陷门和承诺值抽取出承诺的比特$b$
• 隐藏模式的统计隐藏性（Statistically Hiding in Hiding Mode）：要求隐藏模式下的承诺值具备统计隐藏性

双模承诺的构造方式可以看$[BHY09,PW08,HLOV11,AFMP20]$

3.1 Non-Interactive Zero-Knowledge Arguments of NP

本文主要考虑布尔电路可满足性的NP语言，也即考虑布尔电路$C:\{0,1\}^n\times\{0,1\}^h\rarr \{0,1\}$，Statement为$\mathbf x$，witness为$\mathbf w$，满足$C(\mathbf x,\mathbf w)=1$

对应的布尔电路可满足性语言如下

$$ \mathcal L_C=\big\{\mathbf x\in \{0,1\}^n:\exist \mathbf w\in\{0,1\}^h,C(\mathbf x,\mathbf w)=1 \big \} $$

然后看一下NP的NIZK的定义

Def 2（NIZK Argument for NP）：这里定义为三元组$\Pi_{NIZK}=(Setup,Prove,Verify)$

• $Setip(1^\lambda)$：初始化算法输出CRS
• $Prove(crs,C,\mathbf x,\mathbf w)\rarr\pi$：输入$\mathbf x,\mathbf w$，构造一个证明$\pi$
• $Verify(crs,C,\mathbf x,\pi)\rarr b$：验证证明

$\Pi_{NIZK}$需要满足完备性、计算合理性和计算零知识性

3.2 Non-Interactive Batch Arguments for NP

这里介绍一下本文研究的密码原语：NP的非交互式批处理论证，和上面一样，考虑布尔电路可满足性的NPC语言

首先回顾一下$[KPY19,CJJ21a]$中非交互式批处理论证的定义

Def 3（Batch Argument for NP）：定义为一个算法三元组$\Pi_{BARG}=(Setup,Prove,Verify)$

• $Setup(1^\lambda,1^T,1^s)$：输入实例数量$T$和电路大小的界$s\in \N$，输出CRS
• $Prove(crs,C,(\mathbf x_1,\dots,\mathbf x_T),(\mathbf w_1,\dots,\mathbf w_T))\rarr \pi$：构造$T$个实例的证明
• $Verify(crs,C,(\mathbf x_1,\dots,\mathbf x_T),\pi)\rarr b$：验证通过则$b=1$

$\Pi_{BARG}$需要满足完备性、证明大小的简洁性和半适应合理性（Semi-adaptive Soundness），其中证明大小的简洁性要求电路大小至多为$s$，证明大小$|\pi|\leq poly(\lambda,\log T,s)$

构造方式可参考$[CJJ21b,DGKV22,CGJ+22,KVZ21,WW22]$

3.3 Hidden-Bits Generator

隐藏比特生成器定义如下，这里沿用了$[KMY20]$中的子集相关证明的概念

Def 3（Hidden-Bits Generator）：隐藏比特生成器定义为算法四元组$\Pi_{HBG}=(Setup,GenBits,Prove,Verify)$

• $Setup(1^\lambda,1^m)$：输入为随机串的输入长度$m$，初始化算法输出CRS
• $GenBits(crs)\rarr(\mathbf r,st)$：输出随机串$\mathbf r$和状态$st$
• $Porve(st,I)\rarr\pi$：输入一个子集$I\sube[m]$，构造证明$\pi$
• $Verify(crs,I,\mathbf r_I,\pi)$：验证证明

$\Pi_{HBG}$满足正确性、计算绑定性、计算隐藏性和输出的稀疏性，其中输出的稀疏性要求：对于初始化算法声称得CRS，存在一个集合$\mathcal V^{crs}$，对于$\gamma<1$和固定的多项式$p$，对于任意的输出长度$m=m(\lambda)$，有$|\mathcal V^{crs}|\leq 2^{m^\gamma\cdot p(\lambda)}$

这里有一个相关的定理

Thm 1（NIZK from Hidden-Bits Generator$[KMY20, Thm 5]$）：若存在具有子集相关证明的隐藏比特生成器，则存在一个关于NP的满足计算性的NIZK

4 Hidden-Bits Generator from Batch Arguments

本节介绍如何利用NP的批处理论证和双模承诺、低复杂度的PRG来构建具有子集相关证明的HBG，之后再将其与前面的定理2.11相结合来得到NP的NIZK

Construction 3.1（Hidden-Bits Generator from Batch Arguments）：记$n=n(\lambda,m)$表示PRG种子长度参数，记$B=B(\lambda.m)$表示块长度参数，构造如下

• $G_\lambda:\{0,1\}^\lambda\rarr\{0,1\}^{l(\lambda)}$：表示PRG族，低局部性为$k$，这里要求$l(n)\geq mB$
• $\Pi_{BC}$：双模比特承诺
• $\Pi_{BARG}$：NP的批处理论证，证明大小记为$l_{BARG}$

对$i\in [l]$，令$i_1,\dots,i_k\in[n]$表示种子中与输出相关的$k$个比特，令$\mathbf s\in\{0,1\}^n$表示种子，令$G_n^{(i)}:\{0,1\}^k\rarr \{0,1\}$表示输入$k$比特种子，输出$G_n(\mathbf s)$的第$i$比特，定义NP关系$\mathcal R[n,crs_{BC}]$如下

基于上述组件，构造本文的隐藏比特生成器

$Setup(1^\lambda,1^m)$：进行如下三个步骤，输出HBG的CRS串$crs=(n,crs_{BARG},crs_{BC},\mathbf v_1,\dots,\mathbf v_m)$

1. 调用双模承诺方案的初始化设置，得到对应的CRS串$(crs_{BC},td)$
2. 令$n$表示PRG的种子长度，$C$表示计算上述关系$\mathcal R$的电路，调用BARG的初始化设置，得到对应的CRS串$(crs_{BARG})$
3. 令$B$表示块大小，随机选择$\mathbf v_1,\dots,\mathbf v_m\rarr \{0,1\}^B$

$GenBits(crs)\rarr(\mathbf r,st)$：进行下列两个步骤，输出隐藏比特串$\mathbf r=r_1||r_2||\cdots||r_m\in \{0,1\}^m$和生成器状态$st=(n,crs_{BARG},crs_{BC},\mathbf s,c_1,\dots,c_n,\sigma_1,\dots,\sigma_n)$

1. 随机选择种子$\mathbf s\larr \{0,1\}^n$，计算$\mathbf t=\{0,1\}^{mB}\larr G_n(\mathbf s)$，然后对于$\forall i \in[n]$，对$\mathbf s$中的第$i$位计算双模承诺$(c_i,\sigma_i)$
2. 将$\mathbf t$切分为$m$个大小为$B$的块$\mathbf t=t_1||t_2||\cdots||t_m$，然后对于$\forall i \in[n]$，计算$r_i\larr \mathbf v_i^\top \cdot \mathbf t_i$

$Prove(st,I)$：记$\mathbf t[i]=t_i,G_n[i]=G_n^{(i)}$，记$I=\{i^{(1)},\dots,i^{(L)}\}$，记$\mathbf t[i^{(j)},\beta]\in \{0,1\}$表示$\mathbf t[i^{(j)}]$的第$\beta$位

然后定义一个函数$\mathrm{idx}:[L]\times[B]\times[k]\rarr [n]$，$\mathrm{idx}(i^{(j)},\beta,\gamma)$表示$\mathbf s$的第$\gamma$位，且$\mathbf t[i^{(j)},\beta]$依赖于该输入位，根据这个定义和之前的$k$局部性，$G_n[i^{(j)},\beta]$包含了$\mathrm{idx}(i^{(j)},\beta,1),\dots,\mathrm{idx}(i^{(j)},\beta,k)$

对于$j\in [L].\beta\in [B]$，定义statement和witness$(x_{j,\beta},w_{j,\beta})$如下

$Prove$算法首先调用BARG的证明算法，得到BARG证明$\pi_{BARG}$，然后输出证明$\pi$

$$ \pi=(\pi_{BARG},(c_1,\dots,c_n),(\mathbf t_{i^{(1)}},\dots,\mathbf t_{i^{(L)}})) $$

$Verify(crs,I,\mathbf r_I,\pi)$：分为两个步骤

1. 对$\forall j\in [L]$，验证$r_{i^{(j)}}= \mathbf v_{i^{(j)}}^\top \cdot \mathbf t_{i^{(j)}}$
2. 对$\forall j\in [L],\beta\in [B]$，按照上图构造$x_{j,\beta}$调用BARG验证算法$BARG.Verify(crs_{BARG},C,(x_{1,1},\dots,x_{1,B}),(x_{L,1},\dots,x_{L,B}))$

上述HBG的四个性质的证明可以看原文的13-19页

References

$[1]$ Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments (iacr.org)

$[2]$ 零知识证明（11）：非交互式零知识证明 - 三两老友杂的小岛 (snowolf0620.xyz)

‍