A Zero-Knowledge PCP Theorem

我们证明了对于每一个多项式 q*，都存在针对 NP 的多项式规模、常数查询次数、非自适应的 PCP，这些 PCP 能够在对抗最多进行 q* 次查询的（自适应）对手时实现完美的零知识。此外，我们还构建了针对 NEXP 的指数规模、常数查询次数的 PCP，这些 PCP 能够在对抗任何多项式时间对手时实现完美的零知识。这不仅改进了最近关于 #P 的完美零知识 PCP 构造（STOC 2024），也超越了 Kilian、Petrank 和 Tardos 的开创性工作（STOC 1997）。

该论文试图解决的问题是为NP和NEXP构建具有完美零知识特性的概率可验证证明（PCP），特别是针对能够进行多项式数量查询的适应性对手。这是一个在理论计算机科学和密码学领域内的重要问题，涉及如何在不泄露任何额外信息的情况下验证计算的正确性。

论文的关键思路在于构造了两种不同规模的PCP系统：对于NP类问题，构建了多项式大小、常数查询次数的非自适应PCP，这些PCP对最多进行q*次查询的适应性对手具有完美零知识特性；而对于NEXP类问题，则构建了指数大小、常数查询次数的PCP，对任何多项式时间对手也具有完美零知识特性。这一思路在保持验证效率的同时，显著增强了系统的安全性。

论文的主要亮点包括：1) 构建了多项式大小的PCP系统，适用于NP类问题，并且能够抵抗适应性对手的攻击；2) 对于NEXP类问题，构建了指数大小的PCP系统，进一步扩展了完美零知识PCP的应用范围；3) 改进了之前的工作，如Kilian, Petrank和Tardos (STOC 1997) 的成果，以及最近关于#P类问题的完美零知识PCP的研究 (STOC 2024)。此外，论文没有提及具体的数据集或开源代码，但强调了未来研究的方向，例如如何进一步减少PCP的大小和查询次数。

近年来，在这一领域内的相关研究包括：1) Kilian, Petrank和Tardos (STOC 1997) 提出的早期PCP系统，奠定了这一领域的基础；2) STOC 2024上的关于#P类问题的完美零知识PCP的研究，展示了在特定复杂度类中的应用；3) 其他相关研究还包括Micali (FOCS 1994) 的关于NEXP的PCP系统，以及Goldreich, Micali和Wigderson (STOC 1986) 在零知识证明方面的开创性工作。