Black-Box Uselessness: Composing Separations in Cryptography

on YouTube ↗37m

" summary

Defines a composable notion called black-box uselessness and proves that infinitely-often one-way functions are useless for building key agreement when one party makes a constant number of OWF queries. Proof uses the Impagliazzo–Rudich style attack instantiated with a random oracle + PSPACE oracle, plus a case split that either inverts Z-relative functions or replaces the OWF by one built from Z; complexity analysis shows attacks blow up exponentially unless queries are constant.

AI-written summary · about

" chapters (11)

1. 0:00The cryptographic landscape
2. 1:24Reductions and black boxes
3. 4:04Black-box separations
4. 6:44Limitations of current methods
5. 8:44Defining black-box uselessness
6. 11:03Contributions and framework
7. 13:16Core results and conjectures
8. 16:12Proof of separation
9. 22:50Inherent complexity of security
10. 25:40Technical proof limitations
11. 35:38Future research directions

" related talks

• 48mBlack-Box Separations in Quantum CryptographyMohammad Mahmoody · Minimal Complexity Assumptions for Cryptography 2023
• 55mFoundations 2Iftach Haitner · 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
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 08mWhite-box CryptographyAtis Straujums · droidcon Berlin 2023
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023