# 欧密2022之十篇零知识证明论文简介

- [A PCP Theorem for Interactive Proofs and Applications](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_3)
提出PCP定理的扩展--IOP定理：任何k轮IP可以判定的语言都具有一个k轮公开抛币IOP，其中验证者在每条消息中读取$O(1)$的比特。几个应用：对一个随机可满足性问题的新的近似困难结果，IOP到IOP转换，新概念index-decodable PCP，允许对非确定性计算在ROM中得到一个commit-and-prove SNARK。

- [Families of SNARK-friendly 2-chains of elliptic curves](https://eprint.iacr.org/2021/1359.pdf)
CANS’20引入了对递归zk-SNARK友好的配对友好椭圆曲线的2链：由BLS12-377曲线和新的BW6-761曲线构成。本文推广到定义在任意BLS12曲线上的任意BW6曲线，构成了一个新的2链配对友好曲线簇。导出新的CP曲线上的optimal ate and optimal Tate配对的高效公式，说明对BLS12和BLS24，BW6的构造相比于CP曲线具有最快的配对速度。BLS12-377/BW6-761对Groth16是最优的，而BLS24-315/BW6-672对PlonK是最优的。

- [Gemini: elastic SNARKs for diverse environments](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_15)
提出Elastic SNARKs：证明者可以依据执行环境和要证明的语句灵活分配不同的时间（线性或准线性）空间（线性或对数）资源，且生成的结果不变。提供elastic PIOP的定义框架并给出elastic PIOP到支持对输入顺序或随机访问的预处理论证系统的编译器。给出Gemini，一个新的无FFT的预处理elastic SNARKs。

- [SNARGs for P from Sub-exponential DDH and QR](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_18)
基于亚指数DDH和QR假设，得到对任意确定性计算和受限空间非确定性计算的公开可验证SNARGs。

- [Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_10)
构造一个IOP，同时满足：零知识，线性时间证明，多项式对数时间验证。通过已知转换，可以得到证明者线性时间验证者多项式对数时间的零知识论证系统，且该构造只黑盒使用抗碰撞哈希，因而是后量子的。

- [Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_11)
$\mathrm{NC}^1$细粒度场景，即敌手在$\mathrm{NC}^1$中。基于$\mathrm{NC}^{1} \subsetneq \oplus \mathrm{L} / \mathrm{poly}$ 假设，构造出首个对电路可满足性问题的NIZK。在从$\Sigma$协议到NIZK的转换中不使用RO，和FS转换不同。在细粒度场景中提出全同态加密作为构造组件。通过扩展该方法，得到了URS模型中的两个NIZK和两个ZAP。

- [On Succinct Non-Interactive Arguments in Relativized Worlds](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_12)
提出低阶随机预言模型，其中存在对所有NP计算的相对于该预言$\mathcal{O}$的透明SNARKs，该SNARK可以直接证明和其自身验证者算法相关的计算（即递归证明组合）。提出更广义的线性编码随机预言模型LCROM。展示了如何在LCROM中对查询预言的计算，通过给定一个对预言查询的累加器方案，得到SNARKs，并对一个低阶随机预言构造了该累加器方案。

- [Fiat-Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_14)
在AGM中证明了FS-Bulletproofs满足simulation-extractability（模拟可抽取），进而蕴含其为非延展的。

- [Stacking Sigmas: A Framework to Compose Sigma-Protocols for Disjunctions](https://eprint.iacr.org/2021/422)
提出一个广义框架：将一大类多个对单独语句（相同或不相同）的$\Sigma$协议编译为一个新的证明这些语句的并的$\Sigma$协议。通信复杂度只和最大的子句成正比。该编译器可以应用在很多著名的$\Sigma$协议上，比如Schnorr，GQ，MPC-in-the-head，Ligero等等。

- [One-Shot Fiat-Shamir-based NIZK Arguments of Composite Residuosity and Logarithmic-Size Ring Signatures in the Standard Model ](https://eprint.iacr.org/2020/1334)
对于Paillier的DCR假设相关的语言给出了首个一次提供可靠性的陷门$\Sigma$协议，通过指数大的挑战空间。通过使用CIHF范式，得到证明一个元素是composite residue的simulation-sound的NIZK论证。给出标准模型中基于标准假设对数大小的环签名，基于DCR和LWE假设证明安全。