Interactive oracle proofs with constant rate and query complexity

DOI10.4230/LIPICS.ICALP.2017.40MaRDI QIDQ5111371zbMATH OpenFDO

Authors Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Publication date 27 May 2020

zbMATH Keywords

probabilistically checkable proofsinteractive proofssumcheckproof composition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Recommendations

• A toolbox for barriers on interactive oracle proofs
• Interactive oracle proofs
• Linear-size constant-query IOPs for delegating computation
• Fast Reed-Solomon interactive oracle proofs of proximity
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Cited in

(22)

• Parallelizable delegation from LWE
• Polynomial IOPs for linear algebra relations
• Ligero: lightweight sublinear arguments without a trusted setup
• Sumcheck arguments and their applications
• Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II
• On interactive oracle proofs for Boolean R1CS statements
• Interactive oracle proofs
• Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
• Fast Reed-Solomon interactive oracle proofs of proximity
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• SPARKs: succinct parallelizable arguments of knowledge
• Linear-size constant-query IOPs for delegating computation
• Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
• \textsc{Zeromorph}: zero-knowledge multilinear-evaluation proofs from homomorphic univariate commitments
• Computing Riemann-Roch spaces via Puiseux expansions
• Constant-round interactive proofs for delegating computation
• STIR: Reed-Solomon proximity testing with fewer queries
• A PCP theorem for interactive proofs and applications
• Zero-knowledge IOPs approaching witness length
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Succinct interactive oracle proofs: applications and limitations
• A toolbox for barriers on interactive oracle proofs

This page was built for publication: Interactive oracle proofs with constant rate and query complexity

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