Quasi-linear size zero knowledge from linear-algebraic PCPs

DOI10.1007/978-3-662-49099-0_2MaRDI QIDQ2799089zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

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

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 1559565
• On Efficient Zero-Knowledge PCPs
• Languages with efficient zero-knowledge PCPs are in SZK
• Zero knowledge protocols from succinct constraint detection
• Probabilistically checkable proofs of proximity with zero-knowledge

Cites work

• A one-round, two-prover, zero-knowledge protocol for NP
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Combinatorial Nullstellensatz
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• scientific article; zbMATH DE number 708807 (Why is no real title available?)
• scientific article; zbMATH DE number 708820 (Why is no real title available?)
• scientific article; zbMATH DE number 1559565 (Why is no real title available?)
• scientific article; zbMATH DE number 1405671 (Why is no real title available?)
• scientific article; zbMATH DE number 4185024 (Why is no real title available?)
• Interactive locking, zero-knowledge PCPs, and unconditional cryptography
• Interactive PCP
• IP = PSPACE
• Languages with efficient zero-knowledge PCPs are in SZK
• Nearly-linear size holographic proofs
• Non-deterministic exponential time has two-prover interactive protocols
• On Efficient Zero-Knowledge PCPs
• On the concrete efficiency of probabilistically-checkable proofs
• Polylogarithmic two-round argument systems
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Robust PSPs of proximity, shorter PSPs and applications to coding
• Short PCPs with Polylog Query Complexity
• Short PCPs with projection queries
• Small PCPs with low query complexity
• The knowledge complexity of interactive proof-systems
• The PCP theorem by gap amplification
• Zero-knowledge proofs from secure multiparty computation

Cited in

(20)

• Zero knowledge protocols from succinct constraint detection
• Marlin: preprocessing zkSNARKs with universal and updatable SRS
• Publicly verifiable zero knowledge from (collapsing) blockchains
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• Linear-size constant-query IOPs for delegating computation
• Nearly-linear size holographic proofs
• Interactive oracle proofs
• Zero-knowledge proofs of proximity
• Constant-round interactive proofs for delegating computation
• Fast Reed-Solomon interactive oracle proofs of proximity
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• scientific article; zbMATH DE number 7250164 (Why is no real title available?)
• Computational integrity with a public random string from quasi-linear PCPs
• Sublinear zero-knowledge arguments for RAM programs
• Theory of Cryptography
• Witness-succinct universally-composable SNARKs
• A toolbox for barriers on interactive oracle proofs
• Beyond MPC-in-the-head: black-box constructions of short zero-knowledge proofs
• Zero-knowledge IOPs approaching witness length
• Hamming weight proofs of proximity with one-sided error

This page was built for publication: Quasi-linear size zero knowledge from linear-algebraic PCPs

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