Crypto + Meta-complexity 1
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Claim: average-case hardness of time‑bounded Kolmogorov complexity (KT/MKTP, uniform input) is equivalent to existence of one‑way functions; proof builds a weak one‑way function by splitting a program into prefix+index and running the prefix, and reverses via PRG arguments. Key tools: Goldreich‑Levin/HILL, multiplicative‑distance support arguments, and entropy‑preserving PRG or weaker “conditional PRG” constructions. Status: error‑less hardness follows from auxiliary‑input OWFs; full average‑case via OWFs needs an open entropy‑preserving construction; some non‑uniform Perebor conjecture cracks are known.
AI-written summary · about
chapters (9)
- 0:00Introduction to meta complexity
- 5:24Kolmogorov complexity basics
- 11:51Time-bounded complexity
- 20:41Hardness and scientific insight
- 26:01Average-case hardness definitions
- 31:59One-way functions and Kt
- 36:51Weak one-way function construction
- 45:56Advanced PRG constructions
- 59:34Conditioning and future directions
related talks
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
01h 05mCryptography and Kolmogorov Complexity: A Quick Tutorial
47mCapturing One-Way Functions via NP-Hardness of Meta-Complexity
45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa
48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
29mKolmogorov Complexity Characterizes Statistical Zero Knowledge
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information