Foundations 1
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Claims a concrete path from one-way function → PRG via pseudoentropy: build G(x,h,i) that outputs f(x), h and a prefix of h·x whose length depends on x’s degeneracy d(x), then use the leftover-hash lemma and the Goldreich–Levin inner product to show that replacing the final bit by uniform creates a one-bit pseudoentropy gap. Early efficient fixes randomize i and accept a 1/n gap, costing about n^8 f-calls; later work refines this via next-block pseudoentropy and related notions (Yao incompressibility, inaccessible entropy, KL-hardness) to get practical PRGs.
AI-written summary · about
chapters (10)
- 0:00Program introduction
- 1:03Foundation of cryptography
- 3:44One-way functions explained
- 8:06Reductions and progress
- 11:39Pseudoentropy generators
- 19:34Entropy analysis
- 28:28Refining the construction
- 35:22Next-block pseudoentropy
- 41:17Efficiency and generalizations
- 48:08Computational analogues
related talks
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
44mLPN Based IO Part 1
10mPseudorandom Generators and Small-Space Derandomization
01h 06mPseudorandom Obfuscation
26mPseudorandom Generators for Unbounded-Width Permutation Branching Programs
01h 01mDerandomization: A Quick Tutorial
57mIndistinguishability Obfuscation from Well-Founded Assumptions
38mRecent Advances on Foundations of Program Obfuscation