Pebbling and Proofs of Work

DOI10.1007/11535218_3zbMath1145.68427OpenAlexW1875376608MaRDI QIDQ5451017

Moni Naor, Hoeteck Wee, Cynthia Dwork

Publication date: 17 March 2008

Published in: Advances in Cryptology – CRYPTO 2005 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11535218_3

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Authentication, digital signatures and secret sharing (94A62)

Related Items

Cumulative Space in Black-White Pebbling and Resolution ⋮ Proof of Space from Stacked Expanders ⋮ PoW-Based Distributed Cryptography with No Trusted Setup ⋮ Proofs of Space ⋮ Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting) ⋮ Parallelizable delegation from LWE ⋮ Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks ⋮ Individual cryptography ⋮ The cost of adaptivity in security games on graphs ⋮ How to build time-lock encryption ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ SPARKs: succinct parallelizable arguments of knowledge ⋮ Proofs of Catalytic Space ⋮ Efficiently Computing Data-Independent Memory-Hard Functions ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Depth-Robust Graphs and Their Cumulative Memory Complexity ⋮ Scrypt Is Maximally Memory-Hard