Constant-Round Interactive Proofs for Delegating Computation
From MaRDI portal
Publication:4997311
DOI10.1137/16M1096773zbMath1464.68128OpenAlexW2982087871WikidataQ113779137 ScholiaQ113779137MaRDI QIDQ4997311
Guy N. Rothblum, Omer Reingold, Ron D. Rothblum
Publication date: 29 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1096773
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Non-interactive publicly-verifiable delegation of committed programs ⋮ Nearly optimal property preserving hashing ⋮ Parallelizable delegation from LWE ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Lattice-based succinct arguments for NP with polylogarithmic-time verification ⋮ Faster sounder succinct arguments and \textsf{IOP}s ⋮ Succinct interactive oracle proofs: applications and limitations ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of interactive proofs with bounded communication
- Bit commitment using pseudorandomness
- NP is as easy as detecting unique solutions
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Highly resilient correctors for polynomials
- Pseudorandom generators for space-bounded computation
- On interactive proofs with a laconic prover
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
- Fast approximate probabilistically checkable proofs
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Improved low-degree testing and its applications
- Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
- Nearly-linear size holographic proofs
- From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
- IP = PSPACE Using Error-Correcting Codes
- Secure Two-Party Computation with Low Communication
- Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
- How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
- Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
- Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
- Succinct Randomized Encodings and their Applications
- Non-Interactive Proofs of Proximity
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- Short Pairing-Based Non-interactive Zero-Knowledge Arguments
- Efficient Probabilistically Checkable Debates
- Bravely, Moderately: A Common Theme in Four Recent Works
- Property testing and its connection to learning and approximation
- Delegating Computation
- Interactive Oracle Proofs
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- New Limits to Classical and Quantum Instance Compression
- Arguments of Proximity
- Locally testable codes and PCPs of almost-linear length
- Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
- Improved Delegation of Computation Using Fully Homomorphic Encryption
- From Secrecy to Soundness: Efficient Verification via Secure Computation
- Undirected connectivity in log-space
- The Knowledge Complexity of Interactive Proof Systems
- Relations Among Complexity Measures
- A Pseudorandom Generator from any One-way Function
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Robust Characterizations of Polynomials with Applications to Program Testing
- Succinct Non-interactive Arguments via Linear Interactive Proofs
- Quadratic Span Programs and Succinct NIZKs without PCPs
- Non-interactive delegation and batch NP verification from standard computational assumptions
- How to delegate computations
- On codes derivable from the tensor product of check matrices
- Constant-round interactive proofs for delegating computation
- Separating succinct non-interactive arguments from all falsifiable assumptions
- Recursive composition and bootstrapping for SNARKS and proof-carrying data
- Delegation for bounded space
- Interactive proofs of proximity
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Computational Complexity
- The PCP theorem by gap amplification
