Best Award Paper
Batch Arguments for NP and More from Standard Bilinear Group Assumptions
Original Paper Link:
Batch Arguments for NP and More from Standard Bilinear Group Assumptions
NP的非交互式批处理参数提供了一种在多个实例中摊销NP验证成本的方法,它们使证明者能够说服多个NP陈述的验证者，其通信量远小于总见证长度，验证时间远小于单独检查每个实例
本文从具有双线性映射的群上的标准假设（具体地说，从复合阶群中的子群决策假设或从素数阶群中对于任何$k\ge1$$的$k-Lin假设），给出了NP的非交互式批处理自变量的第一个构造，而以前NP的批处理参数仅从LWE、多个假设的组合或非标准/不可伪造的假设中已知
本文的工作还引入了一种新的直接批量验证方法，并避免了以前方法中常见的相关难处理的哈希函数或概率可检查的证明等繁重工具
作为本文主要构造的推论，本文获得了RAM程序的第一个可公开验证的非交互式委托方案（即，P的SNARG），其CRS大小为次线性（在RAM程序的运行时间内），以及来自双线性映射的标准假设的第一个聚合签名方案（支持有界聚合）
Lattice-based Zero Knowledge
Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General
Original Paper Link:
Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General
基于模块SIS和模块LWE问题的硬度，本文提出了一个改进的实用协议，用于证明满足$As=t\bmod-q$的短向量$s$的知识
目前构造这种证明的最有效技术是通过证明$s$的$\ell_\infty$范数很小来工作，该工作创建了对多项式向量$m$的承诺，其CRT系数是$s$的系数，并表明
- $A\cdot \mathsf{CRT}(m)=t\bmod\,q$
- 想要证明$\ell_\infty$范数至多为$1$的情况下，多项式乘积$(m-1)\cdot m\cdot(m+1)$等于$0$
虽然这些方案在实际应用中已经相当有效，但使用CRT嵌入并且仅自然地适用于证明$\ell_\infty$-范数的要求阻碍了这种方法的效率
本文证明了有一种直接有效的方法来证明$s$的系数具有小的$\ell_2$范数，该范数不需要与$\ell_\infty$范数模棱两可，也不需要转换为CRT表示
本文观察到，两个向量$r$和$s$之间的内积可以表现为多项式之间的乘积（或乘积和）的系数，多项式是$r$的函数和$s$的函数，因此通过使用多项式乘积证明系统并隐藏除一个系数外的所有系数，能够证明模$q$的两个向量的内积的知识
使用廉价的近似范围证明，可以将证明提升到$\mathbb Z$以上，而不是$\mathbb{Z}_q$以上
本文的证明短范数的协议适用于所有（有趣的）多项式环，但对于像$\mathbb{Z}[X]/(X^n+1)$这样的环特别有效，其中与向量和多项式乘积的内积相关的函数恰好是“nice”自同构
新的证明系统可以以黑盒的方式插入到各种基于格的隐私原语的结构中
作为例子，本文实例化了一个可验证的加密方案和一个群签名方案，它们的紧凑性是以前最好的解决方案的两倍多
Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
Original Paper Link:
Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
简洁的非交互式知识论证（SNARK）允许证明者产生一个简短的证明，证明某个NP语句的真实性，在过去的十年里，大量工作研究了对量子攻击者安全的候选结构，然而并没有已知的候选者能够与基于双线性配对的（前量子）构造的效率和期望特征相匹配
本文解决了上述问题，提出了第一个同时满足许多期望财产的基于格的SNARK
- 暂时是量子后安全的
- 满足公开可验证性
- Verifier Time为对数阶
- 具有纯代数结构，使其易于高效递归组合
本文构建源于本文所开发的一个通用技术工具包，用于将基于配对的方案转换为基于格的方案
本文SNARK的核心是一种新的基于格的向量承诺（VC）方案，支持对常次多元多项式映射的开放，这是构造具有对超越线性函数的开放的VC方案的开放问题的候选解决方案
然而本文的构造的安全性是基于一系列新的基于格的计算假设，这些假设自然地概括了标准的短整数解（SIS）假设
Practical Sublinear Proofs for R1CS from Lattices
Original Paper Link:
Practical Sublinear Proofs for R1CS from Lattices
本文提出了一个实用的基于格的R1CS亚线性大小零知识证明系统，证明大小与witness大小的平方根成正比
对于大型R1CS实例，本文的方案大约为Ligero的1/2~1/3
Zero Knowledge
Orion: Zero Knowledge Proof with Linear Prover Time
Original Paper Link:
Orion: Zero Knowledge Proof with Linear Prover Time
零知识证明是一种强大的密码原语，在现实世界中有各种应用，然而现有方案在证明生成时间上存在高开销，该开销在表示为算术电路的语句的大小上是超线性的，限制了它们在实践中的效率和可扩展性
本文提出了一个新的零知识自变量系统Orion，它实现了域运算和哈希函数的$O(N)$证明时间和$O(\log^2 N)$验证大小
Orion是具体有效的，实现表明，对于具有$2^{20}$乘法门的电路，证明时间为3.09秒，证明大小为1.5MB，在所有现有系统中的验证时间最快，证明规模比Golovenv等人2021的最新方案小一个数量级
本文的方案提出了两种新技术，从而提高了效率
- 在最密子图算法的基础上，本文提出了一种新的算法来测试随机二分图是否是无损扩展图，它允许以压倒性的概率对无损扩展器进行采样，该技术利用线性证明时间提高了所有现有零知识论证方案的效率和/或安全性
- 开发了一种高效的证明组合方案——代码切换，以将证明大小从平方根减少到对数多项式，该方案建立在线性码的编码电路上，并表明第二个零知识自变量的见证与线性码中的消息相同，证明组合只在证明时间上引入了一小部分开销
Moz$\mathbb{Z}_{2^k}$zarella: Efficient Vector-OLE and Zero-Knowledge Proofs Over $\mathbb{Z}_{2^k}$
Original Paper Link:
Link
零知识证明系统通常被设计为支持$\mathbb{F}_2$或$\mathbb{F}_p$上电路的计算，但不支持$\mathbb{Z}_{2^k}$上的计算，尽管可以使用素数模来模拟$\mathbb{Z}_{2^k}$算术过程，但是会引入不可避免的开销
Baum等人（CCS 2021）提出了一个在$\mathbb{Z}_{2^k}$上运行的指定验证器零知识证明系统的候选构造，但是该构造需要在$\mathbb{Z}_{2^k}$上实例化VOLE（vector oblivious linear evaluation）
本文提出一种恶意安全的VOLE扩展协议，该协议可以将$\mathbb{Z}_{2^k}$上的短种子VOLE转换为同一环上更长的伪随机VOLE
本文的构造借用了最近在有限域上的协议中的思想，本文对其进行了非平凡的调整，以在$\mathbb{Z}_{2^k}$上工作
此外本文还表明QuickSilver零知识证明系统（Yang等人，CCS 2021）所采用的方法可以推广到支持$\mathbb{Z}_{2^k}$上的计算
本文称这种新的基于VOLE的证明系统为QuarkSilver，比Baum等人提出的以前的零知识协议产生了更好的效率
此外，本文实现了我们的VOLE扩展和零知识证明系统，并表明它们可以为64到256位环每秒生成13-5000万个VOLE，并且在零知识中评估每秒130万次64位乘法运算
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Original Paper Link:
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
我们引入了一种实现增量可验证计算（IVC）的新方法，其中证明者递归地证明了形式为$y=F^{(\ell)}(x)$，其中$F$是一种（潜在的非确定性）计算，$x,y$分别代表输出，$\ell > 0$
与先前实现IVC的方法不同，本文的方法完全避免了简洁的非交互式知识论证（SNARK）（以及一般的知识论证），相反，本文引入并使用了折叠方案，这是一种更弱、更简单、更有效的可实现原语，它在某种程度上减少了检查两个实例的任务，而不是检查单个实例的任务
本文为NP构造了一个折叠方案，并表明它暗示了一个具有改进效率特性的IVC方案
- “递归开销”（即Prover除了证明F的执行之外还证明的步骤数）是一个常数，并且它由表示为电路的两组标量乘法所支配（这是文献中最小的递归开销）
- Prover在每一步的工作都由两个大小为$O(|F|)$的多重指数决定，提供了文献中最快的证明人，但本文结果表明，使用现有zkSNARK的变体，证明者可以用$O(\log{|F|})$个群元素简洁地证明有效证明的知识
本文方法基于DLOG，既不需要可信设置，也不需要FFT，因此它可以有效地实例化任何椭圆曲线的循环
A New Approach to Efficient Non-Malleable Zero-Knowledge
Original Paper Link:
A New Approach to Efficient Non-Malleable Zero-Knowledge
非延展性零知识最初是在中间人攻击的背景下引入的，它是防止不同协议共存和交织的并发攻击的重要组成部分
虽然这个原始模型在普通模型中允许几乎最优的构造，但它们在实践中比独立的零知识慢几个数量级，这与不可延展承诺形成了鲜明对比，在不可延展的承诺中，实际结构（在DDH假设下）已经知道一段时间了
本文提出了一种新的方法，用于为NP中的所有语言构建高效的非可延展零知识，该方法基于一种称为基于实例的非可伸缩承诺（IBNMC）的新原语
本文展示了如何利用亚线性零知识协议的模拟器比诚实证明算法快得多的事实来构建实用的IBNMC，通过IBNMC的有效实现，本文的方法产生了第一个通用的非延展性零知识协议，该协议在普通模型中实现了实际效率
本文所有的协议都可以从对称原语（如块密码和哈希函数）实例化，在实践中具有合理的效率，并且是通用的
本文的技术还产生了第一个没有公钥假设的高效非延展承诺方案
Proof Systems
Parallel Repetition of $(k_1,\dots,k_{\mu})$-Special-Sound Multi-Round Interactive Proofs
Original Paper Link:
Link
许多情况下，交互式证明的知识误差$\kappa$不够小，因此需要减少，这可以通过并行地重复交互式证明来实现，虽然已经有许多工作研究了平行重复对交互式证明和论点的稳健性误差的影响，但并行重复对知识误差的影响在很大程度上仍未得到研究
直到最近才表明，对于任何不可忽略的项$\nu$，$t$-倍并行重复的交互式协议将知识误差从$\kappa$降低到$\kappa^t+\nu$，这种一般结果是次优的，因为它没有给出典型协议所期望的知识误差$\kappa^t$，更糟糕的是，知识误差仍然不可忽略
本文证明了任何$(k_1,\dots,k_{\mu})$特殊合理性多轮公共掷币交互式证明的$t$倍并行重复都能将知识误差从$\kappa$最优地降低到$\kappa^t$
本文的结果的核心是一种替代方法，在某种意义上更细粒度地衡量不诚实证明者的质量，而不是其成功概率，为此，本文证明了它表征了何时可以提取知识，当分析这种交互证明的并行重复时，这一新措施变得非常方便，虽然并行重复减少了知识误差，但很容易看出会增加完整性误差
出于这个原因，本文将结果推广到$s$-of-$t$阈值并行重复的情况，其中如果并行实例的$s$out-of$t$正在接受，则验证器接受，适当选择的阈值$s$允许同时减少知识误差和完整性误差
Public-Coin 3-Round Zero-Knowledge from Learning with Errors and Keyless Multi-Collision-Resistant Hash
Original Paper Link:
Public-Coin 3-Round Zero-Knowledge from Learning with Errors and Keyless Multi-Collision-Resistant Hash
本文为NP构建了一个公共硬币3轮零知识论证，要求下列假设
- LWE问题的次指数硬度
- 存在针对稍微超多项式时间对手的无键多重碰撞抵抗散列函数
这些假设几乎与最近用于获得私人硬币3轮零知识论证的假设相同$[Bitansky et al.，STOC 2018]$，不同之处在于本文假设LWE问题的硬度为亚指数硬度，而不是拟多项式硬度
Faster Sounder Succinct Arguments and IOPs
Original Paper Link:
Faster Sounder Succinct Arguments and IOPs
简洁的论据允许证明者使用极短的证明来说服验证者给定的陈述是真的，一个主要的瓶颈一直是大量工作的焦点，它是为了证明计算的正确性而减少证明器所产生的开销（这里的开销指的是证明正确性的成本除以原始计算的成本）
本文对于一大类布尔电路C构造了电路可满足性的简洁自变量，其合理性误差为$2^{-k}$，并且具有证明开销$polylog(k)$，这一结果依赖于（亚指数安全的）线性大小可计算的抗冲突散列函数的存在
可以通过处理的一类布尔电路包括具有重复子结构的电路，这些电路出现在自然应用中，如批量计算/验证、哈希和相关的块链应用
简洁的论点是通过为同一类语言构造交互式预言机证明来获得的，证明开销为$polylog(k)$，合理性误差为$2^{-k}$
之前的工作表名，布尔电路的最佳IOP要么具有Ben~Sasson等人（STOC，2013）提出的基于有效PCP的$polylog(|C|)$的证明开销，要么具有Rothblum和Ron Zewi提出的$poly(k)$（STOC（2022）
Succinct Interactive Oracle Proofs: Applications and Limitations
Original Paper Link:
Succinct Interactive Oracle Proofs: Applications and Limitations
交互式Oracle证明（Interactive Oracle Proofs，IOP）是一种新型的证明系统，它结合了交互式证明和PCP的关键性质：IOP使验证器能够通过与不受信任的证明程序进行交互来确信语句的正确性，同时只读取证明程序发送的少量消息
近年来，IOP在高效证明系统的设计中变得非常突出，本文研究了简洁的IOP，即在原始见证中通信复杂度是多项式（甚至线性）的IOP
尽管简洁PCP（即长度为见证中多项式的PCP）的存在有很强的不可能性结果，但已知在小空间中可判定的丰富类NP关系具有简洁的IOP
本文展示了简洁的IOP:1的新应用程序和限制
基于单向函数，本文展示了如何将IOP编译为零知识证明，同时几乎保留证明长度，这补充了Ben Sasson等人最近发起的一项工作。（TCC，2016B）
该工作中将IOP汇编成超简洁的零知识论证，将编译器应用于最先进的简洁IOP，可以产生有界空间NP关系的零知识证明，其通信长度几乎等于原始见证长度，这从单向函数的最小假设中产生了已知最短的零知识证明
其次，对于更一般的NP关系，本文给出了获得简洁IOP的障碍，本文研究表明：如果一种语言具有简洁的IOP，那么在经过有界时间概率预处理后，它可以在仅与见证长度成比例的空间中决定
本文利用这一结果，在一个简单而可信的复杂性理论猜想下，CSAT不存在简洁的IOP