On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model

Explore the complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model in this 26-minute Eurocrypt 2016 conference talk. Delve into password hashing, sequential memory hardness, and the design of memory-hard functions. Examine the ROMix algorithm, cumulative memory complexity, and the concept of entangled adversaries. Investigate the connection between memory-hard functions and pebbling games, including key lemmas and potential functions. Gain insights into randomized pebbling games and their implications for cryptographic security.

Intro
Motivation: Password Hashing
Moderately hard F
Traditional cost metric: Time
Sequential Memory Hardness[Per09]
Designing sequential memory-hard functions
Sequential Memory hard functions: ROMix[Per 09] Phase 1
Cumulative Memory Complexity/A515
Memory hardness, revisited
Entangled Adversary
Generalization
Model MHF by Pebblingtas15
Reduction
Randomized Pebbling game
Key lemma
Potential
Remove random challenge
Wrap-up