Capturing One-Way Functions via NP-Hardness of Meta-Complexity
summary
Main theorem: a one-way function iff NP is worst-case hard and distributional Kolmogorov complexity is NP-hard under randomized polynomial-time reductions. Distributional K is defined as the length of the shortest t-time program that outputs x given y sampled from distribution D with success probability ≥ λ. Proof combines Gap-MdKP completeness, oracle (P/poly) nonadaptive reductions, Impagliazzo–Levin style universality, and recent barriers (Saks–Santhanam) to both build a candidate one-way function from the reduction and show the converse.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:45Main theorem overview
- 3:25Cryptographic worlds
- 6:10Implications and barriers
- 8:28Meta-complexity approach
- 12:09Previous approaches
- 16:10Distributional complexity
- 20:57Addressing open questions
- 25:33Formal definitions
- 30:11The MDKP problem
- 35:13Equivalence proofs
- 40:01Techniques and conclusion
related talks
01h 06mCrypto + Meta-complexity 1
45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
01h 17mCrypto + Meta-complexity 2
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information
29mKolmogorov Complexity Characterizes Statistical Zero Knowledge
59mQuantum cryptography and quantum complexity
59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa