Edited by ZKPunk
Highlights
Dan Boneh - Thirty Years of Pairings, and What Comes Next
OpenSSH Post-Quantum Cryptography
Beyond Zero Knowledge: How Fully Homomorphic Encryption Enables Private Shared State
Updates
zkPDF and zkID with Vikas Rushi and Ying Tong
Papers
Time-Space Trade-Offs for Sumcheck
Sumcheck 协议是概率证明系统设计中的一个基本构件，近年来已成为高效简洁论证（succinct arguments）研究中的关键组成部分。我们在流式计算模型中研究了 Sumcheck 协议中证明者的时间-空间权衡，并给出了精确刻画证明者可实现效率的上下界结果。
- 对于关于单个多线性多项式的Sumcheck，我们提出了一种算法，该算法在任意参数 $k \geq 1$ 下运行时间为 $O(kN)$，空间复杂度为 $O(N^{\frac{1}{k}})$。对于非自适应证明者（non-adaptive provers，包含了所有已知的Sumcheck算法），我们证明该时间-空间权衡是最优的。
- 对于关于多线性多项式乘积的 Sumcheck，我们设计了一种证明者算法，其运行时间为 $O(N\log\log N + k)$，空间复杂度为 $O(N^{\frac{1}{k}})$，适用于任意 $k \geq 1$。我们进一步证明，在一个关于多线性多项式乘法的自然问题存在计算困难的前提下，任何使用 $O(N^{\frac{1}{2}-\epsilon})$ 空间的“自然”证明者算法都必须消耗 $\Omega(N(\log\log N + \log \epsilon))$ 的时间。
我们实现并评估了该多线性多项式乘积的证明者算法。实验表明，相较于线性时间的证明者算法，我们的算法最多可减少内存使用 $120\times$，同时时间开销控制在 $2\times$ 以内。
上述算法及其下界均适用于交互式证明模型。而在多项式交互式 oracle 证明（PIOP）模型中，我们设计了一种新协议，在任意 $k \geq 1$ 下可实现 $O(N^{\frac{1}{k}})$ 空间与 $O(N(\log^* N + k))$ 时间的更优时间-空间权衡。
If you’d like to receive updates via email, subscribe us!
🎉 Supported by GCC 🎉