Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Bandwidth-Hard Functions - Reductions and Lower Bounds

Association for Computing Machinery (ACM) via YouTube

Overview

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.

Syllabus

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

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Bandwidth-Hard Functions - Reductions and Lower Bounds

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.