Bandwidth-Hard Functions - Reductions and Lower Bounds

Explore the concept of Memory Hard Functions (MHFs) and their applications in password hashing, key stretching, and proofs of work in this 30-minute ACM conference talk. Delve into the motivation behind MHFs, including their role in addressing the computational speed disparity between general-purpose CPUs and Application Specific Integrated Circuits (ASICs). Examine various metrics for quantifying memory hardness and learn about Data Independent Memory Hard Functions (IMHFs). Investigate the evaluation of iMHFs through red-blue pebbling, energy cost analysis, and pebbling reductions in the Random Oracle Model. Gain insights into bandwidth-hard functions, their reductions, and lower bounds, concluding with an overview of the importance of MHFs in modern cryptographic applications.

Intro
Motivation: Offline Attacks
Offline Attacks: A Common Problem
Desiderata: Moderately Hard Function
What is the ASIC Advantage?
Reducing ASIC Advantage
Data Independent Memory Hard Function (IMHF)
Data Independent Labeling Function GH
Evaluating an iMHF (red-blue pebbling)
Red-Blue Pebbling Cost RD17
What iMHFs are maximally bandwidth hard?
Pebbling Reduction?
Energy Cost of an Algorithm
Energy Cost of a Function
Pebbling Reduction: Random Oracle Model
Pebbling Lower Bounds
Conclusion