Pebbling and Proofs of Work

DOI10.1007/11535218_3MaRDI QIDQ5451017zbMATH OpenOpenAlexFDO

Authors Cynthia Dwork, Moni Naor, Hoeteck Wee

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)

Recommendations

• Proofs of space: when space is of the essence
• Proofs of space
• Advances in Cryptology - CRYPTO 2003
• Simple proofs of sequential work
• Publicly verifiable proofs of sequential work

Cited in

(32)

• Moderately hard functions: definition, instantiations, and applications
• How to build time-lock encryption
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Tight time-space lower bounds for finding multiple collision pairs and their applications
• SPARKs: succinct parallelizable arguments of knowledge
• The cost of adaptivity in security games on graphs
• Efficiently computing data-independent memory-hard functions
• Proofs of space: when space is of the essence
• Balloon hashing: a memory-hard function providing provable protection against sequential attacks
• Cryptographic primitives enforcing communication and storage complexity
• Stronger difficulty notions for client puzzles and denial-of-service-resistant protocols
• scientific article; zbMATH DE number 5859846 (Why is no real title available?)
• Proof of space from stacked expanders
• PoW-based distributed cryptography with no trusted setup
• Proofs of space
• An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol Based on Merkle Trees
• Cumulative space in black-white pebbling and resolution
• Proofs of Catalytic Space
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Resource Burning for Permissionless Systems (Invited Paper)
• Depth-robust graphs and their cumulative memory complexity
• Scrypt is maximally memory-hard
• Advances in Cryptology - CRYPTO 2003
• Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting)
• Parallelizable delegation from LWE
• Individual cryptography
• Better incentives for proof-of-work
• Advancing scalability in decentralized storage: a novel approach to proof-of-replication via polynomial evaluation
• On sequential functions and fine-grained cryptography
• Cumulative memory lower bounds for randomized and quantum computation
• On graphs of incremental proofs of sequential work
• Space-deniable proofs

This page was built for publication: Pebbling and Proofs of Work

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