Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance

DOI10.1007/978-3-031-58737-5_5MaRDI QIDQ6637522

Rafael Pass, Omer Paneth, Cody Freitag

Publication date: 13 November 2024

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Communication complexity, information complexity (68Q11)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Parallel coin-tossing and constant-round secure two-party computation
On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
The hunting of the SNARK
Transparent SNARKs from DARK compilers
SPARKs: succinct parallelizable arguments of knowledge
Marlin: preprocessing zkSNARKs with universal and updatable SRS
Spartan: efficient and general-purpose zkSNARKs without trusted setup
Public-coin zero-knowledge arguments with (almost) minimal time and space overheads
Time- and space-efficient arguments from groups of unknown order
SNARGs for P from sub-exponential DDH and QR
Zero-knowledge proofs on secret-shared data via fully linear PCPs
Scalable zero knowledge with no trusted setup
Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
Limits of Extractability Assumptions with Distributional Auxiliary Input
On the Existence of Extractable One-Way Functions
Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits
Local zero knowledge
Constant-Size Commitments to Polynomials and Their Applications
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Interactive Oracle Proofs
Delegating RAM Computations
Short PCPs with Polylog Query Complexity
Universal Arguments and their Applications
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Interactive proofs and the hardness of approximating cliques
A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order
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
Constant-Round Interactive Proofs for Delegating Computation
Fast Reed-Solomon Interactive Oracle Proofs of Proximity
Polynomial IOPs for Linear Algebra Relations
How to delegate computations publicly
Succinct delegation for low-space non-deterministic computation
How to delegate computations
Separating succinct non-interactive arguments from all falsifiable assumptions
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
The PCP theorem by gap amplification
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
Batch arguments for \textsf{NP} and more from standard bilinear group assumptions
Parallelizable delegation from LWE
SNARGs for monotone policy batch NP
On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives
Correlation intractability and SNARGs from sub-exponential DDH
Boosting batch arguments and RAM delegation

This page was built for publication: Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance