Computational Integrity with a Public Random String from Quasi-Linear PCPs
From MaRDI portal
Publication:5270376
DOI10.1007/978-3-319-56617-7_19zbMath1415.94409OpenAlexW2613376966MaRDI QIDQ5270376
Matan Hamilis, Daniel Genkin, Mark Silberstein, Michael Riabzev, Madars Virza, Eran Tromer, Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Evgenya Pergament, Alessandro Chiesa
Publication date: 23 June 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-56617-7_19
Related Items
A compressed \(\varSigma \)-protocol theory for lattices, Does Fiat-Shamir require a cryptographic hash function?, Linear-size constant-query IOPs for delegating computation, On the (In)security of Kilian-based SNARGs, Ligero: lightweight sublinear arguments without a trusted setup, Multikey Fully Homomorphic Encryption and Applications, \(\mathcal{Lunar}\): a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions, A toolbox for barriers on interactive oracle proofs, Publicly verifiable zero-knowledge and post-quantum signatures from VOLE-in-the-head, Fast transforms over finite fields of characteristic two, Marlin: preprocessing zkSNARKs with universal and updatable SRS, A non-PCP approach to succinct quantum-safe zero-knowledge, New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shorter arithmetization of nondeterministic computations
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
- Practical verified computation with streaming interactive proofs
- From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
- Time-Optimal Interactive Proofs for Circuit Evaluation
- SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
- Scalable Zero Knowledge via Cycles of Elliptic Curves
- On Efficient Zero-Knowledge PCPs
- Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
- NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Short Pairing-Based Non-interactive Zero-Knowledge Arguments
- Round-Efficient Sub-linear Zero-Knowledge Arguments for Linear Algebra
- Efficient Zero-Knowledge Arguments from Two-Tiered Homomorphic Commitments
- Proof verification and the hardness of approximation problems
- Interactive Oracle Proofs
- Polynomial Codes Over Certain Finite Fields
- Locally testable codes and PCPs of almost-linear length
- Zero-Knowledge Proofs from Secure Multiparty Computation
- Two-query PCP with subconstant error
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
- Short PCPs with Polylog Query Complexity
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- The Knowledge Complexity of Interactive Proof Systems
- Probabilistic checking of proofs
- Computing Partitions with Applications to the Knapsack Problem
- Algebraic methods for interactive proof systems
- Computationally Sound Proofs
- Languages with Efficient Zero-Knowledge PCPs are in SZK
- Succinct Non-interactive Arguments via Linear Interactive Proofs
- Quadratic Span Programs and Succinct NIZKs without PCPs
- Additive Fast Fourier Transforms Over Finite Fields
- Some optimal inapproximability results
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
- Recursive composition and bootstrapping for SNARKS and proof-carrying data
- On the concrete efficiency of probabilistically-checkable proofs
- Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
- Small PCPs with low query complexity
