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)

Full work available at URL https://doi.org/10.1007/978-3-031-22318-1_16

zbMATH Keywords

interactive oracle proofslower boundsprobabilistically checkable 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

• 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
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 7706036 (Why is no real title available?)
• 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 complexity of interactive proofs with bounded communication
• On the NP-hardness of MAX-Not-2
• 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 complexity of satisfiability problems
• The PCP theorem by gap amplification
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier

Cited in

(8)

• Barriers for succinct arguments in the random oracle model
• A PCP theorem for interactive proofs and applications
• Interactive oracle proofs
• Interactive oracle proofs with constant rate and query complexity
• On interactive oracle proofs for Boolean R1CS statements
• Succinct interactive oracle proofs: applications and limitations
• Hamming weight proofs of proximity with one-sided error
• Quantum interactive oracle proofs

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)