Foundations 2
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Best one-way-function PRG constructions use seed length n^3 and about n^3 oracle calls; black-box reductions cannot substantially beat that for length-doubling outputs: any black-box length-doubling PRG that makes fewer than n / log n calls to a one-way (even permutation) oracle is impossible. the proof reduces to the fact that a random permutation is exponentially hard to invert with subexponential queries and uses an emulation/concatenation trick; many amplification and dichotomy questions (e.g., weak OWF amplification, OT vs key-agreement, single-bit decorrelator = uncorrelated vs key-agreement) remain open.
AI-written summary · about
chapters (10)
- 0:00Black-box reduction bounds
- 3:20Hardness of random functions
- 13:41Weak one-way function hurdles
- 18:12Necessity of one-way functions
- 25:42Beyond minicrypt
- 28:52Key agreement limitations
- 37:00Correlated protocol concepts
- 40:39Dichotomy of protocols
- 46:09Caveats and extensions
- 50:47Oblivious transfer research
related talks
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
26mPseudorandom Generators for Unbounded-Width Permutation Branching Programs
01h 01mDerandomization: A Quick Tutorial
57mIndistinguishability Obfuscation from Well-Founded Assumptions
10mPseudorandom Generators and Small-Space Derandomization
35mLower-Bounds on Public-Key Operations in PIR
46mQuantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity
37mBlack-Box Uselessness: Composing Separations in Cryptography