Depth-Robust Graphs and Their Cumulative Memory Complexity

DOI10.1007/978-3-319-56617-7_1zbMath1390.94827OpenAlexW2613194369MaRDI QIDQ5270356

Jeremiah Blocki, Joël Alwen, Krzysztof Pietrzak

Publication date: 23 June 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-56617-7_1

zbMATH Keywords

data-independent memory hard functions (iMHFS)

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items

Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries, Static-memory-hard functions, and modeling the cost of space vs. time, Cumulative Space in Black-White Pebbling and Resolution, Rifflescrambler -- a memory-hard password storing function, Parallelizable delegation from LWE, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, Cost-asymmetric memory hard password hashing, Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes, Sustained space and cumulative complexity trade-offs for data-dependent memory-hard functions, Unnamed Item, The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs, Cost-asymmetric memory hard password hashing, SPARKs: succinct parallelizable arguments of knowledge, Proofs of Catalytic Space, Scrypt Is Maximally Memory-Hard

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• A family of graphs with expensive depth-reduction
• Tradeoff Cryptanalysis of Memory-Hard Functions
• Efficiently Computing Data-Independent Memory-Hard Functions
• Adaptively Secure Garbled Circuits from One-Way Functions
• High Parallel Complexity Graphs and Memory-Hard Functions
• Publicly verifiable proofs of sequential work
• One-Time Computable Self-erasing Functions
• Adaptive Security of Yao’s Garbled Circuits
• Proofs of Space
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Space-time trade-offs on the FFT algorithm
• Key-Evolution Schemes Resilient to Space-Bounded Leakage
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Advances in Cryptology - CRYPTO 2003
• Pebbling and Proofs of Work
• On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model