Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

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

zbMATH Keywords

quasilinear-size proof lengthzero-knowledge multi-prover interactive proof

Mathematics Subject Classification ID

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