Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
From MaRDI portal
Publication:5445495
DOI10.1007/978-3-540-78524-8_1zbMath1162.68448OpenAlexW1836725053MaRDI QIDQ5445495
Publication date: 5 March 2008
Published in: Theory of Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-78524-8_1
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (43)
\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Proof-carrying data without succinct arguments ⋮ Time- and space-efficient arguments from groups of unknown order ⋮ On the (In)Security of SNARKs in the Presence of Oracles ⋮ Interactive Oracle Proofs ⋮ Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs ⋮ A PCP theorem for interactive proofs and applications ⋮ On succinct non-interactive arguments in relativized worlds ⋮ Families of SNARK-friendly 2-chains of elliptic curves ⋮ Succinct arguments in the quantum random oracle model ⋮ Fully homomorphic NIZK and NIWI proofs ⋮ Incrementally verifiable computation via incremental PCPs ⋮ Proof-carrying data from arithmetized random oracles ⋮ On Valiant's conjecture. Impossibility of incrementally verifiable computation from random oracles ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Practical statistically-sound proofs of exponentiation in any group ⋮ Zero-knowledge for homomorphic key-value commitments with applications to privacy-preserving ledgers ⋮ Non-interactive universal arguments ⋮ 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 ⋮ Nova: recursive zero-knowledge arguments from folding schemes ⋮ Zero-knowledge succinct non-interactive arguments of knowledge based on sets of polynomials ⋮ Verifiable private information retrieval ⋮ The hunting of the SNARK ⋮ Revisiting cycles of pairing-friendly elliptic curves ⋮ Algebraic reductions of knowledge ⋮ Lattice-based timed cryptography ⋮ Tight security bounds for Micali's SNARGs ⋮ Unnamed Item ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Practical homomorphic message authenticators for arithmetic circuits ⋮ Zero-knowledge proofs for set membership: efficient, succinct, modular ⋮ SPARKs: succinct parallelizable arguments of knowledge ⋮ \textsc{Fractal}: post-quantum and transparent recursive proofs from holography ⋮ Continuous verifiable delay functions ⋮ Simple verifiable delay functions ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs
This page was built for publication: Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
