eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2023/1062

IOPs with Inverse Polynomial Soundness Error

Gal Arnon, Weizmann Institute of Science
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Eylon Yogev, Bar-Ilan University
Abstract

We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity. This achieves parameters that surpass all previously known PCPs and IOPs. Specifically, we construct an IOP with perfect completeness, soundness error $1/n$, round complexity $O(\log \log n)$, proof length $poly(n)$ over an alphabet of size $O(n)$, and query complexity $O(\log \log n)$. This is a step forward in the quest to establish the sliding-scale conjecture for IOPs (which would additionally require query complexity $O(1)$). Our main technical contribution is a high-soundness small-query proximity test for the Reed-Solomon code. We construct an IOP of proximity for Reed-Solomon codes, over a field $\mathbb{F}$ with evaluation domain $L$ and degree $d$, with perfect completeness, soundness error (roughly) $\max\{1-\delta , O(\rho^{1/4})\}$ for $\delta$-far functions, round complexity $O(\log \log d)$, proof length $O(|L|/\rho)$ over $\mathbb{F}$, and query complexity $O(\log \log d)$; here $\rho = (d+1)/|L|$ is the code rate. En route, we obtain a new high-soundness proximity test for bivariate Reed-Muller codes. The IOP for NP is then obtained via a high-soundness reduction from NP to Reed-Solomon proximity testing with rate $\rho = 1/poly(n)$ and distance $\delta = 1-1/poly(n)$ (and applying our proximity test). Our constructions are direct and efficient, and hold the potential for practical realizations that would improve the state-of-the-art in real-world applications of IOPs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. FOCS 2023
Keywords
interactive oracle proofsReed-Solomon proximity testingsliding-scale conjecture
Contact author(s)
galarnon42 @ gmail com
alessandro chiesa @ epfl ch
eylon yogev @ biu ac il
History
2023-10-28: last of 4 revisions
2023-07-07: received
See all versions
Short URL
https://ia.cr/2023/1062
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1062,
      author = {Gal Arnon and Alessandro Chiesa and Eylon Yogev},
      title = {IOPs with Inverse Polynomial Soundness Error},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1062},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1062}},
      url = {https://eprint.iacr.org/2023/1062}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.