A Duality Between One-Way Functions and Average-Case Symmetry of Information

on YouTube ↗40m

" summary

Proves an equivalence: one-way functions do not exist (infinitely often) if and only if average-case symmetry of information for pK^poly holds, and similarly quasipolynomial-time security fails iff rK_quasipoly obeys average SoI. Key tools are an optimal coding theorem for pK^poly, an efficient extrapolator (Impagliazzo–Luby/Levin style) that samples conditional distributions when inversion is possible, and recent heuristics linking rK to K; this yields average-case conditional coding, language-compression variants, and the stated iff characterizations.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 2:07Time-Bounded Kolmogorov Complexity
3. 2:53Symmetry of Information.
4. 8:55Probabilistic Versions of Kolmogorov Complexity
5. 10:55Symmetry of Information and One-Way Functions
6. 14:35Proof Outline
7. 15:05Coding Theorem
8. 23:31Conditional Coding and Sol
9. 25:40OWFs and Average-Case Conditional Coding
10. 29:36Sol for rKquasipoly
11. 31:53More Characterizations

" related talks

• 01h 17mCrypto + Meta-complexity 2Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mCrypto + Meta-complexity 1Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 12mOne-Way Functions Imply Secure Computation in a Quantum WorldAndrea Coladangelo · Meet the Fellows Welcome Event
• 01h 05mCryptography and Kolmogorov Complexity: A Quick TutorialYanyi Liu · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mSomething about new average-case hard problems?Tselil Schramm · Obfuscation
• 34mHigh-entropy dual functions and locally decodable codesFarrokh Labib, Jop Briet · ITCS 2021
• 48mGeometry of Secure ComputationHemanta Maji · Minimal Complexity Assumptions for Cryptography 2023
• 33mGeometry of Secure ComputationHemanta Maji · Secure Computation 2025