Paper 2019/1062
Local Proofs Approaching the Witness Length
Noga RonZewi and Ron D. Rothblum
Abstract
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). In this work we construct, for a large class of NP relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any NP relation for which membership can be decided in polynomialtime and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, VertexCover, 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 nondeterministic 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 rate approaching 1: the communication complexity is $(1+\gamma) \cdot t$, for circuits of size $t$ and any constant $\gamma>0$. This improves upon the prior stateoftheart work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length $c \cdot t$ for a large (unspecified) constant $c \geq 1$. Our proof leverages recent constructions of highrate locally testable tensor codes. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., ReedSolomon, ReedMuller or AG codes)  a core component in all known short PCP/IOP constructions.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MINOR revision.FOCS 2020
 Keywords
 PCPIOP
 Contact author(s)

rothblum @ cs technion ac il
noga @ cs haifa ac il  History
 20210112: revised
 20190921: received
 See all versions
 Short URL
 https://ia.cr/2019/1062
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1062, author = {Noga RonZewi and Ron D. Rothblum}, title = {Local Proofs Approaching the Witness Length}, howpublished = {Cryptology ePrint Archive, Paper 2019/1062}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1062}}, url = {https://eprint.iacr.org/2019/1062} }