摘要 Abstract
我们针对三变量Reed-Muller码提供了一种交互式oracle证明系统(IOPP),在某些安全参数范围内实现了已知的最佳查询复杂度。具体而言,对于次数为$d$且安全参数$\lambda\leq \frac{\log^2 d}{\log\log d}$的情况,我们的IOPP具有$2^{-\lambda}$的逐轮声辩性,$O(\lambda)$次查询,$O(\log\log d)$轮次以及$O(d)$长度。这优于FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] 和STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] 对Reed-Solomon码的IOPP,后者的查询和轮次复杂度分别较大,分别为$O(\lambda \log d)$和$O(\log d+\lambda\log\log d)$。我们利用该IOPP给出了NP完全语言Rank-1-Constraint-Satisfaction的IOP,具有相同的参数。我们的构造基于低声辩性下的线对点测试。与之前工作使用的轴平行测试相比,一般仿射线测试具有改进的声辩性,这是改进声辩性的主要来源。使用此测试涉及若干复杂情况,最显著的是投影到仿射线不保持单项式的次数,我们展示了如何克服这些困难。在此过程中,我们将一些现有工具扩展到了更一般的设置。具体来说,我们给出了Reed-Muller码的接近生成器,展示了一种处理IOP构造中“侧条件”的更系统的方法,并将[Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] 的编译程序推广到一般码。
We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifically, for degree $d$ and security parameter $\lambda\leq \frac{\log^2 d}{\log\log d}$ , our IOPP has $2^{-\lambda}$ round-by-round soundness, $O(\lambda)$ queries, $O(\log\log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda\log\log d)$ respectively. We use our IOPP to give an IOP for the NP-complete language Rank-1-Constraint-Satisfaction with the same parameters. Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling ``side conditions'' in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.