The Magic of ELFs

Explore the concept of Extremely Lossy Functions (ELFs) in cryptography through this 21-minute conference talk by Mark Zhandry at Crypto 2016. Delve into the Random Oracle Model and its limitations, standard-model security definitions, and assumption families. Examine the progression from standard lossy functions to ELFs, including bounded adversary ELFs and the transition to unbounded scenarios. Learn about the security proof sketch, involving ELF magic and the Goldreich-Levin theorem. Discover the applications and implications of ELFs in modern cryptographic systems.

Intro
Random Oracle Model BR'93
Power of Random Oracles
Limitations of Random Oracles
Standard-model Security Defs for H
Assumption Families
Security Properties vs Assumptions
Standard Lossy Functions [PW'08]
Extremely Lossy Functions (ELFS)
Bounded adversary ELFS
Bounded to Unbounded
Security Proof Sketch
Step 1: Invoke ELF Magic
Step 2: Invoke Goldreich-Levin
Undo ELF Magic
Randomness of y
Applications
Conclusion