Cryptography and Kolmogorov Complexity: A Quick Tutorial
summary
Claim: existence of one-way functions is equivalent to some polynomial time bound t for which t-time Kolmogorov complexity Kt is mildly hard-on-average over the uniform distribution. Proof builds a candidate f that takes a random long program and a random index i, truncates to the i-bit prefix, runs it for t(n) steps and outputs (i,y); an inverter for f yields an algorithm that computes Kt on most inputs. Consequences include Kt hardness implies O(log n) approximation hardness and a sampled-instance variant pKt equivalence for samplable distributions, giving a concrete win‑win: crypto or efficient Occam‑style discovery.
AI-written summary · about
chapters (8)
- 0:00Cryptography & Kolmogorov intro
- 1:49One-way functions in crypto
- 7:16Kolmogorov complexity
- 13:31Meta complexity & Kt hardness
- 25:16One-way functions from Kt
- 41:21Win-win implications
- 57:34Excluding Pessiland
- 1:01:38Summary
related talks
01h 06mCrypto + Meta-complexity 1
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
01h 17mCrypto + Meta-complexity 2
59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information
29mKolmogorov Complexity Characterizes Statistical Zero Knowledge
01h 03mLinear-Time Zero-Knowledge Arguments with Logarithmic Proof-Size