A toolbox for barriers on interactive oracle proofs

DOI10.1007/978-3-031-22318-1_16MaRDI QIDQ6169366zbMATH OpenFDO

Authors Gal Arnon, Amey Bhangale, Alessandro Chiesa, Eylon Yogev

Publication date 14 August 2023

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

zbMATH Keywords

lower boundsprobabilistically checkable proofsinteractive oracle proofs

Mathematics Subject Classification ID

Cryptography (94A60)

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

Cites work

• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 7706036 (Why is no real title available?)
• A PCP characterization of AM
• A PCP theorem for interactive proofs and applications
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Barriers for succinct arguments in the random oracle model
• Computational integrity with a public random string from quasi-linear PCPs
• Constant-round interactive proofs for delegating computation
• Efficient probabilistically checkable proofs and applications to approximations
• Fast Reed-Solomon interactive oracle proofs of proximity
• Interactive oracle proofs
• Interactive oracle proofs with constant rate and query complexity
• Interactive proofs and the hardness of approximating cliques
• Libra: succinct zero-knowledge proofs with optimal prover computation
• Linear-time arguments with sublinear verification from tensor codes
• Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• On interactive proofs with a laconic prover
• On the NP-hardness of MAX-Not-2
• On the complexity of interactive proofs with bounded communication
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Short PCPs with Polylog Query Complexity
• Succinct interactive oracle proofs: applications and limitations
• The PCP theorem by gap amplification
• The complexity of satisfiability problems
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier

Cited in

(6)

• Barriers for succinct arguments in the random oracle model
• Interactive oracle proofs
• Interactive oracle proofs with constant rate and query complexity
• Succinct interactive oracle proofs: applications and limitations
• A PCP theorem for interactive proofs and applications
• On interactive oracle proofs for Boolean R1CS statements

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)