Proving as fast as computing: succinct arguments with constant prover overhead

DOI10.1145/3519935.3519956MaRDI QIDQ6083591zbMATH OpenFDO

Authors

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3519935.3519956

zbMATH Keywords

interactive oracle proofsIOPsuccinct arguments

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Faster sounder succinct arguments and \textsf{IOP}s
• Linear-time arguments with sublinear verification from tensor codes
• Succinct arguments from multi-prover interactive proofs and their efficiency benefits
• Barriers for succinct arguments in the random oracle model
• Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance

Cited in

(23)

• Accelerating tableaux proofs using compact representations
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
• Fast DQBF Refutation
• Using Abduction to Compute Efficient Proofs
• On the virtue of succinct proofs
• Oblivious transfer with constant computational overhead
• Succinct arguments for RAM programs via projection codes
• Brakedown: linear-time and field-agnostic SNARKs for R1CS
• Lattice-based succinct arguments for NP with polylogarithmic-time verification
• Faster sounder succinct arguments and \textsf{IOP}s
• Probabilistically checkable arguments for all NP
• Approximate lower bound arguments
• Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
• More efficient zero-knowledge protocols over \(\mathbb{Z}_{2^k}\) via Galois rings
• Zero-knowledge IOPs approaching witness length
• STIR: Reed-Solomon proximity testing with fewer queries
• Linear-size Boolean circuits for multiselection
• Blaze: fast SNARKs from interleaved RAA codes
• Local proofs approaching the witness length
• The Fiat-Shamir transformation of (_1,,_ )-special-sound interactive proofs
• \textsf{FREPack}: improved SNARK frontend for highly repetitive computations
• Quantum rewinding for IOP-based succinct arguments
• Sum-check protocol for approximate computations

This page was built for publication: Proving as fast as computing: succinct arguments with constant prover overhead

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