Paper 2022/790

A Toolbox for Barriers on Interactive Oracle Proofs

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

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing succinct arguments. In this work, we study the limitations of IOPs, as well as their relation to those of PCPs. We present a versatile toolbox of IOP-to-IOP transformations containing tools for: (i) length and round reduction; (ii) improving completeness; and (iii) derandomization. We use this toolbox to establish several barriers for IOPs: -- Low-error IOPs can be transformed into low-error PCPs. In other words, interaction can be used to construct low-error PCPs; alternatively, low-error IOPs are as hard to construct as low-error PCPs. This relates IOPs to PCPs in the regime of the sliding scale conjecture for inverse-polynomial soundness error. -- Limitations of quasilinear-size IOPs for 3SAT with small soundness error. -- Limitations of IOPs where query complexity is much smaller than round complexity. -- Limitations of binary-alphabet constant-query IOPs. We believe that our toolbox will prove useful to establish additional barriers beyond our work.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
probabilistically checkable proofs interactive oracle proofs lower bounds
Contact author(s)
gal arnon @ weizmann ac il
amey bhangale @ ucr edu
alessandro chiesa @ epfl ch
eylon yogev @ biu ac il
History
2022-06-20: approved
2022-06-19: received
See all versions
Short URL
https://ia.cr/2022/790
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/790,
      author = {Gal Arnon and Amey Bhangale and Alessandro Chiesa and Eylon Yogev},
      title = {A Toolbox for Barriers on Interactive Oracle Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/790},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/790}},
      url = {https://eprint.iacr.org/2022/790}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.