Paper 2023/1062
IOPs with Inverse Polynomial Soundness Error
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
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
-
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}, url = {https://eprint.iacr.org/2023/1062} }