Local Proofs Approaching the Witness Length [Extended Abstract]
Local Proofs Approaching the Witness Length [Extended Abstract]
复制标题
接近见证长度的局部证明[扩展摘要]
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ron D. Rothblum
中科院分区：
文献类型：
--
作者：
Noga Ron;Ron D. Rothblum
交互式甲骨文证明（IOPS）是交互式证明和PCP之间的混合体。在IOP中，供供者可以通过向验证者发送相对较长的消息来与验证者（例如在交互式证明中）进行交互，后者又只允许查询发送的几个位点（例如在PCP中） 。有效的IOP是领导高效证明系统实践实施的核心。在这项工作中，我们构建了一系列的N P关系，其中沟通复杂性接近证人的时间。更确切地说，对于任何可以在多项式时间和有限的多项式空间（例如SAT，Hamiltonity，Clique，Clique，cover-Cover等）中决定会员资格的任何n p关系）以及任何常数$ gamma> 0 $，我们构建一个iop具有通信复杂性$（1+伽玛）CDOT n $，其中$ n $是原始的证人长度。 IOP验证者的回合数以及查询数量是恒定的。该结果通过两种方式改进了简短的IOP/PCP上的先前工作。首先，在这些简短的IOP中的沟通复杂性与验证NP证人的复杂性成正比，NP证人可以多一项大于证人的规模。其次，即使忽略了证人长度和非确定性验证时间之间的差异，先前的作品（至少至少）会引起通信复杂性的巨大恒定乘法开销。特别是，作为一种特殊情况，我们还获得了带有通信复杂性$（1+gamma）CDOT t $的Circuitsat IOP，用于$ t $的电路和任何常数$ gamma> 0 $。这改善了Ben Sasson等人先前的最新工作。 （ICALP，2017年），为通信长度$ ccdot t $构建一个IOP，用于大型（未指定）常数$ CGEQ 1 $。我们的证明利用了局部可检验性和（放松的）高速张量代码的局部可靠性，以及它们对类似于Sumcheck的程序的支持。特别是，我们绕过了乘法代码低率（例如，芦苇 - 固体，芦苇 - 马勒或AG代码）所施加的障碍，这是所有已知的短PCP/IOP构造的关键构建块。
Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are at the core of leading practical implementations of highly efficient proof-systems. In this work we construct, for a large class of N P relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any N P relation for which membership can be decided in polynomial-time and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, Vertex-Cover, etc.) and for any constant $gamma > 0$, we construct an IOP with communication complexity $(1+gamma)cdot n$, where $n$ is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant. This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity. In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity $(1+gamma)cdot t$, for circuits of size $t$ and any constant $gamma > 0$. This improves upon the prior state-of-the-art work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length $ccdot t$ for a large (unspecified) constant $cgeq 1$. Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a key building block of all known short PCP/IOP constructions.