A toolbox for barriers on interactive oracle proofs

DOI10.1007/978-3-031-22318-1_16zbMATH Open1519.94035MaRDI QIDQ6169366FDOQ6169366

Gal Arnon, Amey Bhangale, Alessandro Chiesa, Eylon Yogev

Publication date: 14 August 2023

Published in: Theory of Cryptography (Search for Journal in Brave)

Recommendations

• Interactive oracle proofs with constant rate and query complexity
• Interactive oracle proofs
• A PCP theorem for interactive proofs and applications
• Linear-size constant-query IOPs for delegating computation
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier

zbMATH Keywords

lower boundsprobabilistically checkable proofsinteractive oracle proofs

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• Proof verification and the hardness of approximation problems
• Short PCPs with Polylog Query Complexity
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• The complexity of satisfiability problems
• On interactive proofs with a laconic prover
• A PCP theorem for interactive proofs and applications
• On the complexity of interactive proofs with bounded communication
• Efficient probabilistically checkable proofs and applications to approximations
• Title not available (Why is that?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The PCP theorem by gap amplification
• Constant-round interactive proofs for delegating computation
• Random Debaters and the Hardness of Approximating Stochastic Functions
• On the NP-Hardness of Max-Not-2
• Libra: succinct zero-knowledge proofs with optimal prover computation
• Interactive Oracle Proofs
• Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
• Title not available (Why is that?)
• Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
• Fast Reed-Solomon Interactive Oracle Proofs of Proximity
• Title not available (Why is that?)
• Computational Integrity with a Public Random String from Quasi-Linear PCPs
• Linear-time arguments with sublinear verification from tensor codes
• Barriers for succinct arguments in the random oracle model
• Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
• Succinct interactive oracle proofs: applications and limitations
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• A PCP Characterization of AM
• Title not available (Why is that?)

Cited In (3)

• Barriers for succinct arguments in the random oracle model
• On interactive oracle proofs for Boolean R1CS statements
• Succinct interactive oracle proofs: applications and limitations

This page was built for publication: A toolbox for barriers on interactive oracle proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169366)