Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
From MaRDI portal
Publication:2799089
DOI10.1007/978-3-662-49099-0_2zbMath1375.94101OpenAlexW2291472021MaRDI QIDQ2799089
Eli Ben-Sasson, Madars Virza, Alessandro Chiesa, Ariel Gabizon
Publication date: 8 April 2016
Published in: Theory of Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-49099-0_2
Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Interactive Oracle Proofs, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier, Linear-size constant-query IOPs for delegating computation, Witness-succinct universally-composable SNARKs, A toolbox for barriers on interactive oracle proofs, Zero-Knowledge Proofs of Proximity, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, Sublinear Zero-Knowledge Arguments for RAM Programs, Marlin: preprocessing zkSNARKs with universal and updatable SRS, Unnamed Item, Publicly verifiable zero knowledge from (collapsing) blockchains, Constant-Round Interactive Proofs for Delegating Computation, Computational Integrity with a Public Random String from Quasi-Linear PCPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- A one-round, two-prover, zero-knowledge protocol for NP
- Nearly-linear size holographic proofs
- On Efficient Zero-Knowledge PCPs
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Proof verification and the hardness of approximation problems
- Interactive PCP
- Zero-Knowledge Proofs from Secure Multiparty Computation
- Robust pcps of proximity, shorter pcps and applications to coding
- Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography
- Polylogarithmic two-round argument systems
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- Combinatorial Nullstellensatz
- Algebraic methods for interactive proof systems
- IP = PSPACE
- The knowledge complexity of interactive proof-systems
- Languages with Efficient Zero-Knowledge PCPs are in SZK
- Short PCPs with Projection Queries
- On the concrete efficiency of probabilistically-checkable proofs
- 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