Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity

on YouTube ↗46m

" summary

Proves a precise equivalence: existence of (quasi‑polynomial or subexponential) one-way functions is iff mild average‑case hardness of MK^tP[polylog n] (or MK^tP[2^{O(√log n)}]) against sublinear-time algorithms. Gives a reduction from sublinear MK^tP hardness to a weak OWF by encoding a random short program as its truth table and inverting that map, and conversely builds a conditionally secure, entropy‑preserving PRG from OWFs via hash/extractor layers and a new method to handle guessing the seed’s degeneracy i.

AI-written summary · about

" chapters (10)

1. 0:00Cryptography and meta complexity
2. 1:06Meta complexity basics
3. 5:06One-way functions intro
4. 8:28Time-bounded K complexity
5. 10:42Threshold hardness equivalence
6. 18:25Average-case hardness for MKtP
7. 22:08Main theorem formal
8. 24:59Proof sketch: one-way functions
9. 34:28PRG construction
10. 44:09Summary and open problems

" related talks

• 01h 06mCrypto + Meta-complexity 1Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 05mCryptography and Kolmogorov Complexity: A Quick TutorialYanyi Liu · Minimal Complexity Assumptions for Cryptography 2023
• 01h 17mCrypto + Meta-complexity 2Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 47mCapturing One-Way Functions via NP-Hardness of Meta-ComplexityShuichi Hirahara · Minimal Complexity Assumptions for Cryptography 2023
• 46mQuantum pseudorandomness in Algorithmica, and its implications to cryptography and complexityLuowen Qian · Minimal Complexity Assumptions for Cryptography 2023
• 01h 09mCrypto + ML 1Shafi Goldwasser · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025