Recursive composition and bootstrapping for SNARKS and proof-carrying data
From MaRDI portal
Publication:5495781
DOI10.1145/2488608.2488623zbMath1293.68264OpenAlexW2144238522MaRDI QIDQ5495781
Nir Bitansky, Eran Tromer, Ran Canetti, Alessandro Chiesa
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488623
Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (60)
\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Proof-carrying data without succinct arguments ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Time- and space-efficient arguments from groups of unknown order ⋮ Non-interactive batch arguments for NP from standard assumptions ⋮ Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge ⋮ On the (In)Security of SNARKs in the Presence of Oracles ⋮ Delegating RAM Computations ⋮ Efficient proof composition for verifiable computation ⋮ On succinct non-interactive arguments in relativized worlds ⋮ Families of SNARK-friendly 2-chains of elliptic curves ⋮ Gemini: elastic SNARKs for diverse environments ⋮ SNARGs for P from sub-exponential DDH and QR ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ Fully homomorphic NIZK and NIWI proofs ⋮ On the (In)security of Kilian-based SNARGs ⋮ Incrementally verifiable computation via incremental PCPs ⋮ On Zero-Knowledge with Strict Polynomial-Time Simulation and Extraction from Differing-Input Obfuscation for Circuits ⋮ Plumo: an ultralight blockchain client ⋮ Maliciously-secure MrNISC in the plain model ⋮ Proof-carrying data from arithmetized random oracles ⋮ On Valiant's conjecture. Impossibility of incrementally verifiable computation from random oracles ⋮ Spartan and bulletproofs are simulation-extractable (for free!) ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ Non-interactive publicly-verifiable delegation of committed programs ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Multi-key Homomorphic Authenticators ⋮ Efficient zero-knowledge arguments in discrete logarithm setting: sublogarithmic proof or sublinear verifier ⋮ Succinct arguments for RAM programs via projection codes ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ The pseudorandom oracle model and ideal obfuscation ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ Proofs for inner pairing products and applications ⋮ Nova: recursive zero-knowledge arguments from folding schemes ⋮ Unnamed Item ⋮ Zero-knowledge succinct non-interactive arguments of knowledge based on sets of polynomials ⋮ Fully succinct batch arguments for \textsf{NP} from indistinguishability obfuscation ⋮ Verifiable private information retrieval ⋮ The hunting of the SNARK ⋮ Impossibilities in succinct arguments: black-box extraction and more ⋮ \textsf{Orbweaver}: succinct linear functional commitments from lattices ⋮ Correlation intractability and SNARGs from sub-exponential DDH ⋮ Algebraic reductions of knowledge ⋮ Unnamed Item ⋮ Practical homomorphic message authenticators for arithmetic circuits ⋮ Chosen-Ciphertext Secure Fully Homomorphic Encryption ⋮ Sublinear Zero-Knowledge Arguments for RAM Programs ⋮ No-signaling linear PCPs ⋮ No-signaling linear PCPs ⋮ \textsc{Fractal}: post-quantum and transparent recursive proofs from holography ⋮ Witness indistinguishability for any single-round argument with applications to access control ⋮ Constrained PRFs for Unbounded Inputs with Short Keys ⋮ On the Existence of Extractable One-Way Functions ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Keyed-fully homomorphic encryption without indistinguishability obfuscation ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Succinct non-interactive secure computation
This page was built for publication: Recursive composition and bootstrapping for SNARKS and proof-carrying data
