Fast Reed-Solomon Interactive Oracle Proofs of Proximity
From MaRDI portal
Publication:5002680
DOI10.4230/LIPIcs.ICALP.2018.14zbMath1499.68141OpenAlexW2885314357MaRDI QIDQ5002680
Yinon Horesh, Iddo Bentov, Michael Riabzev, Eli Ben-Sasson
Publication date: 28 July 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9018/pdf/LIPIcs-ICALP-2018-14.pdf/
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Cyclic codes (94B15)
Related Items (26)
\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Time- and space-efficient arguments from groups of unknown order ⋮ Does Fiat-Shamir require a cryptographic hash function? ⋮ High-threshold AVSS with optimal communication complexity ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ A PCP theorem for interactive proofs and applications ⋮ Gemini: elastic SNARKs for diverse environments ⋮ Linear-size constant-query IOPs for delegating computation ⋮ On the (In)security of Kilian-based SNARGs ⋮ On interactive oracle proofs for Boolean R1CS statements ⋮ HyperPlonk: Plonk with linear-time prover and high-degree custom gates ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Lattice-based succinct arguments for NP with polylogarithmic-time verification ⋮ On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ \textsc{Poseidon}2: a faster version of the \textsc{Poseidon} hash function ⋮ \textsf{Bingo}: adaptivity and asynchrony in verifiable secret sharing and distributed key generation ⋮ \textsf{Orbweaver}: succinct linear functional commitments from lattices ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Unnamed Item ⋮ Transparent SNARKs from DARK compilers ⋮ \textsc{Fractal}: post-quantum and transparent recursive proofs from holography ⋮ Unnamed Item ⋮ Practical product proofs for lattice commitments
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Self-testing/correcting with applications to numerical problems
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
- Nearly-linear size holographic proofs
- Practical verified computation with streaming interactive proofs
- From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
- SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
- Proof verification and the hardness of approximation problems
- Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
- Polynomial Codes Over Certain Finite Fields
- Interactive PCP
- Two-query PCP with subconstant error
- Short PCPs with Polylog Query Complexity
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Computationally Sound Proofs
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- New Direct-Product Testers and 2-Query PCPs
- Quadratic Span Programs and Succinct NIZKs without PCPs
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Constant-round interactive proofs for delegating computation
- Some optimal inapproximability results
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
- On the concrete efficiency of probabilistically-checkable proofs
- Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- The PCP theorem by gap amplification
This page was built for publication: Fast Reed-Solomon Interactive Oracle Proofs of Proximity
