Crypto + Meta-complexity 2
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Equivalence shows one-way functions ↔ average-case MKtP and the proof uses a conditional PRG notion plus an entropy-preserving strengthening to get density in outputs. Hirahara’s route converts worst-case MKtP to errorless average-case via Nisan–Wigderson style reconstructive extractors and a non‑black‑box compressor that uses the attacker. A boundary MKTP promise suffices for reductions, a circuit attack yields a nonuniform algorithm around 2^{4/5 n}, and a direct PRG prototype runs in about 0.1s on a laptop.
AI-written summary · about
chapters (8)
- 0:00Kolmogorov complexity basics
- 8:37Equivalence proof insights
- 20:23Hirahara's breakthrough
- 30:00Zero knowledge connection
- 37:05MKTP complexity
- 54:55NP completeness barriers
- 1:03:17Interactive complexity key exchange
- 1:09:23PRGs future directions
related talks
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
01h 05mCryptography and Kolmogorov Complexity: A Quick Tutorial
01h 06mSecure Computation and Low-Complexity Cryptography
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
46mNP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
01h 01mDerandomization: A Quick Tutorial