下个月召开的密码学顶会Crypto22中的零知识证明相关论文简介。

看完摘要我直呼牛逼，谁说零知识证明学术理论研究已经结束，现在只剩工程应用的果子了？

https://www.iacr.org/cryptodb//data/paper.php?pubkey=32215

新零知识论证系统 Orion，域运算和哈希函数的 O(N)的证明时间，O(log^2 N)证明大小。提出了一种基于最密集子图算法的新算法来测试随机二分图是否是无损扩展图。开发了一种有效的证明组合方案，代码转换，以将证明大小从平方根减少到多项式对数。

https://eprint.iacr.org/2022/819

提出恶意安全的 VOLE 扩展协议，将短的种子 VOLE 转换为同样环上的伪随机 VOLE。新基于 VOLE 的证明系统 QuarkSilver。

https://eprint.iacr.org/2021/370

实现增量可验证计算 (IVC)的新方法，完全避免使用 SNARKs，而是使用折叠方案。常数递归开销，每步证明者开销由两个多指数支配，证明本身线性但使用已知 zkSNARK 可以对有效证证明进行简洁的零知识知识证明，不需要可信设置，不需要 FFT。

https://eprint.iacr.org/2022/767

构造对 NP 语言的高效非延展零知识的新方法，基于新原语：基于实例的非延展承诺。第一个无需公钥假设的非延展承诺方案。

https://eprint.iacr.org/2022/820

假设：1.带错误学习问题的亚指数困难性，2.存在对稍微超多项式时间敌手的无密钥抗多碰撞哈希函数，构造了对 NP 的公开抛币 3 轮零知识论证系统。

https://eprint.iacr.org/2021/1259

说明了任何 k_1,…,k_mu 特殊可靠多轮公开抛币交互式证明系统，t 路并发重复最优地降低了知识错误。结果泛化到 t 中取 s 门限并发重复，以同时降低知识错误和完备性错误。

https://www.iacr.org/cryptodb//data/paper.php?pubkey=32176

假设存在亚指数安全线性可计算抗碰撞哈希函数，对具有重复子结构等一大类布尔电路，构造 IOP 以及相应的简洁论证系统，证明者开销 polylog(k)。

https://eprint.iacr.org/2022/281

简洁 IOP，通信复杂度是证据的多项式（甚至线性），介绍其应用和局限。对空间受限 NP 关系，使用单向函数，展示如何保持证明长度同时编译 IOP 为零知识证明，通信复杂度几乎和证据长度相等，得到最小假设下最短的零知识证明。对更一般 NP 关系，证明在一个新复杂度理论猜想下，不存在对 CSAT 的简洁 IOP。

https://eprint.iacr.org/2021/1315

提出对 QMA 的经认证的永久零知识证明，这是一种计算零知识证明，但验证者发送其已经删除所有的量子信息的经典证书。如果证书有效，达到统计零知识。引入原语：统计绑定和经认证的永久隐藏承诺方案，基于带证书删除的量子加密方案构造。并将其和对 QMA 的量子 Sigma 协议组合，在量子随机预言模型下得到对 QMA 的经认证的永久零知识证明。

https://eprint.iacr.org/2022/284

基于模 SIS 和模 LWE 问题困难假设，构造对满足 As=t mod q 的短向量 s 的知识证明系统。展示了证明 s 系数具有小的 l2 范式的更直接高效的方法。

https://www.iacr.org/cryptodb//data/paper.php?pubkey=32191

基于 SIS 的扩展假设，提出首个格基 SNARK，同时满足：1. 后量子安全 2. 公开课验证 3. 对数时间验证者 4. 支持高效递归组合。将配对方案转译成格基方案的技术组件。新格基向量承诺方案，支持对常数阶多边量多项式映射的打开。

https://www.iacr.org/cryptodb//data/paper.php?pubkey=32247

提出基于格的对 R1CS 的亚线性大小零知识证明系统，证明大小是证据的平方根，比 Ligero 小 2-3 倍。Schwartz-Zippel 引理的交互式变体。

https://eprint.iacr.org/2022/857

假设不可区分混淆和带错误学习的后量子安全，构造了通信复杂度和验证者运行时间是量子计算多项式对数的经典可验证简洁交互式论证系统，是首个平凡模型中对量子计算简洁论证系统。对 QMA 的简洁论证系统；量子随机预言模型中对 QMA 的简洁非交互论证系统；假设带错误学习,对 QMA 的简洁批量论证系统。

https://eprint.iacr.org/2022/336

首个基于双线性群上标准假设的对 NP 的非交互批量论证系统构造。不使用相关困难哈希函数和概率可检验证明证明的构造批量验证的直接方法。首个亚线性 CRS 的对 P 的 SNARG，以及首个基于双线性标准假设的聚合签名。

https://eprint.iacr.org/2022/188

对随机线性码上的特征解码问题的零知识证明系统，依赖 MPC-in-the-head 范式。得到超过 Picnic3 并和 SPHINCS+ 比较的签名算法。

https://eprint.iacr.org/2022/270

承诺并打开 Sigma 协议会得到在线可抽取性的非交互方案，在量子随机预言模型中证明了紧致在线可抽取性。对 Picnic 签名的可证明后量子安全性得到了巨大的提升。

https://eprint.iacr.org/2022/178

基于随机化指数时间假设，证明了随机预言模型中的 SNARG 的紧致下界，对非可适应性验证者和加盐可靠性的构造都成立。

https://eprint.iacr.org/2021/1516

后量子安全单向函数，后量子常数轮黑盒两方安全计算协议。

https://www.iacr.org/cryptodb//data/paper.php?pubkey=32139

可验证关系分享 VRS 是对秘密分享和零知识证明的泛化概念，每个高效可计算的关系可以通过具有两轮最佳轮复杂度的 VRS 来实现，其中第一轮与输入无关（离线轮），UC 安全。产生了多验证者零知识证明 (MVZK) 的 2 轮离线 / 在线构造。