On interactive proofs with a laconic prover
By Oded Goldreich, Salil P. Vadhan, Avi Wigderson. 2001
124 citations recorded by the source corpus.
AbstractWe continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Håstad (1998). Let L be a language that has an interactive proof in which the prover sends few (say b) bits to the verifier. We prove that the complement $\bar L$ has a constant-round interactive proof of complexity that depends only exponentially on b. This provides the first evidence that for NP-complete languages, we cannot expect interactive provers to be much more “laconic” than the standard NP proof. When the proof system is further restricted (e.g., when b = 1, or when we have perfect completeness), we get significantly better upper bounds on the complexity of $\bar L$.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Dan Boneh
- Srinath T. V. Setty
- Eli Ben-Sasson
- Yuval Ishai
- Eran Tromer
- Alessandro Chiesa
- Henry Corrigan-Gibbs
- Jens Groth
In Computational Theory and Mathematics
- Eli Ben-Sasson
- Dan Boneh
- Eran Tromer
- Alessandro Chiesa
- Srinath T. V. Setty
- Henry Corrigan-Gibbs
- Yuval Ishai
- Benedikt Bünz
Citations in the corpus
- Transparent SNARKs from DARK Compilers (2020, background): “Succinct statistically sound proofs are unlikely to exist [32].”
- Introduction to Property Testing (2017, background): “22 Advanced comment: The focus on short proofs is reminicent of the study of laconic interactive proof systems, but that study focused on systems in which at least two messages are sent [159].”
- Interactive Oracle Proofs (2016, background): “The relaxation from statistical soundness to computational soundness allows circumventing various limitations of IPs [BHZ87, GH98, GVW02, PSSV07], while also avoiding “structural” assumptions on the prover, which can be hard to enforce in applications.”
- Recursive composition and bootstrapping for SNARKS and proof-carrying data (2013, background): “Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data Nir Bitansky* Ran Canetti Alessandro Chiesa Eran Tromer nirbitan@tau.ac.il canetti@tau.ac.il alexch@csail.mit.edu tromer@tau.ac.il Tel Aviv University Boston University and MIT Tel Aviv University Tel Aviv University ABSTR”
- Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation (2016, background): “te). Gur and Rothblum [GR15] obtain a similar square-root speedup for checking sums in the “non-interactive property testing” setting. Goldreich and Hastad [GH98] and Goldreich, Vadhan, and Wigderson [GVW02] studied interactive proofs which seek to minimize the number of bits sent from Merlin to Art”
- Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, background): “It will then follow from negative results on laconic proof systems for NP [72] that there are some simple languages L which separate between the two settings.”
- Efficient Arguments without Short PCPs (2007, unknown): “Before describing our approach, we give some background to put it in context.”
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Such proof systems cannot be statistically sound (under plausible complexity-theoretic assumptions [18, 42, 45, 92]) so that one must settle for argument”
- Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting (2016, background): “However, proofs cannot in general have communication that is smaller than the witness size unless surprising results about the complexity of solving SAT instances hold [15, 17].”