# 美密22零知识证明论文19篇简介 By [Kurt Pan](https://paragraph.com/@kurtpan) · 2022-07-19 --- > 下个月召开的密码学顶会`Crypto22`中的零知识证明相关论文简介。 > > 看完摘要我直呼牛逼，谁说零知识证明学术理论研究已经结束，现在只剩工程应用的果子了？ [https://www.iacr.org/cryptodb//data/paper.php?pubkey=32215](https://www.iacr.org/cryptodb//data/paper.php?pubkey=32215) 新零知识论证系统Orion，域运算和哈希函数的O(N)的证明时间，O(log^2 N)证明大小。提出了一种基于最密集子图算法的新算法来测试随机二分图是否是无损扩展图。开发了一种有效的证明组合方案，代码转换，以将证明大小从平方根减少到多项式对数。 [https://eprint.iacr.org/2022/819](https://eprint.iacr.org/2022/819) 提出恶意安全的VOLE扩展协议，将短的种子VOLE转换为同样环上的伪随机VOLE。新基于VOLE的证明系统QuarkSilver。 [https://eprint.iacr.org/2021/370](https://eprint.iacr.org/2021/370) 实现增量可验证计算 (IVC)的新方法，完全避免使用SNARKs，而是使用折叠方案。常数递归开销，每步证明者开销由两个多指数支配，证明本身线性但使用已知zkSNARK可以对有效证证明进行简洁的零知识知识证明，不需要可信设置，不需要FFT。 [https://eprint.iacr.org/2022/767](https://eprint.iacr.org/2022/767) 构造对NP语言的高效非延展零知识的新方法，基于新原语：基于实例的非延展承诺。第一个无需公钥假设的非延展承诺方案。 [https://eprint.iacr.org/2022/820](https://eprint.iacr.org/2022/820) 假设：1.带错误学习问题的亚指数困难性，2.存在对稍微超多项式时间敌手的无密钥抗多碰撞哈希函数，构造了对NP的公开抛币3轮零知识论证系统。 [https://eprint.iacr.org/2021/1259](https://eprint.iacr.org/2021/1259) 说明了任何k\_1,...,k\_mu特殊可靠多轮公开抛币交互式证明系统，t路并发重复最优地降低了知识错误。结果泛化到t中取s门限并发重复，以同时降低知识错误和完备性错误。 [https://www.iacr.org/cryptodb//data/paper.php?pubkey=32176](https://www.iacr.org/cryptodb//data/paper.php?pubkey=32176) 假设存在亚指数安全线性可计算抗碰撞哈希函数，对具有重复子结构等一大类布尔电路，构造IOP以及相应的简洁论证系统，证明者开销polylog(k)。 [https://eprint.iacr.org/2022/281](https://eprint.iacr.org/2022/281) 简洁IOP，通信复杂度是证据的多项式（甚至线性），介绍其应用和局限。对空间受限NP关系，使用单向函数，展示如何保持证明长度同时编译IOP为零知识证明，通信复杂度几乎和证据长度相等，得到最小假设下最短的零知识证明。对更一般NP关系，证明在一个新复杂度理论猜想下，不存在对CSAT的简洁IOP。 [https://eprint.iacr.org/2021/1315](https://eprint.iacr.org/2021/1315) 提出对QMA的经认证的永久零知识证明，这是一种计算零知识证明，但验证者发送其已经删除所有的量子信息的经典证书。如果证书有效，达到统计零知识。引入原语：统计绑定和经认证的永久隐藏承诺方案，基于带证书删除的量子加密方案构造。并将其和对QMA的量子Sigma协议组合，在量子随机预言模型下得到对QMA的经认证的永久零知识证明。 [https://eprint.iacr.org/2022/284](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](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](https://www.iacr.org/cryptodb//data/paper.php?pubkey=32247) 提出基于格的对R1CS的亚线性大小零知识证明系统，证明大小是证据的平方根，比Ligero小2-3倍。Schwartz-Zippel引理的交互式变体。 [https://eprint.iacr.org/2022/857](https://eprint.iacr.org/2022/857) 假设不可区分混淆和带错误学习的后量子安全，构造了通信复杂度和验证者运行时间是量子计算多项式对数的经典可验证简洁交互式论证系统，是首个平凡模型中对量子计算简洁论证系统。对QMA的简洁论证系统；量子随机预言模型中对QMA的简洁非交互论证系统；假设带错误学习,对QMA的简洁批量论证系统。 [https://eprint.iacr.org/2022/336](https://eprint.iacr.org/2022/336) 首个基于双线性群上标准假设的对NP的非交互批量论证系统构造。不使用相关困难哈希函数和概率可检验证明证明的构造批量验证的直接方法。首个亚线性CRS的对P的SNARG，以及首个基于双线性标准假设的聚合签名。 [https://eprint.iacr.org/2022/188](https://eprint.iacr.org/2022/188) 对随机线性码上的特征解码问题的零知识证明系统，依赖MPC-in-the-head范式。得到超过Picnic3并和SPHINCS+比较的签名算法。 [https://eprint.iacr.org/2022/270](https://eprint.iacr.org/2022/270) 承诺并打开Sigma协议会得到在线可抽取性的非交互方案，在量子随机预言模型中证明了紧致在线可抽取性。对Picnic签名的可证明后量子安全性得到了巨大的提升。 [https://eprint.iacr.org/2022/178](https://eprint.iacr.org/2022/178) 基于随机化指数时间假设，证明了随机预言模型中的SNARG的紧致下界，对非可适应性验证者和加盐可靠性的构造都成立。 [https://eprint.iacr.org/2021/1516](https://eprint.iacr.org/2021/1516) 后量子安全单向函数，后量子常数轮黑盒两方安全计算协议。 [https://www.iacr.org/cryptodb//data/paper.php?pubkey=32139](https://www.iacr.org/cryptodb//data/paper.php?pubkey=32139) 可验证关系分享VRS是对秘密分享和零知识证明的泛化概念，每个高效可计算的关系可以通过具有两轮最佳轮复杂度的 VRS 来实现，其中第一轮与输入无关（离线轮），UC安全。产生了多验证者零知识证明 (MVZK) 的 2 轮离线/在线构造。 --- *Originally published on [Kurt Pan](https://paragraph.com/@kurtpan/22-19)*